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

譚立狀+贠國瀟+張家華

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

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

3 實驗測試

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

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

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

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

4 總結(jié)

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

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

【參考文獻】

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

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

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

[4]劉朝華，張英杰，章兢，等.蟻群算法與免疫算法的融合及其在TSP 中的應(yīng)用[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]譚艷艷. 基于分解的多目標進化算法研究及應(yīng)用[D].西安電子科技大學(xué)，西安，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]李宏.求解幾類復(fù)雜優(yōu)化問題的進化算法及其應(yīng)用[D].西安電子科技大學(xué)，西安，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].自動化技術(shù)與應(yīng)用， 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.

[責(zé)任編輯：楊玉潔]