一種求解TSP問題的協(xié)同進化算法

魏士偉

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

關鍵詞： 遺傳算法;進化算法;TSP;協(xié)同進化;資源調(diào)度

【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）是圖論中一個著名的組合優(yōu)化問題。現(xiàn)實世界很多行業(yè)中的優(yōu)化問題，如快遞配送線路安排、飛機航線安排、應急災害調(diào)度、車輛路徑規(guī)劃、印制電路的制作、衛(wèi)星位置的調(diào)整、人類基因排序、晶體結構分析和數(shù)據(jù)串聚類等[1-3]，都可以歸納為TSP問題。因此，研究求解TSP問題的高效算法具有十分重要的意義。

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

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

2 TSP問題描述及求解模型

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

3.3 協(xié)同進化技術

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

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

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

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

3.4 協(xié)同進化算法的詳細描述

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

算法1 協(xié)同進化算法

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

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

Step 3 對subpopA中的每個個體，根據(jù)公式（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中選擇出的相同數(shù)目的個體進行交叉操作，新生成的個體將以概率Pm進行變異操作，再將其放置于下一代群體POP（t+1）中。

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

Step 8 令t=t+1。

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

4 實驗與結果分析

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

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

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

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

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

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

5 結束語

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

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

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

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