TSP问题的遗传算法

1、TSP问题的遗传算法 n 个城市之间的相互距离,现有一个推销员必须遍访这 n 个城市,并且每 个城市只能访问一次, 最后又必须返回出发城市. 如何安排他对这些城市的访问 次序,可使其旅行路线的总长度最短？用图论的术语来说,假设有一个图 g=(v,e) ,其中 v 是顶点集, e 是边集, 设 d=(dij) 是由顶点 i 和顶点 j 之间的距离所组成的距离矩阵, 旅行商问题就是求 出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路.这个问题可分为对称旅行商问题(dij=dji,任意i,j=1,2,3,n)和非对称旅行商问题(dij丰dji,任意i,j=1,2,3,n).假设对于城市v=

2、v1,v2,v3,vn的一个访问顺序为 t=(t1,t2,t3,ti,tn),其中ti v(i=1,2,3,n),且记tn+1= t1 ,那么旅行商问题的数学模型为：min l= (T d(t(i),t(i+1) (i=1,n)旅行商问题是一个典型的组合优化问题,并且是一个 np 难问题,其可能的路径数目与城市数目 n 是成指数型增长的,所以一般很难精确地求出其最优解, 本文采用遗传算法求其近似解.遗传算法：初始化过程：用v1,v2,v3,vn代表所选n个城市.定义整数pop-size作为染色 体的个数,并且随机产生 pop-size 个初始染色体,每个染色体为 1到 18的整数 组成的随机序

3、列.适应度f的计算：对种群中的每个染色体 vi,计算其适应度,f=(7 d(t(i),t(i+1). 评价函数 eval(vi) ：用来对种群中的每个染色体 vi 设定一个概率,以使该染色体 被选中的可能性与其种群中其它染色体的适应性成比例, 既通过轮盘赌, 适应性价函数为eval(vi)=alpha*(1-alpha)4(i-1).随机规划与模糊规划选择过程：选择过程是以旋转赌轮 pop-size 次为根底,每次旋转都为新的种群选择一个染色体.赌轮是按每个染色体的适应度进行选择染色体的.stepl、对每个染色体 vi,计算累计概率 qi , q0=0;qi= c eval(vj) j=1,i

4、;i=1,pop-size.step2、从区间(0,pop-size)中产生一个随机数r;step3、假设qi-1<r<qi,那么选择第i个染色体；step4、重复step2和step3共pop-size次,这样可以得到 pop-size个复制的 染色体.grefenstette 编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体,本文采用 grefenstette 编码?遗传算法原理及应用?可以防止这种情况的出现.所谓的 grefenstette 编码就是用所选队员在未选(不含淘汰)队 员中的位置,如：8 15 2 16 10 7 4 3 11 14 6 12

5、 9 5 18 13 17 1对应：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 .交叉过程：本文采用常规单点交叉.为确定交叉操作的父代,从 到 pop-size 重 复以下过程：从0 , 1冲产生一个随机数r,如果rvpc,那么选择vi作为一个父 代.将所选的父代两两组队,随机产生一个位置进行交叉,如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 16 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1交叉后为：8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 16 12 3 5 6 8 5 6

6、3 7 3 4 3 2 4 2 2 1 变异过程：本文采用均匀多点变异.类似交叉操作中选择父代的过程,在 r<pm 的标准下选择多个染色体 vi 作为父代.对每一个选择的父代,随机选择多个位 置,使其在每位置按均匀变异(该变异点 xk 的取值范围为 ukmin,ukmax, 产生一个0 , 1中随机数r,该点变异为x'k=ukmin+r(ukmax-ukmin)操作.如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1变异后：8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1反 grefenstette 编码：交叉和变异都是在

7、grefenstette 编码之后进行的,为了循 环操作和返回最终结果, 必须逆 grefenstette 编码过程,将编码恢复到自然编码.循环操作：判断是否满足设定的带数 xzome,否,贝U跳入适应度f的计算；是, 结束遗传操作,跳出.function bestpop,trace=ga(d,termops,num,pc,cxops,pm,alpha)% %bestpop,trace=ga(d,termops,num,pc,cxops,pm,alpha) %d: 距离矩阵%termops: 种群带数%num: 每带染色体的个数%pc: 交叉概率%cxops: 由于本程序采用单点交叉,交叉点的

8、设置在本程序中没有很好的解决, 所以本文了采用定点,即第 cxops ,可以随机产生.%pm: 变异概率%alpha:评价函数 eval(vi)=alpha*(1-alpha)4(i-1).%bestpop: 返回的最优种群%trace: 进化轨迹%citynum=size(d,2);n=nargin;if n<2disp('缺少变量！ ！)endif n<2termops=500;num=50;pc=0.25;cxops=3;alpha=0.10;endif n<3num=50;pc=0.25;cxops=3;pm=0.30;alpha=0.10;endif n&l

9、t;4pc=0.25;cxops=3;pm=0.30;alpha=0.10;endif n<5cxops=3;pm=0.30;alpha=0.10;endif n<6pm=0.30;alpha=0.10;endif n<7alpha=0.10;endif isempty(cxops)cxops=3;endt=initializega(num,citynum);for i=1:termopsl=f(d,t);x,y=find(l=max(l);trace(i)=-l(y(1);bestpop=t(y(1),:);t=select(t,l,alpha);g=grefenstett

10、e(t);g1=crossover(g,pc,cxops);g=mutation(g1,pm);% 均匀变异t=congrefenstette(g);endfunction t=initializega(num,citynum)for i=1:num t(i,:)=randperm(citynum);end function l=f(d,t)m,n=size(t);for k=1:mfor i=1:n-1l(k,i)=d(t(k,i),t(k,i+1);endl(k,n)=d(t(k,n),t(k,1); l(k)=-sum(l(k,:);end function t=select(t,l,a

11、lpha)m,n=size(l);t1=t;beforesort,aftersort1=sort(l,2);%fsort from l to ufor i=1:naftersort(i)=aftersort1(n+1-i); %changeend for k=1:n;t(k,:)=t1(aftersort(k),:);l1(k)=l(aftersort(k);endt1=t;l=l1;for i=1:size(aftersort,2)evalv(i)=alpha*(1-alpha)4(i-1);endm=size(t,1);q=cumsum(evalv);qmax=max(q);for k=1

12、:mr=qmax*rand(1);for j=1:mif j=1&r<=q(1)t(k,:)=t1(1,:);elseif j=1&r>q(j-1)&r<=q(j)t(k,:)=t1(j,:);endendend function g=grefenstette(t)m,n=size(t);for k=1:mt0=1:n;for i=1:nfor j=1:length(t0)if t(k,i)=t0(j) g(k,i)=j; t0(j)=; breakendendendend function g=crossover(g,pc,cxops)m,n=siz

13、e(g);ran=rand(1,m);r=cxops;x,ru=find(ran<pc);if ru>=2for k=1:2:length(ru)-1g1(ru(k),:)=g(ru(k),1:r),g(ru(k+1),(r+1):n);g(ru(k+1),:)=g(ru(k+1),1:r),g(ru(k),(r+1):n);g(ru(k),:)=g1(ru(k),:);endend function g=mutation(g,pm) % 均匀变异 m,n=size(g);ran=rand(1,m);r=rand(1,3); %dai gai jin rr=floor(n*rand(1,3)+1);x,mu=find(ran<pm);for k=1: