共查询到18条相似文献,搜索用时 62 毫秒
1.
TSP问题是典型的NP—hard组合优化问题,蚁群算法是一种求解此类问题的优化算法,通过模拟蚂蚁觅食行为来解决NP问题。文章使用蚁群算法求解TSP问题,并结合TSP问题的特点选择了一种合适的蚁群更新策略。 相似文献
2.
针对标准蚁群算法在求解旅行商问题(TSP)时存在收敛速度慢,易陷入局部最优等缺陷,提出一种自适应蚁群优化算法.该算法设计了一种实时监测机制和一种新的搜索方向,实时监测机制可以让算法跳出局部最优值,并且当算法跳出局部最优值时,沿着新的搜索方向搜索,可以加快算法收敛到全局最优.通过对典型的TSP实例仿真实验,与基本蚁群算法、MMAS算法相对比,结果显示该算法在克服早熟现象和收敛速度方面有很大的优越性. 相似文献
3.
求解TSP问题的改进蚁群算法 总被引:10,自引:1,他引:10
分析了标准蚁群算法易于出现早熟停滞现象的主要原因,在原有算法基础上引入局部信息激素、最优最差路径信息激素更新策略及变参数策略,扩大了解的搜索空间,有效抑制了收敛过程中的早熟停滞现象,大大提高了算法收敛速度;同时引入局部最优搜索策略,增大了解突变的机率,求解质量得到了极大的改善.对于典型旅行商问题库中旅行商问题的实验及与标准蚁群算法的比较实验验证了该方法的有效性. 相似文献
4.
蚁群优化算法在TSP中的应用 总被引:2,自引:3,他引:2
提出了一种求解TSP问题的有效算法———蚁群优化算法。该算法通过模拟蚁群搜索食物的过程,求解TSP问题。算法的主要特点是,正反馈、分布式计算、与某种启发式算法相结合。并给出了算法原理及流程;最后用计算机仿真得出结果,证明了该算法的有效性。 相似文献
5.
针对旅行商问题(TSP),研究了网络地理信息系统(WebGIS)中的蚁群优化算法(ACO)在其问题上的应用.为提高蚁群优化性能,采用一种空间拓扑结构与蚁群优化算法结合,并引入了局部搜索策略2-opt.在城市数目一定的情况下,改进蚁群算法能够得到所求TSP的全局最优解,与遗传算法和模拟退火算法比较,它具有更快的收敛速度和更高的收敛精度,并可扩展到一类相关的组合优化问题之中.结果表明,改进蚁群算法对于求解TSP问题效果是很明显的. 相似文献
6.
赵越 《吉林建筑工程学院学报》2009,26(5):71-74
通过分析蚂蚁在觅食过程中对最短路径的搜索策略,给出蚁群算法在求解旅行商问题(TSP)中的应用,并使用3—opt方法对所求问题的解进行局部优化,实验结果证明了该解决方案的有效性. 相似文献
7.
为保持所求得的多目标优化问题Pareto最优解的多样性,文章提出了一种新的蚁群算法。选择策略采用多信息素权重,信息素更新结合了局部信息素更新与全局信息素更新。其中,全局信息素更新采用了两个最好解。此外,通过在外部设置外部集来存储Pareto解,并将改进的算法应用在双目标TSP上。最后进行了仿真实验,结果表明新方法比NSGA-II和SPEA2更有效。 相似文献
8.
蚁群算法是一种群智能算法,可用于求解图模型最优化路径的计算问题.它于1992年由Dorigo M.提出,借鉴蚂蚁在蚁群与食物之间寻找最短路径.本文集中讨论了几种典型的求解旅行商问题的蚁群算法扩展,讨论其相应的优缺点,并对其学术与工业的应用领域与合理发展进行了总结与展望. 相似文献
9.
求解TSP问题的快速蚁群算法 总被引:2,自引:0,他引:2
针对蚁群算法求解旅行商问题时存在收敛速度慢并容易陷入局部最优的问题,提出了一种改进的蚁群算法。改进算法采用信息素挥发因子自适应调整机制,调节算法收敛速度,保证算法的全局搜索能力。同时根据公共路径降低蚁群算法运算时间,诱导蚁群寻找更优解。实验结果表明,改进算法在迭代次数相对较少的情况下求得的平均解与已知最优解偏差为0.46%,最优解与已知最优解偏差为0.23%,在收敛速度及求解精度上均取到了较好的效果。 相似文献
10.
11.
一种基于免疫蚁群混合算法的TSP求解模型 总被引:1,自引:0,他引:1
为了解决传统蚁群算法搜索速度慢、容易出现早熟、停滞的缺点,以及传统免疫算法由于反馈信息利用不足存在大量无为的冗余迭代导致求解效率低的缺点,提出了一种蚁群与免疫克隆相结合的混合算法,该算法在前期采用免疫算法来产生蚁群算法的初始信息分布,在后期根据路径浓度抑制机制调整路径上的信息量,从而保持了蚁群多样性,并将该算法用于求解旅行商问题进行计算机仿真,从实验结果可以看出,该算法具有针对性的改进,是一种收敛速度和寻优能力都较好的优化方法. 相似文献
12.
基于聚类和分段优化的蚁群算法 总被引:2,自引:0,他引:2
针对蚁群算法在求解大规模旅行商问题(TSP)时精度和时间方面的不足,提出了一种新的算法,该算法采用多阶段的蚁群寻优策略.算法的复杂度分析及在大规模TSP问题上的实验表明:该算法在保证获得较好解的前提下收敛速度得到了较大的改进. 相似文献
13.
围绕TSP问题研究了基本蚁群算法.在此基础上,研究了串行蚁群算法的并行策略,使用C++语言调用MPI接口函数实现了并行蚁群算法.最后,分析研究了影响并行蚁群算法的因素,采用了更高效的信息素更新和变参数机制对并行蚁群算法进行了改进.通过仿真实验分析表明,改进的并行蚁群算法有较广泛的适用性,与基本蚁群算法相比,具有更高的精度和更短的收敛时间. 相似文献
14.
基于改进蚁群算法对最短路径问题的分析与仿真 总被引:2,自引:0,他引:2
使用传统蚁群算法求解图的最短路径问题时,随着节点的增加会出现搜索速度变慢且易于陷入局部最优解.针对这个问题,提出一种改进的蚁群算法,通过引入搜索方向和搜索热区机制提高算法的搜索性能.仿真实验证明:改进的蚁群算法较传统的蚁群算法具有更高搜索速度且容易得到全局最优解. 相似文献
15.
基于边缘搜索的蚁群算法 总被引:1,自引:0,他引:1
蚁群算法是根据真实蚁群的觅食原理提出的一种新兴的启发式搜索算法。算法应用于解决组合优化问题,取得了良好的效果。定义了一种新的旅行商问题,即过程旅行商问题,针对这个问题提出了一种基于边缘搜索的改进蚁群算法。该算法通过限制蚂蚁的起点城市,提高了蚁群算法的搜索效率;并通过减少蚂蚁数量加快计算速度。应用于过程旅行商问题的仿真计算表明,该算法具有相同的计算结果和更快的求解速率。 相似文献
16.
翟梅梅 《淮南工业学院学报》2009,(3):58-63
遗传算法具有快速全局搜索能力,但对于系统中的反馈信息却没有利用,往往导致无为的冗余迭代,求解效率低。根据这一缺陷提出一种将蚁群算法融合到遗传算法的新策略:为了弥补遗传算法中的变异算子变异过程中的盲目无原则性,将蚁群算法的正反馈思想引入到遗传算法中。利用蚁群算法信息素更新原则指导变异规则,有效地提高了算法的寻优效率,优化了解的质量。为了验证算法的有效性,对TSPLIB库中的两个公共实际事例eil51和gr202以及安徽省17个城市的数据进行了仿真实验,结果表明改进后的算法是有效的。 相似文献
17.
基于MPI的并行蚁群算法的研究与实现 总被引:1,自引:0,他引:1
在消息传递接口(message passing interface,MPI)的基础上,采用划分蚁群的策略,实现了基于MPI的并行蚁群算法,并对该算法采用旅行商问题进行了实验.实验结果表明,使用并行计算技术,可以很好地提高运行速度. 相似文献