遗传算法及其在TSP问题中的应用研究

贵州大学硕士学位论文遗传算法及其在TSP问题中的应用研究姓名：李薇申请学位级别：硕士专业：计算机应用技术指导教师：王力20080401遗传算法及其在TSP问题中的应用研究作者：李薇学位授予单位：贵州大学相似文献(10条)1.期刊论文陈晶.CHENJing基于遗传算法的避障TSP问题算法设计-现代计算机（专业版）2006(2)主要探讨复杂环境下避障TSP问题的遗传算法的求解方法.针对TSP问题和避障TSP问题的不同,在染色体的编码方式、有效范围、基因选取、遗传算子等方面对传统遗传算法进行改进,同时引入了代价矩阵和基因库以提高算法的收敛速度.2.学位论文彭丹平遗传算法在TSP问题上的应用2006旅行商问题(TravelingSalesmanProblem，TSP)是一个经典的组合优化问题，是多种复杂问题的一种简化形式。TSP问题的搜索空间随着城市数的增加而增大，在庞大的空间中寻找最优解，往往需要大量的求解时间，因此需寻求一种求解时间短且精度较高的算法来解决此问题。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，其简单通用、鲁棒性强、适于并行处理等，借助遗传算法解决TSP问题是一个自然的想法。本文针对遗传算法求解TSP问题进行了研究。首先分析了遗传算法的基本原理，遗传算法的研究及应用，接着对TSP问题的应用价值及其研究现状作了相应的分析，并结合遗传算法及TSP问题的特点，在对基本遗传算法改进的基础上，设计了一个新的算法，并通过实验验证了算法的有效性，本文主要研究工作如下：1．针对遗传算法求解TSP问题，提出了基于适应度对种群进行分级，采用小种群并行育种的方式。让适应度较高的个体用于实现最优解的开采以保证算法的收敛性；适应度较低的个体产生较多的个体对搜索空间进行探索，以保证种群的多样性，避免陷入局部最优解。而且在每级内使用了精英保留策略。2．基于遗传算法的交叉策略，使用混合交叉算子，即PMX和一种启发式交叉算子，既可保留父代中相同的模式，又可以较大概率生成优于父体的个体。3．改进了变异算子，提出了对种群使用混合变异算子，即2-opt和一种贪婪倒位变异算子。4．将本文算法进行了数值实验和相关比较，从而验证了本文算法的可行性。3.期刊论文方铖遗传算法及其在TSP问题中的应用-四川教育学院学报2008,24(1)遗传算法是一种模拟自然界生物进化过程的随机搜索算法;遗传算法目前已经在组合优化、机器学习和并行处理等领域得到了越来越广泛的应用;文章对遗传算法的理论与应用进行了一些研究和分析,介绍了遗传算法的理论,以及它在TSP问题中的应用.4.学位论文林志毅改进的遗传算法求解TSP问题2006本文由三个部分组成，第一部分是对研究背景的介绍，给出了最优化问题的描述，概括了求解最优化问题的数学方法和演化计算方法。第二部分是对遗传算法的研究：对传统的遗传算法进行了简要的分析，介绍了一些改进的遗传算法，在此基础上，提出了一种基于相似性的遗传算法。第三部分是遗传算法的应用实践：将所设计的算法应用到代表性的旅行商问题(TravelingSalesmanProblem，简称TSP)和车间调度问题，并将结果与传统的方法进行比较，结果显示本文设计的算法表现出了良好的性能。本文的主要工作和创新点：1、定义了距离、相似性和邻域等概念，用距离反映个体间的差异程度，用相似性描述个体间的类似程度，用邻域实现对种群的划分。2、在新解的产生过程中引入了分级策略，对种群按照适应值进行划分，对处于不同级别的个体采用不同的遗传操作，使得个体在相似性的指导下产生新解，避免了新解产生的盲目性，从而使得子代较好继承了父代的优势特征。此外，用一定概率保留较差个体和对于重复个体用随机产生的个体替换保证了种群的多样性。从而使算法的效果和效率达到较好的平衡。为了使算法更快地搜索到最优解，还设计了加速算子。3、提出了一种基于相似性的遗传算法。将该算法运用到TSP问题中，其中结合了TSP问题的特点，定义了TSP问题的距离、相似性和邻域等并设计了符合TSP问题的加速算子。数值实验表明该算法收敛速度快，结果也较好。4、对TSP问题进行了综述。介绍了TSP问题的历史和研究现状、数学模型、时间复杂度、评价标准。然后以综合性能的角度对解TSP算法进行了一定的归纳和分析。最后介绍了遗传算法求解TSP问题的研究进展。5.期刊论文包明遗传算法求解TSP问题的改进-硅谷2008(7)针对遗传算法解决TSP问题的特点,构造出遗传算法需要的初始种群.运用相同算法对改进前后的两种种群进行实验,得出改进方法具有增强遗传算法效率的作用.6.期刊论文徐珊.司守奎.唐金国.XUShan.SIShou-kui.TANGJin-guo求解TSP问题的遗传算法-海军航空工程学院学报2004,19(5)无人侦察机的巡航问题,如果不考虑其它约束条件,实际上是一个TSP问题.目前还没有求解TSP问题的比较有效的实时算法,我们首先利用改良圈算法求得一个较好的初始种群,再应用遗传算法就可以实时地求得一个较满意的解.7.学位论文孙海雷改进的遗传算法求解TSP问题2007遗传算法是一种模拟自然界生物进化的搜索算法，由于它简单易行、鲁棒性强，尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程，从而使它的应用范围极为广泛，并且已在众多领域得到了实际应用，取得了令人瞩目的成果，引起了广大学者和工程人员的关注。TSP问题是一个典型NP难题，具有广泛的应用，多年来一直是学者们研究的热点。由于大多数学者认为NP问题不存在多项式时间内的完全算法，因此设计TSP问题的近似算法具有非常重要的意义。TSP问题还成为了衡量近似算法效率的主要标准。本文对遗传算法的理论与应用进行了一些研讨。首先介绍了遗传算法的基本原理及其应用，其次分析了TSP问题的研究现状、数学模型、求解方法等，最后在标准遗传算法的基础上提出了改进的遗传算法。针对TSP问题的特点，在遗传算法的交叉过程中对边的邻接状况采用了新的评价标准，结合顺序交叉算子和贪婪策略，本文设计提出了两种新的交叉算子：顺序插入交叉算子与动态顺序插入交叉算子，它们有效地利用了局部信息，并且能很好地继承父代的优秀基因段，实例仿真表明了该算法的可行性和有效性。8.期刊论文彭青松.戴炳荣求解TSP问题的遗传算法新方法研究-福建电脑2007(3)遗传算法是一种基于自然选择与遗传变异等生物进化机制的全局优化搜索算法.由于它在搜索空间中同时考虑许多点,这样就减少了收敛于局部极小的可能,也增加了处理的并行性.因此可以利用遗传算法研究典型的组合优化实例-TSP问题的求解问题.本文借助于遗传算法,采用新的交叉算子,给出了旅行销售员问题较优解的求解方法.9.期刊论文熊伟清.郭举良.魏平一种快速求解TSP问题的遗传算法-微电子学与计算机2004,21(1)文章受求最短路径算法的启发,提出一个启发算子用于遗传算法求解TSP问题,通过50,144,150等城市的TSP问题求解,表明该算法求解速度快并且解的质量也非常好.10.学位论文任昊南用遗传算法求解TSP问题2008巡回旅行商问题(TSP)是一个组合优化方面的问题，已经成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以求出该问题的最优解。但是对现有的计算机来说，使用常规的穷举法在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求解TSP问题的优化算法应运而生了，本文所用到的遗传算法也在其中。遗传算法是一种高效智能搜索方法，并行遗传算法是遗传算法研究中的一个重要方向。并行遗传算法能够提供各种大型计算问题的解决方案。Java语言提供了对并发的语言级支持，这个特性是Java的伟大创新之一，同时为并行遗传算法的设计提供了最佳的技术支持。在收集国内外相关资料，阅读了相关文献的基础上，本文系统地阐述了遗传算法的构成原理。介绍了作者借助Java语言实现的一种应用“轮盘赌”选择操作，顺序交叉操作以及启发式变异操作求解TSP问题的遗传算法。在了解和掌握并行遗传算法的基本概念和工作原理后，针对TSP问题，提出了两种基于并行遗传算法的求解方法。第一章介绍了课题的研究背景、研究的可行性和意义，并行遗传算法的基本理论以及所面对的问题。此外还介绍了TSP问题的研究现状，并对论文内容进行了概括性综述。第二章介绍了遗传算法及并行遗传算法模型。第三章介绍了遗传算法求解TSP问题的基本理论，提出了一种求解TSP问题的串行遗传算法模型，结合实例分析了该算法的创新之处。第四章介绍了两种求解TSP问题的并行遗传算法模型，详细地论述了采用这两种并行模型求解TSP问题的过程。分别分析了这两种遗传算法的创新之处，并通过实例对它们之间的性能进行了比较。第五章总结了整个研究工作，并对研究的方向进行了展望。本文链接：下载时间：2010年3月17日