资源描述：
《人工蚁群算法的实现与性能分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、目录I摘要VAbstractVI第一章引言11.1非对称TSP问题（ATSP）及其求解方法概述11.2人工蚁群算法的主要思想和特点11.3主要工作2第二章ATSP问题分析32.1ATSP问题的数学模型32.2ATSP问题与TSP问题的比较3第三章求解ATSP问题的人工蚁群算法43.1ATSP问题的蚁群算法表示43.2人工蚁群算法的实现43.2.1人工蚁群算法的流程图53.2.2蚁群的规模、算法终止条件63.2.3路径选择方法和信息素的更新方法7第四章实验和分析104.1测试环境104.2测试用例104.3实验结果及参数分析104.3.1br17.atsp的
2、测试结果104.3.2ft53.atsp的测试结果124.3.3ftv33.atsp的测试结果134.3.4ftv35.atsp的测试结果134.3.5br17.atsp相关参数修改后的测试结果14第五章总结16致谢17参考文献17摘要旅行商问题(TSP问题)是组合优化的著名难题。它具有广泛的应用背景,如计算机、网络、电气布线、加工排序、通信调度等。已经证明TSP问题是NP难题,鉴于其重要的工程与理论价值,TSP常作为算法性能研究的典型算例。TSP的最简单形象描述是:给定n个城市,有一个旅行商从某一城市出发,访问各城市一次且仅有一次后再回到原出发城市,要求
3、找出一条最短的巡回路径。TSP分为对称TSP和非对称TSP两大类,若两城市往返距离相同,则为对称TSP,否则为非对称TSP。本文研究的是对称的ATSP。实质上，ATSP问题是在TSP问题上发展而来的，它们的区别就在于两座城市之间的往返距离是否相同。例如，有A,B两个城市，在TSP问题中，从A到B的距离是等于从B到A得距离的，是一个单向选择的连通问题。而在ATSP问题中，从A到B的距离就不一定等于从B到A的距离，所以这是双向选择的联通问题。本文主要阐述了用人工蚁群算法的原理和一些与其相关联的知识结构点。通过对算法原理的理解，及在函数优化问题上的应用，与优化组
4、合问题的研究来了解ATSP问题以及人工蚁群算法解决实际问题上的应用与研究。关键词：ATSP；组合优化；人工蚁群算法；TSPAbstractTravelingsalesmanproblem(TSP)istheFamouscombinationoftheoptimizationproblem.Ithasbroadapplications,suchascomputer,network,electricalwiring,processing,sortandcommunicationscheduling,andetc.HasalreadyprovedTSPisadi
5、fficultNPproblem,giveningitsimportantengineeringandtheoreticalvalued,TSPisoftenusedasthetypicalexampleofalgorithmperformancestudy.ThemostsimpleimagedescriptionofTSPis:givenncity,atravelingsalesmanstartfromonecity,Visitothercitiesonceandonlyonceagainreturntothestartcity,askedtoiden
6、tifyashortestpathofthetour.TSPcanbeclassificatedsymmetricTSPandasymmetricTSPtwobigkinds.Iftwocitiesfromthesamedistance,thatissymmetricTSP,orfortheasymmetricTSP.ThispaperstudiestheATSPproblem.Inessence,ATSPproblemisbasedontheTSPproblem.Thedifferenceliesintwocitiesroundtripdistanceb
7、etweenthesameordifferent.Forexample,therearetwocities,AandB,inTSPproblem,fromAtoBisequaltothedistancefromBtohaveAdistance,itsaone-waychoicetheconnectedproblems.ButinATSPproblem,fromAtoBdoesn'tnecessarilyequaltothedistancefromthedistanceBtoA,sothisisthetwo-waychoiceconnectivityprob
8、lem.Thispapermainlyexpoundstheemp
