劉景鑫 李林林 李治華 張?jiān)藕?/p>

摘? 要： 旅行商問(wèn)題是一類(lèi)經(jīng)典的組合最優(yōu)化問(wèn)題，在理論研究和實(shí)際應(yīng)用領(lǐng)域具有重要的研究?jī)r(jià)值。本文提出了一種自適應(yīng)遺傳算法，通過(guò)變異率的自適應(yīng)策略平衡算法的全局性和局部性，同時(shí)利用外部存檔策略為種群進(jìn)化提供具有全局指導(dǎo)信息的父代個(gè)體，提高了算法的收斂速度。通過(guò)對(duì)TSPLIB標(biāo)準(zhǔn)庫(kù)中實(shí)例的測(cè)試，驗(yàn)證了算法的可行性和有效性。

關(guān)鍵詞： 旅行商問(wèn)題; 遺傳算法; 自適應(yīng); 外部存檔

中圖分類(lèi)號(hào)：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1006-8228（2019）07-51-03

Abstract： Traveling Salesman Problem is a classical combinatorial optimization problem， which has important research value in theoretical research and practical application. In this paper， an adaptive genetic algorithm is proposed， which balances the global ability and local ability of the algorithm by adapting the self-adaptive mechanism of mutation probability. An external archiving strategy is used to provide better parent individuals which have global guiding information for the evolutionary process， to improve the convergence speed of the algorithm. The feasibility and effectiveness of the proposed algorithm are verified by the test on the instances in TSPLIB standard library.

Key words： Traveling Salesman Problem; genetic algorithm; self-adaptation; external archiving

0 引言

旅行商問(wèn)題是一類(lèi)復(fù)雜的組合優(yōu)化問(wèn)題[1]，在理論計(jì)算機(jī)科學(xué)和運(yùn)籌學(xué)研究中非常重要。問(wèn)題易于描述但難以求解，是典型的NP難問(wèn)題[2]。旅行商問(wèn)題的目標(biāo)通常是最小化總行程，而且所有節(jié)點(diǎn)都必須訪(fǎng)問(wèn)一次。旅行商問(wèn)題可以被應(yīng)用與各個(gè)領(lǐng)域，如電路板設(shè)計(jì)、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、物流配送等領(lǐng)域[3-5]。求解旅行商問(wèn)題的算法包括遺傳算法、爬山算法、模擬退火算法、蟻群算法、禁忌搜索算法、粒子群算法等[7-10]。

1 遺傳算法

遺傳算法是一類(lèi)最經(jīng)典的基于種群的隨機(jī)優(yōu)化算法，它模仿達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程。算法通過(guò)種群中個(gè)體的并行繁殖和選擇，保留優(yōu)良個(gè)體，得到新的下一代種群，通過(guò)這種優(yōu)勝劣汰的自然選擇不斷的保留優(yōu)秀個(gè)體，進(jìn)而最終得到問(wèn)題的最優(yōu)解。遺傳算法非常適合與求解排列組合問(wèn)題。遺傳算法的基本流程如下：

步驟1 初始化種群;

步驟2 評(píng)價(jià)種群中個(gè)體的適應(yīng)值;

步驟3 對(duì)種群中的當(dāng)前個(gè)體，利用進(jìn)化操作生成新個(gè)體：

步驟3.1 從當(dāng)前種群中隨機(jī)選擇2個(gè)個(gè)體;

步驟3.2 對(duì)2個(gè)個(gè)體利用交叉操作生成實(shí)驗(yàn)個(gè)體;

步驟3.3 對(duì)實(shí)驗(yàn)個(gè)體利用變異操作生成后代個(gè)體;

步驟4 重復(fù)步驟3直到終止條件滿(mǎn)足。

對(duì)于遺傳算法來(lái)說(shuō)，最核心的部分就是選擇合適的交叉算子和變異算子，其中交叉算子能夠組合不同個(gè)體的基因，變異算子改變基因信息，進(jìn)而改進(jìn)種群的多樣性，提高算法的全局搜索能力。選擇和使用合適的交叉和變異算子，能夠防止算法出現(xiàn)早熟收斂等問(wèn)題，同時(shí)保持種群的多樣性。本文在第二部分展示旅行商問(wèn)題的模型，第三部分展示提出算法的結(jié)構(gòu)，第四部分和第五部分給出實(shí)驗(yàn)和結(jié)論。

2 TSP旅行商問(wèn)題

旅行商問(wèn)題是所有城市節(jié)點(diǎn)搜索最短的漢密爾頓回路。描述方式如下：有N個(gè)城市，城市之間的距離用矩陣D=（dij）N×N表示，dij表示從城市i到城市j之間的距離，問(wèn)題的目標(biāo)是從所有路徑中找到最短路徑，如公式⑴，這是一種遞歸方式的表達(dá)，其中πi表示路徑經(jīng)過(guò)的第i個(gè)城市。一般TSP問(wèn)題可以按照距離矩陣分為兩類(lèi)：對(duì)稱(chēng)性TSP問(wèn)題和非對(duì)稱(chēng)性TSP問(wèn)題。本文主要對(duì)常見(jiàn)的對(duì)稱(chēng)性TSP問(wèn)題進(jìn)行求解。

