求解TSP的一种改进遗传算法

TSP问题是典型的NP-hard组合优化问题,GA是求解此类问题的一种方法。但它存在如何较快地找到最优解并防止“早熟”收敛的问题。文章针对上述问题并结合TSP问题的特点,提出了改进的遗传算法。它从相似性的思想出发,按适应值相似性将群体分级,在不同的级内采用不同的操作,产生数目不等的新解并利用加速算子使其更接近局部极小值。改进后的算法较好地解决了群体多样性与收敛性的矛盾。实验结果表明,该文算法的改进是有效的。

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

针对遗传算法求解TSP问题解质量不高的缺陷,该文提出并设计了一种基于遗传算法的多策略优化求解方法。首先,应用最邻近法构建TSP的初始解;接着将路径长度作为适应度评价指标,构建基于遗传算法的TSP初始解优化方法,并根据试验结果确定适合的遗传算法参数;然后,针对遗传算法易陷入局部最优的缺陷,借助去交叉和小角操作进一步优化TSP解路径;在此基础上,将遗传算法进行并行化处理,通过增加遗传算法的多样性提高TSP解质量。最后,应用标准测试集(TSPLIB)进行试验,结果表明:该算法能有效提高TSP解的质量,经并行遗传算法、去交叉和小角优化后各测试数据集TSP解误差率平均下降了22.57%;解的误差率均在7.94%以内,质量明显优于最邻近法、插入法、2-Opt优化等传统方法;在节点数多的测试数据集中算法也获得了良好加速性能,8进程时算法加速比达2.51。

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

文章针对TSP问题,运用一种新的巡回路线编码方法和基于个体浓度的群体更新及个体多样性保持策略,提出了一种改进的遗传算法,在解决该类问题上取得了较显著的效果。

遗传算法的自适应进化策略及TSP问题的遗传优化

本文研究遗传算法的进化策略，提出了一种在遗传操作层次上将局部搜索方法与基本遗传算法相结合，依据遗传群体的环境参量动态地调整遗传算法的进化策略和控制局部搜索强度的自适应进化策略，并结合货郎担（ＴＳＰ）优化问题介绍其具体实现方法，给出实验结果．

改进的分布式并行遗传算法求解大规模TSP问题

TSP问题的应用十分广泛,而传统的遗传算法在求解TSP问题时存在求解精度低和时间长等不足。针对该问题提出了一种改进的分布式并行遗传算法用来求解大规模TSP问题。改进遗传算法使父代染色体进行顺序交叉、就近变异和局部最优选择,将大规模TSP问题用k-均值聚类算法进行分组,使用分布式并行算法将子问题分配到不同的计算节点上用改进的遗传算法求解。求解得到的子问题用Delaunay三角剖分算法进行合并,从而得到整个问题的解。通过TSPlib数据库进行实验,结果显示提出的算法在求解时间和求解精度上均有所提高。

基于贪心策略的混合遗传算法在TSP中的实现

由于标准遗传算法初始种群是随机产生的,可能导致算法的收敛速度较低,并陷入局部最优解.为了解决这一问题,提出了一种改进的遗传算法.改进后的遗传算法先用贪心算法产生初始种群,使算法能够更快地达到最优解.选择操作时采用竞标赛方法,在每代进化结束后立即采取了末尾淘汰机制,从而使适应度高的个体被选中的概率增大.并用模拟退火算法改善其局部搜索,通过仿真实验可以看到,提出的邻近倒位变异以及新的非零递减自适应函数可以进一步提高算法的运行效率.

遗传算法求解TSP的进化策略

本文提出用遗传算法（ＧＡ）求解旅行商问题（ＴＳＰ）的一整套进化策略，包括染色体的编码、反向运算、循环运算、交换运算．其中除反向运算外，均与通常的ＧＡ算法所采用的策略不同．文中解释了它们的几何意义．用该算法求解中国３１个城市的ＴＳＰ问题得到了１５４０４公里的新的路径长度．

