蚁群算法在TSP问题中的应用.doc

单位代码01学号090111004分类号O24密级毕业论文蚁群算法在TSP问题中的应用院(系)名称信息工程学院专业名称信息与计算科学学生姓名王利超指导教师王爱苹2013年5月15日黄河科技学院毕业论文第页蚁群算法在TSP问题中的应用摘要蚁群算法是近年来发展起来的一种新型模拟进化算法，它是由意大利学者M．D0rigo等人在20世纪90年代初提出来的．这种算法模仿了蚂蚁在搬运食物的过程中，自发寻找最短路径的行为特征，加以改进并应用到不同的领域．蚁群算法作为一种新的启发式算法，它具有正反馈、分布式计算以及结构性的贪心启发等特点，使其能够成功地解决许多问题.本文首先介绍了蚁群算法的基本原理及相关背景；其次描述了蚁群算法在实际问题中的应用，如：旅行商问题；然后针对蚁群算法编写MATLAB程序求解最优路径；最后给出结论与展望。关键词：蚁群算法，TSP问题，最优路径，启发式算法ApplicationofAntColonyAlgorithmInTheTSPProblemAuthor:WangLichaoTutor:WangAipingAbstractAntcolonyalgorithmisdevelopedinrecentyearsanewtypeofsimulatedevolutionaryalgorithm,whichisbytheItalianscholarM.Dorigopeopleintheearly1990s.Thisalgorithmmimicstheantsintheprocessoftransportingfood,spontaneousbehaviorcharacteristicstofindtheshortestpathtobeimprovedandappliedtodifferentfields.Antcolonyalgorithmasanewheuristicalgorithm,ithasapositivefeedback,distributedcomputingandstructuralgreedyinspired,toenablethemtosuccessfullysolvemanyproblems.Thispaperfirstintroducesthebasicprinciplesofantcolonyalgorithmandbackground;Second,wedescribetheapplicationoftheantcolonyalgorithminpracticalproblems,suchas:travelingsalesmanproblem;preparedfortheantcolonyalgorithmMATLABprogramforsolvingtheoptimalpath;FinallyconclusionsandProspect.Keywords:Antcolonyalgorithm,TSP,Theoptimalpath,Heuristicalgorithm目录TOC\o"1-3"\h\uHYPERLINK\l"_Toc324661931"1绪论PAGEREF_Toc324661931\h1HYPERLINK\l"_Toc324661932"1.1数值方法背景简介PAGEREF_Toc324661932\h1HYPERLINK\l"_Toc324661933"1.2非线性方程简介PAGEREF_Toc324661933\h2HYPERLINK\l"_Toc324661934"1.2.1非线性方程的背景PAGEREF_Toc324661934\h2HYPERLINK\l"_Toc324661935"1.2.2非线性方程的研究内容PAGEREF_Toc324661935\h2HYPERLINK\l"_Toc324661936"1.2.3根的存在性定理PAGEREF_Toc324661936\h3HYPERLINK\l"_Toc324661937"2非线性方程的数值解法PAGEREF_Toc324661937\h4HYPERLINK\l"_Toc324661938"2.1引言PAGEREF_Toc324661938\h4HYPERLINK\l"_Toc324661939"2.2二分法PAGEREF_Toc324661939\h4HYPERLINK\l"_Toc324661940"2.2.1二分法简介PAGEREF_Toc324661940\h4HYPERLINK\l"_Toc324661941"2.2.2二分法的原理PAG