基于GA遗传优化的CDVRP,CVRP,DVRP,TSP以及VRPTW常见路径优化问题求解matlab仿真-摩杜云开发者社区

1.算法仿真效果 matlab2022a仿真结果如下：

TSP最优路径 TSP最优路径 TSP最优路径 Best Route: 0 -> 2 -> 10 -> 5 -> 3 -> 6 -> 9 -> 1 -> 4 -> 7 -> 8 -> 0 Total Distance = 95.275 km

DVRP最优路径 DVRP最优路径 DVRP最优路径总路程 = 198.801 km Best Route: 0 -> 10 -> 5 -> 2 -> 0 -> 3 -> 6 -> 9 -> 1 -> 0 -> 7 -> 4 -> 8 -> 0

CVRP最优路径 CVRP最优路径 CVRP最优路径总路程 = 198.801 km Best Route: 0 -> 3 -> 6 -> 9 -> 1 -> 0 -> 7 -> 4 -> 8 -> 0 -> 10 -> 5 -> 2 -> 0

CDVRP最优路径 CDVRP最优路径 CDVRP最优路径总路程 = 238.771 km Best Route: 0 -> 3 -> 6 -> 9 -> 0 -> 10 -> 5 -> 2 -> 0 -> 8 -> 0 -> 7 -> 1 -> 4 -> 0

VRPTW最优路径 VRPTW最优路径 VRPTW最优路径总路程 = 268.177 km Best Route: 0 -> 7 -> 8 -> 0 -> 3 -> 1 -> 4 -> 0 -> 6 -> 9 -> 2 -> 0 -> 5 -> 10 -> 0

2.算法涉及理论知识概要遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

   其主要步骤如下：

1．初始化

   选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。

   通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。

2．选择

  根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。

给出目标函数f，则f(bi)称为个体bi的适应度。以

为选中bi为下一代个体的次数。

显然．从式(3—86)可知：

(1)适应度较高的个体，繁殖下一代的数目较多。

(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。

这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。

3．交叉

   对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。

3.MATLAB核心程序

addpath 'TSP\';
%初始化
CityNum=size(City,1)-1;    %需求点个数
 
NIND=60;       %种群大小
MAXGEN=100;     %最大遗传代数
GGAP=0.9;       %代沟概率
Pc=0.9;         %交叉概率
Pm=0.05;        %变异概率
mindis = zeros(1,MAXGEN);
bestind = zeros(1,CityNum+2);
 
%初始化种群
Chrom=InitPop(NIND,CityNum);
 
%迭代
gen=1;
while gen <= MAXGEN
 
    [ttlDistance,FitnV]=Fitness(Distance,Chrom);  
    [mindisbygen,bestindex] = min(ttlDistance);
    
    mindis(gen) = mindisbygen; 
	bestind = Chrom(bestindex,:); 
    
    %选择
    SelCh=Select(Chrom,FitnV,GGAP);
    %交叉操作
    SelCh=Crossover(SelCh,Pc);
    %变异
    SelCh=Mutate(SelCh,Pm);
    SelCh=Reverse(SelCh,Distance);
    Chrom=Reins(Chrom,SelCh,FitnV);
    gen=gen+1;
end
 
%历史最短距离
mindisever = mindis(MAXGEN);  
bestroute = bestind; 
disp('TSP最优路径')
disp('TSP最优路径')
disp('TSP最优路径')
 
TextOutput(bestroute,mindisever) 
 
figure
subplot(121)
plot(mindis,'LineWidth',2) 
xlim([1 gen-1])
set(gca, 'LineWidth',1)
xlabel('Num of Iterations')
ylabel('Min Distance(km)')
title('TSP')
 
subplot(122)
DrawPath(bestroute,City)
 
 
Err1=mindis;
 
 
%% DVRP
addpath 'DVRP\';
%初始化
CityNum=size(City,1)-1;    
NIND=60;       %种群大小
MAXGEN=100;     %最大遗传代数
GGAP=0.9;       %代沟概率
Pc=0.9;         %交叉概率
Pm=0.05;        %变异概率
mindis = zeros(1,MAXGEN);
bestind = zeros(1,CityNum*2+1);
%初始化
Chrom=InitPop(NIND,CityNum,Distance,Travelcon);