position2=find(path(i,:)==b); %找出终点在路线中的位置 pathlong(i)=0; for j=1:position2-1
pathlong(i)=pathlong(i)+A(path(i,j),path(i,j+1)); end end
%计算适应度
Fitness=length(A)*max(max(A))-pathlong; %因要求最小值，采且常数减函数值构造适应度 Fitness=Fitness./sum(Fitness);
%****** Step 1 : 选择最优个体 ****** Bestindividual(k)=min(pathlong);
[Orderfi,Indexfi]=sort(Fitness); %按照适应度大小排序
Bestfi=Orderfi(Popsize); %Oderfi中最后一个即是最大的适应度 BestS=path(Indexfi(Popsize),:); %记录每一代中最优个体的路线
%****** Step 2 : 选择与复制操作****** temppath=path;
roulette=cumsum(Fitness); for i=1:Popsize tempP=rand(1); for j=1:length(roulette) if tempP path(i,:)=temppath(j,:); end %************ Step 3 : 交叉操作 ************ temppath2=path; for i=1:2:row tempP2=rand(1); if(tempP2 temPm2=fix((rand(1)+0.2)*10); %因起点基因不能改变 temPm3=fix((rand(1)+0.2)*10); %随机取出两个位置为2到11基因座 temPm4=min(temPm2,temPm3); temPm5=max(temPm2,temPm3); temp1=path(i,temPm4:temPm5); %将两点之间的基因储存，方便交叉 temp2=path(i+1,temPm4:temPm5); [c d]=find(ismember(path(i,:),temp2)); path(i,d)=0; %找出i行在i+1行取出区域中的数，置为0 [e f]=find(ismember(path(i+1,:),temp1)); path(i+1,f)=0; %找出i+1行在i行取出区域中的数，置为0 [g h]=find(path(i,:)~=0); v1=path(i,h); %取出i行的非零元素，成一向量 [l m]=find(path(i+1,:)~=0); v2=path(i+1,m); %取出i+1行的非零元素，成一向量 path(i,:)=[v1(1:temPm4-1) temp2 v1(temPm4-1+size(temp1):end)]; path(i+1,:)=[v2(1:temPm4-1) temp1 v2(temPm4-1+size(temp2):end)]; %基因交叉 end end path(Popsize,:)=BestS; %************ Step 4: 变异操作 ************** for i=1:Popsize tempPm=rand(1); if(tempPm temPm6=fix((rand(1)+0.2)*10); temPm7=fix((rand(1)+0.2)*10); %产生两个用于交换的随机数 tempvessel=path(i,temPm6); %交换前用一临时容器存放数据 path(i,temPm6)=path(i,temPm7); path(i,temPm7)=tempvessel; %变异交换 end end path(Popsize,:)=BestS; end [aa bb]=find(BestS==b); %找出终点 Bestpath=BestS(1:bb); %剔除后面无用的点，留下实际路线 outdistance(a,b)=Bestindividual(k); %将最短距离写入矩阵 outpath{a,b}=Bestpath; %写入路径，因数据类型为矩阵，所以采用元胞数组储存 end end for i=1:pointnumber for j=1:i outdistance(i,j)=outdistance(j,i); %实现距离的对称 outpath{i,j}=fliplr(outpath{j,i}); %实现路径的对称与翻转 end end %*************** 结果输出 ***************** outdistance celldisp(outpath) %xlswrite('tempdata.xls', outpath) %存入excel中进行操作 四、实验结果与总结（10分） 距离矩阵：a(i,j) i表示起点，j表示终点。 outdistance = 0 2 7 1 3 6 10 5 12 11 14 2 0 5 3 1 4 8 3 10 9 12 7 5 0 7 4 1 5 6 7 6 9 1 3 7 0 4 8 9 6 11 10 13 3 1 4 4 0 3 7 2 9 8 11 6 4 1 8 3 0 4 5 6 5 8 10 8 5 9 7 4 0 9 2 1 4 5 3 6 6 2 5 9 0 7 8 9 12 10 7 11 9 6 2 7 0 1 2 11 9 6 10 8 5 1 8 1 0 3 14 12 9 13 11 8 4 9 2 3 0 路径：b(i,j) i表示起点，j表示终点。 outpath: 12,13,6,5,2,14,15,2,16,5,2,17,4,18,5,2,19,6,3,110,7,4,111,9,10,7,4,11,223,6,5,24,1,25,26,5,27,6,5,28,5,29,8,5,210,7,6,5,211,9,10,7,6,5,21,2,5,6,31,42,5,6,32,1,434,35,6,36,37,6,38,5,6,39,6,310,7,6,311,9,6,33,445,2,1,46,3,47,48,5,2,1,49,10,7,410,7,411,9,10,7,41,2,52,53,6,54,1,2,556,5 7,6,58,59,8,510,7,6,511,8,51,2,5,61,4,72,5,62,5,6,73,64,3,65,667,68,5,69,610,7,611,9,63,6,74,75,6,76,778,9,10,79,10,710,711,9,10,71,2,5,82,5,83,6,5,84,1,2,5,85,86,5,87,10,9,889,810,9,811,81,3,6,91,4,7,101,4,7,10,9,112,5,8,92,5,6,7,102,5,6,7,10,9,113,6,94,7,10,95,8,96,97,10,98,9910,911,93,6,7,104,7,105,6,7,106,7,107,108,9,109,101011,9,103,6,9,114,7,10,9,115,8,116,9,117,10,9,118,119,1110,9,1111 此程序运算速度有待提高，程序的收敛速度不是很快。可能的原因如下： （1） 在变异操作时，可能将本来很好的解弃掉，换来更差的染色体，导致收敛 速度不佳。解决办法：可以在变异操作时，增加个体求优的自学习过程。即在某位基因变异后，计算新染色体的适应函数值，若适应值变大，即路径更短，则保留；否则，保持原来的染色体不变。 （2） 算法的进一步改进，例如可加入Floyd算法的思想，在父代产生子代的过 程中，不是单纯的交叉，可以考虑随机加入顶点是否路径变短。 参考文献： [1]康晓军，王茂才.基于遗传算法的最短路径问题的求解.计算机工程与应用[J],2008,44(23) 第二题代码： clc;clear; %Rosenbrock函数的极大值0-1编码的GA算法 %初始参数 tic; Size=80; G=100; CodeL=10; umax=5.12; umin=-5.12; E=round(rand(Size,3*CodeL)); %生成初始种群 %主程序 for k=1:1:G time(k)=k; for s=1:1:Size m=E(s,:); y1=0;y2=0; y3=0; %解码方法 m1=m(1:1:CodeL); for i=1:1:CodeL y1=y1+m1(i)*2^(i-1); end x1=(umax-umin)*y1/1023+umin; m2=m(CodeL+1:1:2*CodeL); for i=1:1:CodeL y2=y2+m2(i)*2^(i-1); end x2=(umax-umin)*y2/1023+umin; m3=m(2*CodeL+1:1:end); for i=1:1:CodeL y3=y3+m3(i)*2^(i-1); end x3=(umax-umin)*y3/1023+umin; F(s)=x1^2+x2^2+x3^3; end %****** Step 1 : 选择最优个体 ****** BestJ(k)=min(F); %记录每一代中最大个体的函数值 fi=F; %适应度函数 [Oderfi,Indexfi]=sort(fi); %按照适应度大小排序 Bestfi=Oderfi(1); %Oderfi中最后一个即是最大的适应度 BestS=E(Indexfi(1),:); %记录每一代中最优个体的0-1编码 bfi(k)=Bestfi; %记录每一代中最优个体的适应度 %****** Step 2 : 选择与复制操作****** fi_sum=sum(fi); fi_Size=(Oderfi/fi_sum)*Size; %计算个体相对适应度 fi_S=floor(fi_Size); %对80个个体依据相对适应度进行划分等级 kk=1; for i=1:1:Size for j=1:1:fi_S(i) %选择等级高的个体，等级越高被选次数越多 TempE(kk,:)=E(Indexfi(i),:); kk=kk+1; %选择进入下一代个体的个数，显然不够80个个体 end end %************ Step 3 : 交叉操作 ************ pc=0.60; n=ceil(20*rand); for i=1:2:(Size-1) temp=rand; if pc>temp %交叉条件 TempE(i,n:end)=E(i+1,n:end); TempE(i+1,n:end)=E(i,n:end); end end TempE(Size,:)=BestS; %最优个体保留 E=TempE; %种群替换 %************ Step 4: 变异操作 ************** %pm=0.001; %pm=0.001-[1:1:Size]*(0.001)/Size; %自适应变异概率 %pm=0.0; %没有变异 pm=0.1; %较大的变异概率 for i=1:1:Size for j=1:1:2*CodeL temp=rand; if pm>temp %变异条件 if TempE(i,j)==0 TempE(i,j)=1; else TempE(i,j)=0; end end end end TempE(Size,:)=BestS; %保留当代最优个体 E=TempE; %种群替换 end %*************** 结果输出 ***************** Max_Value=Bestfi BestS x1 x2 figure(1); plot(time,BestJ); xlabel('Times');ylabel('Best J'); figure(2); plot(time,bfi); xlabel('times');ylabel('Best F'); toc;