用GAAA求解TSP问题设计.doc

《用GAAA求解TSP问题设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、河北工业大学毕业设计说明书(论文)题目：用GAAA求解TSP问题毕业设计（论文）中文摘要旅行商问题（TSP）是一个典型的、易于描述却难以处理的NP完全难题，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。本文采用了遗传算法（GA）和蚂蚁算法（AA）的混合优化策略来解决旅行商问题。在搜索最优路径的初期使用遗传算法快速形成有效聚类，而搜索后期使用蚂蚁算法来避免遗传算法冗余迭代，这样就实现了两种算法的优势互补。该文首先介绍了TSP问题并论述了混合优化策略的基本思想，然后对30个城市的TSP问题进行计算

2、，得出了较好的结果，最后进行了实验分析。关键词旅行商问题蚂蚁算法遗传算法混合优化策略毕业设计（论文）外文摘要TitleResolvetheTSPProblemUsingGAAAAAbstractTravelingsalesmanproblem(TSP)isatypical,easytodescribebutdifficulttodisposeofNP-completeproblems.Inthispaper,ageneticalgorithm(GA)andAntAlgorithm(AA)hybridoptim

3、izationstrategiestosolvethetravelingsalesmanproblem.Searchoptimalpathintheearlyuseofgeneticalgorithmtorapidlydevelopeffectiveclustering,Searchandlateantalgorithmtousegeneticalgorithmstoavoidredundancyiteration,sothetwoalgorithmstoachievethecomplementarystre

4、ngths.ThearticleintroducestheTSPanddiscussesthehybridoptimizationstrategybasicidea,Thenthe30citiesintheTSPforcalculation,thebettertheoutcome,theexperimentalanalysis.KeywordsTravelingSalesmanproblemGeneticAlgorithmAntAlgorithmHybridOptimizationStrategy目次1引言1

5、1.1TSP问题简介11.2蚂蚁算法概述11.3遗传算法概述22开发工具介绍32.1Delphi简介32.2Delphi的可视化开发环境32.3Delphi6.0的使用43算法综述73.1遗传算法综述73.2蚂蚁算法综述113.3算法的混合优化策略144软件使用介绍154.1软件简介154.2软件界面介绍154.3实例演示17结论18参考文献19致谢201引言随着科技的发展和工程问题围的拓宽，问题的规模和复杂度越来越大，传统算法的优化结果往往不够理想，同时算法理论研究的落后也导致了单一算法改进程度的局限性，而

6、给予自然机理来提出新的优化思想是一进很困难的事。基于这种现状，算法混合的思想已发展成为提高算法优化性能的一个重要且有效的途径，其出发点就是各种单一算法相互取长补短，产生更好的优化策略[1]。本课题是将遗传算法和蚂蚁算法相结合的方法求解TSP问题。遗传算法和蚂蚁算法都是启发式优化算法，单一的算法有时会陷入局部极小，因此采用混合算法进行求解，来避免陷入局部极小。1.1TSP问题简介旅行商问题(TSP)是指一个商人要遍历n个城市(每个城市只走一次)，且使总路径最短。它是一个典型的、易于描述却难于处理的NP问题，是许

7、多领域出现的多种复杂问题的集中概括和简化形式。对于TSP问题，没有确定的算法能够在多项式时间得到问题的解。目前针对这一问题已有许多种解法，如穷举搜索法、贪心法、动态规划法、分支界定法等这些方法都存在着一个共同问题，就是当城市数目N较大时，会产生所谓的“组合爆炸”问题。因此，有效地解决TSP问题，再可计算理论上具有重要的理论意义同时也具有重要的实际应用价值[2]。1.2蚂蚁算法概述蚁群算法是一种新型的模拟进化算法,由意大利学者M.Dorigo、V.Maniezzo和A.Colorini等人在90年代首先提出[3

8、,4],称之为蚁群系统(antcolonysystem)。它是受到人们对自然界中真实的蚁群集体行为的研究成果的启发而提出的一种基于种群的模拟进化算法。生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢之间的最短路径,而单只蚂蚁则不能。蚂蚁间相互协作的方法是它们在运动过程中,能够在所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此指