英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
遗传算法用于旅行商问题
摘要
本文认为：旅行商问题的鲁棒遗传算法（TSP）应保持和增加良好的边缘效应，同时保持了种群的多样性好。我们通过实验分析了几个旅行商问题的遗传算法的优点和缺点。为了评估这些因素，我们提出了一种新的遗传算法，整合遗传算子和异构配对选择。前者可以保持和增加好的边缘效应和以后能保持种群的多样性。所提出的方法进行评价的15个著名的TSP的城市范围从101到13509的数字。实验结果表明，我们的方法，有点慢，非常强劲的表现，在我们最好的调查方法非常有竞争力的。我们相信，一个遗传算法如果可以保持和增加边缘效应有效并维持种群的多样性是研究旅行商问题稳定的方法。
关键词：边缘装配交叉，异构配对选择，遗传算法，邻接突变，旅行商问题
1介绍
旅行商问题（TSP）是一个著名的NP-难的优化问题，需要最短的路线穿过每个城市访问的起下一组城市的测定。TSP问题提出了重要的问题，因为在科学，工程和生物信息学等领域的许多问题，如路线、调度问题，柔性制造系统，物理映射问题[ 1 ]，并构建系统发育树[ 14 ]可归结为TSP问题。大量的方法已经开发了用于求解TSP问题。一个很有前途的方向是遗传算法（GA）。它是基于从遗传学和自然选择借来的想法。遗传算法是解决问题的一个普遍适用的概念。它特别适合解决不同的优化问题，传统的优化方法效果较小。然而，在解决TSP问题不是很有效，尤其对大问题。
为了进一步让遗传算法应用于旅行商问题，许多方法被提出。在这些方法中，设计特定的算法和当地特定的研究结合在一起，同时保持种群多样性被视为有前途的策略。设计专业交叉，如循环交叉，[种群重组交叉，最大限度地保留交叉和边缘交叉等，可以提高遗传算法解决旅行商问题的能力。结合主要特定的搜索技术到遗传算法具有全局最优性局部搜索算法的收敛。保持种群多样性可以有效避免早熟。
几个反应遗传算法在旅行商问题中的应用将被讨论。在这里，我们解决了这些问题，通过对一些著名的TSP一些交叉和变异算子的行为。我们发现，遗传算法的TSP应该至少有三个机制：强大的遗传算子，可以保持和增加“边缘”（即边缘的最佳旅游）以及一种机制来保持种群的多样性。基于这些因素，我们设计了一种新的遗传算法求解旅行商问题。对15个著名城市的旅行商问题进行了评价，其数量的城市范围从101到13509。实验结果表明，所提出的遗传算法的解决方案的质量保持在0.00043从测试问题的最优解。它比起其他比较方法更为稳定。本文的其余部分组织如下。在第2节，通过分析交叉算子、变异算子以及种群多样性的机制，讨论了遗传算法的设计问题。第3节介绍了一种新的遗传算法的基础上分析这些因素，并比较它与其他对一些问题的基准著名的方法。第4节得出结论意见。
2基于遗传算法的旅行商问题
这部分通过实验讨论基于遗传算法的旅行商问题。一些交叉和变异算子将在保持和增加种群多样性的原则被分析。实验结果表明，基于边缘的遗传算子，如边缘交叉和邻居加入突变，能够满足这些特点。为了保持种群多样性，异构配对选择将被发展。
2.1分析交叉算子
针对旅行商的交叉算子将被分为三类：区间保持，基于位置的，基于边缘的交叉。在一个区间保持交叉，如部分映射交叉（PMX），顺序交叉（OX），基于订单的交叉（OBX），和最大的保持交叉（MPX），选择的两个城市之间的子路径从一个父复制到后代。其他城市被添加到根据另一个父母的相对顺序。它执行就像典型的两点交叉和维修基于父母的信息解决方案。一种基于位置的交叉保留了父母的相对位置，并与传统的均匀交叉。它试图创建一个后代从父母那里每一个位置是由一个对应的元素从父。最具代表性的是循环交叉（CX）和基于位置的交换（PBX）。基于交叉的边缘，如启发式交叉（HX）边重组交叉（ERX），距离保持交叉（DPX），和边缘组件交叉（EAX）的边缘保持在父母和添加新的边缘试探性地产生后代。不同的方法运用不同的保存和添加机制。
图1测试简单遗传算法的伪代码。
我们用一个简单的遗传算法来分析这些交叉算子的性能。图1显示的简单遗传算法的伪代码，其中轮选择是用来选择配对的染色体和精英总代更换适合选择下一个种群。人口规模是一个平等的终止标准，数量的函数评价超过10000N，其中N是城市的数量。
表1显示了每个测试的交叉实验结果与简单遗传算法（无突变），包括att48，eil76、eil101、kroa150，和kroa200。
在表中，括号中的值表示最佳的旅游长度。列“length”代表着卵的大小（L）。卵的大小是一个遗传算子生成的解决方案的数量。平均误差定义为1/100。每个问题测试20次。据观察，当卵的大小为1，所有的基于边缘的交叉，除了ERX，优于基于区间的和基于位置的交叉。当卵的大小是20，所有算子的解决方案质量得到改善除了CX，这是一个基于位置的交叉。另一个基于位置的横过来，PBX，这里没有显示因为测试结果类似于CX。同时，基于边缘的交叉，包括EAX，HX，DPX和ERX明显比那些没有基于边缘的交叉更好。根据这些实验结果，我们认为，一个好的交叉算子应保持边缘交叉的精神和执行一个较大的卵的大小。下面的描述，以保持和添加良好的边缘是一个边缘为基础的算子的主要精神。在这些被调查的基于边缘的交叉算子，eax是最好的。我们进一步讨论了这些算子在几个大型项目的结果。这些边缘的结果为基础的交叉的八个TSP的基准，如图2所示，在卵的大小是20。每一个问题都是20次执行。误差为1/100。EXA是最好的。
表1比较9个不同搜索长度的交叉遗传算子在5个TSP
在圆括号中的值表示最佳的游览长度。“length”指卵的大小。每个实验误差为1/100，试验20次。
图2基于边缘的交叉，比较包括EAX，HX，ERX，和DPX在8个TSP使用简单遗传算法，平均误差为1/100。
HX和DPX得到类似的结果，城市数量的增加，而ERX变得更糟。在下面，我们将分析优势的特点，基于他们的保留和添加边了解两问题能力基础算子：为什么边缘的算子比没有边缘基础算子，为什么eax是最好的这些测试运营商之间。在上一段提到的，基于边缘的交叉保值的边缘试探性地产生后代。
表2 简略总结了保持和增加边缘的4个交叉算子。
|
算子 |
机制 |
|
|
保存边缘 |
增加边缘 |
|
|
ESX |
后代继承了父母的边缘根据边的长度和频率出现在种群 |
新的边缘被添加到后代去修改中间解决通过一个跨越增加短边树的方法 |
|
DPX |
只有父母双方的共同边缘被传给后代 |
直观地增加短边，使中间的解决方法 |
|
HX |
后代继承了父母的边缘边的长度是尽可能短的 |
新的边缘被随机添加成为一个可行的解决方案 |
|
ERX |
后代继承了父母的边缘尽可能多，但最大继承的边数不保证 |
新的边缘被随机添加成为一个可行的解决方案 |
EAX是最好的。HX和DPX结果是相似的，而城市数量增加，ERX更糟糕。通过添加短边的中间方法，ERX和HX随机添加新的边缘形成可行的解决方案，和EAX保留边缘试探性地增加了新的边缘与贪婪的方法，类似于一个最小生成树。为了进一步研究保留和添加边缘的机制，我们测量了添加和保存“边缘”的能力（即边缘的最佳旅游）EAX，DPX，HX，和ERX算子。
图3显示的结果这四个算子的测试问题LEM att532.tsp添加和保存“边缘”和平均边长。平均增加的“边缘”是边后增加的遗传算子的应用解决方案。
为了进一步研究保留和添加边缘的机制，我们测量了添加和保存“边缘”的能力（即边缘的最佳旅游）EAX，DPX，HX，和ERX算子。图3显示的结果四运营商测试的问题att532.tsp添加和保存“边缘”和平均边长。平均增加的“边缘”是定义边增加后的遗传算子应用于求解n是人口规模。边的定义也类似。
表2。机制保存和添加基于边缘的交叉、边缘包括EAX，DPX，HX，和ERX
图3。基于边缘的交叉，比较eax，DPX，HX，和ERX，对att532.tsp基于平均增加了“边缘”a，平均保存“边缘”b和平均边长c。人口规模和育雏大小设置分别为500和20。只有250代观察。其他问题得到类似的结果。图3（a）表明EAX可以不断添加更多的“边缘”比其他算子在前期（第七十代之前）。在第七十代中，平均存储的“边缘”的价值（图3（b））和平均边长（图3（c））的值比其他算子。HX和DPX具有相似行为这三个因素和ERX最值。这些结果与我们以前的讨论是一致的。总之，一个好的交叉算子应该基于边缘的和具有添加和保存“边缘”的好机制。如果被认为是一个很好的交叉要符合这些要求。
2.2分析变异算子
一些当地的启发式搜索，如交换、2-opt、3-opt 、[ 28 ]和邻居加入Lin-Kernighan用遗传算法变异算子解决TSP问题，使用本地搜索通常被称为模因算法。这些突变交换一些边缘的父母产生新的子代。一般来说，突变的强（本地搜索）GA的性能更好。
图4 比较遗传算法用于8TSP的3个变异算子2-opt, 2-opt, and NJ。误差定义为1/100，NJ是最好的一个，其余两个随着城市数目的增加表现越差。
图5三突变，比较2-swap, 2-opt和NJ在att532.tsp基于平均增加了“边缘”a，平均保留“边缘”b和平均边长c。
图6增加和保持良好的边缘值的能力和NJ的问题fnl4461。他们似乎能够补偿对方加入“边缘”和类似的保持“边缘”。
图4显示了三个测试的突变，结果包括2-swap, 2-opt, and NJ与简单遗传算法在（图1）8TPS基准。这些问题包括att48, eil76, eil101, kroa150, kroa200, lin318, pcb442 , and att532.在这一系列测试中没有交叉算子。平均误差为1/100，每个实验测试20次。NJ表现最好，2-opt随着城市数目的增加表现变坏，2-swap表现最差。
增加和保持边缘变异的机制非常广泛。2-swap的突变两城市在同一时间，因此四边随机取出四边随机添加。对于2-opt和NJ，他们交换了一些边缘，如果解决方案是更好的。在每一次迭代2-opt和NJ分别交换2和4的边缘。
我们使用相同的策略，交叉算子来衡量能力的增加和保持“边缘”的NJ，2-opt和交换突变。图5显示的结果这些算子测试的问题att532.tsp添加和保存“边缘”和平均边长。我们可以从其他问题得到相似的结果。图5（a）表明，NJ可以添加更多的“边缘”比其他算子在前期以及平均保存“边缘”（图5（b））在后。在加入2-opt和交换的边缘也有类似的行为，维护良好的边缘，然而交换较差。这些结果与我们之前的观察是一致的。总之，一个好的变异算子应该保持和增加边缘。NJ复合这些要求而被认为最好的变异算子。实验表明，NJ结合EAX可以解决TSP问题。为了检测NJ与EAX的互补特性，我们通过EAX和NJ算子测量的增加和保持“边缘”的能力（即边缘的最佳旅游）。图6（a）表明，NJ可以添加更多的“边缘”比EAX早，而EAX后期优于NJ。保持“边缘”这两个算子的能力是相似的（图6（b））。虽然我们不能从理论上证明结合EAX和NJ无缝，在我们的实验中他们确实互相补偿的添加和保存“边缘”。
2.3保持多样性机制
保持种群多样性是遗传算法应用于TSP的另一个问题。在这里，我们设计了一个新的配对选择，称为异构配对选择（HPS），选择交叉算子的基础上降低人口的边缘相似性早熟收敛效果的两个父母。
表3 比较各种不同的选择包括：HPS，RPS，随机，排名，和锦标赛选择轮，与简单遗传算法（图1）和基于“误差”定义为1/100的EAX.
表明HPS的性能，我们比较HPS与我的选择，包括随机配对选择（RPS），随机选择，排序选择，轮盘赌选择，和表3显示，HPS比这八个测试问题具有相同功能的评价别人锦标赛选择，8 TSP基准。简单遗传算法（图1）中进行搜索的长度设置为20。对于att532，eax与HPS 可以找到方案在20次独立实验中的19次。对于其他问题，HPS和EAX总是可以找到最优方法在每次实验中。总之，我们证明了HPS是能够通过方法提高EAX方案的质量。这些方法都是在20个独立的试验的平均质量的基础上，测试了八个问题。
图7。我们所提出的遗传算法的概述
初始带有N个方案的初始种群S
基于HPS选择来挑选父本母本
重复挑选在种群S个体si
通过在It上应用变异算子NJ产生子代
让新种群代替旧种群
从子代和父本母本中选择好的个体插入到下一个种群
输出最好解决方案
否
条件满足终止
是
3系统和结果
基于第II部分的讨论，我们调查结合边缘组件交叉遗传算法（EAX），邻居加入突变（NJ），与非配对选择（HPS）。图7显示了该方法的主要步骤。氮的解决方案是随机产生的初始种群。在评估适应性，群体中每个方案依次使用HPS选择本身（
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[146536]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
