模拟退火遗传算法求解TSP问题

本文提出了一个用于求解TSP问题的改进模拟退火的遗传算法,利用遗传算法的全局搜索能力弥补了模拟退火算法容易陷入局部最优的问题。用100个城市和255个城市的TSP问题验证算法,实验测试的结果表明该方法具有较好的收敛效果和可靠的稳定性。     

求解TSP问题的改进模拟退火遗传算法

巡回旅行商问题（TSP）是最典型的NP的难题,遗传算法（GA）是解决这类问题的有效方法之一。由于该问题的解是一种特殊的序列,一般的交叉算子在该问题的求解效果方面并不理想,提出了贪心的3PM交叉算子,同时又引入退火选择方法,形成一种新的模拟退火遗传算法GCBSAGA（Greed Cross-3PM Based on Simulated Annealing Genetic Algorithms）。该算法还将模拟退火算法与遗传算法相结合,使得遗传算法在前期发挥着全局搜索的强大功能,很容易收敛到全局较优解;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能,最终收敛到全局最优解。经过国际公认的TSPLIB提供的实验数据的验证,GCBSAGA在实例eil76、eil101、pr144、st70均找到了比TSPLIB提供的最优路径更优的解。     

求解TSP问题的改进模拟退火算法

通过分析传统模拟退火算法的原理和存在的不足,提出了一个用于求解TSP问题的改进模拟退火算法。新算法增加了记忆当前最好状态的功能以避免遗失当前最优解,并设置双阈值使得在尽量保持最优性的前提下减少计算量。根据TSP和SA的特征设计了个体邻域搜索方法和高效的计算能量增量方法,加快了算法的运行速度。实验测试的结果表明,新算法比传统的模拟退火算法具有更快的收敛速度和更优的解质量。     

一种基于构建基因库求解TSP问题的遗传算法

传统的遗传算法通常被认为是自适应的随机搜索算法．该文在分析其特点后针对TSP问题提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge-GA)．该算法利用基因库指导种群的进化方向，并在此基础上使用全局搜索算子和局部搜索算子增强遗传算法的“探测”和“开发”能力．Ge-GA算法大大加快了遗传算法的收敛速度和寻优能力．作者测试了TSPLIB中的多个实例(城市数目从70～1577)，试验结果与最优解的误差都不超过0．001％．特别是对于难求解的TSP问题，如att532和fl1577，都能够在理想的时间内找到最优解．     

遗传算法和模拟退火算法求解TSP的性能分析

旅行商问题（Traveling Salesman Problem,TSP）是一个典型的组合优化问题,并且是一个NP难题,其可能的路径总数与城市数目是呈指数型增长的,所以一般很难精确地求出其最优解,因而寻找出有效的近似求解算法就具有重要的意义。目前求解TSP问题的主要方法有模拟退火算法（Simulated Annealing,SA）、遗传算法（Genetic Algorithm,GA）和神经网络算法等。GA是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应的全局优化概率搜索算法。SA算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。文中将提出遗传算法和模拟退火算法求解TSP问题,通过试验比较两者求解TSP问题的性能,结果表明GA的性能要优于SA的性能。     

改进的遗传算法求解TSP问题

实际应用中经常用人工智能算法如遗传算法求解TSP等一类NP难题．针对原有的遗传算法在初始化种群随机性的缺陷以及在产生子代过程中无法保存最优个体的问题．给出基于贪心算法的种群初始化和交叉变异后最优个体保存算法相结合的改进遗传算法,并在VC＋＋平台上对该算法的实现过程进行动态演示。     

蚂蚁遗传算法求解TSP问题

利用蚂蚁算法的正反馈机制改进两交换启发交叉方法（HGA）,从而使遗传算法的交叉操作摆脱了选择初始城市和使用贪婪策略的影响,加快了算法向全局最优解的收敛。仿真实验证明,该改进算法在求解质量和求解效率上都取得了很好的效果。     

基于一种改进遗传模拟退火算法的TSP求解

快速收敛于全局最优解是遗传算法的一个研究重点.在对遗传算法和模拟退火算法研究的基础上,分析了两种算法各自的优缺点,对已有的遗传模拟退火算法进行了改进.结合遗传算法和模拟退火算法的优点,给出了一种并行的多层搜索结构,提高了算法的效率;同时,在此基础上,提出一种种群早熟评价指标.最后,将此改进算法应用到旅行商问题中,并分别对10个城市和30个城市的旅行商问题进行了仿真,用于验证算法的可行性和快速性.仿真结果表明.改进的遗传模拟退火算法能够较快的收敛于全局最优解.     

基于混合遗传模拟退火算法求解TSP问题

