數(shù)學(xué)建模之求解TSP問題的遺傳算法(共6頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上求解TSP問題的遺傳算法實現(xiàn) 邱文（湖北工業(yè)大學(xué)機(jī)械學(xué)院，湖北，武漢，）摘要：本文應(yīng)用遺傳算法（GA）解決TSP（travel salesman problem）問題，在此采用基于對各個城市訪問順序的編碼方案，同時在探討影響GA性能的遺傳算子的基礎(chǔ)上，介紹了可以改善解的質(zhì)量的倒位算子。最后通過在VC+6.0上運行該算法的程序得到問題的最優(yōu)解。關(guān)鍵詞：遺傳算法（GA）TSP問題 倒位算子 最優(yōu)解Genetic Algorithm for Solving TSP Problems Qiu Wen(School of Science, Hubei University of

2、 Technology, Hubei, Wuhan,）Abstract: This paper apply genetic algorithm to solve TSP(travel salesman problems) problem .The encoding scheme based on sequence of each city .During the same time , on the studying of the performance of genetic algorithm which based on the genetic operators , we introdu

3、ce an inversion operator to improve the quality of solution . Keywords: genetic algorithm (GA); TSP problem; inversion optimal solution1 引言TSP問題（Traveling Salesman Problems 可描述為：已知n個城市之間的相互距離，現(xiàn)有一推銷員必須遍歷這n個城市，并且每個城市只能訪問一次，最后又必須返回出發(fā)城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短。用圖論的術(shù)語來說，假設(shè)有一個圖G=（V,E）,其中V是頂點集，E是邊集，設(shè)

4、D=（dij）是由頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只能通過一次的具有最短距離的回路。若對于城市V=v1,V2,V3,vn的一個訪問順序為T=（t1, t2, t3, , ti, , tn），且記tn+1=t1，則TSP問題的數(shù)學(xué)模型為：Min L=i=1ndti,ti+1TSP問題是一個典型的組合優(yōu)化問題，并且是一個NP難題，其可能的路徑數(shù)與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確的求出自由解因而尋找出其他有效的近似求解算法就具有重要的理論意義，另一方面，很多實際應(yīng)用問題，比如印制電路板的鉆孔路線方案、連鎖店的貨物配送路線等，經(jīng)過簡化處

5、理后，均可以建模為TSP問題，因而對TSP問題的求解具有重要的應(yīng)用價值，同時研究TSP問題對促進(jìn)遺傳算法也有重大意義。遺傳算法（GA）是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它包括對表示可行解的個體編碼，再對這些編碼進(jìn)行選擇、交叉和變異等遺傳操作。與傳統(tǒng)的優(yōu)化算法相比，遺傳算法的優(yōu)越性主要表現(xiàn)在：（1） 它在搜索過程中不易陷入局部最優(yōu)，即使在所定義的適應(yīng)函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲的情況下，它也能以最大的概率找到群體最優(yōu)解；（2） 由于它固有的并行性，遺傳算法非常適合大規(guī)模并行計算機(jī)。2 初始群體設(shè)定由于遺傳操作是對眾多個體同時進(jìn)行的，這眾多的個體組成

6、了群體，在遺傳算法中考慮到初始群體的多樣性，群體中的個體是隨機(jī)產(chǎn)生的，先隨機(jī)生成一定數(shù)目的個體，然后從中挑出最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)達(dá)到了預(yù)先確定的規(guī)模。/*群體初始化*/void initpop ()unsigned char j1;unsigned int j, k, j2,j3,j4,p5maxstring;j=0;for(k=0;k<lchrom;k+)oldpopj.chromk=k;for(k=0;k<lchrom;k+)p5k=oldpopj.chromk;srand(unsigned)time(NULL); for(j=0;j

7、<popsize;j+)j2=rand()%(lchrom);for(k=0;k<j2+20;k+)j3=rand()%(lchrom);j4=rand()%(lchrom);j1=p5j3;p5j3=p5j4;p5j4=j1;for(k=0;k<lchrom;k+)oldpopj.chromk=p5k;for(k=0;k<lchrom;k+)for(j=0;j<lchrom;j+)ddk*lchrom+j=_hypot(xk-xj,yk-yj); for(j=0;j<popsize;j+)oldpopj.x=(double)decode(oldpopj.c

8、hrom);oldpopj.fitness=objfunc (oldpopj.x);oldpopj.parent1=0;oldpopj.parent2=0;oldpopj.xsite=0;3 目標(biāo)函數(shù)和適應(yīng)度函數(shù)的設(shè)計遺傳算法的一個特點是它僅適用所求問題的目標(biāo)函數(shù)值就可以得到下一步的有關(guān)搜索信息，對目標(biāo)函數(shù)值的使用是通過評價個體的適應(yīng)度來體現(xiàn)的。評價個體適應(yīng)度的一般過程是：（1）對個體編碼串進(jìn)行解碼處理后，可得到個體的表現(xiàn)型。（2）由個體的表現(xiàn)型可計算出對應(yīng)個體的目標(biāo)函數(shù)值。（3）由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個體的適應(yīng)度。在TSP的求解中，將求取距離總和L的最小值Min L作為目標(biāo)函數(shù)，適

9、應(yīng)度函數(shù)常取路徑長度L的倒數(shù)，即f=1/L。/*個體適應(yīng)度計算*/double objfunc(double x1)double y;y=100.0*ff/x1;return y;/*群體適應(yīng)度統(tǒng)計*/void statistics( pp *pop)unsigned int j;sumfitness=pop0.fitness;min=pop0.fitness;max=pop0.fitness;maxpp=0;minpp=0;for(j=1;j<popsize;j+)sumfitness=sumfitness+popj.fitness;if(popj.fitness>max) ma

10、x=popj.fitness;maxpp=j;if(popj.fitness<min)min=popj.fitness;minpp=j;avg=sumfitness/(double)popsize;4 遺傳算法4 .1 編碼設(shè)計在遺傳算法的運行過程中，它不對所求解的問題的實際決策直接進(jìn)行操作，而是對表示可行解的個體編碼施加遺傳運算，通過這種遺傳操作來達(dá)到優(yōu)化的目的，在遺傳算法中把一個問題的解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就叫做編碼。在TSP問題的求解方法中，本文描述旅行路線的方法為巡回旅行路線所經(jīng)過的各個城市的順序排列。它是采用所遍歷的城市的排序來表示各個個體的編碼串，由

11、于一般的個體編碼方法進(jìn)行的交叉運算、變異運算會使群體中產(chǎn)生一些不滿足問題約束條件或無實際意義的巡回路線。因此本文采用Grefenstetee 等提出的一種新的巡回路線編碼方法，該方法能夠使得任意的基因型個體都能夠?qū)?yīng)于一條具有實際意義的巡回路線。即對于TSP問題的N個城市列表W，對各個城市的一個訪問順序為T：T=（t1, t2, t3, , tn）,規(guī)定每訪問完一個城市，就從城市列表W中將其去掉，則用第i（i=1,2,3,n）個所訪問的城市ti在所有未訪問的城市列表W= t1, t2, t3, , ti-1 中的對應(yīng)位置序號gi （i<gi<=N-i+1）就可具體訪問哪個城市，如此

