蚁群算法实现求解TSP问题

蚁群算法是一种模拟自然界蚂蚁群体觅食的仿生优化算法,本文主要介绍了蚂蚁系统算法的基本原理,并应用该算法使用C语言编程解决TSP问题,并对算法进行了时间复杂度的分析,证明了该算法的有效性。     

求解TSP问题的自适应离散型布谷鸟算法

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

求解TSP算法

首先提出旅行商问题（TSP）,并将其转化为最短有向图哈密尔顿回路问题,然后介绍了三种类型的求解TSP的算法。第一种为传统算法,包括分支定界法、改良回路法、贪婪算法、MST算法、MM算法、插入法等;第二种为现代优化算法,包括模拟退火算法、人工免疫算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络算法等;第三种为论文提出的DNA计算算法。并对这些算法的复杂度、误差范围以及优劣点进行了分析。     

禁忌搜索求解TSP问题

本文采用改进的禁忌搜索算法求解TSP问题,该算法是通过禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,最终实现全局优化。实验结果证明该算法的可行性。     

基于聚类集成的蚁群算法求解大规模TSP问题

ACA（Ant Colony Algorithm）是一种可以有效求解组合优化的TSP（Travelling Salesman Problem）问题的方法。然而,当TSP问题的规模较大时,该算法的求解性能将会明显减弱。本文针对大规模TSP问题提出一种基于聚类集成的蚁群算法IAPACA（Improved AP Ant Colony Algorithm）的求解方法。利用AP（Affinity Propagation）聚类对大规模旅行商问题进行处理,将大规模旅行商问题分为若干子问题,并对每个子问题用蚁群算法进行寻优。然后用改进的集成方案对子问题进行组合,得到问题的结果。最后进行TSPLIB标准库测试算例的实验仿真,实验结果表明,基于聚类集成的蚁群算法具有更好的求解效果。     

TSP问题的蚁群算法求解

群集智能是近年来人工智能领域研究的一个新的热点课题,本文介绍了蚁群算法的原理及求解TSP问题的具体实现步骤。     

求解TSP问题的多线程演化算法

提出了一种基于单处理器的多线程演化算法。该算法着重于发挥线程之间通讯高效的特点,充分利用演化线程之间大量的通讯,避免演化计算的过早收敛。求解TSP（traveling salesman problem）问题的实验结果表明,该算法大大地提升了原简单演化算法解的质量,而且该算法的解也明显优于使用相同简单演化算法实现的基于孤岛模型的分布式演化算法所得到的解。     

混合蛙跳算法求解TSP问题

蛙跳算法中子种群的进化方式对问题求解性能影响很大。本文在蛙跳算法的子种群进化中使用了高效的演化算子。通过数据集pr76和berlin52进行仿真试验,仿真结果证实了算法的有效性。     

改进的猫群算法求解TSP问题

针对了求解TSP问题给出一种新算法,改进的猫群算法。猫群算法,作为一种群智能优化算法,有较快的收敛速度、向“他人”学习等优点,但国内目前对它的研究还处在起步阶段,所以做这方面的尝试性研究。通过引入交换子概念和改进猫的行为模式将算法用于求解TSP问题。最后通过MATLAB仿真,并将实验结果与已知最优解相比较,验证了该算法的有效性。故不仅拓宽了猫群算法的应用范围,也给求解TSP等路径优化问题提供一种新的解决办法。     

一种结合局部搜索策略的求解TSP的演化算法

介绍了一种结合局部搜索策略的求解流动旅行商问题（TSP）的演化算法。该算法的主要思想是将局部搜索策略在邻域内搜索的快速性与演化方法在全局搜索上的鲁棒性结合起来，从而跳离局部最优。将该算法用于TSPLIB中部分TSP实例上的试验结果表明：与传统的各种求解TSP的演化方法相比，该算法在获得全局最优解的精确度上有了一定的改善。     

基本蚂蚁算法中参数的讨论与改进

从基本蚂蚁算法出发,结合实验结果,讨论了ρ、Q及α、β的变化对实验结果的影响,提出了相应的参数改进方案。并将经此方案修正的蚂蚁算法与基本蚂蚁算法同时运用于经典TSP问题中,对仿真结果进行了比较。     

蚁群算法在K-TSP问题中的应用

针对K-TSP(K—person Traveling Salesman Problem)问题,该文提出了一种利用蚁群算法求解该问题的新思路。该算法采用k只蚂蚁共同构造问题的一个解,并通过多组(每组k只)蚂蚁相互协作最终达到搜索最优解的目的。实验结果显示,该算法行之有效,是一种求解K-TSP问题的有效算法。     

基于竞争演化算法的TSP求解

针对NP完全问题的TSP问题,该文提出了一种属于启发式算法的竞争演化算法。并用构造能量函数的方法证明,用这种算法能使能量函数减小。最终必找到一条有意义的路径。微机仿真结果说明,这种算法能在较少的迭代步骤内找出一条较短的路径。     

一种求解TSP问题的多种群并行遗传算法

遗传算法是一种基于自然群体遗传机制的有效搜索算法,由于它在搜索空间中同时考虑许多点.减少了收敛于局部极值的可能,也增加了处理的并行性.因此可以利用并行遗传算法研究典型的TSP问题的求解.提出一种有效的多种群并行算法求解旅行商(TSP)问题,应用多种群遗传并行进化的思想,并在种群之间进行遗传信息交流,以解决经典遗传的收敛到局部最优值问题.仿真实验结果表明,方法在解的精度上以及解的质量上优于经典的遗传算法.     

一种改进的遗传算法及其在TSP中的实现

TSP问题是典型的NP完全问题，遗传算法是求解NP完全问题的一种方法。文章针对TSP问题．提出了一种改进的遗传算法。在遗传算法中引入进化算法的思想，在此基础上提出顶端培育策略和分阶段策略，以求在保证群体多样性的同时加快收敛速度。在算法的仿真和测试中，改进后的算法明显优于传统的遗传算法。这表明，该算法具有良好的可行性和实用性。     

基于混合杂交的遗传算法求解旅行商问题

通过混合使用多种杂交算子,提出了一种求解旅行商问题的新型遗传算法,并给出了实验验证。通过实验用该算法求解了城市数为50到100不等的旅行商问题,获得了比其它算法更精确或更接近最优的解,表明了算法的有效性。     

人工神经网络求解TSP问题新方法

本文在分析Hopfield/Tank方法的基础上提出一种新的人工神经网络方法,采用优化约束条件的能量函数,具有收敛速度快、不易陷入无效解、易获得亚优解等优点。     

小窗口蚁群算法

在蚁群算法的基础上,提出了小窗口蚁群算法。通过对旅行商问题解集的分析,找到其最优解的特点,通过限定蚂蚁每次只向距离最近的几个城市移动,大大缩小其搜索范围,减少对算法中主要参数的依赖,提高其搜索精度并减少搜索时间。实验结果表明该算法有较好的效果。     

大规模旅行商问题的竞争决策算法

针对旅行商问题,利用竞争决策算法的通用模型,给出了一种基于竞争决策思想,能求解大规模和超大规模TSP问题的快速求解方法,经过大量数据测试和验证,获得了较好的结果.