求解TSP的改进遗传算法

遗传算法是求解旅行商问题的一种全局优化概率搜索算法方法.文中针对遗传算法较快的找到最优解并防止"早熟"收敛问题,提出了一种新的分级方法,该方法在各级中以群体当前最优个体替代各级中的最差个体,并在各级中采用自适应变异概率,改进后的遗传算法不但有效的维持了群体的多样性,而且提高了收敛速度.最后实验表明,改进的算法是可行和有效的.

一种GASA混合优化策略

结合遗传算法的并行搜索结构和模拟退火的概率突跳性 ,提出了一种高效的GASA混合优化策略 .基于典型TSP问题的仿真研究表明 ,混合策略的优化性能较单一算法和启发式算法有很大改善 .

基于多种群多策略的混合遗传-蚁群算法及应用研究

为了充分利用蚁群算法的并行、正反馈机制、高效求解和遗传算法的随机、快速以及全局收敛等优点,在分析遗传算法的选择、交叉、变异等策略和蚁群算法的寻优策略基础上,基于多种群和多策略,提出一种带有参数自适应调整的混合遗传-蚁群(HPSGAO)算法。在HPSGAO算法的每次循环中,遗传算法获得最优解用于初始化蚁群算法的信息素分配,以实现遗传策略和蚁群策略的有效结合,动态平衡HPSGAO算法的收索范围与收敛速度间的矛盾,进而提高HPSGAO算法的全局择优能力。为了验证提出混合遗传-蚁群算法的优化性能,选择10个TSP问题进行测试,仿真实验结果表明,在多次循环后,HPSGAO算法具有遗传算法和蚁群算法的优势互补,以及较好的求解效率。

基于近邻策略的旅行商问题求解

根据TSP问题的特征信息并借鉴邻域搜索算法的有关思想,提出了一种基于近邻策略的TSP问题求解算法,该算法首先依据TSP问题的特殊性求出相应的近邻模式,再将近邻模式用于初始种群的生成,而后在进化过程中随机引入这类模式。该算法可以大大缩短遗传进程,提高进化效率。通过仿真实验,验证了该算法的有效性,并且随着城市数目的增加其优越性更为明显。

基于多算法改进的遗传策略

本文通过蒙特卡洛、最近邻、2-opt、3-opt、最远插入、Christofides等算法改进了算法性能和精确度,同时引入了俄罗斯轮盘赌等相关数据操作手段,综合了多种算法的优缺点,基于效率和准确度提出了新的改进方案.在对数十组数据进行评测后,对结果进行了可视化处理,达到了预期的收敛速度和度量标准.与传统的模拟退火及遗传算法等启发式算法相比,该算法采用了更加合理的初始解选取方法,采用了适合大多数数据的淘汰准则及计算标准,精度损失控制在2%~5%.通过各种算法的精度对比和数理逻辑推算,表明在该改进方法下误差降低了近10%.

快速求解巡回施行商问题的遗传算法策略

传统的遗传算法收敛速度与问题解的质量是影响算法寻优性能的一对矛盾。该文提出一种新的遗传算法的控制策略——精英子空间算子、变交叉概率Pc和变异概率Pm算子和变维子空间算子。实例计算表明该算法收敛速度快,可以进一步改善遗传算法的性能。

(N+M)容错系统优化模型求解的父代保留免疫遗传算法

针对(N+M)容错系统优化模型复杂非线性的特点,结合免疫遗传算法和父代保留策略,提出了模型求解的父代保留免疫遗传算法。该算法在进行交叉和变异操作后,新产生的个体不覆盖父代个体,扩展种群进行基于矢量距浓度机制的选择操作,这样可避免较优个体的损失,增强种群的多样性,提高算法的搜索能力及收敛性能。算法性能分析揭示了算法性能改善的机理。优化模型求解结果表明,该文提出的算法较免疫遗传算法在寻优精度和收敛速度方面有一定改善。