一種求解TSP問題的協同進化算法

魏士偉

摘 要：傳統的遺傳算法GA在求解TSP問題時容易出現早熟和陷入局部最優等現象。為此本文提出了一種基于協同進化的遺傳算法（CEGA）用于解決GA算法的缺陷。該算法通過定義個體的適應度值和個體間的差異度值，將適應度值高和差異度大的個體分別放入2個不同的子群體。在進化過程中這2個子種群相互協同進化，既保證了種群向最優解的方向移動，又保持了種群的多樣性。實驗結果表明，本文所提出的算法在解決TSP問題時，具有收斂速度快、容易跳出局部最優等特點，相較其他GA算法具有更好的性能。

關鍵詞： 遺傳算法;進化算法;TSP;協同進化;資源調度

【Abstract】 The traditional Genetic Algorithm （GA） is more prone to be of premature convergence and fall into local optimums when solving TSP problems. In order to overcome these defects， a new Co-Evolution based Genetic Algorithm （CEGA） is proposed is this paper. By defining the fitness value of individuals and the difference value between individuals， this new algorithm puts individuals with high fitness values into a sub-population and put individuals with large differences into another sub-population. These two sub-populations coevolves with each other during the evolution process， which not only ensures the movement of the whole population towards the optimal value， but also maintains the diversity of the population. The experimental results show that the algorithm proposed in this paper has characteristics of fast convergence and being easy to jump out of local optimums when solving TSP problems. The research demonstrates that the proposed algorithm has better performance than other GA algorithms.

【Key words】 ?Genetic Algorithm; evolutionary algorithm; TSP; Co-Evolution; resource scheduling

1 概述

旅行商問題（Traveling Salesman Problem，TSP）是圖論中一個著名的組合優化問題。現實世界很多行業中的優化問題，如快遞配送線路安排、飛機航線安排、應急災害調度、車輛路徑規劃、印制電路的制作、衛星位置的調整、人類基因排序、晶體結構分析和數據串聚類等[1-3]，都可以歸納為TSP問題。因此，研究求解TSP問題的高效算法具有十分重要的意義。

求解TSP問題的傳統算法通常有窮舉法[4]、分支限界法[5]和動態規劃法[6]等。然而，TSP已被證明是一個NP完全問題，隨著問題規模的擴大，所需的計算時間呈指數級增加，依靠這些傳統算法求解TSP問題已經變得不可能。針對大規模TSP問題，一些進化算法顯示出其獨特的優越性。例如，蟻群算法[7-8]、模擬退火算法[9]、啟發搜索式算法[10]、遺傳算法 （GA）以及一些混合智能算法[11-14]等。 特別是遺傳算法，模擬了生物進化論的自然選擇的機理和遺傳學的生物進化過程，能夠使生物群體不斷地向好的方向進化，從而搜索到最優解。由于具有良好的全局最優解搜索能力、隱含的并行計算能力和靈活的應用方式，在解決大規模復雜問題時遺傳算法（GA）已經成為近期吸引學界高度關注的進化算法。例如，陳林等人[11]利用貪婪思想產生初始種群，通過改進的遺傳算法來加快尋優速度，從而優化遺產算法的質量和尋優效率。姜群等人[12]通過動態調整種群的交叉和變異概率控制了進化過程，以便使遺傳算法獲得更好的性能。孫文彬等人[13]針對遺傳算法求得的解質量不高等缺陷，設計了一種基于遺傳算法的多策略優化求解方法來處理TSP問題，并取得了良好效果。張玉州等人[14]通過組合局部搜索算子集合并將其嵌入遺傳算法，從而形成混合遺傳算法來求解TSP問題。

這些改進的遺傳算法在研究TSP問題時，一定程度上都表現出良好的性能。然而，隨著問題規模的進一步擴大，遺傳算法依然會出現早熟收斂、容易陷入局部最優等問題。為此，本文提出一種基于協同進化的遺傳算法，來改善算法易于早熟收斂的缺陷，強化搜索全局最優解的能力。實驗結果表明新提出的算法在解決TSP問題時具備良好的性能。

2 TSP問題描述及求解模型

具體的個體選擇策略為，將群體分為2個子群體subpopA和subpopB，各子群體中的個體數量各占群體總數的1/2。接著即需確定subpopA中的個體，可使用輪盤賭的方式將適應度值高的個體選擇進來，待subpopA一旦確定后，就可以根據subpopA中的每個個體從種群中查找出和其差異度最高的個體而組成subpopB， 從而完成個體的選擇。

