第一步:相关参数的设定,一般主要包含编码长度L,种群大小M,迭代次数G,交叉率Pc,变异率Pm等。
第二步:算法中不能直接采用数学模型中的解进行运算,需要对解进行处理,去构造适应函数的染色体。
第三步:随机产生M个个体组成初始种群Po,并且让个体有序的分布在解空间中,每个个体为问题对应的一个解。
第四步:计算出每个个体的适应度,根据适应度进行种群中的选择和其他操作。
第五步:根据每个个体适应度的大小,选择适应度高的个体进行个体的选择等操作,通常采用的方法有轮盘赌等。
第六步:设置交叉率Pc控制父代染色体的交叉操作,被交叉的个体将代替父代进入新种群。
第七步:设置突变率Pm,控制父代染色体的突变操作。突变可导致群体中未出现或在选择过程中被淘汰的基因重新出现,突变个体取代父代进入新种群。
第八步:判断下一次迭代的选择、交叉、变异操作后的更新种群是否满足终止条件,如果不满足,则重新进入第四步进行循环迭代过程;如果满足,则停止算法运行,通常采用最大迭代次数作为终止准则。
第九步:对符合终止条件的染色体进行解码,得到问题的最优解。根据以上步骤,可知遗传算法的基本过程
clear clc close all tic %% 用importdata这个函数来读取文件 % shuju=importdata('cc101.txt'); load('cc101'); shuju=c101; % bl=importdata('103.txt'); bl=3; cap=60; %车辆最大装载量 %% 提取数据信息 E=shuju(1,5); %配送中心时间窗开始时间 L=shuju(1,6); %配送中心时间窗结束时间 zuobiao=shuju(:,2:3); %所有点的坐标x和y pszx=zuobiao(1:4,:); customer=zuobiao(5:end,:); %顾客坐标 cusnum=size(customer,1); %顾客数 v_num=20; %车辆最多使用数目 demands=shuju(5:end,4); %需求量 a=shuju(5:end,5); %顾客时间窗开始时间[a[i],b[i]] b=shuju(5:end,6); %顾客时间窗结束时间[a[i],b[i]] s=shuju(5:end,7); %客户点的服务时间 h=pdist(zuobiao); dist=squareform(h); % dist=load('dist.mat'); % dist=struct2cell(dist); % dist=cell2mat(dist); dist=dist./1000;%距离矩阵,满足三角关系,暂用距离表示花费c[i][j]=dist[i][j] %% 遗传算法参数设置 alpha=100000; %违反的容量约束的惩罚函数系数 belta=90;%违反时间窗约束的惩罚函数系数 belta2=60; chesu=20; NIND=300; %种群大小 MAXGEN=1000; %迭代次数 Pc=0.9; %交叉概率 Pm=0.05; %变异概率 GGAP=0.9; %代沟(Generation gap) N=cusnum+v_num-1; %染色体长度=顾客数目+车辆最多使用数目-1 % N=cusnum; %% 初始化种群 % init_vc=init(cusnum,a,demands,cap); dpszx = struct('ps',[], 'Chrom',[]); dpszx.Chrom=InitPopCW(NIND,N,cusnum,a,demands,cap); %构造初始解 ps=pszxxz(dpszx.Chrom,cusnum); %% 输出随机解的路线和总距离 disp('初始种群中的一个随机值:') [VC,NV,TD,violate_num,violate_cus]=decode(dpszx.Chrom(1,:),cusnum,cap,demands,a,b,L,s,dist,chesu,bl); % [VC,NV]=cls(dpszx.Chrom(1,:),cusnum); % [~,~,bsv]=violateTW(VC,a,b,s,L,dist,chesu,bl); % disp(['总距离:',num2str(TD)]); disp(['车辆使用数目:',num2str(NV),',车辆行驶总距离:',num2str(TD)]); disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~') %% 优化 gen=1; figure; hold on;box on xlim([0,MAXGEN]) title('优化过程') xlabel('代数') ylabel('最优值') ObjV=calObj(dpszx.Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta,belta2,chesu,bl,ps); %计算种群目标函数值 preObjV=min(ObjV); %% while gen<=MAXGEN %% 计算适应度 ObjV=calObj(dpszx.Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta,belta2,chesu,bl,ps); %计算种群目标函数值 line([gen-1,gen],[preObjV,min(ObjV)]);pause(0.0001)%画图 最优函数 preObjV=min(ObjV); FitnV=Fitness(ObjV); %% 选择 [SelCh,psc]=Select(dpszx.Chrom,FitnV,GGAP,ps); %% OX交叉操作 [SelCh,psc]=Recombin(SelCh,Pc,psc,cusnum); %% 变异 [SelCh,psc]=Mutate(SelCh,Pm,psc,cusnum); %% 重插入子代的新种群 [dpszx.Chrom,ps]=Reins(dpszx.Chrom,SelCh,ObjV,psc,ps); %% 打印当前最优解 ObjV=calObj(dpszx.Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta,belta2,chesu,bl,ps); %计算种群目标函数值 [minObjV,minInd]=min(ObjV); disp(['第',num2str(gen),'代最优解:']) [bestVC,bestNV,bestTD,best_vionum,best_viocus]=decode(dpszx.Chrom(minInd(1),:),cusnum,cap,demands,a,b,L,s,dist,chesu,bl); disp(['车辆使用数目:',num2str(bestNV),',车辆行驶总距离:',num2str(bestTD)]); fprintf('\n') %% 更新迭代次数 gen=gen+1 ; end %% 画出最优解的路线图 ObjV=calObj(dpszx.Chrom,cusnum,cap,demands,a,b,L,s,dist,alpha,belta,belta2,chesu,bl,ps); %计算种群目标函数值 [minObjV,minInd]=min(ObjV); %% 输出最优解的路线和总距离 disp('最优解:') bestChrom=dpszx.Chrom(minInd(1),:); bestps=ps(minInd(1),:); [bestVC,bestNV,bestTD,best_vionum,best_viocus]=decode(bestChrom,cusnum,cap,demands,a,b,L,s,dist,chesu,bl); disp(['车辆使用数目:',num2str(bestNV),',车辆行驶总距离:',num2str(bestTD)]); disp('-------------------------------------------------------------') % [cost]=costFuction(bestVC,a,b,s,L,dist,demands,cap,alpha,belta,belta2,chesu,bl,); %% 画出最终路线图 draw_Best(bestVC,zuobiao,bestps); % save c101.mat % toc
配送路线1:2->62->61->60->59->56->54->2
配送路线2:2->39->83->7->5->40->2
配送路线3:1->3->2->1->108->19->12->1
配送路线4:2->80->79->42->2
配送路线5:1->94->58->57->63->73->71->1
配送路线6:4->105->104->103->102->4
配送路线7:4->38->31->30->29->87->86->89->88->4
配送路线8:1->106->70->69->68->67->65->91->1
配送路线9:2->16->15->14->13->98->2
配送路线10:3->53->6->66->78->3
配送路线11:1->77->76->75->1
配送路线12:1->92->90->85->84->82->1
配送路线13:1->95->93->101->100->34->28->27->26->25->1
配送路线14:1->33->32->1
配送路线15:3->23->22->21->20->45->44->43->3
配送路线16:2->52->51->50->49->48->2
配送路线17:4->74->72->97->24->4->18->46->96->4
配送路线18:1->107->11->10->1
配送路线19:4->99->41->35->37->36->4
配送路线20:3->47->55->9->8->64->17->81->3
代码下载https://www.cnblogs.com/matlabxiao/p/14883637.html