蚁群算法在TSP问题中的应用及其优化研究

蚁群算法是一种新型的模拟进化算法。分析了蚁群算法的基本模型和算法在TSP问题中的实现方式,针对其缺陷对基本的蚁群算法进行了一定的改进。     

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

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

构建系统发生树后缀表示的蚁群算法

提出一种基于后缀表示的构建系统发生树的蚁群算法(SR-PTC),该算法用蚂蚁访问物种集合以形成一个对应最优系统发生树的后缀表示序列。为构成一个合法的系统发生树的后缀表示,蚂蚁对内部结点的选择要受到限制,分别为叶结点和内部结点设置两个不同的选择概率,并用赌轮盘选择方法来决定两种结点的选择。另外,在信息素更新时,加入当前树的评价值来影响蚂蚁的运动方向。实验结果表明,此方法能得到较为准确的拓扑结构,在物种数目较小时可以较快地得到结果。     

求解TSP的新量子蚁群算法

鉴于蚁群算法（ACA）在求解TSP时表现出的优越性,以及量子进化算法（QEA）在求解组合优化问题时表现出的高效性,将ACA与QEA的算法思想进行融合,提出一种新的求解TSP的量子蚁群算法。该算法对各路径上的信息素进行量子比特编码,设计了一种新的信息素表示方式,即量子信息素;采用量子旋转门及最优路径对信息素进行更新,加快算法收敛速度;为了避免搜索陷入局部最优,设计了一种量子交叉策略,以改善种群信息结构。仿真实验结果表明了该算法具有较快的收敛速度和全局寻优能力,性能明显优于ACS。     

基于TSP的蚁群算法研究

介绍蚁群算法的研究现状并对蚁群算法的逻辑结构进行分析,根据旅行商问题的描述,建立求解TSP的Ant Cycle蚁群算法模型,对该算法的步骤进行描述以及实现,对该算法复杂度进行分析研究,并对该算法的特点作以总结.     

应用蚁群算法求解TSP

介绍了一种求解复杂TSP的蚁群算法,阐述了该算法的基本原理、模型以及实现过程,并介绍了蚁群算法在旅行商问题(TSP)中的应用思路。     

求解TSP的改进蚁群算法*

针对蚁群算法存在的搜索时间长、易限于局部最优解等缺陷,提出了一种改进的蚁群算法。通过在初始化信息素矩阵中采用候选城市列表减少劣质解,在局部搜索中采用聚类进行二次搜索,缩小了算法的搜索范围、改善了解空间的质量,提高了搜索速度。仿真结果表明,改进后的蚁群算法在TSP的求解中,收敛速度和全局寻优能力均得到较大的提高。     

基于变异和启发式选择的蚁群优化算法

为了解决传统蚁群算法求解TSP问题的求解时间较长、易于局部收敛的问题,提出了一种基于变异和启发式选择的蚁群优化算法。利用较优路径中城市相互之间的邻接特点,避免了大范围搜索求解,使得能具有较好的初始解,将算法的时间复杂度大大降低;同时为了加快算法的收敛速度,对于路径的启发式选择进行重新定义;引入变异机制,充分利用2-交换法简洁高效的特点,既提高了变异效率,也改进了变异质量。实验结果证明,在一些经典TSP问题上新算法表现出很好的性能。     

基于粒子群优化的蚁群算法在TSP中的应用

结合粒子群算法的问题,提出用混合蚁群算法来求解著名的旅行商问题.问题的核心是应用粒子群算法对蚁群算法的控制参数:启发式因子、信息素挥发系数、随机性选择阈值进行优化,以及运用蚁群系统算法寻找最短路径.新算法对于蚂蚁算法中的参数调整大大减低,减少了大量盲目的实验,力求在开发最优解和探究搜索空间上找到平衡点.对旅行商问题的仿真实验表明,新算法的优化质量和效率都优于传统蚁群算法和遗传算法,接近理论最佳值.新算法也可推广用于其他NP问题的求解.     

基于局部优化策略求解TSP的蚁群算法*

为了克服基本蚁群算法收敛速度慢、易于停滞的缺陷,提出了一种基于局部优化策略的蚁群算法（LOACA）。该算法根据TSP的特点,采用了三种局部优化算子来交换搜索路径中城市的位置,以改进解的质量。以TSP为例进行的实验结果表明,该算法优于ACA和ACAGA。     

智能算法求解TSP问题的比较

目前TSP问题的求解方法不仅种类繁多,而且模型迥异。集中讨论求解TSP问题的智能算法,将其分为进化算法、Hopfield神经网络和自组织映射3类,对每类方法进行了原理研究、性能分析和优缺点比较。最后通过不同规模的实验进行验证,发现进化算法与局部搜索的组合求解TSP性能最好。今后的研究将集中在如何寻找更优的局部搜索。     

一种基于格的蚁群算法

针对蚁群算法容易陷入局部搜索的问题,提出了一种基于格的蚁群算法。将问题空间划分为n块格子,基于随机策略,将m只蚂蚁分别放在n块格子中,对于每个格子,再次基于随机策略,将格子内的蚂蚁放置在不同的节点上。仿真结果显示,在不影响最优解的情况下,基于格的策略加速了算法的收敛性。     

基于云模型的模糊自适应蚁群算法研究

针对蚁群算法存在控制参数难以确定和易陷入停滞等不足,采用云模型理论对蚁群算法进行改进,将云模型作为模糊隶属函数,选择部分较优路径进行全局信息素更新,从而提高算法对路径的开发和探索,同时通过对云隶属函数的参数控制,实现算法的自适应调整策略。针对TSP问题进行仿真实验对比,结果也表明基于云模型的蚁群算法要明显优于ACS和MMAS算法。     

求解TSP问题的社会演化算法

将社会演化算法和蚁群算法相结合,以蚁群算法作为认知主体的推理过程,再以范式的学习和更新方式获得最优解,提出一种求解TSP问题的社会演化算法。最后通过两个算例实验仿真与TSP已知最优解进行对比分析,结果表明,社会演化算法在种群规模较小,迭代次数较少的情况下也可获得TSP最优解。     

新型的双种群蚁群算法

基于对蚂蚁种群中兵蚁和工蚁在觅食过程中合作关系的仿生,提出了一种改进型蚁群算法。在该算法中同时存在着兵蚁子种群与工蚁子种群两个种群,两个子种群并行搜索,通过兵蚁的分布来影响到工蚁的移动选择,以取得各蚂蚁子群体中解的多样性和收敛性之间的动态平衡。基于旅行商问题的实验证明,算法具有较好的全局搜索能力和收敛速度。     

一种基于路径相似度的蚁群算法

提出了路径相似度的概念,并根据较优可行解与最优解的相似度,来进行路径选择和信息素更新,以求能更快加速收敛和防止早熟、停滞现象。该算法根据截之间的相似度,自适应地调整路径选择策略和信息量更新策略。基于旅行商问题的实验验证了算法比一般蚁群算法具有更好的全局搜索能力、收敛速度和解的多样性。     

改进的求解TSP问题文化蚁群优化方法

在文化算法基础上提出了一种改进的用于求解TSP问题的蚁群优化算法。改进算法采用新的双层进化机制对文化算法的种群空间与信念空间进行了重新设计,用最大最小蚁群系统（MMAS）构建种群空间,在信念空间中对当前最优解进行改进的3-OPT交叉变换操作,由于采用了这种双层进化机制,种群空间获得了更高的进化效率。通过仿真实验结果表明,改进算法比传统的蚁群算法（ACO）、文化蚁群算法（CACS）效果更好,收敛速度更快,精确度更高。