共查询到19条相似文献,搜索用时 78 毫秒
1.
针对TSP问题的特点,在遗传算法的交叉运算过程中设计了三角距离差函数作为评价标准,运用贪婪策略思想,提出了一种新的交叉算子:顺序插入交叉(OrderInsertCrossover,简称OIC)算子,该算子有效地利用了局部信息,并且能很好地继承父代优秀的基因,实例仿真验证了该算子的有效性。 相似文献
2.
求解TSP问题的遗传算法新方法研究 总被引:1,自引:0,他引:1
遗传算法是一种基于自然选择与遗传变异等生物进化机制的全局优化搜索算法。由于它在搜索空间中同时考虑许多点.这样就减少了收敛于局部极小的可能,也增加了处理的并行性。因此可以利用遗传算法研究典型的组合优化实例-TSP问题的求解问题。本文借助于遗传算法,采用新的交叉算子,给出了旅行销售员问题较优解的求解方法。 相似文献
3.
4.
5.
TSP问题(旅行商问题)是一个典型的组合优化问题,遗传算法(Generation Algorithm,GA)和蚁群算法(Ant Colony Qptimization,ACO)都属于仿生型优化算法,通过两种算法解决TSP的仿真实验,对问题规模、运行时间、性能稳定性及正确性进行了对比分析.得出问题规模小于20时,ACO算... 相似文献
6.
旅行商问题(TSP,Traveling Salesman Problem)是一种经典的NP组合优化问题。遗传算法在求解这类组合问题方面明显优于传统算法,同时也提出了许多求解较好路径的交叉算子。在对比分析唐立新提出的两种启发式交叉算法的基础上,提出了一种新的交叉算子。该算子通过判断父代的城市是否相邻来保存有效基因片断,通过加入一个移动的窗口来加快算法收敛。实验结果表明了该算子的有效性。 相似文献
7.
基于遗传算法求解TSP问题的一种新方法 总被引:3,自引:0,他引:3
针对基于遗传算法求解TSP的效率问题,提出了一种基于位操作编码技术,并给出了基于位操作的交配、变异等基本操作的实现方法,有效地提高了计算过程中的空间利用率和计算效率。 相似文献
8.
一种基于遗传算法求解TSP问题的优化算法 总被引:1,自引:0,他引:1
韩凤娇 《网络安全技术与应用》2012,(7):36-39
旅行商问题是组合优化的一个经典问题,也是评价算法好坏的一个标准,它要求在给定的一张图中寻找一条哈密尔顿回路,使得该回路在所有的回路中长度最短。然而,该问题是一个NP完全问题,其求解时间会随着问题规模的扩大急剧上升。因此,只能希望在允许的时间内寻求问题的一个较优的解来替代。本文借助生物学的相关理论与思想采用遗传算法对该问题进行求解,最后通过对遗传算法的进一步分析,提出了一种可行的改进算法,达到了获得较优解的目的。 相似文献
9.
针对旅行商(TSP)问题的特点,在遗传算法的交叉过程中对边的邻接状况采用了新的评价标准,结合顺序交叉算子和贪婪策略设计提出了一种新的交叉算子:动态顺序插入交叉(DOIC)算子。该算子有效地利用了局部信息,并且能很好地继承父代优秀的基因段,实例仿真表明了该算子的有效性。 相似文献
10.
主要研究了用遗传算法求解TSP问题。阐述了简单遗传算法的设计方法、基本原理和基本步骤。描述了简单遗传算法在TSP问题中的应用现状。根据种群个体的多样性和分布情况,提出了判定遗传算法的截止代数。简单遗传算法具有易于陷入局部最优解、收敛速度慢的特点,针对这些特点,通过改进交叉算子,加入初始化启发信息,提高了遗传算法解的精度和收敛性。 相似文献
11.
一种求解TSP问题的动态杂交算子 总被引:3,自引:0,他引:3
TSP(TravelingSalesmanProblem)问题是最经典的NP-hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的时间内解决大规模问题。论文在文犤5犦提出的两交换启发交叉算子的基础上,通过分析,发现该算子的杂交结果与所选择的首城市有关,因而不同的首城市的选择会大大影响该算子的效率,此外,在杂交母体范围内执行贪婪策略也导致了算法的效率较低。为此,提出了一种新的有效利用局部信息的杂交算子,该算子能够有效地保存母体信息,进一步摆脱首城市的选择问题。实例仿真证明了该算子的有效性。 相似文献
12.
13.
一种改进的遗传算法及其在TSP中的实现 总被引:4,自引:1,他引:4
TSP问题是典型的NP完全问题,遗传算法是求解NP完全问题的一种方法。文章针对TSP问题.提出了一种改进的遗传算法。在遗传算法中引入进化算法的思想,在此基础上提出顶端培育策略和分阶段策略,以求在保证群体多样性的同时加快收敛速度。在算法的仿真和测试中,改进后的算法明显优于传统的遗传算法。这表明,该算法具有良好的可行性和实用性。 相似文献
14.
15.
基于遗传算法求解TSP问题的一种算法 总被引:12,自引:1,他引:12
TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。利用交换启发交叉算子实现局部搜索加快算法的收敛速度和利用变换变异算子维持群体的多样性防止算法早熟收敛,给出了一种求解TSP问题的遗传算法。仿真实验结果表明了该算法的有效性和可行性。 相似文献
16.
在单亲初始种群上,设计了单点插入、线段插入、路径插入和变异四种算子,构造了基于单亲算子的TSP演化算法。该算法在单个个体上进行演化操作,随机选取单个个体,选择随机长度的路径并顺序地插入其余的任何两结点间形成新路径,对新路径进行变异操作以得到最终的路径。实验结果表明,和简单的TSP遗传算法相比,该算法可得更好的解,且减少了演化时间。 相似文献
17.
TSP问题是一个典型的组合优化问题,并且也是一个NP难题,其可能的路径总数与城市数目n成指数型增长,一般很难精确地求出其最优解。这里对BP问题提出了一种改进的遗传算法,通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试,实验结果证明此处提出的方法能更有效的求解TSP问题。 相似文献
18.
19.
文化基因算法求解TSP问题的研究 总被引:2,自引:0,他引:2
TSP是组合优化问题中著名的NP-hard问题。针对粒子群算法求解离散的TSP问题收敛速度慢,求解精度低,易于陷入局部最优和模拟退火算法的性能与参数初始值有关及参数敏感等不足,提出了将改进的粒子群算法作为全局搜索策略,改进的模拟退火算法作为局部搜索策略的文化基因算法。介绍了两种算法的协同方法,定义了局部搜索邻域的确定以及在新种群产生中引入自组织随机移民策略。仿真结果表明,改进算法在求解TSP问题中具有很快的收敛速度,且能搜索到最优解。 相似文献