共查询到17条相似文献,搜索用时 109 毫秒
1.
钟文亮 《微电子学与计算机》2006,23(Z1):183-186
通过选择合适的算子和参数,遗传算法(GA)可以有效求解旅行商问题(TSP)。GA通常可以获得满意解,但容易陷入早熟,因而较难求得全局最优解。传统的变异算子在求解该问题时性能并不理想,甚至会引起反作用。文章通过实验分析多种变异算子在求解TSP时的表现,提出了一个改进的破坏重建变异法,并利用该方法对算法进行优化。经仿真实验测试,该方法效果明显。 相似文献
2.
针对蚁群算法加速收敛和早熟停滞现象的矛盾,根据遗传算法的交叉算子、变异算子和粒子群算法的粒子极值,采用一种优化蚁群算法,以在加速收敛和防止早熟停滞现象之间取得更好的平衡.在利用该算法解决TSP问题中,当前解与个体极值和全局极值分别进行交叉操作,产生的解为新的位置信息.通过对50个城市问题进行实验,结果表明,该方法比一般蚁群算法具有更好的收敛速度和稳定性,适合于求解大规模的问题. 相似文献
3.
4.
5.
一种快速求解TSP问题的遗传算法 总被引:9,自引:1,他引:8
文章受求最短路径算法的启发,提出一个启发算子用于遗传算法求解TSP问题,通过50,144,150等城市的TSP问题求解,表明该算法求解速度快并且解的质量也非常好。 相似文献
6.
对遗传算法求解TSP问题进行了完整的描述。介绍几种交叉算子和变异算子,并对其作了比较。提出对算法的交叉概率、变异概率进行自适应调整以维护群体多样性,防止算法过早收敛。 相似文献
7.
8.
改进的量子进化算法及其在TSP问题中的应用 总被引:1,自引:0,他引:1
针对量子进化算法(Quantum—inspired Evolutionary Algorithm,QEA),在解决实际问题中遇到的困难,提出一种改进的量子进化算法,应用于求解旅行商问题(Travelling Salesman Problem,TSP),并提出了TSP中的Hamilton圈的随机搜索编码技术。通过求解TSP问题库中的部分问题,表明改进的算法比经典的量子进化算法及免疫遗传算法具有更快的收敛速度和更好的全局寻优能力。 相似文献
9.
混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)是解决组合优化问题的有效方法,’但是应用于TSP问题时,由于SFLA没有充分利用最佳个体的优良信息,导致收敛速度太慢。文中把遗传算法(Genetic Algorithm,GA)的交叉和变异引入SFLA,提出了一种针对旅行商问题(Traveling Salesman Problem,TsP)的改进混合蛙跳算法(Improved Shuffled Frog Leaping Al—gorithm,ISFLA)。应用于TSP的实验结果表明:ISFLA的收敛速度明显高于SFLA,同时优于GA和简单翻转算子。ISFLA不仅表现出了更快的收敛速度,而且能有效地缓解局部早熟收敛。 相似文献
10.
11.
改进的演化近似算法求解TSP问题 总被引:2,自引:1,他引:1
TSP是典型的具有NPC复杂性的组合优化问题。在演化算法的基础上,提出了一种有效求解TSP问题的近似算法IEAA。IEAA采用单性生殖方式,通过保留一组较优个体加速了算法的收敛。详细介绍了的算法的设计和实现.并用于求解CTSP问题,实验结果表明,该算法能有效的解决CTSP问题,且算法性能优于基本演化算法SEA。 相似文献
12.
一种衡量TSP问题种群多样性的新方法 总被引:2,自引:1,他引:1
文章针对遗传算法求解TSP问题,探讨了一种新的衡量种群多样性的方法——边数统计法。通过将之与传统的方法进行比较可知,本文所提出的方法不仅有效且大大降低了运算量,具有一定的实用价值。 相似文献
13.
14.
基于遗传算法的TSP问题求解与仿真 总被引:1,自引:0,他引:1
TSP问题常用的自然编码方式在进行遗传操作时,会产生不合法路径.设计了一种新的编码方式,能有效避免这一问题,遗传操作简单易行,无需对不合理的基因片段进行合法化修正.在求解过程中,为了解决遗传算法的收敛速度和全局收敛性之间的矛盾、避免早熟,运用了Doping策略和参数切换方法.最后进行了仿真测试.结果表明,该算法能迅速淘汰劣解,具有较快的收敛速度;能有效遏制早熟,对不同规模的TSP问题能有效求得最优解. 相似文献
15.
16.
针对PCB板的表面贴装技术(Surface Mount Technology,SMT)优化问题,提出一种基于蜜蜂进化型遗传算法和蚁群系统的混合智能算法(the Hybrid Intelligent Algorithm based on Bee Evolutionary Genetic Algorithm and Ant Colony System,BAHA).该算法的关键有4点:①通过两个种群的融合实现信息共享,提高算法的收敛速度;②采用改进的OX的交叉算子,合理保留优秀个体基因的排列顺序;③加入局部搜索算子,在当代最优解附近进行更加精细的搜索;④信息素重置防止陷入局部最优解.用TSP30问题、eil51问题与相关文献进行对比测试,仿真结果表明BAHA收敛速度快,寻优能力强.通过对5种不同PCB板的元件贴装顺序进行优化计算,结果表明,BAHA能有效的提高贴装效率. 相似文献
17.
基因多样性是影响算法收敛性能的重要因素之一,为了维持种群足够的多样性以保证演化高效进行,从变异算子设计思想入手,分析了传统变异算子存在的不足,即固定的、与问题无关的变异算子的设计思想存在不足。提出了基于信息熵的变异算子,并讨论了它在克服早熟收敛方面的作用;最后,通过实验证明了该方法的有效性。 相似文献