求旅行商_TSP_问题的几种改进遗传算法的比较分析

求旅行商_TSP_问题的几种改进遗传算法的比较分析

求旅行商（ＴＳＰ）问题的几种改进遗传算法的比较分析

张

求旅行商_TSP_问题的几种改进遗传算法的比较分析

科技广场２００７．１

２６

求旅行商_TSP_问题的几种改进遗传算法的比较分析

行分类，接着找出矩阵中属于同一类的元素，将其所对应的城市的排列构成一个新的矩阵后进行模糊识别，最后找到相似解。

１．３遗传算法与贪婪算法结合求解ＴＳＰ问题常规的遗传算法在求解ＴＳＰ问题时，收敛速度过慢，并且随着搜索的进程，群体多样性水平越来越低，容易陷入局部最优解。而将贪婪算法与遗传算法相结合以后，能较好地解决这样的问题。

１．３．１遗传算法与贪婪算法结合的基本思想本文介绍的结合贪婪算法的改进遗传算法，主要是针对传统遗传算法的杂交和变异方式进行了改进，增强了其快速收敛的能力，以实现全局最优。

１．３．２遗传算法与贪婪算法结合的改进之处结合了贪婪算法的改进遗传算法，在操作步骤上与常规遗传算法相似，这里就不再赘述，只是针对杂交和变异方式的改进之处做一下介绍。

在传统的遗传算法中，通常采用次序杂交原则，即为了能充分保留优良亲体中的次序［６］，更看重城市的次序，而非位置，这种算法的效率不高。改进后的杂交方式为，随机选择一个顶点，先比较两组父代Ａ和Ｂ某一边的长度，如果Ａ　的短于Ｂ的，就选择Ａ的一边，然后选择它的下一个顶点继续比较选择。同样，另一边也采取同样的方式进行操作，产生子代，这样就能够充分发挥出遗传算法的快速收敛优势。

在利用常规的遗传算法求解ＴＳＰ问题时，常用的变异操作有交换变异、到位变异、插入变异等多种方式。通常，在求解ＴＳＰ问题时，要充分考虑边的邻接关系，即要很好地保留原有边的邻接关系［７］，只有倒位变异算子具有这样的特点，能够将巡回路线上的良好性能很好地遗传到下一代的种群中。因此，这里介绍一种贪婪倒位变异算子。首先，随机地选择一个城市，然后在该种群中再选择一个除了位于它左右两边外距离它最近的城市，作为第２点，与位于初选城市右边的城市进行倒位。例如有一个父本个体Ｐ（　１　２　３　４　５　６），若随机选择一个城市２，离城市２最近的城市有４和６，若选城市４作为第２点，　则倒位后产生新个体（　１　２　４　３　５　６），　若选城市６作为第２点，　则倒位后产生新个体（　１　２　６　４　５３）。２结束语

本文所介绍的三种改进遗传算法，都能够在提

高收敛速度，节约运算时间上得到很好的结果。随着进化代数的增加，模拟退火遗传算法必然能够更好地改善时间性能。通过周期性的引入知识库中的相似解，能够很好地维持群体的多样性，以实现全局最优。

ＴＳＰ问题属于ＮＰ难的，随着问题规模和复杂度的增加，单一的算法已经不能得到让人满意的解，混合优化策略方法必然成为研究趋势。但就目前的研究状况来看，各种算法结合的方式虽然比较多，但还没有哪一种能够完美地解决ＴＳＰ问题，因此混合优化策略方法是亟待发展的一个方向。参考文献

［１］李敏强，寇纪淞，等．遗传算法的基本理论与应用［Ｍ］．北京：科学出版社，２００２．

［２］阎庆，鲍远律．新型遗传模拟退火算法求解物流配送路径问题［Ｊ］．　计算机应用，２００４，２４（Ｓ１）：２６１－２６３．

［３］Ｄ　Ｂ　ｅａｋｅ．Ｃａｓｅ－Ｂａｓｅｄ　Ｒｅａｓｏｎｉｎｇ：Ｅｘｐｅｒｉｅｎｃｅｓ，Ｌｅｓｓｏｎｓ，ａｎｄ　Ｆｕｔｕｒｅ　Ｄｉｒｅｃｔｉｏｎｓ［Ｊ］．Ｍｅｎｌｏ　Ｐａｒｋ，ＣＡ：ＡＡＡＩ／ＭＩＴ　ｐｒｅｓｓ，１９９６．

［４］Ａ　Ｇｏｅｌ　ａｎｄ　Ｂ　Ｃｈａｎｄｒｅｓｅｋａｒａｎ．　Ｃａｓｅ－Ｂａｓｅｄｄｅｓｉｇｎ：Ａ　ｔａｓｋ　Ａｎａｌｙｓｉｓ．ｉｎ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎ　Ｅｎｇｉ－ｎｅｅｒｉｎｇ　Ｄｅｓｉｇｎ［Ｊ］．Ａｃａｄｅｍｉｃ　ｐｒｅｓｓ，Ｉｎｃ，１９９２　ＶｏｌⅡ：１６５－１８４．

［５］韦雪洁，黎明，刘高杭，田贵超．基于知识库求解ＴＳＰ问题的改进遗传算法［Ｊ］．计算机仿真，２００６，０８：１６１－１６３．

［６］谢季坚，刘坚平．模糊数学方法及其应用［Ｍ］．武汉：华中科技大学出版社，２０００．

［７］许丽佳，蒲海波，蒋宏健．改进遗传算法的路径规划研究［Ｊ］．　微计算机信息，２００６，２２：２５１－２５３．

［８］彭丹萍，林志毅，王江晴．求解ＴＳＰ的一种改进遗传算法［Ｊ］．计算机工程与应用，２００６，１３：９１－９３．作者简介

张