【改进遗传-退火算法求解车辆路径问题MATLAB】（代码+测试集）

%无自适应概率 %遗传算法求解VRP问题 %function vrp04_ga_01() clc; clear; close all; % [capacity,xyPos,demand]=initDataC101(); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % [capacity,xyPos,demand]=initDataA33_k5();%659 % [capacity,xyPos,demand]=initDataA33_k6();%742 % [capacity,xyPos,demand]=initDataA36_k5();% 799 % [capacity,xyPos,demand]=initDataA39_k6(); % [capacity,xyPos,demand]=initDataA69_k9();%1159 1178 % [capacity,xyPos,demand]=initDataA65_k9();%1174 1189 % [capacity,xyPos,demand]=initDataA80_k10(); % [capacity,xyPos,demand]=initDataP45_k5();%510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% [capacity,xyPos,demand]=initDataA32_k5();%784 % [capacity,xyPos,demand]=initDataE22_K4();%1021 % [capacity,xyPos,demand]=initDatakelly_1();%5646/ % [capacity,xyPos,demand]=initDataE101_K14();%1071 /1129 % [capacity,xyPos,demand]=initDataE101_k8();%817/ 846 % [capacity,xyPos,demand]=initDataE76_k14();%1032 /1047 % [capacity,xyPos,demand]=initDataE76_k10();%832 /843 % [capacity,xyPos,demand]=initDataE76_k8();%735/ 750 % [capacity,xyPos,demand]=initDataE76_k7(); % [capacity,xyPos,demand]=initDataE33_k4();%835/840 % [capacity,xyPos,demand]=initDataE51_k5();%521/524 % [capacity,xyPos,demand]=initDataE30_k4();%534/ 508 % [capacity,xyPos,demand]=initDataE23_k3();%569/ 568 %数据的初始化 nowDist=createDist(xyPos); [Averecord,record,b,a,chromes,time,routes,optDist]=GA4VRP(nowDist,capacity,demand,xyPos); [route,sumDist,eachWeight]=getFitness(routes,capacity,demand,nowDist); drawRoute(route,xyPos,sumDist) %%算法结构程序 function [Averecord,record,b,a,chromes,time,routes,optDist]=GA4VRP(nowDist,capacity,demand,xyPos) tic; %算法控制参数 pop=120;%%120 maxGeneration=200;%360 500 a= 0; p2=0.25; p1=p2; p4=(1-(p1+p2))/2; p3=p4; inLooNum=10;%每个温度迭代次数 20!!!!!!!!!!!!!!!!!!!!!!!!!!!! customerQty=size(demand,1)-1;%客户点 temp=0.025; % 种群定义和初始化 chromes=initChrome(pop, customerQty); [b,chromes]=seeChromes(chromes); %结果存储 nowFitnesses=getFitnesses(chromes,nowDist,capacity,demand); [sortfit,sortIdx]=sortrows(nowFitnesses'); optRoute=chromes(sortIdx(1),:) ;%种群最优路径 optFitness=sortfit(1);%种群最优结果 nowGeneration=0; record=zeros(maxGeneration,1); Averecord=zeros(maxGeneration,1); recordRate=zeros(maxGeneration,1); %进化过程循环 while nowGeneration<maxGeneration crossRate=0.6; muteRate=0.1; nowGeneration %选择操作 chromes=gaSelect(chromes,nowDist,capacity,demand) ; %交叉操作 chromes=gaCrossover2(chromes,crossRate) ; % 变异操作 （大变异操作） [MuteRate,chromes]=gaMute2(chromes,muteRate,capacity,demand,nowDist); %% %模拟退火算法 （原） for i=1:inLooNum LearnChromes=chromes; rt2=inverse(LearnChromes); fitnesses1=getFitnesses(rt2,nowDist,capacity,demand); fitnesses2=getFitnesses(LearnChromes,nowDist,capacity,demand); for j=1:pop deltDist=(fitnesses2(j)-fitnesses1(j))/fitnesses1(j); if deltDist>0 LearnChromes(j,:)=rt2(j,:); else if exp(deltDist/temp)>rand(1) LearnChromes(j,:)=rt2(j,:); end end end chromes=LearnChromes; % 计算经过交叉、变异操作之后的种群中的最好解 nowFitnesses=getFitnesses(chromes,nowDist,capacity,demand); [sortfit,sortIdx]=sortrows(nowFitnesses'); midOptRoute=chromes(sortIdx(1),:) ;%种群最优路径 midOptFitness=sortfit(1);%种群最优结果 % 进行最优解的更新 if midOptFitness< optFitness optFitness=midOptFitness; optRoute=midOptRoute; end end temp=temp*0.99;%温度更新 %% %计算经过交叉、变异操作之后的种群中的最好解 nowFitnesses=getFitnesses(chromes,nowDist,capacity,demand); [sortfit,sortIdx]=sortrows(nowFitnesses'); midOptRoute=chromes(sortIdx(1),:) ;%种群最优路径 midOptFitness=sortfit(1);%种群最优结果 %进行最优解的更新 if midOptFitness< optFitness optFitness=midOptFitness; optRoute=midOptRoute; end nowGeneration=nowGeneration+1; record(nowGeneration)=optFitness; Averecord(nowGeneration)=sum(nowFitnesses)/pop; recordRate(nowGeneration)=MuteRate; end %输出结果数据 %% figure(2); x1=[1:max(size(record))]; x2=[1:max(size(Averecord))]; plot(x1,record,'k',x2,Averecord,'k--'); %画出最大值的变化过程 plot(x1,Data_SA,'k--',x2,Data_GA,'k:',x3,Data_SAGA,'k'); legend('最短路径长度','平均路径长度'); xlabel('迭代次数') ylabel('适应度值') lg1 =title('迭代曲线'); set(lg1,'FontSize',15,'FontWeight','bold'); figure(3); plot(recordRate); %画出最大值的变化过程 title('变异概率曲线'); %% optFitness optRoute routes=optRoute; optDist=optFitness; toc; time=toc; end %根据相关数据计算当前种群每个染色体的路径总长度 function fitnesses=getFitnesses(chromes,nowDist,capacity,demand) %每个染色体适应度 [pop,~]=size(chromes); fitnesses=zeros(1,pop); for i=1:pop [~,thisDist,~]=getFitness(chromes(i,:),capacity,demand,nowDist); fitnesses(i)=thisDist; end end %根据节点顺序编码和相关参数，获取车辆路径安排和总里程 function [route,sumDist,eachWeight]=getFitness(rt,capacity,demand,nowDist) % rt=routes; % rt=R; customerQty=size(demand,1)-1; rt(rt==1)=[]; route=zeros(customerQty,customerQty+2);%加了 首尾的1 %生成路径 nowRouteId=1; midWeight=0; startId=1; for i=1:max(size(rt)) midWeight=midWeight+demand(rt(i),2); if midWeight>capacity include=startId:(i-1); includeIds=[1 rt(include) 1]; route(nowRouteId,1:size(includeIds,2))=includeIds(1,:);%更新路径矩阵 nowRouteId=nowRouteId+1; midWeight=demand(rt(i),2); startId=i; end end % route %判断最后一条路径是否添加进去 if startId<=max(size(rt)) include=startId:max(size(rt)); includeIds=[1 rt(include) 1]; route(nowRouteId,1:size(includeIds,2))=includeIds(1,:); end %将route精简，全是0的行和列删除 emptyRowIdx=sum(route,2)==0; route(emptyRowIdx,:)=[]; emptyColIdx=sum(route)==0; route(:,emptyColIdx)=[]; %计算路径方案的总里程 [row,col]=size(route); eachWeight=zeros(1,row); sumDist=0; for i=1:row for j=2:col if route(i,j)>0 eachWeight(i)=eachWeight(i)+demand(route(i,j),2); sumDist=sumDist+nowDist(route(i,j-1),route(i,j)); end end end end %单个染色体适应度 %初始化种群 function chromes=initChrome(pop, customerQty) chromes=zeros(pop,customerQty+1); for i=1:pop chromes(i,:)=randperm(customerQty+1); end end %%初始化问题数据 %根据点的xy坐标，求各点之间的距离矩阵 function nowDist=createDist(xyPos) newXY=xyPos(:,2:3)'; nowDist=dist(newXY); end %轮盘赌策略