源程序.txt

1、TSP問題的遺傳算法轉(zhuǎn)載我這幾天做了一個隊員選擇問題，其中一個問題我是用遺傳算法做的，現(xiàn)在我把它整理成解決tsp問題的遺傳算法：旅行商問題(travelingsalemanproblem簡稱tsp)：已知n個城市之間的相互距離，現(xiàn)有一個推銷員必須遍訪這n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短？用圖論的術(shù)語來說，假設(shè)有一個圖g=(ve)，其中v是頂點集，e是邊集

2、，設(shè)d=(dij)是由頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的回路。這個問題可分為對稱旅行商問題(dij=dji任意ij=123，…n)和非對稱旅行商問題(dij≠dji任意ij=123，…n)。若對于城市v=v1v2v3…vn的一個訪問順序為t=(t1t2t3…ti…tn)其中tiv(i=123…n)∈，且記tn1=t1，則旅行商問題的數(shù)學(xué)模型為：minl=σd(

3、t(i)t(i1))（i=1…n）旅行商問題是一個典型的組合優(yōu)化問題，并且是一個np難問題，其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，本文采用遺傳算法求其近似解。遺傳算法：初始化過程：用v1v2v3…vn代表所選n個城市。定義整數(shù)popsize作為染色體的個數(shù)，并且隨機產(chǎn)生popsize個初始染色體，每個染色體為1到18的整數(shù)組成的隨機序列。適應(yīng)度f的計算：對種群中的每個染色體vi，計算其適應(yīng)度，f=

4、σd(t(i)t(i1)).評價函數(shù)eval(vi)：用來對種群中的每個染色體vi設(shè)定一個概率，以使該染色體被選中的可能性與其種群中其它染色體的適應(yīng)性成比例，既通過輪盤賭，適應(yīng)性強的染色體被選擇產(chǎn)生后臺的機會要大，設(shè)alpha(01)∈，本文定義基于序的評價函數(shù)為eval(vi)=alpha(1alpha).^(i1)。[隨機規(guī)劃與模糊規(guī)劃]選擇過程：選擇過程是以旋轉(zhuǎn)賭輪popsize次為基礎(chǔ)，每次旋轉(zhuǎn)都為新的種群選擇一個染色體。賭輪是

5、按每個染色體的適應(yīng)度進行選擇染色體的。step1、對每個染色體vi計算累計概率qi，q0=0qi=σeval(vj)j=1…ii=1…popsize.step2、從區(qū)間(0popsize)中產(chǎn)生一個隨機數(shù)r；step3、若qi1rqi則選擇第i個染色體；step4、重復(fù)step2和step3共popsize次，這樣可以得到popsize個復(fù)制的染色體。grefenstette編碼：由于常規(guī)的交叉運算和變異運算會使種群中產(chǎn)生一些無實際意義

6、的染色體，本文采用grefenstette編碼《遺傳算法原理及應(yīng)用》可以避免這種情況的出現(xiàn)。所謂的grefenstette編碼就是用所選隊員在未選（不含淘汰）隊員中的位置，如：815216107431114612951813171對應(yīng)：81421386325734324221。交叉過程：本文采用常規(guī)單點交叉。為確定交叉操作的父代，從到popsize重復(fù)以下過程：從[0，1]中產(chǎn)生一個隨機數(shù)r，如果rpc，則選擇vi作為一個父代。將所選的

7、父代兩兩組隊，隨機產(chǎn)生一個位置進行交叉，如：814213863257343242216123568563185633211交叉后為：814213863251856332116123568563734324221變異過程：本文采用均勻多點變異。類似交叉操作中選擇父代的過程，在rpm的標準下選擇多個染色體vi作為父代。對每一個選擇的父代，隨機選擇多個位置，使其在每位置按均勻變異（該變異點xk的取值范圍為[ukminukmax]產(chǎn)生一個[0，

8、1]中隨機數(shù)r，該點變異為xk=ukminr(ukmaxukmin)）操作。如：81421386325734324221變異后：814213106322734524121反grefenstette編碼：交叉和變異都是在grefenstette編碼之后進行的，為了循環(huán)操作和返回最終結(jié)果，必須逆grefenstette編碼過程，將編碼恢復(fù)到自然編碼。循環(huán)操作：判斷是否滿足設(shè)定的帶數(shù)xzome，否，則跳入適應(yīng)度f的計算；是，結(jié)束遺傳操作，跳出

9、。endifn7alpha=0.10endifisempty(cxops)cxops=3end[t]=initializega(numcitynum)fi=1:termops[l]=f(dt)[xy]=find(l==max(l))trace(i)=l(y(1))bestpop=t(y(1):)[t]=(tlalpha)[g]=grefenstette(t)[g1]=crossover(gpccxops)[g]=mutation(g1p

10、m)%均勻變異[t]=congrefenstette(g)endfunction[t]=initializega(numcitynum)fi=1:numt(i:)=rperm(citynum)endfunction[l]=f(dt)[mn]=size(t)fk=1:mfi=1:n1l(ki)=d(t(ki)t(ki1))endl(kn)=d(t(kn)t(k1))l(k)=sum(l(k:))endfunction[t]=(tlalph

11、a)[mn]=size(l)t1=t[befestafterst1]=st(l2)%fstfromltoufi=1:nafterst(i)=afterst1(n1i)%changeendfk=1:nt(k:)=t1(afterst(k):)l1(k)=l(afterst(k))endt1=tl=l1fi=1:size(afterst2)evalv(i)=alpha(1alpha).^(i1)endm=size(t1)q=cumsum(e