12、這樣直接處理完W中的所有城市。如對十個城市作如下排列： W=（A B C D E F G H I J）現(xiàn)有如下所述的兩條巡回路線：TX=（A D B H F I J G E C） TY=（B C A D E J H I F G）按照Grefenstetee所提出的編碼方法，這兩條巡回路線可編碼為：GX= （1 3 1 5 3 4 4 3 2 1） GY=（2 2 1 1 1 5 3 3 1 1 ）4. 2 遺傳算子 標(biāo)準(zhǔn)遺傳算法的操作算子一般都包括選擇（selection），交叉(crossover)，變異(mutation)三種基本形式。它們構(gòu)成了遺傳算法具備強(qiáng)大搜索能力的核心，是模擬自然選

13、擇以及遺傳過程中發(fā)生的繁殖，雜交和突變現(xiàn)象的主要載體。遺傳算法利用遺傳算子產(chǎn)生新一代群體來實現(xiàn)群體進(jìn)化，算子的設(shè)計是遺傳策略的主要組成部分，也是調(diào)整和控制進(jìn)化過程的基本工具。4.2.1 選擇算子選擇操作是建立在對個體適應(yīng)度進(jìn)行評價的基礎(chǔ)之上，是從群體中選擇優(yōu)勝個體即適應(yīng)度較高的個體，淘汰劣質(zhì)個體的操作，其操作的主要目的是為了避免基因缺失，提高全局收斂性和計算效率。TSP問題采用的是基本遺傳操作中的比例選擇方法，其代碼實現(xiàn)如下：/*選擇*/int select()double rand1, partsum;unsigned int j;partsum =0.0;j=0;srand (unsign

14、ed)time(NULL);rand1=rand ()/32767.0*sumfitness;dopartsum =partsum+oldpopj.fitness;j=j+1; while (partsum<rand1)&&(j<T);return j-1;4.2.2 交叉算子交叉算子在遺傳算法中起著核心作用，它是指將個體進(jìn)行兩兩配對，并以交叉概率Pc把配對的父代個體加以替換重組而生成新個體的操作。雜交操作一般分為以下幾個步驟：（1） 從交配池中隨機(jī)選取出要配對的一對個體；（2） 根據(jù)位串長度L，對要配對的一對個體，隨機(jī)選取1，L-1中一個或者對個的整數(shù)k作為交叉位

