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

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

2、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 introduce an inversi

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

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

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

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

7、(lchrom);for(k=0;kj2+20;k+)j3=rand()%(lchrom);j4=rand()%(lchrom);j1=p5j3;p5j3=p5j4;p5j4=j1;for(k=0;klchrom;k+)oldpopj.chromk=p5k;for(k=0;klchrom;k+)for(j=0;jlchrom;j+)ddk*lchrom+j=_hypot(xk-xj,yk-yj); for(j=0;jpopsize;j+)oldpopj.x=(double)decode(oldpopj.chrom);oldpopj.fitness=objfunc (oldpopj.x);old

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

9、nc(double x1)double y;y=100.0*ff/x1;return y;/*群體適應(yīng)度統(tǒng)計(jì)*/void statistics( pp *pop)unsigned int j;sumfitness=pop0.fitness;min=pop0.fitness;max=pop0.fitness;maxpp=0;minpp=0;for(j=1;jmax) max=popj.fitness;maxpp=j;if(popj.fitnessmin)min=popj.fitness;minpp=j;avg=sumfitness/(double)popsize;4 遺傳算法4 .1 編碼設(shè)計(jì)在

10、遺傳算法的運(yùn)行過程中，它不對(duì)所求解的問題的實(shí)際決策直接進(jìn)行操作，而是對(duì)表示可行解的個(gè)體編碼施加遺傳運(yùn)算，通過這種遺傳操作來達(dá)到優(yōu)化的目的，在遺傳算法中把一個(gè)問題的解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就叫做編碼。在TSP問題的求解方法中，本文描述旅行路線的方法為巡回旅行路線所經(jīng)過的各個(gè)城市的順序排列。它是采用所遍歷的城市的排序來表示各個(gè)個(gè)體的編碼串，由于一般的個(gè)體編碼方法進(jìn)行的交叉運(yùn)算、變異運(yùn)算會(huì)使群體中產(chǎn)生一些不滿足問題約束條件或無實(shí)際意義的巡回路線。因此本文采用Grefenstetee 等提出的一種新的巡回路線編碼方法，該方法能夠使得任意的基因型個(gè)體都能夠?qū)?yīng)于一條具有實(shí)際意義的

11、巡回路線。即對(duì)于TSP問題的N個(gè)城市列表W，對(duì)各個(gè)城市的一個(gè)訪問順序?yàn)門：T=（t1, t2, t3, , tn）,規(guī)定每訪問完一個(gè)城市，就從城市列表W中將其去掉，則用第i（i=1,2,3,n）個(gè)所訪問的城市ti在所有未訪問的城市列表W= t1, t2, t3, , ti-1 中的對(duì)應(yīng)位置序號(hào)gi （igi=N-i+1）就可具體訪問哪個(gè)城市，如此這樣直接處理完W中的所有城市。如對(duì)十個(gè)城市作如下排列： 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）按照Grefenstet

12、ee所提出的編碼方法，這兩條巡回路線可編碼為：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)大搜索能力的核心，是模擬自然選擇以及遺傳過程中發(fā)生的繁殖，雜交和突變現(xiàn)象的主要載體。遺傳算法利用遺傳算子產(chǎn)生新一代群體來實(shí)現(xiàn)群體進(jìn)化，算子的設(shè)計(jì)是遺傳策略的主要組成部分，也是調(diào)整和控制進(jìn)化過程的基本工具。4.2.1 選擇算子選擇操作是建立在對(duì)個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上，是從群體中

13、選擇優(yōu)勝個(gè)體即適應(yīng)度較高的個(gè)體，淘汰劣質(zhì)個(gè)體的操作，其操作的主要目的是為了避免基因缺失，提高全局收斂性和計(jì)算效率。TSP問題采用的是基本遺傳操作中的比例選擇方法，其代碼實(shí)現(xiàn)如下：/*選擇*/int select()double rand1, partsum;unsigned int j;partsum =0.0;j=0;srand (unsigned)time(NULL);rand1=rand ()/32767.0*sumfitness;dopartsum =partsum+oldpopj.fitness;j=j+1; while (partsumrand1)&(jT);return j-1;

14、4.2.2 交叉算子交叉算子在遺傳算法中起著核心作用，它是指將個(gè)體進(jìn)行兩兩配對(duì)，并以交叉概率Pc把配對(duì)的父代個(gè)體加以替換重組而生成新個(gè)體的操作。雜交操作一般分為以下幾個(gè)步驟：（1） 從交配池中隨機(jī)選取出要配對(duì)的一對(duì)個(gè)體；（2） 根據(jù)位串長度L，對(duì)要配對(duì)的一對(duì)個(gè)體，隨機(jī)選取1，L-1中一個(gè)或者對(duì)個(gè)的整數(shù)k作為交叉位置；（3） 根據(jù)交叉概率Pc（0Pc1）實(shí)施交叉操作，配對(duì)個(gè)體在交叉位置，相互交換各自的部分內(nèi)容，從而形成新的一對(duì)個(gè)體。本文采用的交叉方法是常規(guī)單點(diǎn)交叉法，即隨機(jī)選取兩條巡回路線上隨機(jī)設(shè)定一個(gè)交叉點(diǎn)i（i=1,2,3,n），互換兩條巡回路線上基因座i上的基因。從而得到兩條新巡回路線。配

