武汉理工大学论文翻译
针对大型多旅行商问题的一种新型高效混合算法
摘 要
多旅行商问题(MTSP)不仅是旅行商问题(TSP)的推广，而且是比TSP更适合于对现实生活中的实际问题进行建模。为了解决多仓库的MTSP问题，以及每个销售人员需要访问的城市数的最大值和最小值的问题，将单种群遗传算法(PGA)和蚁群算法(ACO)相结合，提出了蚁群-并行遗传算法(AC-PGA)。本文的主要思想是将变量分为两部分。详细的说，就是利用遗传算法综合搜索第一部分变量的最优值，然后利用蚁群算法精 确确定第二部分变量的最优值。比较分析采用PGA、改进PGA (IPGA)、两部分狼群搜索(TWPS)、人工蜂群(ABC)和入侵杂草优化(IWO)算法求解MTSP，并通过公开可用的TSPLIB基准进行验证。对比实验结果表明，该算法在求解大规模MTSP问题上是有效的，具有较好的性能。
关键词：遗传算法；单种群遗传算法；蚁群算法；多旅行商问题；杂交算法
第1章 绪论
不同领域的一些研究人员已经注意到了旅行商问题(TSP)，它是组合优化中遇到的经典np完全问题[1]。问题的目标是在假设所有给定的客户节点只被销售人员访问一次的情况下，以最小的成本找到销售人员的路线。有一些精确算法和启发式算法可以有效地求解TSP。例如，分支-切割精确算法[2]，逼近算法[3]，遗传算法[4]，进化算法[5]，人工蜂群算法[6]，蚁群算法[7]，水循环算法[8]，离散蝙蝠算法[9]，随机键杜鹃搜索[10]， 黑洞算法[11]、离散综合学习粒子群优化算法[12]、模拟退火算法[13]、果蝇优化算法[14]和基于种群的增量学习算法[15]。此外，更多的算法可以在文献综述中找到[16]。在实际应用中，TSP模型被广泛应用于不同领域的实际问题，如路由问题[17]、网络问题[18]和调度问题[19]。
多重旅行商问题(MTSP)是TSP的一个变种，可以用来更有效地解释实际应用。在MTSP模型中，不是只有一个销售人员，而是几个销售人员必须访问这些城市，这样每个城市只有一个销售人员访问，目标是最小化每个销售人员路径长度的总和。该模型已广泛应用于调度[20]、维护网络[21]、物流[22]和质量检验[23]。与标准TSP相比，MTSP的研究要少得多，也没有得到同样多的研究努力。随着研究者对MTSP的深入研究，MTSP得到了越来越多的关注，并由此发展了许多有效的方法。这些方法可以可分为两种：精确直接法和启发式法。精确算法是一种基于严格数学理论的早期算法。最著名的算法是首次提出的求解大规模对称MTSP的分支定界法。一个伪多项式时间精确算法[24]被设计用于树上的最小-最大的k-旅行商问题。此外，文章还对GMDTSP可行解的凸包进行了多面体分析[25]。虽然精确算法有严格的数学公式，但它们解决问题的能力完全取决于问题的大小。当尺寸增大时，可能在可接受的时间内无法解决，甚至根本不可解。
为了克服上述计算困难，越来越多的研究人员转向启发式算法的研究，这种算法可以很容易地获得大型MTSP的最优、次优或可行解。在[26]中描述了MTSP现有的一些精确和启发式的求解过程。一个异构的、多个仓库的、多个旅行推销员问题被转化为一个单一的、非对称的旅行推销员问题，然后由著名的Lin-Kernighan-Helsgaun启发式算法解决。使用新交叉算子的遗传算法[27]，改进的两部分狼群搜索算法[28]，进化规划算法[29]，人工蜂群(ABC)算法和入侵杂草优化(IWO)算法[30]先后为MTSP问题而提出。针对k-互联多站多旅行商问题还有一种基于人工蜂群算法的超启发式算法[31]，以缩小搜索空间，减少计算时间。同年，粒子群优化算法[32]也被用于MTSP问题。
遗传算法(GA)是一种遵循适者生存原则的进化算法[33]。对于MTSP问题，使用（两部分）染色体的遗传算法[34]被设计用于寻找接近最优的解决方案和减少无用解的出现次数[35]。为了避免交叉运算，减少计算量，针对MTSP问题又设计了两种并行遗传算法(PGA)[36]。正如我们所看到的，遗传算法可以同时考虑所有的变量，但它在很大程度上取决于种群的初始值。当解空间变大时，算法求解最优解的能力变弱。
蚁群算法(ACO)也是一种用来求解MTSP问题的常见算法，并已被证明是解决一些NP-难问题的一种可接受的方法。这个算法是用来解决多个固定仓库、多个旅行推销员问题[37]，双重标准的多旅行推销员问题和含非随机参数的多个固定仓库、多个旅行推销员问题。值得我们注意的是，在求解MTSP问题时，蚁群算法对初始值的依赖性较弱，对最优解的搜索能力较强。然而，它并不能决定销售人员的仓库。因此，它通常被用来解决固定仓库的MTSP问题。
在本文中，我们考虑了MTSP中来自不同仓库的销售人员，而不是仅仅一个仓库的销售人员，并且每个销售人员必须在起始位置结束他们的旅程。显然，MTSP具有比传统的更高的复杂性，因为变量的数量被认为是增加。上述方法的成功应用，促使我们提出了一种基于遗传算法的求解非固定目标多站多旅行商问题的方法。我们提出了一种基于超启发式的遗传算法，即蚁群-并行遗传算法(AC-PGA)，该算法考虑了MTSP的具体要求，将变量分成两部分分别求解。在已有的MTSP基准实例上，将AC-PGA和其他启发式方法进行比较，结果表明，我们的方法优于其他方法，特别是在大规模数据的情况下。
论文结构如下:第2部分分别介绍了MTSP的概念、并行遗传算法(PGA)和蚁群算法(ACO)。第3部分提出了一种新的蚁群-并行遗传算法(AC-PGA)，这是一种将蚁群算法与PGA相结合的混合算法。第4部分给出了不同算法的计算结果和分析结果。第5部分对全文进行了总结，并提出了今后的研究思路。
第2章 相关工作
2.1 中期战略计划的定义
多重旅行推销员问题(MTSP)是著名旅行推销员问题(TSP)的一个广义模型。在MTSP的情况下，有m个销售人员，而不是一个人去n个城市，其目标是为所有m个销售人员找到成本最低的路线。起点城市和终点城市称为补给站，根据补给站的数量，MTSP有几个版本。
我们考虑的MTSP有多个不固定的仓库，它可以被简明地描述为:给出一个无向图，其中V是节点集，A是表示道路段的弧集。无向图G有与其弧相关的非负的代价。目标函数是:
|
（2.1） |
第一个累加代表的是m个推销员总行驶距离,第二个累加代表第i个推销员的路程(索引的第一个城市,第i个推销员访问是1,最后是)。每个应满足最小和最大的城市数量的要求,即每个销售人员都应该访问城市并且访问城市总数为。表示城市j和第i个销售员下一个需要访问的城市之间的距离。
2.2 介绍单性遗传算法
遗传算法(GA)是一种模拟达尔文生物进化理论的自然进化，然后寻找最优解的计算模型。由于交叉算子的存在，传统的遗传算法不能直接求解TSP问题，不能生成违反问题要求的非法个体。一些研究人员开发了一些特殊的交叉算子，利用遗传算法求解旅行商问题。针对这一问题，提出了改进的遗传算法和单性遗传算法。值得注意的是，同样的情况也可能发生在MTSP中。
每个个体的基因代表了一个可行的解决方案问题和每个个体的适应度是指其基因在PGA中表示的解的适应度函数值。在自然选择的过程中，适应性强的个体更有可能生存下来并繁衍后代。每一个可行解都由一个孩子的基因表示，该基因是由其父母的基因的扰动引起的。在确定了下一代的基因后，进化过程继续进行。这个算法与标准的遗传算法相似，不同之处在于，PGA生成每个孩子的方法是单个生成，而不是两个。这样，在生产下一代产品的过程中就可以避免交叉操作。表2.1给出了PGA的伪代码。
表2.1 算法1
|
算法1 PGA |
|
输入:人口的数量n,自然选择比,最大迭代 输出:找到的最佳解决方案 1:初始化解决方案，并将其与当前种群中的个体关联 2:repeat 3: 计算每个人的适合度 4: 保持个人与更大的健身的比率 5: 个人留下来随机生产下一代 6:until迭代次数达到 7:return找到的最佳解决方案 |
对于求解空间明确的优化问题，可以方便地使用PGA求解。然而，由于孩子的基因来自其父母的基因突变，所以繁殖过程是在当前人口代表所期望的解决方案周围的小范围内进行的局部搜索。也就是说，该算法在很大程度上依赖于初始种群，忽略了解空间中的其他区域。随着数据量的增加，解决方案空间也可能迅速增大。在这种情况下，如果PGA的参数不变，搜索区域的大小不会有很大的变化，被忽略的解的数量也会有很大的增加。这样一来，算法的效率就会大大降低。
2.3 介绍蚁群算法
蚁群算法(ACO)的灵感来自于自然界中真实蚂蚁的行为，它已被证明是一种对于许多NP-hard问题完全可接受的元启发式算法。作为一种应用，蚁群算法有效地解决了TSP问题[38]。假设有一个蚂蚁洞，一块食物和几条路把它们连接起来。一些蚂蚁从洞里开始寻找食物，每只蚂蚁都会在经过的路上留下一定量的信息素，而留下信息素的蚂蚁更有可能选择信息素更多的路径。蚁群找到了获取食物的最佳方式，因为信息素会挥发，更多的信息素会留在较短的路径上。
对于优化问题，蚁群算法通过模拟蚂蚁觅食过程来寻找最优解。可行解由蚂蚁的路径决定，所有可行路径构成问题的解空间。如果蚂蚁经过某条路径，它会在路径上留下一定数量的信息素，但信息素的集中度会随着时间的推移而降低。当当前的蚂蚁完成它的旅程，下一个蚂蚁立刻开始。信息素的浓度和路径的可见性都会影响信息素的选择。所有蚂蚁最终都选择了同一条路，这条路代表了问题的解决方案。表2.2给出了蚁群算法的伪代码。
表2.2 算法2
|
算法2 ACO |
|
输入:初始信息素矩阵P,距离矩阵D,信息素挥发率,信息素的重要性和和的可视化,最大迭代 输出:找到的最佳解决方案 1:repeat 2: 把一只人工蚂蚁放在它最初的位置 3: 蚂蚁根据自己的信息素和可视性来选择路径，并得到一个可行的解决方案 4: 更新信息素矩阵 5: if 蚂蚁通过then 6: 7: else 8: 9: endif 10:until迭代次数达到 11:return找到的最佳解决方案 |
实验结果表明，该算法适用于TSP及其变体的求解。该算法不依赖于初始解，因为信息素会对人工蚂蚁产生影响并使其挥发。利用蚁群算法求解固定目的地多站多旅行商问题，实验结果表明，该算法能较好地解决这类问题。然而，蚁群算法不能确定每个销售人员的仓库。因此，它不能直接用于解决文章中所考虑的问题。
第3章 MTSP的AC-PGA方法
在这一部分中，我们提出了一种新的基于蚁群算法和遗传算法的混合算法来求解MTSP。如前所述，MTSP有许多变量需要考虑，因此我们的算法将它们分为两部分，并使用不同的方法来确定它们的值。本文讨论的遗传算法过于依赖初始值，容易出现早熟现象。另一方面，蚁群算法对初始值的依赖性弱于PGA，不能确定销售人员的库位。因此，它不能直接解决本文所讨论的问题。将蚁群算法的一些计算步骤引入到PGA中，可以减少蚁群算法对初始值的依赖，避免早熟现象，为MTSP算法找到更好的解决方案。
3.1 解决方案的编码
序列编码方法是表达MTSP解的最简单、最有效的方法，它利用一系列数字来表示每个解。有两种常用的方法来使用序列编码方法来表示MTSP的解。一种是使用路径序列和断点序列，另一种是使用路径序列和城市编号序列。下面的示例说明了这两种方法如何表示MTSP的解决方案。例如，假设两个销售人员必须访问10个城市。它们的路线可能是这样的:
bull; 业务员1从5号城市出发，经过3号城市、7号城市、9号城市、6号城市，最终返回5号城市;
bull; 业务员2从8号城市出发，经过1号城市、4号城市、2号城市、10号城市，最后回到8号城市。
第一个代表
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[235378]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
