遺傳算法（GA）在旅行商問題（TSP）中的應(yīng)用

2015-04-02 23:35:30李和壁

科技創(chuàng)新與應(yīng)用 2015年10期

摘要：旅行推銷員問題（Traveling Saleman Problem，TSP）又被譯為旅行商問題，簡稱為TSP，是最基本的路由問題，問題是在尋找從起點單一的旅客，所有給出需求點之后，最后回到最小路徑成本的起源。最早的旅行商問題數(shù)學(xué)規(guī)劃是由Dantzig（1959）等提出。文章通過遺傳算法及三交換啟發(fā)交叉（THGA），較好的解決了點數(shù)較多時最優(yōu)解的查詢，算法結(jié)構(gòu)簡明，可用于大規(guī)模點陣的最優(yōu)路徑問題。

關(guān)鍵詞：遺傳算法；最優(yōu)路徑；旅行商問題；C++指針

1 概述

“旅行商問題”常被稱為“旅行推銷員問題”，指的是需要有一個推銷員拜訪多個地點，如何找到時間來訪問每個地點，然后返回到最短路徑的起點。規(guī)則是簡單的，但增加了位置的數(shù)量后，解決極為復(fù)雜。以42個地點舉例，以確定是否要列出所有最好的旅游路線，然后計算總路徑大，幾乎難以計數(shù)。多年來全球數(shù)學(xué)家竭盡全力，試圖找到一個高效的算法。在文章中，基于遺傳算法尋求TSP問題的更優(yōu)解決。

2 遺傳算法介紹

2.1 遺傳算法的機(jī)理

在遺傳算法中，優(yōu)化問題的解決方案被稱為個體，它可表示為染色體或基因串。染色體通常可以表示為一個簡單的字符串或數(shù)字串，這個過程稱為編碼處理。算法隨機(jī)生成一定數(shù)量的個體。在每一代均可以被評估，并通過計算獲得適應(yīng)度值。之后個體和群體組成的下一代。這個過程是通過交配（crossover）和突變（mutation）來實現(xiàn)。根據(jù)一項新的個體適應(yīng)選擇，這個過程被重復(fù)：每個個體進(jìn)行評價，計算兩個個體的適合度進(jìn)行交配，然后突變，形成第三代。周而復(fù)始，直到終止條件出現(xiàn)。

2.2 遺傳算法的實施步驟

（1）選擇一個編碼；給出一個有N個染色體的出事群體pop，t：=1。

（2）對群體pop（t）中每一個染色體計算它的適應(yīng)函數(shù)fi=fitness（popi（t））。

（3）若停止的規(guī)則滿足，則算法會停止；否則，計算概率

，i=1，2，…，N，

并以概率的分布（9）從pop（t）隨機(jī)選染色體來構(gòu)成一個新種群

NewPOP（t+1）={popi（t）1j=1，2，…，N}

（4）通過交配得到一個擁有N個染色體的CrossPOP（t+1）。

（5）用一個較小概率p，將一個染色體一個基因發(fā)生突變，形成MutePOP（t+1）；t：=t+1，一個新的群體POP（t）=MutePOP（t）產(chǎn)生；返回2步。

3 遺傳算法求解旅行商問題

3.1 編碼

由于遺傳算法不能直接處理空間數(shù)據(jù)的問題，所以我們要質(zhì)疑的空間數(shù)據(jù)被映射到數(shù)據(jù)串型空間的遺傳結(jié)構(gòu)，而基因型字符串變換算法程序結(jié)構(gòu)可以處理基因數(shù)據(jù)的空間。例如，計算現(xiàn)在北京，廣東，天津，新疆四個城市，但算法不直接處理與北京，廣東，天津，新疆，這些數(shù)據(jù)，所以我們給他們編號，北京（0），廣東（1），天津（2），新疆（3），路徑（廣東→新疆→北京→天津）可以將其表示為一個字符串結(jié)構(gòu)型數(shù)據(jù)（1302）。

（1）二進(jìn)制編碼化，基因代碼用0、1表示。例如：基因A：01100100011 （代表一個個體的染色體）

（2）編碼的互換（用于解決排序）。例如旅行商問題中，一串新的基因編碼用來表示遍歷的城市順序，如：6783401295，表示這九個城市中，要先經(jīng)過城市6，再經(jīng)過城市7，依此類推。