TSP问题是典型的NP-hard组合优化问题,遗传算法是求解此类问题的一种方法,但它存在如何较快地找到全局最优解,并防止“早熟”收敛的问题。针对上述问题并结合TSP问题的特点,提出将遗传算法与模拟退火算法相结合形成遗传模拟退火算法。为了解决群体的多样性和收敛速度的矛盾,采用了部分近邻法来生成初始种群,生成的初始种群优于随机产生初始种群。仿真实验结果证明,该算法相对于基本遗传算法的收敛速度、搜索质量和最优解输出概率方面有了明显的提高。     

遗传算法TSP问题的实现及免疫优化

本文介绍了遗传算法的基本知识，并利用遗传算法解决TSP（旅行商）问题，在此基础上，用免疫遗传算法进行优化对比。     

求解TSP问题的混合遗传算法

TSP问题是一类经典的NP问题,目前有很多方法对其求解,而用混合遗传算法对其求解取得了很好的成效。常见的混合遗传算法有遗传算法与最速下降法相结合（GACSDM）、遗传算法与模拟退火法相结合（SAGA）。设计了贪婪的复合变异算子（GCM）,并引入隔代爬山法算子（Climb）增加遗传算法的局部搜索能力。实验结果表明该算法是有效的。     

一种求解TSP问题的新算法

为了求解TSP问题,提出了一种新的遗传算法。它利用距离密集度和适应度定义了自适应的交叉和变异概率,采用改进的交换启发交叉算子,产生不差于父代的个体。根据最优和次优个体的差异,采用2变换法产生新个体或者进行模拟退火操作,局部搜索加快了算法向最优个体靠近的速度。仿真实验表明新算法是一种求解TSP问题的有效方法。     

改进的蚁群算法及其在TSP中的应用

蚂蚁算法是一种元启发式优化算法,研究表明其具有较强的发现较好解的能力,但是也存在一些不足。根据蚂蚁算法的信息素更新的特性,提出了一种信息素更新的新方法,并把其应用于求解TSP问题,仿真结果表明,该方法具有很好的性能。     

求解多目标旅行商问题的混合遗传算法

一般TSP问题是单目标的,只追求一个性能指标：所走路径最短。然而对于具体的TSP问题,实际中常常需要考虑：路程最短、时间最少、费用最省、风险最小等等多方面的因素。设计了贪婪的复合变异算子（GCM）,引入隔代爬山法算子来提高多目标TSP问题的搜索能力。实验结果表明该算法是有效的。     

求解TSP问题的改进果蝇优化算法

基于求解TSP问题,提出一种改进果蝇优化算法（GFOA）,该算法结合TSP问题的特点,把果蝇优化算法的连续空间对应到离散规划,利用轮盘赌法初始化路径,并把遗传算法的交叉、变异操作应用于路径的寻优,同时利用C2Opt算子对局部最优路径进行优化,加快局部搜索能力和收敛速度。通过对13个TSPLIB 标准库的TSP算例进行仿真实验,实验结果表明,提出的算法在较小规模算例中能以较少的迭代次数和运行时间快速收敛到已知最优解,在较大规模算例中能接近理论最优解,具有较快的收敛速度和较高的收敛精度。     

改进的多智能体遗传算法求解TSP研究

多智能体遗传算法是基于智能体对环境感知与反作用的能力提出的一种新的函数优化方法,具有很快的收敛速度,尤其是在优化超高维函数时更显示出了它的优越性。针对这一特点对该算法进行了适当的改进,在邻域正交交叉算子中采用精英保留策略,在自学习算子中引入邻域正交交叉算子并采用小变异概率以加快收敛速度。求解TSP的实验结果显示,改进后算法的性能有了较大的提高。     

求解超大规模旅行商问题的纵深遗传算法

很多演化算法对初始参数设计都敏感,针对于不同的旅行商问题（Traveling Salesman Problem,TSP）实例需要进行相应的初始参数调整。并且,在求解超大规模TSP问题时容易陷于局部最优解。提出了一种纵深遗传算法的TSP问题求解方案,以及新的改良函数、变异函数和交叉函数。对pr1002（259 269.09）、pla85900（152 394 182.43）和brd14051（489 842.93）等实例都获得了比较好的优化解。实验表明该方案在求解TSP问题方面具有优势。     

求解VRPSDP问题的改进模拟退火遗传算法

配送和回收一体化的车辆路径问题（VRPSDP）是一种非常复杂的NP难题。针对这一问题,设计了一种改进的模拟退火遗传算法ISAGA,采用非零自然数编码机制和弱可行解到强可行解的解码机制,将3PM交叉算子和退火选择相结合,形成贪心3PM交叉算子,引进insert 、swap和2-opt分别对解进行迭代优化,并将模拟退火算法和遗传算法巧妙地结合,使得遗传算法在前期发挥着全局搜索的强大功能;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证,ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。