tsp.rar_TSP matlab_TSP 遗传算法_TSP 遗传算法 matlab_matlab TSP_tsp

%自己编的(冗杂)用遗传算法解决TSP问题的Matlab源程序 %----------------------- 遗传算法解决TSP问题 ----------------------- %.........<主程序.Main>......... %******************参数及参数说明****************** %-------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) 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=[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 Fogel figure(1) axis([0 10 0 10]) grid on scatter(xyCity(:,1),xyCity(:,2),'x') grid on nCity=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; end end %计算城市间距离，假设距离为欧几里德范数 xyCity %显示城市坐标 dCity %显示城市距离矩阵 %初始种群 k=input('取点操作结束'); %取点时对操作保护 disp('-------------------') nPopulation=input('种群个体数量：'); %输入种群个体数量 if size(nPopulation,1)==0 nPopulation=20; %默认值 end for 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; end if size(percent,1)==0 percent=0.5; end if size(pMutation,1)==0 pMutation=0.05; end 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; end nR=input('算法终止条件B.最短路径连续保持不变代数：'); if size(nR,1)==0 nR=10; end while counter1<generation&counter2<nR 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 %Rlength disp('最短路经长度:') minR=min(rR) disp('最短路经出现代数:') rr=find(rR==minR) disp('最短路经:') record(rr,:) mR=record(rr(1,1),:); counter1 counter2 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 %.........<选择算子.select operator>......... %目标函数为路径长度 %******************参数及参数说明****************** %-------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; end Rlength=min(Distance); %更新最短路径长度 Rlength rr=find(Distance==Rlength); R=Population(rr(1,1),:); %更新最短路径 R for 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 a<sFitness(j) newPopulation(i,:)=Population(j,:); break end end end for i=1:size(rr,1) if rand<pi(1)&i<=nRemain newPopulation(rr(i,1),:)=Population(rr(i,1),:); end end %newPopulation %显示被选中的新种群个体 %.........<交叉算子.crossover operator>......... %顺序交叉(OX)算子说明： %步骤： %--1.从第一双亲中随机选一个子串； %--2.将子串复制到一个空字串的相应位置，产生一个原始后代； %--3.删去第二双亲中子串已有的城市，得到原始后代需要的其他城市的顺序； %--4.按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。 %******************参数及参数说明****************** %-------offspring：子代种群 %-------pCrossover：交叉概率 %-------wCrossover：交叉宽度 %-------pointCrossove