TSP遗传算法概要

1、实验二 基于遗传算法的T S P求解一、实验目的掌握遗传算法求解TSP问题的实现过程。二、实验内容用遗传算法求解TSR由于其任一可能解一一 一个合法的城市序列，即 n个城市的一个排列，都可以事先构 造出来。于是，我们就可以直接在解空间(所有合法的城市序列)中搜索最佳解。这正适合 用遗传算法求解。三、实验步骤(1)编码路径表示是表示旅程对应的基因编码的最自然、最简单的表示方法。例如，旅程(5 1 7894 623)可以直接表不'为(517894623),基于路径表不'的编码方法，要求个个体(即一条旅程)的染色体编码中不允许有重复的基因码，也就是说要满足任一个城市必须而且只能访问一

2、次的约束。(2)定义适应度函数我们将一个合法的城市序列s= (c1, c2,，cn)作为一个个体。这个序列中相邻两城市之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是：1f (s) = Tj' d(G,Ci 1) i工例如，对于9个城市的TSP,我们用符号1、2、3、4、5、6、7、8、9代表相应的城市， 用这9个符号的序列表示可能解即染色体。然后进行遗传操作用部分匹配交叉PMRT法：匹配操作要求随机选取两个交叉点，确定一个匹配段，根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体.例如，对下面两个父个体的表示，随机选择两个交义点P1: 1 2 3 4

3、 5 6 7 8 9o1:4 2 3 1 8 7 6 5 9P2: 4 5 2 1 8 7 6 9 302:1 8 2 4 5 6 7 9 3交叉方法：随机选取染色体上两个元，然后交换 它们的位置.例如：4 5 2 1 8 7 6 9 3交换后：4 5 6 1 8 7 2 9 3(3 )求解的Tsp问题的城市坐标如下：38.24 20.4239.57 26.1540.56 25.3236.26 23.1233.48 10.5437.5612.1938.4213.1137.5220.4441.239.1041.1713.0536.08-5.2138.4715.1338.1515.3537.511

4、5.1735.4914.3239.3619.5638.0924.3636.0923.0040.4413.5740.3314.1540.3714.2337.5722.56四、程序实现%基于遗传算法的TSP问题求解%D是距离矩阵，n为种群个数，建议取为城市个数的12倍，%C为停止代数，遗传到第C代时程序停止，C的具体取值视问题的规模和耗费的时间而定%m为适应值归一化淘汰加速指数，最好取为1,2,3,4 ,不宜太大%alpha为淘汰保护指数，可取为01之间任意小数，取1时关闭保护功能，最好取为0.81.0%R为最短路径，Rlength为路径长度close all;clc;clear;%城市坐标cit

5、y=38.2420.42;39.57 26.15;40.56 25.32;36.26 23.12;33.48 10.54;37.56 12.19;38.42 13.11;37.52 20.44;41.23 9.10;41.17 13.05;36.08 -5.21;38.47 15.13;38.15 15.35;37.5115.17;35.49 14.32;39.36 19.56;38.09 24.36;36.09 23.00;40.44 13.57;40.33 14.15;40.37 14.23;37.57 22.56;'D=dist(city,city);%城市间距离矩阵n=100;

6、C=100;m=2;alpha=0.9;N,NN=size(D);farm=zeros(n,N);%用于存储种群for i=1:nfarm(i,:)=randperm(N);%随机生成初始种群endR=farm(1,:);%存储最优种群len=zeros(n,1);%存储路径长度fitness=zeros(n,1);%存储归一化适应值counter=0;%记录迭代次数while counter<Cfor i=1:nlen(i,1)=myLength(D,farm(i,:);% 计算路径长度 end maxlen=max(len);minlen=min(len);fitness=fit(l

7、en,m,maxlen,minlen);% 计算归一化适应值 rr=find(len=minlen);R=farm(rr(1,1),1);%更新最短路径FARM=farm;%优胜劣汰，nn记录了复制的个数 nn=0; for i=1:nnn=nn+1;FARM(nn,:)=farm(i,:);if fitness(i,1)>=alpha*randendaa,bb=size(FARM);% 交叉和变异 while aa<nif nn<=2nnper=randperm(2);elsennper=randperm(nn);endA=FARM(nnper(1),:);B=FARM(n

8、nper(2),:);A,B=intercross(A,B);FARM=FARM;A;B;aa,bb=size(FARM);endif aa>nFARM=FARM(1:n,:);%保持种群规模为 n endfarm=FARM;clear FARMcounter=counter+1;endRlength=len(16)% 最优路径farm(16,:)%城市访问次序newcood=city(:,farm(16,:);newcood=newcood newcood(:,1);%路径是封闭连续的分段曲线plot(newcood(1,:),newcood(2,:),'o-');ti

9、tle('最优路径图')%计算归一化适应值子程序function fitness=fit(len,m,maxlen,minlen)fitness=len;for i=1:length(len)fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.000001).Am; end%计算路径的子程序 function len=myLength(D,p) N,NN=size(D);len=D(p(1,N),p(1,1);for j=1:N-1len=len+D(p(1,j),p(1,j+1);function x,y=exchange(x

10、,y)temp=x;x=y;y=temp;function a,b=intercross(a,b)L=length(a);if L<=10%确定交叉宽度W=1;elseif (L/10)-floor(L/10)>=rand&&L>10W=ceil(L/10);elseW=floor(L/10);endp=unidrnd(L-W+1);%随机选择交叉范围，从 p到p+Wfor i=1:W% 交叉x=find(a=b(1,p+i-1);y=find(b=a(1,p+i-1);a(1,p+i-1),b(1,p+i-1)=exchange(a(1,p+i-1),b(1,p+i-1);a(1,x),b(1,y)=exchange(a(1,x),b(1,y);End运行结果：counter =%迭代100次100Rlength =%最优路径程度124.4678ans =%最优路径次序Columns 1 through 10141731841195610Columns 11 through 2020222816121921713Columns 21 through 22115五、问题思考比较用Hopfield求解TSP问题和遗传算法求解TS