蚁群算法在tsp问题中的应用_本科论文.doc

《蚁群算法在tsp问题中的应用_本科论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、单位代码01学　　号090111004分类号O24密级毕业论文蚁群算法在TSP问题中的应用院(系)名称信息工程学院专业名称信息与计算科学学生姓名王利超指导教师王爱苹2013年5月15日黄河科技学院毕业论文第16页黄河科技学院毕业论文第16页蚁群算法在TSP问题中的应用摘要蚁群算法是近年来发展起来的一种新型模拟进化算法，它是由意大利学者M．D0rigo等人在20世纪90年代初提出来的．这种算法模仿了蚂蚁在搬运食物的过程中，自发寻找最短路径的行为特征，加以改进并应用到不同的领域．蚁群算法作为一种新的启发式算

2、法，它具有正反馈、分布式计算以及结构性的贪心启发等特点，使其能够成功地解决许多问题.本文首先介绍了蚁群算法的基本原理及相关背景；其次描述了蚁群算法在实际问题中的应用，如：旅行商问题；然后针对蚁群算法编写MATLAB程序求解最优路径；最后给出结论与展望。关键词：蚁群算法，TSP问题，最优路径，启发式算法黄河科技学院毕业论文第16页ApplicationofAntColonyAlgorithmInTheTSPProblemAuthor:WangLichaoTutor:WangAipingAbstractAn

3、tcolonyalgorithmisdevelopedinrecentyearsanewtypeofsimulatedevolutionaryalgorithm,whichisbytheItalianscholarM.Dorigopeopleintheearly1990s.Thisalgorithmmimicstheantsintheprocessoftransportingfood,spontaneousbehaviorcharacteristicstofindtheshortestpathtobei

4、mprovedandappliedtodifferentfields.Antcolonyalgorithmasanewheuristicalgorithm,ithasapositivefeedback,distributedcomputingandstructuralgreedyinspired,toenablethemtosuccessfullysolvemanyproblems.Thispaperfirstintroducesthebasicprinciplesofantcolonyalgorith

5、mandbackground;Second,wedescribetheapplicationoftheantcolonyalgorithminpracticalproblems,suchas:travelingsalesmanproblem;preparedfortheantcolonyalgorithmMATLABprogramforsolvingtheoptimalpath;FinallyconclusionsandProspect.Keywords:Antcolonyalgorithm,TSP,T

6、heoptimalpath,Heuristicalgorithm黄河科技学院毕业论文第16页目录1绪论11.1数值方法背景简介11.2非线性方程简介21.2.1非线性方程的背景21.2.2非线性方程的研究内容21.2.3根的存在性定理32非线性方程的数值解法42.1引言42.2二分法42.2.1二分法简介42.2.2二分法的原理42.3牛顿迭代法52.3.1牛顿迭代法的简介52.3.2牛顿迭代法的原理52.3.3牛顿迭代法的几何意义62.4割线法72.4.1割线法简介72.4.2割线法的原理83非线性方

7、程的MATLAB实现93.1二分法93.1.1二分法的MATLAB程序93.1.2应用举例103.2牛顿迭代法123.2.1牛顿迭代法的MATLAB程序12黄河科技学院毕业论文第16页3.2.2应用举例133.3割线法143.3.1割线法的MATLAB程序143.3.2应用举例154方法的分析与对比174.1构造非线性方程迭代公式174.2计算迭代公式175实际应用215.1引言215.2问题提出215.3模型建立225.4模型求解23结论25致谢26参考文献27黄河科技学院毕业论文第16页黄河科技学院

8、毕业论文第16页1绪论1.1课题背景及意义伴随计算机技术的飞速发展，许多工程应用和科学研究领域都产生了一些组合优化问题，它们中大多都是NP-优化问题，对该类问题的研究具有广泛的应用价值和十分重要的理论意义，其研究成果对科学研究的发展及国民经济的建设都必将起到极大的推动作用。旅行商问题就是其中经典的问题之一。目前对求解该类问题的研究主要有两个方向：一是传统的数学规划方法来得到全局最优解，但这种算法的复杂性往往是不能接受的，因而难以适应大规模问