一種求解旅行商問題的基于外部存檔的自適應遺傳算法

劉景鑫 李林林 李治華 張耘赫

摘? 要： 旅行商問題是一類經典的組合最優化問題，在理論研究和實際應用領域具有重要的研究價值。本文提出了一種自適應遺傳算法，通過變異率的自適應策略平衡算法的全局性和局部性，同時利用外部存檔策略為種群進化提供具有全局指導信息的父代個體，提高了算法的收斂速度。通過對TSPLIB標準庫中實例的測試，驗證了算法的可行性和有效性。

關鍵詞： 旅行商問題; 遺傳算法; 自適應; 外部存檔

中圖分類號：TP301.6? ? ? ? ? 文獻標志碼：A? ? ?文章編號：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 引言

旅行商問題是一類復雜的組合優化問題[1]，在理論計算機科學和運籌學研究中非常重要。問題易于描述但難以求解，是典型的NP難問題[2]。旅行商問題的目標通常是最小化總行程，而且所有節點都必須訪問一次。旅行商問題可以被應用與各個領域，如電路板設計、無線傳感器網絡、交通網絡、物流配送等領域[3-5]。求解旅行商問題的算法包括遺傳算法、爬山算法、模擬退火算法、蟻群算法、禁忌搜索算法、粒子群算法等[7-10]。

1 遺傳算法

遺傳算法是一類最經典的基于種群的隨機優化算法，它模仿達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程。算法通過種群中個體的并行繁殖和選擇，保留優良個體，得到新的下一代種群，通過這種優勝劣汰的自然選擇不斷的保留優秀個體，進而最終得到問題的最優解。遺傳算法非常適合與求解排列組合問題。遺傳算法的基本流程如下：

步驟1 初始化種群;

步驟2 評價種群中個體的適應值;

步驟3 對種群中的當前個體，利用進化操作生成新個體：

步驟3.1 從當前種群中隨機選擇2個個體;

步驟3.2 對2個個體利用交叉操作生成實驗個體;

步驟3.3 對實驗個體利用變異操作生成后代個體;

步驟4 重復步驟3直到終止條件滿足。

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

2 TSP旅行商問題

旅行商問題是所有城市節點搜索最短的漢密爾頓回路。描述方式如下：有N個城市，城市之間的距離用矩陣D=（dij）N×N表示，dij表示從城市i到城市j之間的距離，問題的目標是從所有路徑中找到最短路徑，如公式⑴，這是一種遞歸方式的表達，其中πi表示路徑經過的第i個城市。一般TSP問題可以按照距離矩陣分為兩類：對稱性TSP問題和非對稱性TSP問題。本文主要對常見的對稱性TSP問題進行求解。

⑴

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

3 基于外部存檔的自適應遺傳算法

3.1 個體編碼

本文以城市序號為基因，對城市序號進行編碼。由于旅行商問題要求最后回到出發城市，因此只需要對從出發城市到途徑城市的序號進行編碼即可。例如個體為{2，3，4，5，1}表示旅行商的線路為從2號城市出發，依次途徑3號城市、4號城市、5號城市、1號城市，最后從1號城市返回2號城市。

3.2 交叉操作

交叉算子是通過對父代個體的基因重組得到實驗個體的過程。這里對LOX算子進行了改進，一般LOX算子父代個體的選擇是來自當前種群中的隨機個體，考慮到外部存檔中的個體具有更高的質量，因此從外部存檔中隨機選擇一個個體作為父代個體，另一個個體選擇種群中的當前個體，在利用LOX操作的方式得到新個體。交叉算子如圖1所示。通過這種方式，能夠使優良基因信息在交叉過程中得到保留，使個體進化具有方向性，進而提高種群進化效率。

3.3 自適應變異率策略

變異操作是對生成個體的一個或幾個基因位進行變化，防止個體的基因信息趨于相似而造成種群進化停滯現象。變異率的大小決定變異操作的機會的大小，變異率過大，會導致算法更加具有隨機性，影響算法的收斂速度;變異率過小，會導致種群多樣性變化太小，而出現早衰或陷入局部最優等問題。因此，為算法設置合適的變異率能夠更好的平衡算法的全局探索能力和局部開采能力。

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

3.4 選擇操作

為了保存優良解，將后代個體與種群當前個體的目標函數值進行比較，如果后代個體的適應值優于當前個體，則利用后代個體更新種群中的當前個體。

3.5 外部存檔

為了保存種群進化中搜索到的歷史最好信息，將進化過程中生成的N個最好個體保存在外部存檔中，用于種群進化的交叉操作。當新生成的后代個體更新種群的當前個體時，則將新個體與外部存檔中所有個體進行比較，如果新個體比外部存檔中的任意一個個體適應值好，則利用新個體替代原來個體。

4 實驗

為了驗證提出算法SEGA及策略的有效性，選取TSPLIB標準庫中的Eil51、Berlin52、St70、Eil76、Pr107、Pr136六個實例進行實驗。算法開發環境為Windows 8，使用Visual Studio2015進行開發，使用C++語言編寫。算法的種群規模NP設置為100，自適應變異系數設置為0.2，外部存檔最大容量N為10，算法的最大進化代數設置為10，000。對每個實例分別運行10次，得到的優化結果作為性能評價指標。本文將提出的算法SEGA與經典的遺傳算法GA及不使用自適應策略的EGA和不使用外部存策略的算法SGA的優化結果進行比較，比較的結果如表1所示。

通過比較發現提出算法SEGA得到的結果均優于其他三種算法，說明算法提出策略是有效的。EGA算法不使用自適應變異率策略對旅行商問題進行求解，算法得到的結果6個實例中有5個實例比使用自適應策略的SGA算法的更差，二所有實例得到的結果均差于SEGA算法得到的結果，說明自適應的變異策略在平衡算法的全局探索能力和局部開采能力方面性能更好。SGA算法不使用外部存檔策略，而外部存檔策略能夠為種群進化過程中提供更好的父代個體，幫助算法提高收斂性。從算法得到的優化結果來看，使用外部存檔策略對于提高算法的收斂性是有效的。

5 結束語

本文提出了一種基于外部存檔的自適應遺傳算法，以對稱性旅行商問題作為研究對象進行研究。通過對TSPLIB標準庫中6個實例測試實驗解結果對比分析，將提出算法與經典遺傳算法及去掉自適應變異率策略、外部存檔策略的算法進行比較，說明自適應變異策略在平衡算法局部能力和全局能力方面具有優越性，也證明了外部存檔策略在提高算法收斂性方面的有效性。

參考文獻（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] 潘穎，解曉宇，薛冬娟，謝忠東.全自適應遺傳算法求解柔性作業車間調度問題[J].牡丹江大學學報，2014.23（3）：151-153

[5] 高立兵，蘇軍德.基于量子蟻群進化算法的大規模無線傳感器網絡目標覆蓋研究[J].自動化應用，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] 王迎，張立毅，費騰等.求解TSP的帶混沌擾動的模擬退火蟻群算法[J].計算機工程與設計，2016.37（4）： 1067-1070

[8] 王忠英，白艷萍，岳利霞.經過改進的求解TSP問題的蟻群算法[J].數學的實踐與認識，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].北京理工大學學報，2013.33（4）：390-393