总第１５卷１６６期 ２０１３年６月 大众科技 Ｐｏｐｕｌａｒ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ Ｖ０１．１５ Ｎｏ．６ Ｊｕｎｅ ２０１３ 混合遗传算法解决单目标旅行商问题的研究 袁成林 （１．广西大学计算机与电子信息学院，广西南宁５３０００４； ２．广西医科大学基础医学院，广西南宁５３００２１） 【摘要】对混合遗传算法解决单目标旅行商问题进行研究，提出了一种基于对应连通子图交叉的混合遗传算法。本算法 还包括初始种群的生成、适应度函数的计算、选择、变异、ＬＫ局部搜索和小生境操作。最后通过具体算例的实验和对比表明算 法是有效的。在计算精度和速度上有较大提高。 【关键词】混合遗传算法；旅行商问题；对应连通子图交叉 【中图分类号】ＴＰ３０９ 【文献标识码】Ａ 【文章编号】１００８—１１５１（２０１３）０６．０００４—０３ Ｒｅｓｅａｒｃｈ ｏｆ Ｈｙｂｒｉｄ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ｔｏ Ｓｏｌｖｅ ｔｈｅ Ｓｉｎｇｌｅ ０ｂｊ ｅｃｔｉｖｅ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ Ａｂｓｒａｃｔ：Ｈｙｂｒｉｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ＳＯｌＶｅ ｔｈｅ ｓｉｎｇｌｅ—ｏｂｊｅｃｔｉｖｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ，ｈｙｂｒｉｄ ｇｅｎｅｔｉｃ ｌａｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ ｂａｓｅｄ ｏｎ ｌｏｏｋｉｎｇ ｆｏｒ ｔｈｅ Ｃｏｒｒｅｓｐｏｎｄｉｎｇ Ｃｏｎｎｅｃｔｅｄ Ｓｕｂｇｒａｐｈ Ｃｒｏｓｓｏｖｅｒ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｌｓｏ ｉｎｃｌｕｄｅｓ ｔｈｅ ｇｅｎｅｒａｔｉｏｎ ｏｆ ｔｈｅ ｉｎｉｔｉａｌ ｐｏｐｕｌａｔｉｏｎ ｔｏ ａｄａｐｔ ｔｏ ｔｈｅ ｃａｌｃｕｌａｔｉｏｎ ｏｆ ｔｈｅ ｆｕｎｃｔｉｏｎ，ｓｅｌｅｃｔｉｏｎ，ｍｕｔａｔｉｏｎ，ＬＫ ｌｏｃａｌ ｓｅａｒｃｈ ａｎｄ ｎｉｃｈｅ ｏｐｅｒａｔｉｏｎ．Ｆｉｎａｌｌｙ，ｅｘｐｅｒｉｍｅｎｔａｌ ａｎｄ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｓｐｅｃｉｉｆｃ ｎｕｍｅｒｉｃａｌ ｅｘａｍｐｌｅｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｅｆｆｅｃｔｉｖｅ ａｎｄ ｈａｓ ｉｍｐｒｏｖｅｄ ｇｒｅａｔｌｙ ｉｎ ａｃｃｕｒａｃｙ ａｎｄ ｓｐｅｅｄ． Ｋｅｙ ｗｏｒｄｓ：ｈｙｂｒｉｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ；ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｃｏｎｎｅｃｔｅｄ ｓｕｂｇｒａｐｈ ｃｒｏｓｓｏｖｅｒ 遗传算法是一种基于进化策略的优化算法“ ，被广泛使 用在组合优化问题中。但是遗传算法在解决问题的时候也有 诸多不足，首先是在早期的搜索中常常丢失种群的多样性 。 方向进化。对于旅行商问题通常采取自然编码，即每个基因 位对应一个城市的号码。例如卜２—３—４－５—６表示依次经过城 市１到６最后回到１。这种编码容易理解，效率高。但是在 这种编码方式下普通的交叉算法就不再适用了，因为可能产 生没有意义的个体。图１中两条可用路径经过交叉操作以后， 产生的卜１－５—６－３—６路径是没有意义的。为了解决这个问题， 很多学者提出了适用于ＴＳＰ的交叉算子，像顺序插入法，启 发式交叉等，但是这些算法会打乱交叉片段中的基因位置因 而不能保存父体的优秀基因片段。 在单目标优化中，对于种群的适应性方面的研究很多，多样 性保持方面常常用的手段是小生境方法。其次由于遗传算法 的局部能力差，也有学者采用其他局部搜索算法来构造混合 遗传算法 ，这些方法对在种群适应性方面是有效的，但是 在种群多样性方面却不足，对于有的优化问题来说，多样性 保持对搜索最优解有着重要的作用。最后在旅行商问题中普 通的交叉算子会破坏要交换的基因片段，针对这个问题本文 提出了对应连通子图交叉（Ｃｏｒｒｅｓｐｏｎｄｉｎｇ Ｃｏｎｎｅｃｔｅｄ 可用路径棹１ 可用路径抖２ Ｓｕｂｇｒａｐｈ Ｃｒｏｓｓｏｖｅｒ，ＣＣＳＣ），结合ＬＫ局部搜索和小生境等操 作构造一种基于ＣＣＳＣ的混合遗传算法（ＣＨＧＡ）。通过几个实例 的计算和对比表明，算法的设计是有效的，求解质量也有较 大提高。 Ｅ叵Ｅ臣四日 ，Ｅ田习卫习 厂———————］田曰珀Ｉ 田 田田珂▲ 田 １对应连通子图交叉 交叉算子是遗传算法中最重要的部分，既可以使个体发 生变化，又能保留父体的优秀基因片段，使种群向着理想的 Ｊ ［田］ 习 不可用路径抖１ Ｊ 臣 习卫习 不可用路径＃２ 图１普通交叉操作产生的不可用路径 【收稿日期】２０１３—０５—１０ 【基金项目】广西大学科研基金（ＸＪＺｌ１０５８５）；广西研究生教育创新项目（ＹＣＳＺ２０１２０１８ ｏ 【作者简介】袁成林（１９８２一），男，广西大学计算机与％５－４￣息学院硕士生，研究方向为计算智能。 ．ｄ． 基于以上分析，本文提出一种新的交叉算子：对应连通 子图交叉（ＣＣＳＣ）。这种交叉方法可以做到严格的交叉，即子 代的基因都是从父代继承所得，所有基因片段都可以在两个 父体中找到。ＣＣＳＣ通过合并两条父体路径，构造连通图Ｇ。 对Ｇ中的对应连通子图进行搜索，然后进行交叉，交叉策略 可以是：随机选择某个或若干个对应连通子图进行交换，还 可以采用贪婪选择对每个对应连通子图进行多次搜索，找到 最短个体，这几种方法时间复杂度都在０（ｎ）之内，本文权衡 算法效率和求解效果，决定采用随机选择若干个对应连通子 图进行交换的交叉策略。明显可以看出若对应连通子图的个 数大于等于１，ＣＣＳＣ就可以创造两个以上的后代个体。若有 ｋ个对应连通子图，则可以产生２ Ｌ２个个体，减２是因为有 两个个体和父体是相同的。 对应连通子图：合并两条父体路径，构造连通图Ｇ，在Ｇ 中，删除两条父体路径的重合边后，得到图Ｇ ，Ｇ 的某个连 通子图中的节点在两条父体中均为连续的基因片段，此连通 子图称为对应连通子图。 图２—２中的ａ—ｂ—Ｃ—ｄ，ａ—ｃ—ｂ—ｄ和ｇ－ｈ—ｊ—ｉ—ｋ，ｇ－ｉ—ｈ—ｊ—ｋ 就是两对对应连通子图： ＼ ｒ １＼ ≮ ｜１ ｂ ｎ ～ ．．．…一 １ ’ ／／／ ＼、ｆ １ｋ 图２对应连通子图示意 寻找对应连通子图的流程如下： （１）删除图Ｇ中两条路径重合的边。 （２）建立队列Ｑ，把度为１的ｎ个节点放在队头，设定 计数器Ｋ＝ｎ。 （３）从队列的ｎ＋１个节点开始进行广度遍历，找出所有 连通子图，把遍历过的点前移，记录连通子图结点个数ｔ ， 直至所有节点操作完成。 （４）对结点个数ｔ 大于等于３的连通子图ｉ，对其父体 进行检查如果连通子图的节点在两父体中均为连续的基因片 段，则该连通子图为一个对应连通子图ｇ，记录ｇ。 （５）如果符合要求的连通子图都已经搜索就退出程序， 否则返回步骤４。 ２混合遗传算法ＣＨＧＡ的实现 ２．１选择算子 选择算子是算法中关键的一环，可以选择优秀个体进入 ．５一 下一代进行交叉和变异操作，本文采用的是轮盘赌法，根据 个体的适应度进行选择，适应度越大个体被选择的概率就越 大，并且可以保留少量适应度较差的个体，增加种群多样性。 ２．２变异和交叉算子 变异：本文采用两点随机交换的变异操作对种群进行扰 动，跳出某些局部最优解。 交叉：本文采用第一节提出的对应联通子图交叉作为交 叉算予。 ２．３小生境操作 经过轮盘赌选择等操作后，适应度大的个体更容易进入 新种群，种群里就会出现很多一样或者很相似的个体，这样 就会导致算法早熟，结果陷入局部最优解，所以本文引入小 生境操作来保持物种多样性。 具体方法是：假设种群共有ｎ个个体，首先计算个体 （１－１，２…ｎ）和其他个体之间的小生境距离￡（ 。在对个体 与其他所有个体的小生境距离 （ ， 求和，计算出个体 的小生境排序值 ＝ Ｌ（ｆ，，）。循环这个步骤直到计 ，＝１ 算出所有Ｓ 。升序排列毋后，用随机产生的个体代替 最高 的ｎ个个体，算法的时间复杂度是０（ｎ。）。 其中Ｌ（ｉ，ｊ）的求法是，假设ＴＳＰ共有Ｎ个城市，取个体 ｉ的第ｋ（ｋ＝ｌ，２，３…Ｎ）个基因位城市ｉ（ｋ），在个体ｊ中找 到城市ｉ（ｋ）的位置ｔ，对ｉ（ｋ）和ｊ（ｔ）左右两边城市号做同或 操作：Ｌ（ｉ，ｊ）＝ｉ（ｋ＋１）ｏｊ（ｔ＋１）＋ｉ（ｋ＋１）ｏｊ（ｔ－１）＋ｉ（ｋ－１）ｏ Ｊ（ｔ＋１）＋ｉ（ｋ－１）ｏｊ（ｔ－１）。因为Ｏ＜Ｌ（ｉ，ｊ）≤２，所以Ｏ＜ｓ Ｅ２ｎ。 小生境排序值Ｓ 越大说明个体ｉ周围的个体越多。对种群的 非精英个体进行小生境操作，起到了保留精英又增加种群多 样性的作用。 ２．４局部搜索 在ＣＨＧＡ中局部搜索算法起着十分重要的作用。它可以使 种群迅速向着希望的方向进化。它的另一个作用是使ＣＨＧＡ 算法的第一代开始就能够找到更多的对应连通子图，提高算 法的效率，本文采用ＬＫ算法 作为局部搜索。 在本文中局部搜索的另一个作用是使算法的第一代开始 就能够找到等多的对应连通子图（ＣＣＳ），通过实验测试ＣＣＳＣ 结合局部搜索算法可以产生的对应连通子图的大致个数，实 验采用ＴＳＰＬＩＢ中的ａｔｔ５３２，ｎｒｗ１３７９和ｕ１８１７三个算例，用 ３－ＯＰＴ，３－ＯＰＴ和Ｍ０一ＬＫ算法对５Ｏ个随即路径进行测试，平 均实验结果如表１。通过实验发现２－ＯＰＴ与ＣＣＳＣ结合在９０％ 的情况下可以产生可用个体，也就是至少有一对对应连通子 图而，结合３－ＯＰＴ和ＬＫ算法的ＣＣＳＣ产生可用解的概率达到 了将近１００％。 表１不同局部搜索找到的对应连通子图个数 ３．ｏＰＴ ２ｌ ５ ５ ７２ ３算例实验 ３．１实验环境 为验证所设计算法的有效性，基于如下实验环境进行相 关实验：联想台式机，其配置为： （１）ＣＰＵ：ＡＭＤ ６４ ２Ｘ ４４００＋： （２）内存：２ Ｇ ＤＤＲ２； （３）操作系统：Ｗｉｎｄｏｗｓ ＸＰ 程序以ＶＣ＋＋２００８编写及编译，实验使用数据取自 ＴＳＰＬＩＢ。算法各参数如表１所示。实验结果均为运行算法１Ｏ 次后计算得到的平均值、最优值以及最差值。 ３．２实验参数 表２混合遗传算法算法的参数设置 ３．３实验结果 本文的算例采用ＴＳＰＬＩＢ数据库中的Ａｔｔ４８、Ｅｉ１５１、 Ｅｉ １７６、ＫｒｏａｌＯ０、Ｃｈｌ３０、Ｔｓｐ２２５、Ｃｈ １５０等６个测试对 象，每个算例进行２Ｏ次计算，结果取平均值，并与文献［５，６］ 进行了对比。具体数据如下： 表３混合遗传算法算法的计算结果 文献 本文 Ｏ∞一 摄 ８ｏｏ一 短 一 路６ｏＯ一 径 一一．一．．． ４ｏＤ一 遗传代 ２ｆ 一 ５ １Ｏ 图３算例ＥｉｉＳ１收敛情况 实验结果表明，本文所做改进效果明显。１００以内规模 的问题每次都可以计算出ＴＳＰＬＡＢ最优解，而且速度上相比文 献所述也有优势。１００以上问题在２Ｏ次实验中可以计算出 ＴＳＰＬＡＢ最优解，而且平均值的误差也在１％以内。在下一步工 作中，可以着力改善算法的计算速度，并且向更大规模的问 题发起挑战。 【参考文献】 【１］Ｈｏｌｌａｎｄ Ｊｏｈｎ Ｈ．Ａｄａｐ￣ｆｉｏｎ ｉｎ ｍｔｕｒａｌ ａｎｄａｒｔｉｉｆｃｉａｌ ｓｙｓｔｅｍｓ：ａｎ ｉｎｔｒｏｄｕｃｔｏｒｙ ａｎａｌｙｓｉｓ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｍ ｔＯ ｂｉｏｌｏｇｙ，ｃｏｎｔｒｏｌ，ａｎｄ ａｒｔｉｉｆｃｉａｌ ｎｉｔｅｌｌｉｇｅｎｃｅ［Ｊ］．ＵＳＡ：Ｕｎｉｖｅ￣ｉｔｙ ｏｆＭｉｃｈｉｇａｎ，１９７５． ［２ 马良，２］旅行推销员问题的算法综述Ⅱ１．数学实践与认识， ２０００，３２（２）：１５６—１６５． 【３】 葛继科，丘玉辉，等．遗传算法研究综述Ｏ】，计算机应用研 究，２００８，２５（１０）：２９１１－２９１７． ［４】Ｈｅｌｓｇａｕｎ Ｋ Ｇｅｎｅｒａｌ ｋ—ｏｐｔ ｓｕｂｒｎｏｖｅｓ ｆｏｒ ｔｈｅ Ｌｉｎ—Ｋｅｍｉ￣ａｎ ＴＳＰ ｈｅｕｒｉｓｉｔｃ［Ｊ］．Ｍａｔｈｅｍａｔｉｃａｌ Ｐｒｏｇ￣ｎｍｉｎｇ Ｃｏｍｐｕｔａｔｉｏｎ，２００９， １（２—３）：１１９—１６３． ［５】 孙凯，吴红星，王浩，丁家栋．蚁群与粒子混合算法求解ＴＳＰ 问题 ．计算机工程与应用，２０１２，４８（３４）：６０－６３． ［６ 李哲，６１夏立，庄浩俊，董红生．ＭＭＡＳ＿ＥＣ算法求解旅行商 问题卟计算机工程与应用，２０１１，４７（９）：４１—４７． （责任编辑伍彬） ．６。