15、置；（3） 根據(jù)交叉概率Pc（0<Pc<1）實施交叉操作，配對個體在交叉位置，相互交換各自的部分內(nèi)容，從而形成新的一對個體。本文采用的交叉方法是常規(guī)單點交叉法，即隨機(jī)選取兩條巡回路線上隨機(jī)設(shè)定一個交叉點i（i=1,2,3,n），互換兩條巡回路線上基因座i上的基因。從而得到兩條新巡回路線。配對個體： Gx=(1 3 1 5 3 4 |4 3 2 1) （1 3 1 5 3 4 |3 3 2 1） 新個體Gx1 Gy=(2 2 1 1 1 5 |3 3 1 1 ) （2 2 1 1 1 5| 4 3 1 1） 新個體Gy1 交叉點4.2.3 變異算子變異操作是以變異概率Pm對群體中個體

16、串某些基因位上的基因值做變動，若變異后子代的適應(yīng)度值更加優(yōu)異，則保留子代染色體，否則，仍保留父代染色體。這里采用的方法是倒位變異法。倒位操作（Inverse Operation）是指顛倒個體編碼串中隨機(jī)指定的二個基因座之間的基因排列順序，從而形成一個新的染色體，即產(chǎn)生一條新的巡回路線。假設(shè)當(dāng)前個體X的編碼串為（1 3 1 5 3 4 4 3 2 1）。如果產(chǎn)生的隨機(jī)數(shù)rand()<Pm ,那么隨機(jī)選擇來自同一個體的兩點，比如說3和7，倒置3和7之間的部份，產(chǎn)生下面的子代X1為（1 3 1 4 3 5 3 2 1）。4.3 關(guān)鍵參數(shù)確定在遺傳算法的運行過程中，存在著對其性能產(chǎn)生極大影響的一

17、組參數(shù)。這組參數(shù)在初始階段或群體進(jìn)化過程中需要合理的選擇和控制，以使遺傳算法以最佳的搜索軌跡達(dá)到最優(yōu)解。主要參數(shù)包括：個體編碼串長度L、群體規(guī)模M、交叉概率Pc、變異概率Pm、進(jìn)化代數(shù)T等。這些參數(shù)對遺傳算法的運行性能影響很大，需要謹(jǐn)慎選取。（1）編碼串長度L：編碼串長度的選取與求取精度有關(guān)，本文采用符號編碼來表示個體，編碼串長度為50。（2）群體大小M：群體大小M表示群體中所含個體數(shù)量，當(dāng)M取值較小時，可提高遺傳算法的運算速度，但是卻會降低群體的多樣性，可能引起早熟現(xiàn)象，而當(dāng)M取值較大時，又會使得遺傳算法的運行效率較低，所以本文群體規(guī)模取值100。（3）交叉概率：交叉概率一般取大值，但是取值

18、太大，會破壞群體中的優(yōu)良模式，取值太小，產(chǎn)生新個體的速度較慢，本文采用的取值為0.8。（4）變異概率若取值較大，可能破壞掉很多較好的模式，是的遺傳算法接近于隨機(jī)算法，若取值太小，操作產(chǎn)生新個體的能力就會變差，這里Pm=0.02。（5） 終止代數(shù)T：表示遺傳算法運行結(jié)束條件，并將當(dāng)前群體中的最佳個體作為所求問題的最優(yōu)解輸出。建議取值為500. 表 遺傳算法參數(shù)表LMPcPmT501000.80.02500結(jié)束語 由于遺傳算法不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的的魯棒性，所以廣泛應(yīng)用于很多領(lǐng)域，比如：函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、人工生命等。應(yīng)用遺傳算法求解TSP問題是遺傳算法的應(yīng)用的一個典型實例，本文應(yīng)用新的變異算法倒位算子，這種算子只是對個體編碼串重新排序，而不改變其特性，既保證了變異過程中個體的合法性，同時也為遺傳算法性能的改進(jìn)提供了希望。遺傳算法早在本世紀(jì)40年代，就有學(xué)者開始研究，進(jìn)入60年代后，Holland教授及其學(xué)生才創(chuàng)造出了遺傳算法，在后來學(xué)者們的不斷努力之下，形成了今天遺傳算法用于求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架。隨著眾多學(xué)者們對遺產(chǎn)算法的研究更加深入，其理論日趨完善。相信在不久的將來，我們可以看到遺