TSP问题求解 新建 Microsoft Word 文档

%vision5更新内容%最大突变概率%突变概率将随着算法的收敛而增大%最终增大到最大突变概率%- 遗传算法解决TSP问题 -%.%*参数及参数说明*%-nCity：城市数量，参数取值范围，2 整数；%-xyCity：城市二维坐标，本例由计算机随机产生，范围(0,1)，假定起始城市为第nCity个城市；%-dCity：城市间距离矩阵，本例考虑城市间往返距离相等，且定义距离为欧几里德范数；%-nPopulation：种群个体数量；%-Population：种群，nPopulation*(nCity-1)矩阵，每行由1,2,.,nCity-1某一个全排列构成；%-generation：算法终止条件一，迭代代数；%-nR：算法终止条件二，最短路径值连续nR代不变；%-R：最短路径；%-Rlength：最短路径长度。%-Shock：当最优个体保持一段时期不变后，产生震荡function R,Rlength=GA_TSP(xyCity,dCity,Population,nPopulation,pCrossover,percent,pMutation,generation,nR,rr,rangeCity,rR,moffspring,record,pi,Shock,maxShock)clear ALL%10个城市坐标%xyCity=0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414;% 0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634;%10 cities d=2.691%-%30个城市坐标xyCity=25 62;7 64;2 99;68 58;71 44;xyCity=41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60; 83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50;%30 cities d=423.741 by D B Fogel%-%50个城市坐标%xyCity=31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;%17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;%27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;%58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67;%50 cities d=427.855 by D B Fogel%-%75个城市坐标%xyCity=48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;%55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;%20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50;%45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15;%44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56;%10 70;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26;%75cities d=549.18 by D B Fogelfigure(1)axis(0 10 0 10) grid onscatter(xyCity(:,1),xyCity(:,2),x)grid onnCity=size(xyCity,1);for i=1:nCity %计算城市间距离，假设距离为欧几里德范数 for j=1:nCity dCity(i,j)=(xyCity(i,1)-xyCity(j,1)2+(xyCity(i,2)-xyCity(j,2)2)0.5; endend %计算城市间距离，假设距离为欧几里德范数xyCity %显示城市坐标dCity %显示城市距离矩阵%初始种群k=input(取点操作结束); %取点时对操作保护disp(-)nPopulation=input(种群个体数量：); %输入种群个体数量if size(nPopulation,1)=0 nPopulation=20; %默认值endfor i=1:nPopulation Population(i,:)=randperm(nCity-1); %产生随机个体end%Population %显示初始种群%添加绘图表示%pCrossover=input(交叉概率：); %输入交叉概率percent=input(交叉部分占整体的百分比：); %输入交叉比率pMutation=input(突变概率：); %输入突变概率nRemain=input(最优个体保留最大数量：);pi(1)=input(选择操作最优个体被保护概率：); %输入最优个体被保护概率pi(2)=input(交叉操作最优个体被保护概率：);pi(3)=input(突变操作最优个体被保护概率：);maxShock=input(最大突变概率：);if size(pCrossover,1)=0 pCrossover=0.85;endif size(percent,1)=0 percent=0.5;endif size(pMutation,1)=0 pMutation=0.05;endShock=0;rr=0;Rlength=0;counter1=0;counter2=0;R=zeros(1,nCity-1);newPopulation,R,Rlength,counter2,rr=select(Population,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain);R0=R;record(1,:)=R;rR(1)=Rlength;Rlength0=Rlength;figure(2)subplot(1,3,1)plotaiwa(xyCity,R,nCity)generation=input(算法终止条件A.最多迭代次数：); %输入算法终止条件if size(generation,1)=0 generation=50;endnR=input(算法终止条件B.最短路径连续保持不变代数：);if size(nR,1)=0 nR=10;endwhile counter1generation&counter2nR if counter2nR*1/5 Shock=0; elseif counter2nR*2/5 Shock=maxShock*1/4-pMutation; elseif counter2nR*3/5 Shock=maxShock*2/4-pMutation; elseif counter2nR*4/5 Shock=maxShock*3/4-pMutation; else Shock=maxShock-pMutation; end counter1 %newPopulation offspring=crossover(newPopulation,nCity,pCrossover,percent,nPopulation,rr,pi,nRemain); %offspring moffspring=Mutation(offspring,nCity,pMutation,nPopulation,rr,pi,nRemain,Shock); newPopulation,R,Rlength,counter2,rr=select(moffspring,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain); counter1=counter1+1; rR(counter1+1)=Rlength; record(counter1+1,:)=R;end%R0%Rlength0%R%RlengthminR=min(rR);disp(最短路经出现代数:)rr=find(rR=minR)disp(最短路经:)record(rr,:)mR=record(rr(1,1),:)disp(终止条件一:)counter1disp(终止条件二:)counter2disp(最短路经长度:)minRdisp(最初路经长度:)rR(1)subplot(1,3,2)plotaiwa(xyCity,R,nCity)subplot(1,3,3)plotaiwa(xyCity,mR,nCity)figure(3)i=1:counter1+1;plot(i,rR(i)grid on%.%目标函数为路径长度%*参数及参数说明*%-newPopulation：选择后的新种群%-Distance：用来存储及计算个体路径长度%-Sum：总路径长度%-Fitness：每个个体的适应概率%-sFitness：累积概率%-a：甩随机数function newPopulation,R,Rlength,counter2,rr=select(Population,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain)Distance=zeros(nPopulation,1); %零化路径长度Fitness=zeros(nPopulation,1); %零化适应概率Sum=0; %路径长度for i=1:nPopulation %计算个体路径长度 for j=1:nCity-2 Distance(i)=Distance(i)+dCity(Population(i,j),Population(i,j+1); end %对路径长度调整，增加起始点到路径首尾点的距离 Distance(i)=Distance(i)+dCity(Population(i,1),nCity)+dCity(Population(i,nCity-1),nCity); Sum=Sum+Distance(i); %累计总路径长度end %计算个体路径长度if Rlength=min(Distance) counter2=counter2+1;else counter2=0;endRlength=min(Distance); %更新最短路径长度Rlengthrr=find(Distance=Rlength);R=Population(rr(1,1),:); %更新最短路径Rfor i=1:nPopulation Fitness(i)=(max(Distance)-Distance(i)+0.001)/(nPopulation*(max(Distance)+0.001)-Sum); %适应概率=个体/总和。已作调整，大小作了调换end%Fitness %显示适应概率sFitness=zeros(nPopulation,1); %累积概率sFitness(1)=Fitness(1);for i=2:nPopulation sFitness(i)=sFitness(i-1)+Fitness(i);end%sFitness %显示累积概率newPopulation=zeros(nPopulation,nCity-1); %零化新种群for i=1:nPopulation %甩随机数 a=rand; %a %显示甩出的随机数 for j=1:nPopulation if asFitness(j) newPopulation(i,:)=Population(j,:); break end endendfor i=1:size(rr,1) if randpi(1)&i=nRemain newPopulation(rr(i,1),:)=Population(rr(i,1),:); endend%newPopulation %显示被选中的新种群个体%.%顺序交叉(OX)算子说明：%步骤：%-1.从第一双亲中随机选一个子串；%-2.将子串复制到一个空字串的相应位置，产生一个原始后代；%-3.删去第二双亲中子串已有的城市，得到原始后代需要的其他城市的顺序；%-4.按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。%*参数及参数说明*%-offspring：子代种群%-pCrossover：交叉概率%-wCrossover：交叉宽度%-pointCrossover：交叉点%-percent：交叉比例function offspring=crossover(newPopulation,nCity,pCrossover,percent,nPopulation,rr,pi,nRemain)offspring=zeros(nPopulation,nCity-1); %初始化后代ccc=0;for i=1:nPopulation s=find(rr=i); if size(s,1)=0&randpi(2)&cccnRemain offspring(i,:)=newPopulation(i,:); ccc=ccc+1; elseif randpCrossover %改进方向：优势个体保留，劣势个体不参与交叉 j=unidrnd(nPopulation); %选择另一参与交叉的个体 while i=j j=unidrnd(nPopulation); %unidrnd(n)产生1,2,.,n里的随机数 end wCrossover=floor(nCity-1)*percent); %确定交叉宽度 backPopulation=newPopulation(i,:); % pointCrossover=unidrnd(nCity-1-wCrossover); %随机产生交叉点，做差确保不溢出 for m=1:wCrossover %OX交叉 offspring(i,pointCrossover+m-1)=newPopulation(j,pointCrossover+m-1); %步骤12 end for n=1:nCity-1 for m=1:wCrossover if backPopulation(n)=newPopulation(j,pointCrossover+m-1) backPopulation(n)=0; end end end for n=1:nCity-1 if backPopulation(n)=0 for o=1:nCity-1 if offspring(i,o)=0 offspring(i,o)=backPopulation(n); break end end end end else offspring(i,:)=newPopulation(i,:); endend%offspring %显示交叉后子代%.%两点互换变异%*参数及参数说明*%-pMutation：突变概率function moffspring=Mutation(offspring,nCity,pMutation,nPopulation,rr,pi,nRemain,Shock)exchange=0;ccc=0;for m=1:nPopulation moffspring(m,:)=offspring(m,:); k=find(rr=m); if size(k,1)=0&randpi(3)&cccnRemain m=rr(k(1,1),1); moffspring(m,:)=moffspring(m,:); ccc=ccc+1; else for i=1:nCity-1 if randpMutation+Shock j=unidrnd(nCity-1); while i=j j=unidrnd(nCity-1); end exchange=moffspring(m,i); moffspring(m,i)=moffspring(m,j); moffspring(m,j)=exchange; end end endend%offspring %显示突变后子代%.function plotaiwa(xyCity,R,nCity)scatter(xyCity(:,1),xyCity(:,2),x)hold onplot(xyCity(R(1),1),xyCity(nCity,1),xyCity(R(1),2),xyCity(nCity,2)plot(xyCity(R(nCity-1),1),xyCity(nCity,1),xyCity(R(nCity-1),2),xyCity(nCity,2)hold onfor i=1:length(R)-1 x0=xyCity(R(i),1); y0=xyCity(R(i),2); x1=xyCity(R(i+1),1); y1=xyCity(R(i+1),2); xx=x0,x1; yy=y0,y1; plot(xx,yy) hold onend%- 遗传算法解决TSP问题 -%.%*参数及参数说明*%-nCity：城市数量，参数取值范围，2 整数；%-xyCity：城市二维坐标，本例由计算机随机产生，范围(0,1)，假定起始城市为第nCity个城市；%-dCity：城市间距离矩阵，本例考虑城市间往返距离相等，且定义距离为欧几里德范数；%-nPopulation：种群个体数量；%-Population：种群，nPopulation*(nCity-1)矩阵，每行由1,2,.,nCity-1某一个全排列构成；%-generation：算法终止条件一，迭代代数；%-nR：算法终止条件二，最短路径值连续nR代不变；%-R：最短路径；%-Rlength：最短路径长度。function R,Rlength=GA_TSP(xyCity,dCity,Population,nPopulation,pCrossover,percent,pMutation,generation,nR,rr,rangeCity,rR,moffspring,record,pi)%10个城市坐标%xyCity=0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414;% 0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634;%10 cities d=2.691%-%30个城市坐标xyCity=41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60; 83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50;%30 cities d=423.741 by D B Fogel%-%50个城市坐标%xyCity=31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;%17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;%27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;%58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67;%50 cities d=427.855 by D B Fogel%-%75个城市坐标%xyCity=48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;%55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;%20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50;%45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15;%44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56;%10 70;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26;%75cities d=549.18 by D B Fogelfigure(1)axis(0 10 0 10) grid onscatter(xyCity(:,1),xyCity(:,2),x)grid onnCity=size(xyCity,1);for i=1:nCity %计算城市间距离，假设距离为欧几里德范数 for j=1:nCity dCity(i,j)=(xyCity(i,1)-xyCity(j,1)2+(xyCity(i,2)-xyCity(j,2)2)0.5; endend %计算城市间距离，假设距离为欧几里德范数xyCity %显示城市坐标dCity %显示城市距离矩阵%初始种群k=input(取点操作结束); %取点时对操作保护disp(-)nPopulation=input(种群个体数量：); %输入种群个体数量if size(nPopulation,1)=0 nPopulation=20; %默认值endfor i=1:nPopulation Population(i,:)=randperm(nCity-1); %产生随机个体end%Population %显示初始种群%添加绘图表示%pCrossover=input(交叉概率：); %输入交叉概率percent=input(交叉部分占整体的百分比：); %输入交叉比率pMutation=input(突变概率：); %输入突变概率nRemain=input(最优个体保留最大数量：);pi(1)=input(选择操作最优个体被保护概率：); %输入最优个体被保护概率pi(2)=input(交叉操作最优个体被保护概率：);pi(3)=input(突变操作最优个体被保护概率：);if size(pCrossover,1)=0 pCrossover=0.85;endif size(percent,1)=0 percent=0.5;endif size(pMutation,1)=0 pMutation=0.05;endrr=0;Rlength=0;counter1=0;counter2=0;R=zeros(1,nCity-1);newPopulation,R,Rlength,counter2,rr=select(Population,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain);R0=R;record(1,:)=R;rR(1)=Rlength;Rlength0=Rlength;figure(2)subplot(1,3,1)plotaiwa(xyCity,R,nCity)generation=input(算法终止条件A.最多迭代次数：); %输入算法终止条件if size(generation,1)=0 generation=50;endnR=input(算法终止条件B.最短路径连续保持不变代数：);if size(nR,1)=0 nR=10;endwhile counter1generation&counter2nR counter1 %newPopulation offspring=crossover(newPopulation,nCity,pCrossover,percent,nPopulation,rr,pi,nRemain); %offspring moffspring=Mutation(offspring,nCity,pMutation,nPopulation,rr,pi,nRemain); newPopulation,R,Rlength,counter2,rr=select(moffspring,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain); counter1=counter1+1; rR(counter1+1)=Rlength; record(counter1+1,:)=R;end%R0%Rlength0%R%Rlengthdisp(最短路经长度:)minR=min(rR)disp(最短路经出现代数:)rr=find(rR=minR)disp(最短路经:)record(rr,:)mR=record(rr(1,1),:);counter1counter2subplot(1,3,2)plotaiwa(xyCity,R,nCity)subplot(1,3,3)plotaiwa(xyCity,mR,nCity)figure(3)i=1:counter1+1;plot(i,rR(i)grid on%.%目标函数为路径长度%*参数及参数说明*%-newPopulation：选择后的新种群%-Distance：用来存储及计算个体路径长度%-Sum：总路径长度%-Fitness：每个个体的适应概率%-sFitness：累积概率%-a：甩随机数function newPopulation,R,Rlength,counter2,rr=select(Population,nPopulation,nCity,dCity,Rlength,R,counter2,pi,nRemain)Distance=zeros(nPopulation,1); %零化路径长度Fitness=zeros(nPopulation,1); %零化适应概率Sum=0; %路径长度for i=1:nPopulation %计算个体路径长度 for j=1:nCity-2 Distance(i)=Distance(i)+dCity(Population(i,j),Population(i,j+1); end %对路径长度调整，增加起始点到路径首尾点的距离 Distance(i)=Distance(i)+dCity(Population(i,1),nCity)+dCity(Population(i,nCity-1),nCity); Sum=Sum+Distance(i); %累计总路径长度end %计算个体路径长度if Rlength=min(Distance) counter2=counter2+1;else counter2=0;endRlength=min(Distance); %更新最短路径长度Rlengthrr=find(Distance=Rlength);R=Population(rr(1,1),:); %更新最短路径Rfor i=1:nPopulation Fitness(i)=(max(Distance)-Distance(i)+0.001)/(nPopulation*(max(Distance)+0.001)-Sum); %适应概率=个体/总和。已作调整，大小作了调换end%Fitness %显示适应概率sFitness=zeros(nPopulation,1); %累积概率sFitness(1)=Fitness(1);for i=2:nPopulation sFitness(i)=sFitness(i-1)+Fitness(i);end%sFitness %显示累积概率newPopulation=zeros(nPopulation,nCity-1); %零化新种群for i=1:nPopulation %甩随机数 a=rand; %a %显示甩出的随机数 for j=1:nPopulation if asFitness(j) newPopulation(i,:)=Population(j,:); break end endendfor i=1:size(rr,1) if randpi(1)&i=nRemain newPopulation(rr(i,1),:)=Population(rr(i,1),:); endend%newPopulation %显示被选中的新种群个体%.%顺序交叉(OX)算子说明：%步骤：%-1.从第一双亲中随机选一个子串；%-2.将子串复制到一个空字串的相应位置，产生一个原始后代；%-3.删去第二双亲中子串已有的城市，得到原始后代需要的其他城市的顺序；%-4.按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。%*参数及参数说明*%-offspring：子代种群%-pCrossover：交叉概率%-wCrossover：交叉宽度%-pointCrossover：交叉点%-percent：交叉比例function o