1、TSP問題的遺傳算法已知n個城市之間的相互距離，現(xiàn)有一個推銷員必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短？用圖論的術(shù)語來說，假設(shè)有一個圖g=(v,e),其中v是頂點集，e是邊集，設(shè)d=(dij)是由頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的回路。這個問題可分為對稱旅行商問題(dij=dji,任意i,j=1,2,3,n)和非對稱旅行商問題(dijwdji,任意i,j=1,2,3,n)。若對于城市v=v1,v2,v3,vn的一個訪問順序為t=(

2、t1,t2,t3,ti,tn),其中tiCv(i=1,2,3,n),且記tn+1=t1,則旅行商問題的數(shù)學(xué)模型為：minl=o-d(t(i),t(i+1)(i=1,n)旅行商問題是一個典型的組合優(yōu)化問題，并且是一個np難問題，其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，本文采用遺傳算法求其近似解。遺傳算法：初始化過程：用v1,v2,v3,vn代表所選n個城市。定義整數(shù)pop-size作為染色體的個數(shù)，并且隨機(jī)產(chǎn)生pop-size個初始染色體，每個染色體為1到18的整數(shù)組成的隨機(jī)序列。適應(yīng)度f的計算：對種群中的每個染色體vi,計算其適應(yīng)度，f=(rd(t(i),

3、t(i+1).評價函數(shù)eval(vi)：用來對種群中的每個染色體vi設(shè)定一個概率，以使該染色體被選中的可能性與其種群中其它染色體的適應(yīng)性成比例，既通過輪盤賭，適應(yīng)性強的染色體被選擇產(chǎn)生后臺的機(jī)會要大，設(shè)alpha(0,1),本文定義基于序的評價函數(shù)為eval(vi)=alpha*(1-alpha).A(i-1)。隨機(jī)規(guī)劃與模糊規(guī)劃選擇過程：選擇過程是以旋轉(zhuǎn)賭輪pop-size次為基礎(chǔ)，每次旋轉(zhuǎn)都為新的種群選擇一個染色體。賭輪是按每個染色體的適應(yīng)度進(jìn)行選擇染色體的。stepl、對每個染色體vi,計算累計概率qi,q0=0;qi=o-eval(vj)j=1,i;i=1,pop-size.step2

4、、從區(qū)間(0,pop-size)中產(chǎn)生一個隨機(jī)數(shù)r；step3、若qi-1<r<qi,則選擇第i個染色體；step4、重復(fù)step2和step3共pop-size次，這樣可以得到pop-size個復(fù)制的染色體。grefenstette編碼：由于常規(guī)的交叉運算和變異運算會使種群中產(chǎn)生一些無實際意義的染色體，本文采用grefenstette編碼遺傳算法原理及應(yīng)用可以避免這種情況的出現(xiàn)。所謂的grefenstette編碼就是用所選隊員在未選(不含淘汰)隊員中的位置，如：815216107431114612951813171對應(yīng)：81421386325734324221。交叉過程：本文采用

5、常規(guī)單點交叉。為確定交叉操作的父代，從到pop-size重復(fù)以下過程：從0,1中產(chǎn)生一個隨機(jī)數(shù)r,如果r<pc,則選擇vi作為一個父代。將所選的父代兩兩組隊，隨機(jī)產(chǎn)生一個位置進(jìn)行交叉，如：814213863257343242216123568563185633211交叉后為：814213863251856332116123568563734324221變異過程：本文采用均勻多點變異。類似交叉操作中選擇父代的過程，在r<pm的標(biāo)準(zhǔn)下選擇多個染色體vi作為父代。對每一個選擇的父代，隨機(jī)選擇多個位置，使其在每位置按均勻變異(該變異點xk的取值范圍為ukmin,ukmax,產(chǎn)生一個0,1中

6、隨機(jī)數(shù)r,該點變異為x'k=ukmin+r(ukmax-ukmin)操作。如：81421386325734324221變異后：814213106322734524121反grefenstette編碼：交叉和變異都是在grefenstette編碼之后進(jìn)行的，為了循環(huán)操作和返回最終結(jié)果，必須逆grefenstette編碼過程，將編碼恢復(fù)到自然編碼。循環(huán)操作：判斷是否滿足設(shè)定的帶數(shù)xzome,否，則跳入適應(yīng)度f的計算；是，結(jié)束遺傳操作，跳出。functionbestpop,trace=ga(d,termops,num,pc,cxops,pm,alpha)%bestpop,trace=ga(d

7、,termops,num,pc,cxops,pm,alpha)%d:距離矩陣%termops:種群帶數(shù)%num:每帶染色體的個數(shù)%pc:交叉概率%cxops:由于本程序采用單點交叉，交叉點的設(shè)置在本程序中沒有很好的解決,所以本文了采用定點，即第cxops,可以隨機(jī)產(chǎn)生。%pm:變異概率%alpha:評價函數(shù)eval(vi)=alpha*(1-alpha).A(i-1).%bestpop:返回的最優(yōu)種群%trace:進(jìn)化軌跡%citynum=size(d,2);n=nargin;ifn<2disp('缺少變量！,)endifn<2termops=500;num=50;pc=0

8、.25;cxops=3;pm=0.30;alpha=0.10;endifn<3num=50;pc=0.25;cxops=3;pm=0.30;alpha=0.10;endifn<4pc=0.25;cxops=3;pm=0.30;alpha=0.10;endifn<5cxops=3;pm=0.30;alpha=0.10;endifn<6pm=0.30;alpha=0.10;endifn<7alpha=0.10;endifisempty(cxops)cxops=3;endt=initializega(num,citynum);fori=1:termopsl=f(d,t)

9、;x,y=find(l=max(l);trace(i)=-l(y(1);bestpop=t(y(1),:);t=select(t,l,alpha);g=grefenstette(t);g1=crossover(g,pc,cxops);g=mutation(g1,pm);%均勻變異t=congrefenstette(g);endfunctiont=initializega(num,citynum)fori=1:numt(i,:)=randperm(citynum);endfunctionl=f(d,t)m,n=size(t);fork=1:mfori=1:n-1l(k,i)=d(t(k,i),t

10、(k,i+1);endl(k,n)=d(t(k,n),t(k,1);l(k)=-sum(l(k,:);endfunctiont=select(t,l,alpha)m,n=size(l);t1=t;beforesort,aftersort1=sort(l,2);%fsortfromltou%changefori=1:naftersort(i)=aftersort1(n+1-i);endfork=1:n;t(k,:)=t1(aftersort(k),:);l1(k)=l(aftersort(k);endt1=t;l=l1;fori=1:size(aftersort,2)evalv(i)=alpha

11、*(1-alpha).A(i-1);endm=size(t,1);q=cumsum(evalv);qmax=max(q);fork=1:mr=qmax*rand(1);forj=1:mifj=1&r<=q(1)t(k,:)=t1(1,:);elseifj=1&r>q(j-1)&r<=q(j)t(k,:)=t1(j,:);endendendfunctiong=grefenstette(t)m,n=size(t);fork=1:mt0=1:n;fori=1:nforj=1:length(t0)ift(k,i)=t0(j)g(k,i)=j;t0(j)=;br

12、eakendendendendfunctiong=crossover(g,pc,cxops)m,n=size(g);ran=rand(1,m);r=cxops;x,ru=find(ran<pc);ifru>=2fork=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),:);end%均勻變異endfunctiong=mutation(g,pm)m,n=size(g);ran=rand(1,m);r=rand(1,3);%daigaijinrr=floor(n*rand(1,3)+1);x,mu=find(ran<pm);fork=1:length(mu)fo