3.3 協同進化技術

選擇出來的個體分別組成了2個子群體subpopA和subpopB，通過各個子群體的內部的交叉變異操作可以生成下一代新的種群個體。同時，子種群subpopA和subpopB之間也可以通過相互的交叉和變異操作，即通過協同進化的方式產生下一代種群新個體，對此進化方法可詳述如下。

（1）子種群subpopA和子種群subpopB各自的獨立進化。對于每個子群體，分別以隨機的方式從子種群中選擇1/3popsize個個體，其后以概率Pc進行兩兩交叉操作，接著又以概率Pm進行變異操作從而生成新的個體，再將其放入下一代群體中。

（2）子種群subpopA和子種群subpopB的協同進化。從subpopA子種群中隨機選擇1/6popsize個個體，從subpopB中選擇同樣數目的個體，并以概率1進行交叉操作，后續則以概率Pm進行變異操作從而生成新的個體，再將其放入到下一代群體中。

采用這種協同進化技術可以讓個體在向最優解靠近的同時，還能保持種群的多樣性，防止種群隨著進化代數的增加過早出現早熟現象，并且各個子種群之間通過相互交叉變異更有可能產生出更優的解，從而找到最優解。下一節將給出協同進化算法的詳細描述。

3.4 協同進化算法的詳細描述

綜合前述研究后可得，多精英協同進化遺傳算法MECGA的基本思想如算法1所示。

算法1 協同進化算法

Step 1 令進化代數t=0，設置的種群大小popsize、交叉概率Pc、變異概率Pm的初始值， 并進行種群初始化操作生成初始化種群POP（t）;

Step 2 對POP（t）中的個體根據式（8）計算適應度值， 以輪盤賭的方式從中選擇1/2popsize個個體組成子群體subpopA;

Step 3 對subpopA中的每個個體，根據公式（9）找出POP（t）中與之差異度最大的個體并將其放置于subpopB中。

Step 4 從subpopA中隨機選擇1/3popsize個體，并以概率Pc進行交叉操作，生成的新個體再以Pm概率進行變異操作，然后將其插入到下一代種群POP（t+1）中;

Step 5 從subpopB中隨機選擇1/3popsize個體，并以概率Pc進行交叉操作，生成的新個體再以Pm概率進行變異操作，然后將其放入種群POP（t+1）中;

Step 6 從subpopA中隨機選擇1/6popsize個體，并讓其與從subpopB中選擇出的相同數目的個體進行交叉操作，新生成的個體將以概率Pm進行變異操作，再將其放置于下一代群體POP（t+1）中。

Step 7 判斷群體POP（t）中最優個體的適應度值是否大于下一代群體POP（t+1）中最優個體的適應度值（精英保留策略），若不大于，則將其放置于POP（t+1）。

Step 8 令t=t+1。

Step 9 判斷是否滿足終止條件，若是，則結束;否則，轉到 Step 2。

4 實驗與結果分析

為了驗證協同進化算法在解決TSP問題時的良好性能，研究將其與傳統的GA算法、帶有精英保留策略的遺傳算法GAE做了實驗對比和分析。本研究中，進行實驗驗證和分析時的部分參數取值詳見表1。

實驗在標準的測試集TSPLIB數據庫（http：//elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html）中選擇了6個數據集進行測試。針對文中選定的3種對比算法運算求得的最短哈曼頓路徑的實驗結果見表2。

從表2中可以看出，GA和GAE算法求得的最短路徑的長度值相差不多，而且受到所處理問題規模的限制，這2種算法都容易陷入局部最優解而缺乏跳出局部機制能力，由其求得的結果并不理想。 而CEGA算法由于設計了精英種群和普通協同進化的思想，既可以保持向最優解不斷靠近的壓力，又保持了種群的多樣性，具備跳出局部最優的能力，所求解的質量要好很多。在此基礎上研究又發現，對于所有的測試案例，CEGA算法的結果總是好于GA算法和GAE算法的結果。特別是att48.tsp測試數據集，CEGA算法求得的最短路徑長度只有GA算法和GAE算法的50%左右。

為了進一步驗證本文所提出的算法的尋找最優解的性能，分別在att48.tsp和berlin52.tsp數據集上對比分析3種對比算法的進化過程。如圖1和圖2所示。

