运用遗传算法求解TSP问题的探讨

1、第 24卷 第 5期 天 中 学 刊 V ol. 24 No. 5 2009年 10月 Journal of Tianzhong Oct. 2009收稿日期:2009-02-25作者简介:刘会超(1982 ,男,河南驻马店人,黄淮学院计算机科学系助教,武汉大学软件工程国家重点实验室硕士研究生.运用遗传算法求解 TSP 问题的探讨刘会超 1, 2,刘 珂 2(1. 武汉大学,湖北 武汉 430072; 2. 黄淮学院,河南 驻马店 463000摘 要:通过对遗传编码方案的改进,克服了 TSP 问题中的数据冗余缺陷,使得搜索性能得到提高.将该遗传 算法应用于实际 TSP 问题,计算结果证明了该遗传

2、算法的有效性. 关键词:TSP ;遗传算法;杂交;变异 1 TSP 问题及其应用TSP 问题是组合优化中典型的 NP-C 问题. TSP问题可以描述为:某商人要到给定 n 个城市推销货物, 从某城市出发遍历其余各城市一次且仅一次,最后再 回到起点,求其最短的行程,即寻找一条巡回路径 12( n P p p p =L , , , , 使得1111( min( ( n i i n i f P d p p d p p +=+, , , (1其中 p i 为城市号, d (p i , p j 表示城市 i 与城市 j 之间的 连接代价.对于对称式 TSP ,有 d (p i , p j = d (p

3、j , p i ; 对于非对称式 TSP , d (p i , p j d (p j , p i . 本文仅讨论对 称式 TSP .TSP 问题涉及网络通讯、车辆调度、管道铺设、电路布线等优化问题,因此快速、有效地解决 TSP 问 题有着极高的实际应用价值.迄今为止,人们为求解 TSP 问题提出了大量的搜索算法,如穷举搜索法、贪婪法、插入算法、 r-opt 算法、神经网络算法、模拟退 火算法、动态规划法、分支定界法、遗传算法及蚁群 算法等 1.2 运用遗传算法求解 TSP 问题遗传算法(Genetic Algorithm,简称 GA 的基本 思想是基于 Darwin 进化论的 Mendel 的

4、遗传学说,它 将问题的解集看作一个种群, 通过不断的选择、 交叉、 变异等遗传操作,使解的质量越来越好.遗传算法最遗传编码方法有多种, 本文采用路径表示法, 即:n 个城市的个体表示为 12( n p p p L , , , , 其中 p 1p n 互不相等;路径 (5 9 1 4 7 2 3 8 6 10 可以直 接表示为 (59147238610 .实际上,由于路径实际表达的是一个首尾相连的 回路,所以存在冗余路径.例如,路径 (5 9 1 4 7 2 3 8 6 10 可以写成 (10 5 9 1 4 7 2 3 8 6 ,也可以写成 (8 6 10 5 9 1 4 7 2 3 等. 也

5、就是说, n 个城市间的任意一条路径就对应有另外 n 1条冗余路径.在本文中,消除冗余路径的做法是:把所有个体 编码的首位 p 1强制设为1号城市,这样,参与演化操 作的所有个体所表达的路径都是以城市1为首位的, 其他 n 1条等价路径就不会出现.去除冗余, 有助于 缩小搜索范围,缩短搜索时间,提高搜索效率,最终 获得更优的解. 2.2 选择机制求解 TSP 问题, 常用的选择机制有轮盘赌选择机 制、最佳个体选择机制、期望值模型机制、联赛选择 机制等 3,本文中采用轮盘赌选择机制.轮盘赌选择 机制先定义种群中个体适应度函数中图分类号:TP18文献标识码:B文章编号:1006-5261(2009

6、 05-0036-02刘会超,刘 珂:运用遗传算法求解 TSP 问题的探讨·37·( i i g f P =, (2再计算个体的相对适应值1( mi i ii i h P g f =, (3最后,根据 ( i i h p 把一个圆盘分成 n 份,每份扇形的中心角为 2i g . 在 (2式和 (3式中, P i 表示某条合法的 路径, ( i f P 表示路径的长度, 12i m =L , , .在进行 选择时,可以假想转动一下圆盘,若某参照点落入第i 个扇形内, 则选择个体 i . 这样, 小扇区的面积越大, 被选中的概率也越大,即个体适应值越大它被选择到 的机会也越多,

7、其基因结构被遗传到下一代的可能性 也越大.运用此选择方式随机生成 m 个体(个体数一 般为 20200 ,最终形成演化种群. 2.3 杂交算子的设计杂交算子是模拟生物进化中染色体的交换组合来 产生新的优良品种,进而搜索到空间中新的点 4.杂 交一般是以概率 0.600.98c q 进行的.关于路径表 示的杂交算子主要有部分匹配杂交(Partially Matched Crossover ,简称 PMX 、顺序杂交(Order Crossover,简称 OX 、 循环杂交 (Cycle Crossover, 简称 CX 等, 本文采用的是 PMX .在 PMX 操作中,首先随机地在父体中选取两个

8、 杂交点,定义这两点之间的区域为匹配区域,一并交 换相应的匹配区域;然后根据匹配区域内的城市确定 部分映射关系;接着在父体上先填入无冲突的城市, 以保证在路径中每个城市被且仅被访问一次;再对有 冲突的城市分别执行这些部分映射,直到填入无冲突 时,则获得杂交后的两后代.例如, 对下面的两父体, 随机选择两个杂交点 (“ |” 表示杂交点1(182 | 4357 | 6109 p =, 2(174 | 6893 | 2510 p =,交换两个杂交点之间的匹配区域,得到1(1* | 6893 |*q =, 2(1* | 4357 |*q =,其中 “ *” 为待定城市号. 由匹配区域确定的部分映射

9、为:4 6, 3 8, 5 9, 7 3.然后,从各自的父体 中填入无冲突的城市,得到1(1*2 | 6893 | *10*q =, 2(1* | 4357 | 2*10 q =.个体 1q 中的第一个 *处原为 8,由映射关系 3 8映射 到 3仍冲突,再由 7 3映射到 7无冲突, 则把 7填入. 类似地进行操作,最终得到的两个子个体为1(172 | 6893 | 4105 q =,2(186 | 4357 | 2910 q =. 2.4 变异算子的设计从遗传算法的观点来看,解的进化主要靠选择机制和杂交算子来完成,变异只是为选择、杂交过程中可能丢失的某些遗传基因进行修复和补充 5.变异一

10、般是以概率 0.050.20m q 进行的.3 实验与结论, , 在相同的演化代数下,传 统方法所求得的较优值 ( 373.660km f P =,较优路径 为 32109871465P =, , , 而用本文去除冗余的 方法所求得的较优值 ( 355.461km f P =,较优路径为表 1 各城市之间的距离 km3484.118471049.524实验结果表明,采用该演化算法能够降低种群生 成时的冗余度, 保持种群的多样性, 提高求解的效率, 而且还能有效地避免“早熟”现象,因而此算法是有 效算法.参考文献:1 王宇平,李英华.求解 TSP 的量子遗传算法 J.计算机学报, 2007, (5:748755.2 黄雪梅,李涛,徐春林,等.一种基于免疫遗传的 TSP 求解方法 J.四川大学学报 (工程科学版 , 20