15、對(duì)個(gè)體： Gx=(1 3 1 5 3 4 |4 3 2 1) （1 3 1 5 3 4 |3 3 2 1） 新個(gè)體Gx1 Gy=(2 2 1 1 1 5 |3 3 1 1 ) （2 2 1 1 1 5| 4 3 1 1） 新個(gè)體Gy1 交叉點(diǎn)4.2.3 變異算子變異操作是以變異概率Pm對(duì)群體中個(gè)體串某些基因位上的基因值做變動(dòng)，若變異后子代的適應(yīng)度值更加優(yōu)異，則保留子代染色體，否則，仍保留父代染色體。這里采用的方法是倒位變異法。倒位操作（Inverse Operation）是指顛倒個(gè)體編碼串中隨機(jī)指定的二個(gè)基因座之間的基因排列順序，從而形成一個(gè)新的染色體，即產(chǎn)生一條新的巡回路線。假設(shè)當(dāng)前個(gè)體X的

16、編碼串為（1 3 1 5 3 4 4 3 2 1）。如果產(chǎn)生的隨機(jī)數(shù)rand()Pm ,那么隨機(jī)選擇來自同一個(gè)體的兩點(diǎn)，比如說3和7，倒置3和7之間的部份，產(chǎn)生下面的子代X1為（1 3 1 4 3 5 3 2 1）。4.3 關(guān)鍵參數(shù)確定在遺傳算法的運(yùn)行過程中，存在著對(duì)其性能產(chǎn)生極大影響的一組參數(shù)。這組參數(shù)在初始階段或群體進(jìn)化過程中需要合理的選擇和控制，以使遺傳算法以最佳的搜索軌跡達(dá)到最優(yōu)解。主要參數(shù)包括：個(gè)體編碼串長度L、群體規(guī)模M、交叉概率Pc、變異概率Pm、進(jìn)化代數(shù)T等。這些參數(shù)對(duì)遺傳算法的運(yùn)行性能影響很大，需要謹(jǐn)慎選取。（1）編碼串長度L：編碼串長度的選取與求取精度有關(guān)，本文采用符號(hào)編碼

17、來表示個(gè)體，編碼串長度為50。（2）群體大小M：群體大小M表示群體中所含個(gè)體數(shù)量，當(dāng)M取值較小時(shí)，可提高遺傳算法的運(yùn)算速度，但是卻會(huì)降低群體的多樣性，可能引起早熟現(xiàn)象，而當(dāng)M取值較大時(shí)，又會(huì)使得遺傳算法的運(yùn)行效率較低，所以本文群體規(guī)模取值100。（3）交叉概率：交叉概率一般取大值，但是取值太大，會(huì)破壞群體中的優(yōu)良模式，取值太小，產(chǎn)生新個(gè)體的速度較慢，本文采用的取值為0.8。（4）變異概率若取值較大，可能破壞掉很多較好的模式，是的遺傳算法接近于隨機(jī)算法，若取值太小，操作產(chǎn)生新個(gè)體的能力就會(huì)變差，這里Pm=0.02。（5） 終止代數(shù)T：表示遺傳算法運(yùn)行結(jié)束條件，并將當(dāng)前群體中的最佳個(gè)體作為所求問題

18、的最優(yōu)解輸出。建議取值為500. 表 遺傳算法參數(shù)表LMPcPmT501000.80.02500結(jié)束語 由于遺傳算法不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的的魯棒性，所以廣泛應(yīng)用于很多領(lǐng)域，比如：函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、人工生命等。應(yīng)用遺傳算法求解TSP問題是遺傳算法的應(yīng)用的一個(gè)典型實(shí)例，本文應(yīng)用新的變異算法倒位算子，這種算子只是對(duì)個(gè)體編碼串重新排序，而不改變其特性，既保證了變異過程中個(gè)體的合法性，同時(shí)也為遺傳算法性能的改進(jìn)提供了希望。遺傳算法早在本世紀(jì)40年代，就有學(xué)者開始研究，進(jìn)入60年代后，Holland教授及其學(xué)生才創(chuàng)造出了遺傳算法，在后來學(xué)者們的不斷努力之下，形成了今天遺傳算法用于求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架。隨著眾多學(xué)者們對(duì)遺產(chǎn)算法的研究更加深入，其理論日趨完善。相信在不久的將來，我們可以看到遺傳算法在越來越多