采用基于遺傳算法的文化基因算法求解TSP問題

譚立狀+贠國瀟+張家華

【摘 要】為更好地求解旅行商問題，本文提出了一種基于遺傳算法的文化基因算法。將2-opt作為局部搜索算子，融入到遺傳算法中，以加快遺傳算法的收斂速度和提高解的局部搜索能力。遺傳算法具有全局搜索的能力，2-opt具有局部搜索的特點，嵌入2-opt局部搜索的遺傳算法力圖在全局和局部搜索中達到平衡和融合，使之更有效地解決TSP問題。為檢測算法的性能，將該算法用于解決標準的TSP測試問題，并將測試結果與標準的遺傳算法及蟻群、粒子群等其它一些優秀的算法的實驗結果做了比較，數值實驗結果證明了算法的有效性。

【關鍵詞】遺傳算法；2-opt；文化基因算法；TSP問題

3 實驗測試

為了測試基于遺傳算法的文化基因算法在解決TSP問題方面的表現，本文從TSP標準問題測試庫中提取了10個測試問題，將本文提出的算法用于求解這10個問題，并將算法的執行結果與當前其它一些優秀的智能算法的運行結果進行了比較。

在測試過程中，算法采用輪盤賭選擇和精英個體保留機制，單點順序交叉，基本位變異，終止代數為500，群體大小為200，交叉概率為0.9，變異概率為0.09。在Matlab環境下，算法對每個測試問題獨立進行10次。在相同的終止迭代條件下，表1給出了幾種算法所求得的最短路徑的平均值。以eil51、bier127、rat195、kroB200為例，圖5形象展示了算法在這些測試問題上獨立運行10次的結果。

圖5 算法在4個測試問題上的求解結果

從表1和圖5可以看出，相較于遺傳算法，本文提出的基于遺傳算法的文化基因算法所求得的路徑更短，可見融入2-opt局部搜索技術對于提高算法的性能是非常有效的。與當前其它一些優秀的算法，包括模擬退火、粒子群算法、蟻群算法相比，在這些測試問題上，基于遺傳算法的文化基因算法均表現了較好的性能，所求得的結果都優于其它算法。如圖5所示，與其它算法相比，本文提出的算法還具有較好的穩定性，魯棒性較強，對問題的敏感性較弱，比較適合解決此類TSP問題。

4 總結

遺傳算法在求解TSP問題時往往存在著求解質量不是很高、容易陷入局部最優等一系列問題。為了克服這些缺陷，本文提出了一種基于遺傳算法的文化基因算法。算法在求解過程中，將2-opt作為局部搜索算子，嵌入到遺傳算法中，以加快遺傳算法的收斂速度和提高局部搜索能力。遺傳算法具有全局搜索的能力，2-opt具有局部搜索的特點，嵌入2-opt局部搜索的遺傳算法力圖在全局和局部搜索中達到平衡和融合，使之更有效地解決TSP問題。

為檢測算法的性能，將該算法在10個標準TSP測試問題上進行了測試，并將測試結果與標準的遺傳算法及蟻群、粒子群等其它一些優秀的算法的實驗結果進行了對比，數值實驗結果表明，本文提出的算法在求解的質量、穩定性上均表現了較好的性能，算法的整體表現要優于其它算法。可見融入局部搜索技術的全局搜索算法對于解決TSP問題是一條有效的途徑。探索其它更高效的局部搜索算法，將這些局部搜索技術有效地融合到遺傳算法、蟻群算法中，以更好地解決TSP問題將是作者今后進一步的研究工作。

【參考文獻】

[1]于瑩瑩，陳燕，李桃迎.改進的遺傳算法求解旅行商問題[J].控制與決策，2014， 29（8）：1483-1488.

[2]高海昌，馮博琴，朱利.智能優化算法求解TSP 問題[J].控制與決策，2006，21（3）： 241-247.

[3]冀俊忠，黃振，劉椿年.一種快速求解旅行商問題的蟻群算法[J].計算機研究與發展，2009，46（6）：968-978.

[4]劉朝華，張英杰，章兢，等.蟻群算法與免疫算法的融合及其在TSP 中的應用[J].控制與決策，2010，25（5）：695-700.

[5]Yannis Marinakis， Magdalene Marinaki. A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem[J]. Computers and Operations Research， 2010， 37（3）： 432-442.

[6]Darrell Whitley， Doug Hains， Adele Howe. A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover[C]// Proc. of the 11th Int Conf. on Parallel Problem Solving from Nature. Berlin：Springer Heidelberg， 2010， 6283： 566-575.

[7]Zakir H Ahmed. Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator[J]. Int J of Biometrics and Bioinformatics， 2010， 3（6）： 96-105.

[8]Murat Albayrak， Novruz Allahverdi. Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J]. Expert Systems with Applications， 2011， 38（3）： 1313-1320.

[9]譚艷艷. 基于分解的多目標進化算法研究及應用[D].西安電子科技大學，西安，2013.

[10]N. Noman， H. Iba. Accelerating differential evolution using an adaptive local search[J]. IEEE Trans. on Evol. Comput.， 2008， 12（1）： 107-125.

[11]Yan-Yan Tan， Yong-Chang Jiao， Hong Li and Xin-kuan Wang. MOEA/D-SQA： a multi-objective memetic algorithm based on decomposition[J]. Engineering Optimization， 2012， 44（9）： 1095-1115.

[12]李宏.求解幾類復雜優化問題的進化算法及其應用[D].西安電子科技大學，西安，2009.

[13]P. Moscato. On evolution， search， optimization， genetic algorithms and martial arts： Towards memetic algorithms[J]. Caltech Concurrent Computation Program， C3P Report， 826， 1989.

[14]劉漫丹.文化基因算法（Memetic Algorithm）研究進展[J].自動化技術與應用， 2007，26（11）：1-4.

[15]Krasnogor N， Smith J. A tutorial for competent memetic algorithms： model， taxonomy， and design issues[J]. IEEE Transactions on Evolutionary Computation， 2005， 9（5）： 474-488.

[責任編輯：楊玉潔]