共查询到20条相似文献,搜索用时 62 毫秒
1.
基于遗传算法求解TSP问题的一种算法 总被引:12,自引:1,他引:12
TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。利用交换启发交叉算子实现局部搜索加快算法的收敛速度和利用变换变异算子维持群体的多样性防止算法早熟收敛,给出了一种求解TSP问题的遗传算法。仿真实验结果表明了该算法的有效性和可行性。 相似文献
2.
描述了一种面向小组软件过程TSP(Team Software process)的仿真模型,根据TSP的特点,采用将离散和连续建模思想结合的一种混合模型。这种模型分为两层建立,外层体现软件开发过程的阶段性,内层体现软件开发过程的连续性,从两个层次上详细说明模型的结构和原理;给出了模型的形式化描述;并用一个例子来说明模型的执行过程及结果。此模型能够从不同角度模拟软件的开发过程,并能够对软件开发过程进行监督和预测。 相似文献
3.
一种基于改进遗传算法的TSP问题求解方法 总被引:2,自引:1,他引:1
通过改进经典遗传算法的交叉算子和变异算子,提出了一种改进遗传算法。介绍了该算法的基本步骤及特点,并对TSP问题进行了仿真实验。实验结果表明改进算法有效地提高了算法的收敛速度与寻优质量,在解决TSP问题时表现出良好特性,与经典遗传算法相比具有明显优势。 相似文献
4.
5.
一种基于构建基因库求解TSP问题的遗传算法 总被引:23,自引:1,他引:23
传统的遗传算法通常被认为是自适应的随机搜索算法.该文在分析其特点后针对TSP问题提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge-GA).该算法利用基因库指导种群的进化方向,并在此基础上使用全局搜索算子和局部搜索算子增强遗传算法的“探测”和“开发”能力.Ge-GA算法大大加快了遗传算法的收敛速度和寻优能力.作者测试了TSPLIB中的多个实例(城市数目从70~1577),试验结果与最优解的误差都不超过0.001%.特别是对于难求解的TSP问题,如att532和fl1577,都能够在理想的时间内找到最优解. 相似文献
6.
遗传算法(GA)是一种基于自然群体遗传机制的有效搜索算法,由于它在搜索空间中同时考虑许多点,这样就减少了收敛于局部极小的可能,也增加了处理的并行性。因此可以利用并行遗传算法(PGA)研究典型的组合优化实例-TSP问题的求解问题。该文提出一种有效的并行算法求解旅行商(TSP)问题,实验结果表明,该方法在解的精度上优于以前的算法。 相似文献
7.
一种基于构建基因库求解TSP问题的遗传算法 总被引:1,自引:0,他引:1
在分析了已有的求解TSP问题的优化算法后,提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge_GA)。该算法的目的是用基因库指导整个种群的进化,其核心问题是基因库的建立及如何将基因库运用到遗传算法中。试验结果表明,基因库有效地提高了群体演化的质量,局部搜索与全局搜索的结合大大提高了算法收敛速度。对于每个测试的实例,其结果与最优解的误差都不超过0.001%。特别是对难于求解的TSP问题,如pcb442和n1577,都能够在理想的时间内找到最优解。 相似文献
8.
为帮助用户在丰富的网络资源中快速、准确地查询到所需要的信息,提出一种基于遗传算法的查询优化方法.其基本思想是首先根据词项与所有查询词的共现程度在相关文档集合中选取扩展词对初始查询进行扩展,然后利用遗传算法为扩展后的查询选择优化的权重.实验结果表明,新方法具有更高的查全率和查准率. 相似文献
9.
TSP的一种改进遗传算法 总被引:6,自引:0,他引:6
旅行商问题(TSP)是研究算法性能的典型算法,具有广泛的应用背景。遗传算法(GA)是由遗传进化理论指导的随机搜索寻优算法。但传统GA的寻优能力与随机搜索能力之间存在着相互制约的关系,所以对地形极其复杂、极无规律的TSP的应用效果并不十分理想。本文通过在传统GA中引入“幼代”及其成长过程,解除了两种能力间的制约关系。实际计算结果表明,求解质量显著提高。 相似文献
10.
11.
一种基于遗传算法求解TSP问题的优化算法 总被引:1,自引:0,他引:1
韩凤娇 《网络安全技术与应用》2012,(7):36-39
旅行商问题是组合优化的一个经典问题,也是评价算法好坏的一个标准,它要求在给定的一张图中寻找一条哈密尔顿回路,使得该回路在所有的回路中长度最短。然而,该问题是一个NP完全问题,其求解时间会随着问题规模的扩大急剧上升。因此,只能希望在允许的时间内寻求问题的一个较优的解来替代。本文借助生物学的相关理论与思想采用遗传算法对该问题进行求解,最后通过对遗传算法的进一步分析,提出了一种可行的改进算法,达到了获得较优解的目的。 相似文献
12.
基于遗传算法的TSP问题优化求解 总被引:1,自引:0,他引:1
旅行商问题(TSP)是典型的NP完全问题,本文运用遗传算法求解TSP问题,提出了该算法在解决这一问题中的一些处理方法,使用该算法能够较快地求出一批最短路径,可根据需要设置叠代代数,求得理想最优解。 相似文献
13.
14.
15.
实际应用中经常用人工智能算法如遗传算法求解TSP等一类NP难题.针对原有的遗传算法在初始化种群随机性的缺陷以及在产生子代过程中无法保存最优个体的问题.给出基于贪心算法的种群初始化和交叉变异后最优个体保存算法相结合的改进遗传算法,并在VC++平台上对该算法的实现过程进行动态演示。 相似文献
16.
TSP问题是一个典型的组合优化问题,并且也是一个NP难题,其可能的路径总数与城市数目n成指数型增长,一般很难精确地求出其最优解。这里对BP问题提出了一种改进的遗传算法,通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试,实验结果证明此处提出的方法能更有效的求解TSP问题。 相似文献
17.
18.
在采用混沌遗传算法优化多目标QoS组播路由时,为克服Logistic映射收敛速度不快,而使传统混沌遗传算法优化效果不好的缺陷,将Tent混沌遗传算法引入QoS组播路由问题的求解中。该算法利用Tent混沌映射优越的区间均匀搜索能力,对通过遗传优选出的个体再次进行混沌优化,优化出适应度最高的个体进行交叉变异,从而保证足够多的下一代,以致算法不会陷入早熟。仿真结果表明,该算法优于Logistic混沌遗传算法,有效地改进了搜索效率,且收敛速度更快、更稳定。 相似文献
19.
基于构建基因库求解TSP问题的改进遗传算法 总被引:1,自引:0,他引:1
文章针对TSP问题设计了一种将基因库和遗传算法结合起来的新算法,该算法首先构建一个基因库,在单亲演化中利用基因库指导种群的进化方向,其次在此基础上采用单亲进化遗传算法中的基因重组操作,保留每次获得的最好解组成初始种群,最后采用顺序交叉算子进行群体演化。给出的实验结果显示,该算法所获得的解与最优解的相对误差都不超过2%,该算法的收敛速度和寻优能力明显优于该问题的单亲进化遗传算法。 相似文献
20.
基于遗传算法求解TSP问题的一种新方法 总被引:3,自引:0,他引:3
针对基于遗传算法求解TSP的效率问题,提出了一种基于位操作编码技术,并给出了基于位操作的交配、变异等基本操作的实现方法,有效地提高了计算过程中的空间利用率和计算效率。 相似文献