⑴

通常旅行商問(wèn)題可以按照距離矩陣可以分為兩類(lèi)：對(duì)稱(chēng)性旅行商問(wèn)題和非對(duì)稱(chēng)性旅行商問(wèn)題。對(duì)稱(chēng)性旅行商問(wèn)題是在一個(gè)帶權(quán)無(wú)向完全圖中找一個(gè)權(quán)值最小的Hamilton回路。在各類(lèi)TSP中，該類(lèi)問(wèn)題的研究成果最多。近幾年來(lái)，研究者或者基于數(shù)學(xué)理論構(gòu)造近似算法，或者使用各種仿自然的算法框架結(jié)合不同的局部搜索方法構(gòu)造混合算法。本文主要針對(duì)對(duì)稱(chēng)性旅行商問(wèn)題進(jìn)行研究。

3 基于外部存檔的自適應(yīng)遺傳算法

3.1 個(gè)體編碼

本文以城市序號(hào)為基因，對(duì)城市序號(hào)進(jìn)行編碼。由于旅行商問(wèn)題要求最后回到出發(fā)城市，因此只需要對(duì)從出發(fā)城市到途徑城市的序號(hào)進(jìn)行編碼即可。例如個(gè)體為{2，3，4，5，1}表示旅行商的線(xiàn)路為從2號(hào)城市出發(fā)，依次途徑3號(hào)城市、4號(hào)城市、5號(hào)城市、1號(hào)城市，最后從1號(hào)城市返回2號(hào)城市。

3.2 交叉操作

交叉算子是通過(guò)對(duì)父代個(gè)體的基因重組得到實(shí)驗(yàn)個(gè)體的過(guò)程。這里對(duì)LOX算子進(jìn)行了改進(jìn)，一般LOX算子父代個(gè)體的選擇是來(lái)自當(dāng)前種群中的隨機(jī)個(gè)體，考慮到外部存檔中的個(gè)體具有更高的質(zhì)量，因此從外部存檔中隨機(jī)選擇一個(gè)個(gè)體作為父代個(gè)體，另一個(gè)個(gè)體選擇種群中的當(dāng)前個(gè)體，在利用LOX操作的方式得到新個(gè)體。交叉算子如圖1所示。通過(guò)這種方式，能夠使優(yōu)良基因信息在交叉過(guò)程中得到保留，使個(gè)體進(jìn)化具有方向性，進(jìn)而提高種群進(jìn)化效率。

3.3 自適應(yīng)變異率策略

變異操作是對(duì)生成個(gè)體的一個(gè)或幾個(gè)基因位進(jìn)行變化，防止個(gè)體的基因信息趨于相似而造成種群進(jìn)化停滯現(xiàn)象。變異率的大小決定變異操作的機(jī)會(huì)的大小，變異率過(guò)大，會(huì)導(dǎo)致算法更加具有隨機(jī)性，影響算法的收斂速度;變異率過(guò)小，會(huì)導(dǎo)致種群多樣性變化太小，而出現(xiàn)早衰或陷入局部最優(yōu)等問(wèn)題。因此，為算法設(shè)置合適的變異率能夠更好的平衡算法的全局探索能力和局部開(kāi)采能力。

種群進(jìn)化前期，算法更加關(guān)注種群進(jìn)化的速度，因此需要設(shè)置較小的變異率來(lái)提高種群中個(gè)體的質(zhì)量;隨著種群的不斷進(jìn)化，算法容易出現(xiàn)多樣性變差等問(wèn)題，因此需要較大的變異機(jī)會(huì)才能夠改變種群的多樣性變差的問(wèn)題。因此利用指數(shù)函數(shù)生成變異率，如公式⑵，其中為0.2。變異算子則采用隨機(jī)交換交叉后生成個(gè)體的兩個(gè)基因位的信息，得到新的后代個(gè)體，如圖2所示。

3.4 選擇操作

為了保存優(yōu)良解，將后代個(gè)體與種群當(dāng)前個(gè)體的目標(biāo)函數(shù)值進(jìn)行比較，如果后代個(gè)體的適應(yīng)值優(yōu)于當(dāng)前個(gè)體，則利用后代個(gè)體更新種群中的當(dāng)前個(gè)體。

3.5 外部存檔

為了保存種群進(jìn)化中搜索到的歷史最好信息，將進(jìn)化過(guò)程中生成的N個(gè)最好個(gè)體保存在外部存檔中，用于種群進(jìn)化的交叉操作。當(dāng)新生成的后代個(gè)體更新種群的當(dāng)前個(gè)體時(shí)，則將新個(gè)體與外部存檔中所有個(gè)體進(jìn)行比較，如果新個(gè)體比外部存檔中的任意一個(gè)個(gè)體適應(yīng)值好，則利用新個(gè)體替代原來(lái)個(gè)體。

