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

魏士偉

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

關(guān)鍵詞： 遺傳算法;進(jìn)化算法;TSP;協(xié)同進(jìn)化;資源調(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)化問題，如快遞配送線路安排、飛機(jī)航線安排、應(yīng)急災(zāi)害調(diào)度、車輛路徑規(guī)劃、印制電路的制作、衛(wèi)星位置的調(diào)整、人類基因排序、晶體結(jié)構(gòu)分析和數(shù)據(jù)串聚類等[1-3]，都可以歸納為TSP問題。因此，研究求解TSP問題的高效算法具有十分重要的意義。

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

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

2 TSP問題描述及求解模型

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

3.3 協(xié)同進(jìn)化技術(shù)

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

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

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

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

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

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

算法1 協(xié)同進(jìn)化算法

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

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

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

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

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

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

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

Step 8 令t=t+1。

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

4 實驗與結(jié)果分析

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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