遗传算法的matlab通用程序

1、已知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=(v1,v2,v3, -,vn 的一个访问顺序

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

3、的每个染色体vi ,计算其适应度，f= bd(t(i),t(i+1).评价函数eval(vi) :用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha (0,1),本文定义基于序的评价函数为 eval(vi)=al pha*(1-alpha).A(i-1)。随机规划与模糊规划选择过程：选择过程是以旋转赌轮pop-size 次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1 、对每个染色体 vi,计算累计概率 qi , q0=0

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

5、 14 6 12 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 ,如果r将所选的父代两两组队，随机产生一个位置进 行交叉，如：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 3 7 3 4 3

6、2 4 2 2 1变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r选择多个染色体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编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作和返回最终

7、结果，必须逆grefenstette 编码过程，将编码恢复到自然编码。循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。matlab 代码distTSP.txt0 6 18 4 87 0 17 3 74 4 0 4 520 19 24 0 228 8 16 6 0%GATSP.mfunction gatsp1()clear;load distTSP.txt;distance=distTSP;N=5;ngen=100;ngpool=10;%ngen=input('# of generations to evolve =');%ngpoo

8、l=input('# of chromosoms in the gene pool = ');% size of genepoolgpool=zeros(ngpool,N+1); % gene pool for i=1:ngpool, % intialize gene pool gpool(i,:)=1 randomize(2:N')' 1;for j=1:i-1while gpool(i,:)=gpool(j,:)gpool(i,:)=1 randomize(2:N')' 1;endendend costmin=100000;tourmin=z

9、eros(1,N);cost=zeros(1,ngpool);increase=1;resultincrease=1;for i=1:ngpool,cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:)');end% record current best solutioncostmin,idx=min(cost);tourmin=gpool(idx,:);disp(num2str(increase) 'minmum trip length = ' num2str(costmin)costminold2=2

10、00000;costminold1=150000;resultcost=100000;tourminold2=zeros(1,N);tourminold1=zeros(1,N);resulttour=zeros(1,N);while(abs(costminold2-costminold1);100)&(abs(costminold1-costmin);100)&(increase ;500)costminold2=costminold1; tourminold2=tourminold1;costminold1=costmin;tourminold1=tourmin;increa

11、se=increase+1;if resultcost>costminresultcost=costmin;resulttour=tourmin;resultincrease=increase-1;endfor i=1:ngpool,cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:)');end% record current best solutioncostmin,idx=min(cost);tourmin=gpool(idx,:);%=% copy gens in th gpool according to

12、 the probility ratio% >1.1 copy twice% >=0.9 copy once% ;0.9 removecsort,ridx=sort(cost);% sort from small to big.csum=sum(csort);caverage=csum/ngpool;cprobilities=caverage./csort;copynumbers=0;removenumbers=0;for i=1:ngpool,if cprobilities(i) >1.1copynumbers=copynumbers+1;endif cprobilitie

13、s(i) <0.9removenumbers=removenumbers+1;endendcopygpool=min(copynumbers,removenumbers);for i=1:copygpoolfor j=ngpool:-1:2*i+2 gpool(j,:)=gpool(j-1,:);endgpool(2*i+1,:)=gpool(i,:);endif copygpool=0gpool(ngpool,:)=gpool(1,:);end%=%when genaration is more than 50,or the patterns in a couple are too c

14、lose,do mutationfor i=1:ngpool/2%sameidx=gpool(2*i-1,:)=gpool(2*i,:);diffidx=find(sameidx=0);if length(diffidx)<=2gpool(2*i,:)=1 randomize(2:12')' 1;endend%=%cross gens in couplesfor i=1:ngpool/2gpool(2*i-1,:),gpool(2*i,:)=crossgens(gpool(2*i-1,:),gpool(2*i,:);endfor i=1:ngpool,cost(i)=su

15、m(diag(distance(gpool(i,:)',rshift(gpool(i,:)');end% record current best solutioncostmin,idx=min(cost);tourmin=gpool(idx,:);disp(num2str(increase) 'minmum trip length = ' num2str(costmin) end disp('cost function evaluation: ' int2str(increase) ' times!')disp('n:&#

16、39; int2str(resultincrease)disp('minmum trip length = ' num2str(resultcost)disp('optimum tour =')disp(num2str(resulttour)%=function B=randomize(A,rowcol)% Usage: B=randomize(A,rowcol)% randomize row orders or column orders of A matrix% rowcol: if =0 or omitted, row order (default)% i

17、f = 1, column orderrand('state',sum(100*clock)if nargin = 1,rowcol=0;endif rowcol=0,m,n=size(A);p=rand(m,1);p1,I=sort(p);B=A(I,:);elseif rowcol=1,Ap=A'm,n=size(Ap);p=rand(m,1);p1,I=sort(p);B=Ap(I,:)'end%=function y=rshift(x,dir)% Usage: y=rshift(x,dir)% rotate x vector to right (down

18、) by 1 if dir = 0 (default)% or rotate x to left (up) by 1 if dir = 1if nargin ;2, dir=0; endm,n=size(x);if m>1,if n = 1,col=1;elseif n>1,error('x must be a vector! break');end % x is a column vectorelseif m = 1, if n = 1, y=x;returnelseif n>1,col=0; % x is a row vector endendif dir=1, % rotate left or upif col=0, % row vector