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

对遗传算法和模拟退火算法的特点进行了比较,阐述了遗传算法与模拟退火算法集合的必要性。提出了一个用于求解TSP问题的改进的模拟退火和遗传算法。利用遗传算法的全局搜索能力弥补了模拟退火算法容易陷入局部最优的问题。在遗传算法中改进了传统的交叉机制,利用父代染色体与子代染色体进行交叉,解决了传统遗传算法中存在的“早熟”问题。针对模拟退火算法收敛速度慢等问题,提出了新的解生成机制和改良算法,提高了算法的收敛速度。实验测试的结果表明,该方法具有较好的收敛效果和更高的稳定性。     

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

本文针对遗传算法（GA）早熟收敛问题就GA的交叉算予进行改进,针对模拟退火算法易陷入局部最小值的缺点．使用HFC—ADM（自适应输入阂值的分等级搜索）的SA（模拟退火算法）和改进后的GA相结合,提出了一种求解TSP问题的遗传模拟退火混合算法,并应用于求解TSP（旅行商问题）问题。实验结果表明,该算法具有比传统的GA以及基于HFC—ADM的SA具有更强的全局搜索能力和更快的收敛速度。     

求解旅行商问题的自适应升温模拟退火算法

针对传统模拟退火算法在求解问题时容易陷入局部最优解的情况,本文通过设计一种自适应的升温控制因子,提出了一种求解旅行商问题(TSP)的自适应升温模拟退火算法,有效地控制局部寻优达到全局寻优能力,并证明了改进的自适应模拟退火算法收敛性.通过TSPLIB数据库对改进算法全局寻优效果的测试,结果表明改进后的算法具有全局寻优能力、泛化性强等特点:即在TSPLIB提供的绝大部分TSP问题数据中,均能找到全局最优解,且收敛速度快.     

改进遗传模拟退火算法在TSP优化中的应用

针对旅行商问题(TSP)优化中,遗传算法(GA)容易陷入局部最优、模拟退火算法(SA)收敛速度慢的问题,提出一种基于改进遗传模拟退火算法(IGSAA)的TSP优化算法.首先根据优化目标建立数学模型;然后对遗传算法部分中的适应度函数、交叉变异算子进行改进,使算法能够更加有效地避免陷入局部最优;最后根据旧种群和新种群每个对应个体的进化程度提出一种改进自适应的Metropolis准则,使模拟退火算法部分的染色体跳变更具有自适应性,利于算法寻优.对不同TSP实例的实验结果表明,与其他路径优化算法优化结果相比,所提出的IGSAA算法能够对不同TSP实例优化得到更优的旅行路径.     

TSP问题的禁忌模拟退火求解

提出了一种加入了禁忌表、并且采用了新的温度控制机制的用于求解TSP问题的模拟退火算法。新算法增加了搜索结束阶段进行“爬坡”移动的概率,吸收了禁忌搜索具有较强局部搜索能力的优点和模拟退火算法产生优质解的能力,并且对问题的依赖性低于传统的模拟退火算法。对标准的TSPLib中不同国家的城市数据进行测试的实验结果表明,新的算法比传统的模拟退火算法在求解TSP问题上有更快的收敛速度,在解的质量上也有一定程度的提高。     

文化基因算法求解TSP问题的研究

TSP是组合优化问题中著名的NP-hard问题。针对粒子群算法求解离散的TSP问题收敛速度慢,求解精度低,易于陷入局部最优和模拟退火算法的性能与参数初始值有关及参数敏感等不足,提出了将改进的粒子群算法作为全局搜索策略,改进的模拟退火算法作为局部搜索策略的文化基因算法。介绍了两种算法的协同方法,定义了局部搜索邻域的确定以及在新种群产生中引入自组织随机移民策略。仿真结果表明,改进算法在求解TSP问题中具有很快的收敛速度,且能搜索到最优解。     

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

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

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

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

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

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

基于遗传-模拟退火的蚁群算法求解TSP问题

传统的蚁群算法具有收敛性好、鲁棒性强等优点,但在解决旅行商(TSP)问题方面存在收敛时间长,容易出现停滞等问题;为了提高传统蚁群算法的解的质量,本文提出了基于遗传-模拟退火的蚁群算法(G-SAACO),将遗传算法和模拟退火算法引入蚁群算法中;其方法是在传统蚁群算法中引入遗传算法的变异与交叉策略来得到候选解,增加解的多样性;同时引进模拟退火算法机制,使得在高温时以较高概率选择候选集中比较差的解加入最新集,温度控制上加入了回火机制,进一步提高解的质量;为了检验改进的蚁群算法,随机选用了TSPLIB中的部分城市进行仿真,结果与传统蚁群算法、模拟退火蚁群算法、遗传蚁群算法相比,算法具有较强的发现较好解的能力,同时增强了平均值的稳定性。     

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

利用模拟退火算法给出了求解旅行商问题的一种新方法.在模拟退火算法的基本原理基础上,针对解变换只交换两个城市而容易落入局部最优解的缺点,提出了在解变换产生新解的过程中,采用逆转操作的改进方法.这使得迭代过程突破局部最优圈,然后跳到另一个搜索空间.这样能够使其更具多样性,改善了模拟退火算法的局部搜索能力.并将其应用于求解旅行商问题,显著改善了它局部寻优的能力.在几个公共测试数据集上的结果表明,算法稳定可行,在求解组合优化问题方面,具有良好的性能.     

PCB数控钻孔最佳走刀路线的建模与求解

目前,采用PCB数控钻自动编程系统生成的钻孔路线并非最佳走刀路线。通过分析,将PCB数控钻孔最佳走刀路线问题归结为大型TSP问题,其目标函数定为钻头的总走刀时间最短。由于TSP问题在理论上属于NP完备问题,因此很难用一般的算法求解。文中详细介绍了用模拟退火方法求解该问题的具体算法,并以上继基础开发了PCB的最优化的自动编程系统。     

一种用于求解TSP问题的随机最佳插入烟花算法

TSP问题是一个NP难问题,求解时间随问题规模呈几何级数增长,如何在较短时间内求得更精确的解一直是重要的研究问题。因为烟花算法在求解过程中能够快速收敛,而且能跳出局部最优解,所以基于烟花算法改进了爆炸资源分配的方式,创新性地提出了2个算子：抛弃节点重新插入的爆炸算子和抛弃路径重新插入的变异算子。再使用精英与轮盘赌相结合的烟花选择策略,设计了一种随机最佳插入的烟花算法（RBIFWA）。将该算法与基本烟花算法、混沌烟花算法、离散蝙蝠算法和自适应模拟退火蚁群算法进行比较,结果显示,RBIFWA算法在迭代次数上明显优于其他算法,且算法的解更加接近已知最优解,表明RBIFWA算法在求解TSP问题上具有更加优秀的性能和更高的求解质量。     

一种融合模拟退火和单亲遗传的优化求解算法

度约束最小生成树是一个经典的组合优化NP难题,其在网络设计和优化中有广泛的应用;现有求解方法往往不能很好地兼顾求解效率和求解精度;为了在缩短求解时间的同时,更好地获得最优解,提出了一种结合模拟退火算法和单亲遗传算法的改进求解算法;首先,改进遗传算法中变异因子的生成方式,避免不可行解个体的产生,并且设计自适应变异率,以提高算法的求解效率;其次,针对单亲遗传算法仅有变异操作可能导致最优解个体跳跃的问题,结合模拟退火的思想,来保证解的全局最优性;最后,在具体的度约束最小生成树问题中进行了三组实验,从运行时间和最优解的情况等方面与传统单亲遗传算法进行对比,实验表明该算法在求解效率和获得最优解方面都有较好的改进效果。     

基于全局和声搜索的模拟退火算法改进

本文针对传统的模拟退火算法存在收敛速度慢的问题,采用全局和声搜索算法对其进行了改进,即在保持模拟退火原有机制的基础上,使用一个函数随机产生模拟退火算法的初始解,采用全局和声搜索算法中产生候选解的方法产生新解。该方法的优点在于保留中间最优解并及时更新,从而既保证了优化质量又提高了算法的搜索效率。最后,采用benchmark测试函数进行仿真,仿真实验结果表明,该方法在收敛速度及优化质量上都优于传统的模拟退火及其它算法,值得进一步研究。     

改进型模拟退火算法在设备布局设计中的应用

由于设备布局问题是NP完全问题，它在有限合理的时间内难以求得最优解，因此问题的求解只能依赖于各种启发式方法。文章针对传统的模拟退火算法经常出现迂回搜索，导致搜索效率低，解的质量差这一现象，通过在传统模拟退火算法搜索过程中增加记忆功能，来避免迂回搜索，将改进的模拟退火算法应用于设备布局的研究中，通过实例证明改进的模拟退火算法解的质量有了很大提高。     

基于改进模拟退火算法的生鲜农产品配送中心选址

运用传统模拟退火算法解决复杂非线性规划问题,存在降温速度与求解质量之间的矛盾,已经不能满足生鲜农产品配送中心选址的需求。为解决这一问题,本文设计一种改进模拟退火算法的生鲜农产品配送中心选址方法。其核心思路是将遗传算法与模拟退火算法融合。首先在退火过程的搜索环节引入以配送中心为编码的染色体个体,并筛选出符合目标函数参数条件的染色体集;然后应用改进模拟退火算法实现选址过程的整体优化;最后采用山东省A公司生鲜农产品配送中心选址问题进行仿真模拟。实验对比结果表明,在多次选址求解过程中,改进模拟退火算法能有效减少传统模拟退火算法在运算后期大量迂回搜索、无效搜索的问题,提升生鲜农产品配送中心选址效率。