改进遗传算法解决TSP问题

陈林 潘大志

摘要：针对基本遗传算法收敛速度慢，易早熟等问题，提出一种改进的遗传算法。新算法利用贪婪思想产生初始种群来加快寻优速度，用贪婪思想来引导交叉操作，在交叉操作之前，把当前较差的一半种群替换成随机种群，最后用改进的变异算子和进化逆转操作进行寻优，利用新的遗传算法求解基本的旅行商问题。仿真结果表明，改进的遗传算法具有全局搜索能力强、收敛速度快的特点，优化质量和寻优效率都较好。

关键词：遗传算法；贪婪思想；进化逆转；旅行商问题

中图分类号： TP18 文献标识码： A

0引言

遗传算法（GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。最早是由美国密歇根大学Holland教授提出，在20世纪80年代左右得到了进一步发展。遗传算法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。目前遗传算法主要多用于优化问题[1]、图像处理[2]、通讯工程[3]等领域。

旅行商问题（TSP）是典型的组合优化问题，求解TSP问题传统的算法有：穷举法、分支限界法、动态规划法[4-5]等。高海昌等[6] 对蚁群算法、遗传算法、模拟退火算法、禁忌搜索、神经网络、粒子群优化算法、免疫算法等进行了论述。随着研究的深入，许多改进的算法不断涌现，李玮[7]采用矩阵编码、交叉、变异的遗传算法来解决TSP问题，雷玉梅[8]提出了一种分而治之的遗传算法思想，姚明海[9]采用遗传算法与其他智能算法结合的思想来解决问题。遗传算法因其高效的搜索能力成为了解决TSP问题的有效方法之一。虽然遗传算法能够较为成功地求解TSP问题，但也存在搜索较慢的问题，特别是遗传算法在解决TSP问题时容易出现早熟的问题。因此本文在交叉操作之前，将一半的当前种群替换成随机种群来防止早熟，再融合贪婪思想产生的初始群体[10]和贪婪思想引导的交叉算子[11]来加快收敛速度，用改进的变异算子[12]进行操作，由此而得到最优解。

5 结束语

文章在基本的遗传算法基础上提出一定改进，引用贪婪思想产生质量相对较好的初始种群，同时又在贪婪思想引导的交叉操作操作之前，把当前较差的一半种群替换成随机种群，二者结合来提升收敛速度又防止了陷入局部最优。实验证明，本文研发的改进遗传算法较好地解决了TSP问题中收敛速度和早熟的问题，且具有较强的鲁棒性，通用于类似的组合优化问题。

参考文献：

[1]袁满，刘耀林.基于多智能体遗传算法的土地利用优化配置[J].农业工程学报， 2014，30（1）： 191-199.

[2]门慧勇.基于遗传算法的图像分割优化研究[D].长春：东北师范大学，2012.

[3]陈侠.基于改进的遗传算法的网络编码优化方法研究[D].武汉：华中科技大学，2012.

[4]周康，强小利，同小军，等.求解TSP算法[J].计算机工程与应用，2007，43（29）：43-47，85.

[5]赵颂华.城市公共资源监管设计新思维[J].科技资讯，2015（15）：31-32.

[6]高海昌，冯博琴，朱利.智能优化算法求解TSP问题[J].控制与决策，2006，21（3）：241-247，252.

[7]李玮.关于旅行商问题的改进遗传算法[D].重庆：重庆大学，2004.

[8]雷玉梅.基于改进遗传算法的大规模TSP问题求解方案[J].计算机与现代化，2015（2）：34-39.

[9]姚明海，王娜，赵连朋.改进的模拟退火和遗传算法求解TSP问题[J].计算机工程与应用，2013， 49（14）：60-65.

[10]于莹莹，陈燕，李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策，2014，29（8）： 1483-1488.

[11]谢胜利，唐敏，董金祥.求解TSP问题的一种改进的遗传算法[J].计算机工程与应用，2002， 38（8）： 58-60，245.

[12]黄立君，许永花.遗传算法和蚁群算法融合求解TSP[J].东北农业大学学报，2008，39（4）： 109-113.

[13]郁磊，史峰.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社，2015： 38-39.