matlab关于旅行商问题遗传算法的研究

《matlab关于旅行商问题遗传算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法对TSP问题的研究摘要：作为一种模拟生物自然遗传与进化过程的优化方法,遗传算法(GA)因其具有隐并行性、不需目标函数可微等特点,常被用于解决一些传统优化方法难以解决的问题。旅行商问题(TSP)是典型的NP难题组合优化问题之一,且被广泛应用于许多领域,所以研究遗传算法求解TSP具有重要的理论意义和应用价值。关键字：遗传算法旅行商问题Abstract：Geneticalgorithm(GA)whichhasthecharacteristicoflatentparallelism,non-differentiabilit

2、yofobjectivefunctionandsoon,asaoptimizationmethodofsimulatingtheprocessofnaturalbioticinheritandevolution,isusedtosolvesomeproblemswhicharedifficulttosolvebythetraditionaloptimizationmethod.Travelsalesmanproblem(TSP)isatypicalNFscombinationandoptimizationproblem,and

3、iswidelyusedinmanyfields.SothegeneticalgorithmtosolveTSPhasimportanttheoreticalsignificanceandapplicationvalue.Keywords：geneticalgorithmTSP一、引言在过去,人们往往只能够处理一些简单的问题，对于大型复杂系统的优化和自适应仍然无能为力。但是在自然界中，生物在这方面表现出了其优异的能力，他们能够通过优胜劣汰、适者生存的自然进化规则进行生存和繁衍，并且慢慢的产生对其生存环境适应性越来越高的优良物种

4、。遗传算法就是模拟自然进化的一种高效的算法。其基本思想就是模拟自然界进化机制和生物进化论而形成的一种过程搜索最优解得算法。遗传算法是一门新的学科，各种理论、方法都尚未成熟，有待于进一步地发展和完善，但它却让我们看到了解决许多复杂问题的希望。尽管在遗传算法的研究和应用过程中出现过许多难题，同时也会产生许多不同的算法设计，但是，目前遗传算法的运用过程中已经展现出了其优异的性能和巨大的发展前景。我们相信，随着研究工作的进一步深入和发展，遗传算法一定能够在智能计算领域中起到关键性作用。巡回旅行商问题(TravelingSalesman

5、Problem,TSP),是一个著名的组合优化问题[1]10,该类问题具有很强的运用背景。如数控机床上的最优钻孔路线的选取、电路板的焊接、物流的调度问题都属于旅行商问题。因此旅行商问题受到了各方面的关注。目前解决TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。有效解决TSP问题在计算理论和实际应用上都有很高的价值。本文主要介绍了运用遗传算法来解决TSP问题。二、研究背景旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货

6、郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值旅行推销员问题是数图论中最著名的问题之一，即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds，Cook和Karp等人发现，这批难题有一个值得注意的性质，对其中一个问题存在有效算法时，每个问题都会有有效算法。迄今为止，这类问题中没有一个找到有效算法。倾向于接受N

7、P完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法旅行商问题在很多领域中都可以应用，例如：1、如何规划最合理高效的道路交通，以减少拥堵；2、如何更好地规划物流，以减少运营成本；3、在互联网环境中如何更好地设置节点，以更好地让信息流动等。三、解决TSP问题所使用的方法旅行商问题是一个典型的NP完全问题，遗传算法是解决这类问题一个比较理想的算法。遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化方法。

8、它的基本思想来自于Darwin的进化论和Mendel的遗传学。10遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控