4 實(shí)驗(yàn)

為了驗(yàn)證提出算法SEGA及策略的有效性，選取TSPLIB標(biāo)準(zhǔn)庫(kù)中的Eil51、Berlin52、St70、Eil76、Pr107、Pr136六個(gè)實(shí)例進(jìn)行實(shí)驗(yàn)。算法開(kāi)發(fā)環(huán)境為Windows 8，使用Visual Studio2015進(jìn)行開(kāi)發(fā)，使用C++語(yǔ)言編寫(xiě)。算法的種群規(guī)模NP設(shè)置為100，自適應(yīng)變異系數(shù)設(shè)置為0.2，外部存檔最大容量N為10，算法的最大進(jìn)化代數(shù)設(shè)置為10，000。對(duì)每個(gè)實(shí)例分別運(yùn)行10次，得到的優(yōu)化結(jié)果作為性能評(píng)價(jià)指標(biāo)。本文將提出的算法SEGA與經(jīng)典的遺傳算法GA及不使用自適應(yīng)策略的EGA和不使用外部存策略的算法SGA的優(yōu)化結(jié)果進(jìn)行比較，比較的結(jié)果如表1所示。

通過(guò)比較發(fā)現(xiàn)提出算法SEGA得到的結(jié)果均優(yōu)于其他三種算法，說(shuō)明算法提出策略是有效的。EGA算法不使用自適應(yīng)變異率策略對(duì)旅行商問(wèn)題進(jìn)行求解，算法得到的結(jié)果6個(gè)實(shí)例中有5個(gè)實(shí)例比使用自適應(yīng)策略的SGA算法的更差，二所有實(shí)例得到的結(jié)果均差于SEGA算法得到的結(jié)果，說(shuō)明自適應(yīng)的變異策略在平衡算法的全局探索能力和局部開(kāi)采能力方面性能更好。SGA算法不使用外部存檔策略，而外部存檔策略能夠?yàn)榉N群進(jìn)化過(guò)程中提供更好的父代個(gè)體，幫助算法提高收斂性。從算法得到的優(yōu)化結(jié)果來(lái)看，使用外部存檔策略對(duì)于提高算法的收斂性是有效的。

5 結(jié)束語(yǔ)

本文提出了一種基于外部存檔的自適應(yīng)遺傳算法，以對(duì)稱(chēng)性旅行商問(wèn)題作為研究對(duì)象進(jìn)行研究。通過(guò)對(duì)TSPLIB標(biāo)準(zhǔn)庫(kù)中6個(gè)實(shí)例測(cè)試實(shí)驗(yàn)解結(jié)果對(duì)比分析，將提出算法與經(jīng)典遺傳算法及去掉自適應(yīng)變異率策略、外部存檔策略的算法進(jìn)行比較，說(shuō)明自適應(yīng)變異策略在平衡算法局部能力和全局能力方面具有優(yōu)越性，也證明了外部存檔策略在提高算法收斂性方面的有效性。

參考文獻(xiàn)（References）：

[1] PADBERG M W，RINALDI G. Optimization of a 532-citysymmetric genetic traveling salesman problems by branch and cut[J].Operation Research Letters，1987.6（1）：1-7

[2] GAREY M R， JOHNSON D S. Computers andIntractability：A Guide to the Theory of NP-Completeness[M]. New York： W. H. Freeman and Company，1979：56-59

[3] Kopanos G M， Puigjaner L， Georgiadis M C.Simultaneousproduction and logistics operations planning in semicontinuous food industries[J].Omega-International Journal of Management Science，2012.40（5）：634-650

[4] 潘穎，解曉宇，薛冬娟，謝忠東.全自適應(yīng)遺傳算法求解柔性作業(yè)車(chē)間調(diào)度問(wèn)題[J].牡丹江大學(xué)學(xué)報(bào)，2014.23（3）：151-153

[5] 高立兵，蘇軍德.基于量子蟻群進(jìn)化算法的大規(guī)模無(wú)線(xiàn)傳感器網(wǎng)絡(luò)目標(biāo)覆蓋研究[J].自動(dòng)化應(yīng)用，2018.10：53-56

[6] Lee W P，Hsiao Y T.Inferring gene regulatory networks?using a hybrid GA-PSO approach with numerical constraints and network decomposition[J].Information Sciences，2012.188：80-99

[7] 王迎，張立毅，費(fèi)騰等.求解TSP的帶混沌擾動(dòng)的模擬退火蟻群算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2016.37（4）： 1067-1070

[8] 王忠英，白艷萍，岳利霞.經(jīng)過(guò)改進(jìn)的求解TSP問(wèn)題的蟻群算法[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012.42（4）：133-140

[9] Grymin R，Jagiello S.Fast branch and bound algorithm for?the travelling salesman problem[C]//Computer Information Systems and Industrial Management，2016：206-217

[10] 劉荷花，崔超，陳晶.一種改進(jìn)的遺傳算法求解旅行商問(wèn)題[J].北京理工大學(xué)學(xué)報(bào)，2013.33（4）：390-393