首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
蚁群算法实现求解TSP问题   总被引:1,自引:0,他引:1  
郝春梅  吴波 《微计算机信息》2012,(9):480-481,233
蚁群算法是一种模拟自然界蚂蚁群体觅食的仿生优化算法,本文主要介绍了蚂蚁系统算法的基本原理,并应用该算法使用C语言编程解决TSP问题,并对算法进行了时间复杂度的分析,证明了该算法的有效性。  相似文献   

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

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

5.
肖驰 《福建电脑》2011,27(9):110-111
本文采用改进的禁忌搜索算法求解TSP问题,该算法是通过禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,最终实现全局优化。实验结果证明该算法的可行性。  相似文献   

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

7.
TSP问题的蚁群算法求解   总被引:1,自引:0,他引:1  
群集智能是近年来人工智能领域研究的一个新的热点课题,本文介绍了蚁群算法的原理及求解TSP问题的具体实现步骤。  相似文献   

8.
求解TSP问题的多线程演化算法   总被引:1,自引:4,他引:1  
李程俊  张求明 《计算机工程与设计》2005,26(7):1744-1746,1750
提出了一种基于单处理器的多线程演化算法。该算法着重于发挥线程之间通讯高效的特点,充分利用演化线程之间大量的通讯,避免演化计算的过早收敛。求解TSP(traveling salesman problem)问题的实验结果表明,该算法大大地提升了原简单演化算法解的质量,而且该算法的解也明显优于使用相同简单演化算法实现的基于孤岛模型的分布式演化算法所得到的解。  相似文献   

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

10.
基于免疫算法的TSP问题求解   总被引:40,自引:2,他引:40  
描述了免疫算法的一种框架结构,并给出了用此免疫算法求解TSP问题的具体实现方法,求解结果体现了免疫算法的良好性能。  相似文献   

11.
李力  张秀丽  周婕  靳蕃 《计算机工程》2003,29(15):40-41,77
针对NP完全问题的TSP问题,该文提出了一种属于启发式算法的竞争演化算法。并用构造能量函数的方法证明,用这种算法能使能量函数减小。最终必找到一条有意义的路径。微机仿真结果说明,这种算法能在较少的迭代步骤内找出一条较短的路径。  相似文献   

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

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

14.
基于混合杂交的遗传算法求解旅行商问题   总被引:4,自引:0,他引:4  
郑立平  郝忠孝 《计算机工程》2005,31(20):168-169,172
通过混合使用多种杂交算子,提出了一种求解旅行商问题的新型遗传算法,并给出了实验验证。通过实验用该算法求解了城市数为50到100不等的旅行商问题,获得了比其它算法更精确或更接近最优的解,表明了算法的有效性。  相似文献   

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

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

17.
黄鉴  彭其渊 《计算机应用研究》2013,30(12):3583-3585
为了改善和声记忆库群体多样性, 提高算法的全局寻优能力, 在度量群体多样性指标的基础上, 从参数动态调整方法、和声记忆库更新策略两个方面对基本和声搜索算法进行了改进, 提出了多样性保持的和声搜索算法, 并将该算法应用于TSP的求解。结合TSP问题特点, 设计了基于交换和插入算子的和声微调方法。实例优化结果表明, 改进后的算法不容易陷入局部最优, 优化性能显著提高。  相似文献   

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

19.
基于遗传算法求解TSP问题的一种算法   总被引:12,自引:1,他引:12  
TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。利用交换启发交叉算子实现局部搜索加快算法的收敛速度和利用变换变异算子维持群体的多样性防止算法早熟收敛,给出了一种求解TSP问题的遗传算法。仿真实验结果表明了该算法的有效性和可行性。  相似文献   

20.
基于局部优化策略求解TSP的蚁群算法*   总被引:7,自引:3,他引:4  
为了克服基本蚁群算法收敛速度慢、易于停滞的缺陷,提出了一种基于局部优化策略的蚁群算法(LOACA)。该算法根据TSP的特点,采用了三种局部优化算子来交换搜索路径中城市的位置,以改进解的质量。以TSP为例进行的实验结果表明,该算法优于ACA和ACAGA。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号