%无自适应概率
%遗传算法求解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
%轮盘赌策略�
