一种基于遗传算法求解TSP问题的优化算法

旅行商问题是组合优化的一个经典问题,也是评价算法好坏的一个标准,它要求在给定的一张图中寻找一条哈密尔顿回路,使得该回路在所有的回路中长度最短。然而,该问题是一个NP完全问题,其求解时间会随着问题规模的扩大急剧上升。因此,只能希望在允许的时间内寻求问题的一个较优的解来替代。本文借助生物学的相关理论与思想采用遗传算法对该问题进行求解,最后通过对遗传算法的进一步分析,提出了一种可行的改进算法,达到了获得较优解的目的。     

组合优化问题的启发式搜索

组合优化是一个离散最优化问题,在规划,调度,资源分配,决策等问题中有着非常广泛的应用。入们已经认识到,组合优化问题的计算复杂度高,属于NP难一类的问题,除了枚举一部分解空间之外,     

一类约束优化问题的改进遗传算法

遗传算法是一种解决非线性无约束优化问题的搜索算法，对于约束优化问题通常采用罚函数法；所提出了的改进算法很好地解决了一类带有凸约束的非红性优化问题。数值结果说明该方法效果较好。     

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

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

旅行商问题(TSP)的一种改进遗传算法

传统的序号编码遗传算法(GA)使用PMX、CX和OX等特殊的交叉算子，这些算子实施起来很麻烦。针对TSP问题的求解，提出了一种新的改进遗传算法：单亲进化遗传算法(PEGA)，PEGA是利用父体所提供的有效边的信息，使用保留最小边的方法进行个体的进化。与传统的遗传算法相比，PEGA算法弥补了它们的不足之处，简化了遗传算法。给出了PEGA算法的数值算例，仿真实验表明了该算法对于对称的TSP和非对称的TSP问题，都具有收敛速度快的特点，证明了该算法的有效性。     

基于遗传算法的TSP优化问题

TSP问题是一个典型的组合优化问题,并且也是一个NP难题,其可能的路径总数与城市数目n成指数型增长,一般很难精确地求出其最优解。这里对BP问题提出了一种改进的遗传算法,通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试,实验结果证明此处提出的方法能更有效的求解TSP问题。     

基于免疫遗传算法的装箱问题求解

装箱是一类典型的ＮＰ完全问题．本文用一种免疫遗传算法来研究装箱问题的求解．免疫遗传算法在传统遗传算法的全局随机搜索基础上,借鉴生物免疫机制中抗体的多样性保持策略,大大提高了算法的群体多样性,实验表明,免疫遗传算法具有很好的全局收敛性,能有效解决装箱问题．     

基于学习的遗传算法及其在布局中的应用

布局问题属于具有很强应用背景的组合优化问题,除其内在的NP完全的计算复杂性,布局还包括约束复杂性问题和布局物体与空间的形状复杂性问题。针对布局求解中存在的问题,该文进行了基于全局优化的布局求解方法研究。布局问题中有一类关于复杂分片光滑连续函数全局优化算法,但目前的各种遗传算法的效率和精度不能令人满意。文中从生物可以从环境中学习生存技巧、自主的趋利避害的思路出发,增加了学习算子,引用函数的局部信息,构造拟牛顿方向,令每个个体在当前状态下有目的地搜索,最有效的向局部最优点趋进。通过典型测试函数与传统遗传算法,模拟退火算法,复合形法进行比较验算,表明该算法具有优良的求解质量和较好的求解效率;并以旋转卫星舱布局的简化模型为背景,建立多目标优化数学模型,与传统遗传算法和乘子法的计算结果比较,该算法求解的质量和效率更优。该文研究表明,基于学习的遗传算法在布局优化中具有应用潜力;启发式随机搜索策略和局部优化算法相结合的求解方案是解决复杂函数优化的有效途径。     

一种改进遗传算法在旅行商(TSP)问题中的应用

遗传算法（GA）是一种基于自然群体遗传机制的高效搜索算法，由于它在搜索空间中同时考虑许多点。这样就减少了收敛于局极小的可能，同时也增加了处理的并行性。因此，可以利用遗传算法研究典型的组合优化实例－TSP问题的求解问题。本文采用了启发式三交叉算子并提出了一种全新的变异算子，使得收敛速度更快，能更有效的解决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问题的自适应离散型布谷鸟算法

对于求解的TSP问题,提出了一种自适应离散型布谷鸟算法（Adaptive Discrete Cuckoo Search,ADCS）。在基于布谷鸟搜索算法（Cuckoo Search,CS）的搜索原理下构造TSP问题的路径求解策略。针对离散型算法整体调整容易破坏已形成的较优路径和随着算法迭代数目增加导致种群多样性下降这两个缺陷,设计了一种针对路径的自适应型局部调整算子和全局随机扰动策略,采用了简单的2-opt优化算子作为局部优化算子以加快算法的收敛速度。最后采用多组不同规模的标准TSPLIB数据与其他的优化算法进行对比实验,结果表明ADCS算法在求解精度和稳定性方面具有优势。     

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

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

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

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

一种基于遗传Hopfield神经网络求解TSP问题的算法

针对Hopfield网络求解TSP问题时出现无效解和收敛性能差的问题,对约束条件能量函数进行改进,构造了一种求解TSP问题的遗传Hopfield神经网络算法,并与经典Hopfield神经网络求解TSP方法进行对比.实验结果表明,本文算法具有更好的整体求解性能.     

求解TSP的改进量子蚁群算法

将量子群进化算法(QEA)与蚁群系统(ACS)进行融合,提出一种新的量子蚁群算法(QACA).该算法的核心是在蚁群系统(ACS)中引入量子算法中的量子的态矢量和量子旋转门来分别表示和更新信息素.该算法在全局寻优能力和种群多样性方面比蚁群算法有所改进,并结合TSP,对算法进行了测试,得到了与现有文献结果相同或更好的解,表明该算法是求解TSP的一种有效的算法.     

改进的免疫算法求解TSP问题

针对TSP问题,提出基于人工免疫理论的提取免疫疫苗和注射疫苗的新算法对免疫算法进行适当的改进,给出了新的疫苗结构,以提高算法求解问题的迭代速度。实验结果表明,改进的免疫算法较原免疫算法在求解TSP问题时具有更快的收敛速度。     

压缩搜索空间的遗传算法在TSP中的应用

旅行商问题的可能解与城市规模n是成指数型增长的,因此规模越大解决越困难.通过设计能够对搜索空间进行压缩的遗传算法,依靠搜索过程中已得到的近优解的信息,可以降低随机搜索的盲目性并加速算法收敛速度.首先利用不完全演化得到一组近优解,然后通过比较近优解获得解的相同模式,将搜索空间划分为一个或多个最优解域,再进行局部的优化,来提高求解速度和解的质量,并用TSP问题进行了验证.