用遗传算法解决TSP问题.doc

用遗传算法解决TSP问题设计思路：1. 初始化城市距离采用以城市编号（i,j=1代表北京，=2代表上海，=3代表天津，=4代表重庆，=5代表乌鲁木齐）为矩阵行列标的方法，输入任意两个城市之间的距离，用矩阵city表示，矩阵中的元素city(i,j)代表第i个城市与第j个城市间的距离。2. 初始化种群通过randperm函数，生成一个一维随机向量（是整数1，2，3，4，5的任意排列），然后将其赋给二维数组group的第一列，作为一个个体。如此循环N次（本例生成了50个个体），生成了第一代种群，种群的每个个体代表一条路径。3. 计算适应度采用的适应度函数为个体巡回路径的总长度的函数。具体为adapt(1,i)=(5*maxdis-dis) (1)在式（1）中，adapt(1,i)表示第i个个体的适应度函数，maxdis为城市间的最大距离，为4077km,dis为个体巡回路径的总长度，这样定义的适应度，当路经越短时适应度值越大。在适应度值的基础上，给出的计算个体期望复制数的表达式为 adaptnum(1,i)=(N* adapt(1,i)/ sumadapt) (2)其中，sumadapt为种群适应度之和。4. 复制采用优秀个体的大比例保护基础上的随机数复制法。具体做法为在生成下一代个体时，先将最大适应度对应的路径个体以较大的比例复制到下一代，然后再用随机数复制法生成下一代的其他个体。其中，有一个问题必须考虑，即若某一次生成的随机数过大，结果能复制一个或极少个样本。为了避免这一情况，采用了限制措施，即压低了随机数的上限。5. 交叉 采用的方法为按步长的单点交叉，为随机选择一对样本，再随机选择一个交叉点位置，按一定的步长进行交叉点的选择。选择一个步长而不是将其设为1，是因为若某一位置处的城市代码因为进行了交叉而发生了改变，则其经过该处的两个距离都会改变。这种交叉兼有遗传和变异两方面的作用，因为若交叉点处的城市编号都相同，则对两个个体而言交叉后样本无变化，否则样本有变化。6. 变异 方法为随机两点I，J的交互位置法。对于A= 1 2 3 4 5 6 7 8 9 10，若I= 3, J=8，则变异后B= 1 2 8 4 5 6 7 3 9 10虽然是简单的随机两点交互，但实际上已经有40%的距离发生了改变。若用dij表示城市i与j之间的距离，则变异后与变异前样本路径的距离差为B23十B34 + B78十B89一A23十A34 + A78 + A89可见，随机两点交互足以产生新的模式样本。较大地提高变异率就会产生大量的新样本，全局最优样本出现的概率随之提高。为了收敛到最优解，借鉴模拟退火算法的思想，采取了变异率由很大逐渐衰减到较小的数量，这样做也利于找到全局最优解。7. 将复制，交叉，变异后得到的种群group1重新赋给group,然后重复3，4，5，6步操作。直至满足循环停止条件，即找到最优路径。程序实现：clcclear allcity=0 1453 157 2087 3768; 1453 0 1326 2523 4077; 157 1326 0 2300 3900; 2087 2523 2300 0 3358; 3768 4077 3900 3358 0 %初始化城市距离maxdis=4077; %城市间最大距离N=50; %每一代种群中的个体数maxlun=100; %迭代次数设为100for i=1:N ttemp=randperm(5); %初始化种群，即随机产生50种路径，放在5行，N列的矩阵group中 for j=1:5group(j,i)=ttemp(j); end endfor lun=1:maxlun %迭代循环maxlun次sumadapt=0; %适度值之和maxadapt(1,lun)=0; %最大适度值初值minadapt(1,lun)=100; %最小适度值初值viprate=0.1; %最优个体复制率copyrate=0.02; %复制率参数maxadaptloc=0; %最大适应值对应的个体号码初值 mindisiii(1,lun)=100000; %每一代的最忧路径对应的旅行距离总和初值for i=1:N dis(1,i)=0; for j=1:4dis(1,i)=dis(1,i)+city(group(j,i),group(j+1,i); end dis(1,i)=dis(1,i)+city(group(1,i),group(5,i); %求一次旅行个体的总长度 adapt(1,i)=5*maxdis-dis(1,i); %第i个个体的适应度函数 sumadapt=sumadapt+adapt(1,i); %适应度函数总和 if dis(1,i)maxadapt(1,lun) maxadapt(1,lun)=adaptnum(1,i); %求本代最大适应值 maxadaptloc=i; %求最大适应值对应的个体号码 end if adaptnum(1,i)minadapt(1,lun) minadapt(1,lun)=adaptnum(1,i); %求本代最小适应值 endend %.%复制操作tcopy50=0; %复制个数初值num=(maxadapt(1,lun)-copyrate-minadapt(1,lun)*rand(1)+minadapt(1,lun); %生成随机数vipnum=viprate*N ; %N=50，确定最优个体复制个数for tcopy50=1:vipnum %先复制vipnum个最优个体至中间矩阵group1 for i=1:5 group1(i,tcopy50)=group(i,maxadaptloc); endendwhile tcopy50num&tcopy50N tcopy50=tcopy50+1; for k=1:5 %由于针对5个城市，故每个个体有五个元素 group1(k,tcopy50)=group(k,i); end endendend%交叉操作pc=0.5-(0.5-0.1)*(lun-1)/(maxlun-1); %交叉率pair=pc*N/2; %最多交叉对数step=2; %交叉步长取为2pairno=0; %当前交叉过的个体数while pairnopair a=floor(N*rand(1)+1); %随机产生两个交叉个体，floor为向负无穷取整函数 b=floor(N*rand(1)+1); marri(1,a)=2; %参与交叉的个体标记初值 marri(1,b)=3; if marri(1,a)=1&marri(1,b)=1&a=b marri(1,a)=1; marri(1,b)=1; %参与交叉的个体标记为1 pairno=pairno+1; location=floor(5*rand(1)+1); %用随机数确定个体中单交叉点位置 l1=0; l2=0; for i=location:step:5 %以下按步长step进行交叉 for j=1:5 %用for确定交叉位置 if group1(i,a)=group1(j,b) l1=j; end end for j=1:5 if group1(i,b)=group1(j,a) l2=j; end end temp=group1(i,a); group1(i,a)=group1(l2,a); group1(l2,a)=temp; temp=group1(i,b); group1(i,b)=group1(l1,b); group1(l1,b)=temp; end endend%变异操作 pb=0.02; %个体变异率 bnum=pb*N; %变异个体数 for i=1:bnum %逐个取个体，随机选择位置进行变异 a1=floor(5*rand(1)+1); a2=floor(5*rand(1)+1); b=floor(N*rand(1)+1); temp=group1(a1,b); group1(a1,b)=group1(a2,b); group1(a2,b)=temp; end %for i=1:N for j=1:5 group(j,i)=group1(j,i); %构造经过复制，交叉，变异后的矩阵，group,准备下次循环 endendendgroupdisp(最优路径为：)for i=1:5 switch group(i,1) case 1,disp(北京) case 2,disp(上海) case 3,disp(天津) case 4,disp(重庆) otherwise,disp(乌鲁木齐) %用文字列出最优路径 endenddisp(更多精彩，即将出现，请稍等.)figure(1);lun=1:1:50;mindis=mindisiii(1,lun);plot(lun,mindis);grid on;figure(2);worldmap(china,patch);for i=1:5 switch group(i,1) case 1,x(1,i)=0.12;y(1,i)=0.72; case 2,x(1,i)=0.23;y(1,i)=0.54; %在地图中定出五个城市的坐标 case 3,x(1,i)=0.15;y(1,i)=0.7; case 4,x(1,i)=0;y(1,i)=0.53; otherwise,x(1,i)=-0.2;y(1,i)=0.73; endendfor i=1:4 u(1,i+1)=x(1,i); v(1,i+1)=y(1,i);endu(1,1)=x(1,5);v(1,1)=y(1,5);for i=1:5 u(1,i)