资源描述：
《基于蚁群算法的旅行商路径搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、基于蚁群算法的旅行商路径搜索xxxx（上海大学机械制造及其自动化学院，上海200072）摘要：蚁群算法(AntColonyAlgorithm,简称ACA)是由意大利学者Dorigo·M等人首先提出来的一种新型的模拟进化算法。其主要特点就是:通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递,搜索从蚁穴至食物间最短路径的集体寻优特征,以及该过程与旅行商问题求解之间的相似性,得到了具有NP非确定型(NondeterministicPolynomial)难度的旅行商问题的最优解答。关键
2、词：蚁群算法；旅行商问题；智能控制；信息素BasedonAntAlgorithmforTravelingSalesmanPathSearchingxxxx(InstituteofMechanicalManufacturingandAutomation,ShanghaiUniversity,Shanghai200072,China)Abstract:Antcolonyalgorithm(AntColonyAlgorithm,abbreviatedasACA)bytheItalianscholarsDorigo•M,whofirstproposedane
3、wtypeofsimulatedevolutionaryalgorithm.Itsmaincharacteristicis:Throughpositivefeedback,distributedcollaborationtofindtheoptimalpath.Thisisapopulation-basedoptimizationheuristicsearchalgorithm.Ittakesfulladvantageofbiologicalantcolonythroughthesimpletransmissionofinformationbetwe
4、enindividuals,thesearchoffoodfromthecolonytotheshortestpathbetweenthecollectiveoptimizationfeatures,aswellasthetravelingsalesmanproblem-solvingprocessandthesimilaritybetweentheobtainedwiththenon-NPdeterministic(NondeterministicPolynomial)theoptimaldegreeofdifficultyofthetraveli
5、ngsalesmanproblemsolution.Keywords:Antcolonyalgorithm;TSP;IntelligentControl;Pheromone1旅行商问题1.1旅行商问题简介旅行商问题(TravelingSalesmanProblem),又称旅行推销员问题,是指给定n个城市,任何两城市之间皆有路连通,其距离为已知,某旅行商从其中某城市出发,要经过每城市一次,且只能一次,最后又必须返回出发城市,要求找出最短的巡回路径.TSP可分为对称TSP(symmetrictravelingsalesmanproblem)和非对称TSP
6、(asymmetrictravelingsalesmanproblem)两大类,若两城市往返的距离相同,则为对称TSP,否则为非对称TSP[1]。本文研究的是对称TSP。TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题[2]。-6-同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所
7、辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题（ChinesePostmanProblemCPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。1.2传统方法解决TSP基于TSP的问题特性,构造型算法成为最先开发的求解算法,如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但是,由于构造型算法优化质量较差,迄今为止已开发了许多性能较好的改进型搜索算法[3],主要有:1)模拟退火算法模拟退火算法(simulatedannealing,SA)是基于MonteCar
8、lo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。S