（3）值的編碼。在值的編碼中，每以個基因就是一串新值。這些新值可以是與問題相關(guān)的任何值。

3.2 適應(yīng)度函數(shù)和選擇

遺傳算法是好還是壞的適應(yīng)度函數(shù)值來評估一個個體的，適應(yīng)度函數(shù)值越大，質(zhì)量越好。在本實施例中，采用的適應(yīng)度比例法是遺傳算法是最常見基本的選擇方法，即選擇每個單獨的概率成正比其適應(yīng)值。

3.3 交叉的過程

生物的進(jìn)化是生物基因重組的中心作用，遺傳算法是核心操作系統(tǒng)交叉，即所謂的交指結(jié)構(gòu)的兩個或更多親本部分由個體重組操作代替生成一個新的個體。

文章采用匹配交叉（PMX）法：先隨機(jī)產(chǎn)生兩個新的交叉點，再定義這兩點間區(qū)域為匹配區(qū)域，并交換兩個父代匹配區(qū)域。

父代A項：132 | 468 | 7638

父代B項：983 | 567 | 3694

變換為：

TEMP A項： 132 | 567 | 7638

TEMP B項： 983 | 468 | 3694

對于 TEMP A、TEMP B中匹配區(qū)域以外出現(xiàn)數(shù)碼的重復(fù)，要依據(jù)匹配區(qū)域內(nèi)的位置進(jìn)行逐一替換。匹配關(guān)系：1<——>5 3<——>6 7<——>0

子代A項：532 | 567 | 0668

子代B項：986 | 468 | 6394

3.4 變異

變異性是指特定基因編碼的字符串被替換為另一種基因突變的概率值的基礎(chǔ)上，對各個值，以形成一個新的個體。GA的變異操作是產(chǎn)生新個體輔助方法，它決定了GA局部搜索的能力，同時還能保持種群的多樣性。

基本位變異算指隨機(jī)分配到一個單獨的代碼串或幾個基因的某些突變操作。用于通過如果值為0的原始基因位點的突變，然后將它變成一個突變操作所需的二進(jìn)制個體表示為1；即1到0，0到1。

變異前：

010001010010100010000

變異后：

001001010001010010001

3.5 其他運行參數(shù)選擇

GA運行參數(shù)應(yīng)根據(jù)具體的問題進(jìn)行選擇處理，并固定，算法參數(shù)到目前為止，沒有一個為所有的應(yīng)用領(lǐng)域的GA理論能適用。下面是使用GA參數(shù)時，一般建議的方法：

（1）交叉率的選擇。交叉率一般應(yīng)該會比較大，推薦會使用85%-96%。（2）變異率的選擇。變異率一般應(yīng)該會比較小，一般使用0.4%-1%最好。（3）遺傳運算終止進(jìn)化代數(shù)。個人的想法是設(shè)置一個計數(shù)器，如果變異連續(xù)幾代出現(xiàn)最佳個體n值相同（嚴(yán)格來說應(yīng)該是，最好的個體適應(yīng)連續(xù)的N-代后代種群<=父最優(yōu)適應(yīng)個性）即可終止運作。

4 試驗及結(jié)果分析

實驗：

采用的算法各參數(shù)設(shè)計為：種群規(guī)模70，交叉概率0.9，變異概率0.1，保留比例0.6，最大代數(shù)20。用上述算法對一個有15個真實城市和真實距離旅行商問題進(jìn)行求解，要求合理安排行程路線，使總的旅行距離最短。

程序結(jié)果最優(yōu)路徑為：

6→13→9→2→4→3→14→5→7→10→8→11→0→1→12→6路徑總長度為：15825

計算總耗時：54.735秒

5 結(jié)束語

（1）隨著迭代次數(shù)遞增，優(yōu)化結(jié)果會逐漸接近最優(yōu)解，并在最佳值附近來回波動。

（2）交叉概率Pc值均對優(yōu)化結(jié)果的影響較大，從0.8選擇值的范圍為1.0，可以得到更好的優(yōu)化效果；突變起到支撐作用，變異概率值只要得到適當(dāng)，不會對優(yōu)化結(jié)果造成太大影響。

（3）初始種群的選取對優(yōu)化結(jié)果有較大的影響。

參考文獻(xiàn)

[1]郭靖揚.旅行商問題概述電子科技大學(xué)光電信息學(xué)院[J].大眾科技，2006.