英语原文共 22 页
英文翻译
外文原文出处：
Expert Systems with Applications
Volume 77, 1 July 2017, Pages 189-194
1.介绍
旅行商问题(TSP)是一种非确定性多项式难题，长期以来一直是基于线性规划和非线性规划的离散或组合优化技术领域的一个有趣问题。TSP的任务是在一组给定的位置(城市)中寻找最佳路径，这样每个位置只经过一次，并且销售人员返回到起始位置(德宾，1987，德宾等人，1989)。在运筹学,旅行商问题仍然最具挑战性的问题之一,不能解决很容易通过使用枚举等传统优化技术方法和数学规划(桑卡和奥兹萨格拉姆，2009)。优化求解TSP需要大量的计算时间，因此需要开发快速启发式，在合理的计算工作中给出接近最优的解决方案(马泰，辛格和米塔尔，2010年)。虽然在小图上执行时间可能不显著，但是在包含数百万个顶点和边的大型数据集上，现有方法的限制(例如路由跟踪，社交图表)变得很明显。随着大数据时代的到来，当我们处理具有不同属性(如稀疏、幂律、稠密)的巨图时，迫切需要开发基于新范式和可伸缩算法的新技术。在可能的方法中，有一些是从元启发式启发而来的方法，这些方法允许更好地探索解空间和更快地收敛到次优解。
在过去的几十年中,许多基于元启发式方法算法策略提出了为了寻找旅行商问题的最佳解决方案,其中包括禁忌搜索(TS)(诺克斯，1994),SA(柯克帕特里克，盖拉特和维奇，1983)、遗传算法(GA)(约翰逊和洛杉矶麦奇，1997)，蚁群优化(ACO)( 多里戈和甘巴德拉，1997),粒子群优化(PSO)(时小虎等人，2007),人工免疫系统(AIS)(法默，帕卡德和佩尔森，1986),人工神经网络(ANN)(若莱和甘巴里，2010)，弹性网络(EN)(德宾等人，1989)，SOS(程旻远和普拉约戈，2014)。
在本文中，我们将重点研究SOS算法，原因如下。该算法通过生态系统中生物体之间存在的共生关系策略，从自然界中获得灵感。提出了求解连续工程优化问题的SOS算法。一些结果(奥拉迪，2013，程旻远等人，2015，特兰，2016，韦尔马等人，2017)使用SOS算法作为优化工具来寻找全局最优解，表明该算法在复杂的数学基准问题上测试时表现出相当强的鲁棒性。因此，SOS在寻找上述优化问题的全局解方面的潜力值得进一步研究。此外，由于SOS在求解离散问题(如路由和分配问题)方面没有得到广泛的认可，我们认为，证明它在求解TSP方面的有效性，可以为解决复杂离散问题的大规模适用性铺平道路。
TSP优化问题被认为是一个大规模的优化问题，仅使用经典的元启发式优化算法如SA、TS、GA和蚁群算法很难得到满意的结果。近年来的研究重点已转向利用不同的杂交技术来解决各种复杂的大规模优化问题。杂交过程的本质主要是利用多种算法的互补优势和增值信息，而单一的基于算法的方法不足以提高求解TSP等大规模问题的效率。最近的两项研究SOS的应用来解决相关的离散优化问题为例,表明经典版本的SOS算法仍然需要某种程度的改进,达到更好的解决方案质量,明显的工作提出了文森特,雷迪,杨，鲁斯卡蒂娜和托萨(2017)和埃基，文森特,布迪和雷迪(2015)。这些研究的实现结果表明，将基本SOS与局部搜索方法或解表示等算法相结合，可以显著提高解的计算效率和质量。混合特征的另一个影响是，它使SOS算法可以很容易地避免陷入局部最优。
虽然本文的具体目标是证明混合SOS是TSP的一个有前途的候选优化解，但结果也强调了SA增强的SOS算法在更广泛的复杂离散问题的有效求解中的未来适用性。拟议中的SOS-SA方法在Matlab中实现和测试数据集使用旅行商问题(http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/)和其他先进的算法如遗传算法粒子群优化蚁群优化(GA-PSO-ACO)(邓等人, 2012),自适应模拟退火算法与贪婪搜索(ASA-GS)(耿，陈，杨，史和赵,2011),多智能体模拟退火算法与基于实例的抽样(MSA-IBS)(王，林，钟和张，2015)基于列表的模拟退火(LBSA)(詹，林，张和钟，2016)，改进的离散Bat算法(IBA)(奥萨巴，杨，迪亚斯，洛佩兹加西亚和卡瓦列多，2016)。之所以选择这些算法集，是因为它们在实现技术上与SOS-SA算法有共同之处。结果表明，混合的SOS-SA算法能够较好地解决TSP基准问题中的大部分问题，涉及的城市从42个到33,810个不等。
本文的技术贡献如下:
1.提出了一种新的TSP优化方法——基于模拟退火的共生生物搜索优化算法。
2.使用不同规模的TSP基准实例实现该方法。
3.与其他先进算法(GA-PSO-ACO、ASA-GS、MSA-IBS、LBSA和IBA)的性能比较。
4..使用不同的统计分析测试，对SOS-SA结果与其他选定方法进行描述性统计验证。
本文的其余部分组织如下:第2节介绍了相关工作;第3节简要介绍了TSP问题;第4节提出了求解TSP的SOS-SA方法;第5节描述和讨论了一些有基准的TSP实例的仿真结果;最后，第6部分给出了研究结论和未来的研究方向。
2.相关的工作
TSP是一个具有很高社会兴趣的硬组合优化问题，在过去的几十年里引起了科学界的关注，提出了创纪录数量的优化算法来解决最小化问题(陈和钱, 2011)。有兴趣的读者可以参考巴尔巴托，格拉普，拉克鲁瓦和卡尔沃 (2016), 科努等人 (2017), 德尔加迪略 (2016),神田等人 (2016年), 莫汉，拉马尼和米斯拉 (2016), 森达尔和拉西姆 (2016)，王，埃尔索伊，何和王(2016),张和周(2016)和张等人(2016)对TSP最近的结果情况。在本节中，我们将介绍一些最具代表性的结果。
TSP是一种非确定性多项式难题,在大多数情况下不承认任何常数因子近似(加里和约翰逊, 1979,除了一些例外情况:本德和西库瑞，2000和莫汉等人, 2016),导致了不同的优化方法的命题,旨在提供解决方案的复杂问题。例如，马泰等人(2010)提出了两种求解TSP的方法。第一种方法使用精确的方法，其最优解的保证由于执行时间的指数成本随问题维数的增加而大大降低。因此，这种方法被认为不适合求解大型的TSP。这种方法的两个常见例子是动态规划(贝尔曼, 1962)和分支界限法(劳勒和伍德, 1966, 欧格林特和琼克，1982)。第二种方法称为近似算法。该方法只给出了近似最优解，但不能保证最优解。这种方法的一个主要优点是，无论问题的维度如何，它都只需要很少的计算工作。近似算法可进一步分为局部搜索算法和启发式优化算法。通常采用局部搜索或改进启发式方法来提高生成的TSP解决方案的质量。这些启发式的例子有2-Opt (约翰逊, 1990)和3-Opt (洛伦索,马丁和斯图茨尔, 2003)交换启发式。
近年来，大多数新提出的求解TSP的方法表明，通过开发克服单个算法缺点的混合算法，传统的基于启发式算法的求解质量有了提高。最近的研究也表明，两种或两种以上算法的结合效果通常比单个算法的效果更好(阿雅玛等人，2000,林等人，2016, 塔勒比，2002, 塔勒比等人，2004)。这通常意味着，大多数混合算法的性能常常比单独的算法更有效。
现有的一些基于混合启发式优化的方法用于搜索前一节所述以外的TSP的最优解，包括: 混合遗传算法粒子群优化蚁群算法(GA-PSO-ACO)(邓等人，2012)，自适应贪心搜索模拟退火算法(ASA-GA)(耿等人，2011)，基于实例抽样的多智能体模拟退火算法(MSA-IBS)(王等人，2015)，基于列表的模拟退火(LBSA)(詹等人,2016),入侵杂草群落优化(硫磺岛)(周，罗，陈,何和吴,2015), 蚊子寄主搜索算法(MHSA)(冯，罗和高,2009),一种改进的离散蝙蝠(IBA)算法(奥萨巴等人, 2016),离散布谷鸟搜索算法(DCS)(阿马尔来，阿希德和杨,2014),遗传模拟退火粒子群优化蚁群系统(陈和钱,2011)和共生有机体搜索(SOS)算法(埃基等人,2015，文森特等人，2017)。这些算法是独立于问题的，具有很强的全局搜索能力，而混合特性使它们能够很容易地避免陷入局部最优。随后，简要回顾了相关文献。
GA-PSO-ACO (邓等人，2012)是一种结合遗传算法、粒子群优化算法和蚁群优化算法的进化思想来解决旅行商问题的算法。其实现需要将遗传算法的随机性、快速性和完整性与粒子群优化方法相结合，实现一系列次优解。最后利用解的并行性、正反馈性和精度高的特点，利用蚁群优化方法对得到的解进行求解，实现对整个问题的求解。奥萨巴等人(2016)提出了一种改进的bat算法(IBA)离散版本，用于求解对称和非对称TSP。该算法在37个TSP实例上进行了测试，得到了令人感兴趣的结果，在大多数情况下都优于其他基准算法。
耿等人(2011)提出了一种自适应混合算法，将模拟退火算法和贪婪搜索技术(ASA-GS)相结合，求解TSP问题。贪婪搜索技术加快了算法的收敛速度，而混合算法在计算时间和求解质量之间取得了较好的平衡。计算结果表明，该算法具有良好的可扩展性，即使在大规模的TSP实例中也具有较好的性能。王等人(2015)提出了多智能体和模拟退火与基于实例的抽样(MSA-IBS)相结合的方法，用于求解TSP。该混合过程利用了基于实例的搜索算法的学习能力，提高了模拟退火算法的采样效率，与ASA-GS算法相比，该算法在解决方案质量和系统资源利用率(如cpu时间)方面具有较好的竞争优势。詹等人(2016)在工作中也提出了一种基于列表的模拟退火算法来求解TSP。该算法利用基于列表的冷却方案的有效性和参数敏感性来控制SA的降温，并以此作为选择候选方案的接受准则。仿真结果表明，该算法具有较好的鲁棒性和较好的性能。
陈和钱(2011)提出了一种求解TSP的新的混合优化方法。本文采用遗传模拟退火、蚁群算法和粒子群优化技术相结合的方法。在实现过程中，利用蚁群系统对遗传算法的求解过程进行初始解的生成，然后对初始解进行模拟退火微调，得到比原算法更好的解。粒子群优化技术的作用是在蚁群系统中，通过预先设定的循环次数，促进种群间信息素信息的交换。仿真结果表明，与其他算法相比，该混合算法具有更好的性能。在马莱克, 古鲁斯瓦米, 潘迪亚和欧文斯(1989)中实现了并行和串行版本的模拟退火和禁忌搜索算法，并用于求解TSP。在方，陈和刘(2007)中，采用模拟退火的粒子群优化方法求解TSP。为了减缓粒子群算法的退化速度，提高粒子群算法的多样性，采用了模拟退火算法。此外，在考虑两个显著特征的情况下，选择与所提出的算法进行比较的基准算法;(i)基于种群的算法实现，即GA-PSO-ACO、IBA和SOS; (ii)基于sa的混合算法实现，即ASA-GS、MSA-IBS和LBSA。
由于这一研究领域的广泛兴趣，总结所有文献中可用的相关材料可能是一项艰巨的任务。因此，感兴趣的读者可以参考以下材料来进一步了解TSP及其计算解决方案(阿普盖特等人，2011, 琼格等人，1995, 赖内尔特, 1994)。
在这项工作中，我们将展示现有的算法，如GA-PSO-ACO、MSA-IBS、LBSA、SOS和IBA，其性能低于我们的混合算法SOS- SA，该混合算法使SOS能够避开局部极小值，并在某些情况下改进了目前已知的一些最佳结果。
3.TSP问题的求解
TSP是一个著名的组合优化问题，在过去的几十年里引起了研究领域的兴趣。文献中提出了不同的求解方法，目前主要用于求解三类TSP问题，即对称问题、非对称问题和多旅行商问题。TSP问题被称为非确定性多项式优化问题，这意味着没有已知的多项式时间算法可以具体保证其最优解的获得，这就是为什么启发式或近似方法仍然是求解TSP问题的首选方法。TSP的许多应用领域突出的马泰等人(2010),其中包括:印刷电路板钻孔,改革燃气涡轮发动机,x射线晶体学,计算机连接,人员调度、面试安排、任务规划、车辆路径,面具策划的PCB生产、全球导航卫星系统测量网络的设计。本文研究的是对称旅行商问题。
对称TSP也可以定义在一个完整的无向图G = (V,E),在设置V = {1,2,hellip;, n}的顶点集,E={(i,j):i,jisin;V,ilt;j}是一个边缘设置(马泰等人,2010)。在E上定义一个代价矩阵X=()ntimes;n。当对于所有1le;ilt; jle;n,1le;klt;lle;n，或对于所有i,j,k时，代价矩阵满足三角不等式。特别地，这是平面问题的情况，其中顶点是平面上的点di=(qi,pi)，是欧氏距离。三角不等式也满意如果最短路径的长度从我到j在G.此外,在经典的组合优化问题(奥兹坎和埃伦图克，2004)，TSP可以定义如下:给定的n个城市和它们之间的距离，通过所有城市的最短距离可以从最小化函数表达的等式（1）得到。
（1）
其中，phi;一组排列phi;→1,2，hellip;，n，n是问题的所有可能的旅行次数，f（phi;）代表排列phi;的成本。
4.基于模拟退火的共生生物搜索(SOS-SA)
在本节中，我们讨论了两种基本的搜索算法，它们构成了求解TSP问题的混合算法。
4.1共生生物搜索算法
在现实世界中，生活在一个生态系统中的两个或两个以上不同物种的不同生物体之间的紧密联系，通常但不一定对每个成员都有利。当这种关系对两种生物都有利时，就称为互利共生。当一种行为对另一种行为有利而对另一种行为没有影响时，这叫做共栖主义;当一种行为对另一种行为有利而对另一种行为有害时，这叫做寄生主义。几乎所有的元启发式优化算法都是从自然生物现象中获得生物灵感的，它们遵循
资料编号：[3408]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
