采用基于遗传算法的文化基因算法求解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.

[责任编辑：杨玉洁]