從圖1、圖2中可以看出，隨著進化代數的推進，GA和CGA算法在進化的前期都能引導種群不斷向最優解的方向移動，所求的最小值也在不斷下降，但是在進化的后期（種群大概進化到60代以后），這種下降的趨勢越來越不明顯，幾乎喪失了進一步尋優的能力。而CEGA算法卻表現出較好的進化態勢，群體尋找到的最優值隨著進化代數的逐漸演進而不斷向最優解靠近，即使到進化的后期，這種趨勢也十分明顯。分析可知，這一結果即得益于CEGA算法的良好設計，由于將群體分為2個子種群，一個子種群中的個體具有較高的適應度值，而另一個子種群具有較高的差異度值，這些子種群之間又相互協同進化，使得種群既有向最優解前進的驅動力，又能夠保持種群的多樣性，從而使群體具備了跳出局部最優解的能力。 至此，圖1、圖2中的結果可以看出，無論是最終求得的解的質量，還是求解過程中的進化趨勢，CEGA算法都優于GA和GAE算法。

此外，關于本文提出算法CEGA在att48.tsp數據集和berlin52.tsp數據集上求得的旅行線路圖，即哈曼頓路徑，見圖3和圖4。

5 結束語

傳統遺傳算法在解決TSP這一NPC問題時容易出現早熟和陷入局部最優等問題。為此，本文提出了一種基于種群協同進化的遺傳算法CEGA。該算法將種群中的個體依據適應度值和定義的差異度值分到了2個子種群中，一個子種群中的個體具有較高的適應度值，而另一個子種群中的個體具有較大的差異度值。在進化過程中，這2個子種群相互協作，共同進化，使種群既能夠向靠近最優解的方向移動，又能保持種群的多樣性。算法具有了易于跳出局部最優解的能力。為了驗證所提出的算法的性能，研究則在TSPLIB數據庫中的測試集上進行了多組實驗。實驗結果表明，CEGA算法在解決TSP問題時，其所求得的解的質量總是好于GA算法和GAE算法，而且在跳出局部最優解的能力方面有著良好表現，算法的穩定性也更高。

參考文獻

[1]申艷光， 張玲玉， 劉永紅. 基于混合遺傳算法的物流路徑優化方法研究[J].計算機技術與發展， 2018， 28（3） ：192-196.

[2]吳新勝， 姜婷， 趙夢超， 等. 基于群智能混合算法的應急物流路徑優化研究[J]. 四川理工學院學報（自然科學版）， 2018， 31 （4） ：68-73.

[3]唐健， 史文中， 孟令奎. 基于遺傳算法的時相關動態車輛路徑規劃模型[J]. 武漢大學學報（信息科學版）， 2008， 33 （8） ：875-879.

[4]許玲. 優化窮舉法求旅行商問題的近似最優解[J]. 微型機與應用， 1998（10）：20，33.

[5]陳濤， 張思發. 分支限界法求解實際TSP問題[J]. 計算機工程與設計， 2009， 30（10）：2431-2434.

[6]來學偉. 動態規劃法在TSP問題中的應用[J]. 吉林化工學院學報， 2017， 34（3）：65-67.

[7]王寶生， 屈寶存. 蟻群算法在求解TSP問題中的改進研究[J]. 電子設計工程， 2014，22（22）：14-18，21.

[8]康嵐蘭， 李康順. 蟻群算法在求解TSP問題上與遺傳算法的對比研究[J]. 計算機系統應用， 2008， 17（10）：60-63.

[9]周君， 賈昆霖. 求解旅行商路徑規劃問題的改進模擬退火算法[J]. 電子科技， 2017， 30（7）：62-64，68.

[10]鄧志剛， 何琦， 肖媛娥， 等. 一種基于TSP問題的啟發式搜索算法研究[J]. 科技廣場， 2010（9）：29-31.

[11]陳林， 潘大志. 改進遺傳算法解決TSP問題[J]. 智能計算機與應用， 2016， 6（5）：17-19，23.

[12]姜群， 晏雨. 改進的遺傳算法在TSP問題中的應用[J]. 重慶理工大學學報（自然科學）， 2012，26（9）：96-99.

[13]孫文彬， 王江. 一種基于遺傳算法的TSP問題多策略優化求解方法[J]. 地理與地理信息科學， 2016， 32（4）：1-4.

[14]張玉州， 梅俊， 徐廷政. 一種求解TSP問題的混合遺傳算法[J]. 安慶師范大學學報（自然科學版）， 2018，24（3）：77-81.