探析蚁群算法在tsp中的应用研究

《探析蚁群算法在tsp中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：U4910710一S06241263该步夫海硕士学位论文蚁群算法在TSP中的应用研究导师姓名职称申请学位级别隆忠华许宏科教授㈣刳必坩硕士学科专业名称交通信息工程及控制论文提交日期2009年4月15日论文答辩日期2009年5月22日学位授予单位长安大学答辩委员会主席学位论文评阅人苏诗琳副教授刘彦明教授赵忠杰教授摘要随着经济的快速发展和车辆数量的不断增加，日益严重的交通问题已经成为制约城市发展的重要瓶颈。智能运输系统(IntelligemTranspoIrtationSystem，ITS)是解决社会交通需求与供给之间矛盾的重要途径之一。近几年来，智能运输系统越来越

2、受到人们的重视，它是以科学技术为支撑，将计算机技术、通信技术、数据库技术、人工智能技术等运用于交通领域，以达到缓解交通拥挤、保证交通安全、提高交通网络使用效率等目的。最优路径的选择，作为智能运输系统中的一个研究热点，是一类典型的组合优化问题，适合采用蚁群算法(ACO)求解。蚁群算法通过其内在的搜索机制和正反馈特性，在解决一系列组合优化问题中取得了成效，这已经是被大量研究成果证明了的。但是蚁群算法也存在着一些缺陷，如在蚂蚁的移动过程中，路径选择虽然受到信息素和启发信息的指导，但仍具有随机性，特别是当问题规模较大时，路径的选择通常需要较长的搜索时间。此外，由于个别路径上的

3、信息素可能被过于强化，容易使算法陷入局部最优解。本文首先分析了基本蚁群算法的优缺点，通过仿真实验研究了参数对算法性能的影响，确定了参数的合理取值范围，然后，针对信息素的优化策略进行了改进，有效地抑制了收敛过程中的早熟停滞现象。最后，结合TSP问题实例，对改进后的蚁群算法有效性进行了验证，结果表明该算法具有较快的收敛速度，能够在较短的时间内搜索到全局最优解。关键词：最优路径；蚁群优化算法；旅行商问题；信息素；交通仿真AbstractWitharapiddevelopmemofeconomyaIldquantit)rofVellicle，theincreaSin91yse

4、riouStramcproblemhasbecomeacriticalbottlenecktorestrictcitydeVelopment．IntelligentTI’ansportationSystemisoneoftllemostimporrcantsolutiollstodeal而thtllecoⅢ1ictofdemand锄dsupplyinsocial舰mc．Inrecentyears，晰ththesupportofscienceandtechnology，ITShaSbeenmoreaIldmoreregardedbypeopleforitappliesc

5、omputertechnology，comm疵cationteclul010鼢da协asetec

6、Ⅱlologyandanificialintelligencetechnologyto仃amcareatosolvetramcjaIIl，ensuretramcsafet)，aIldimproVetlleefficiencyoftra币cnetwork．AsahotresearChpointofITS，tlleoptimumPathsselection，Whichisacombinatorialoptimizationproblem，canbe、VeUsolVedbyAC

7、O．IthaSbeenprovedbyagreatdealofresearchachieVements，ACOisgoodatsolVingcombinatorialoptimizationproblemsbyitsiImersearchingmech耐smaIldpositiVefeedbacktrait．However，ACOalsohassomedefects．Forex锄ple，duringthemoVementofants，routeselectioninstmctedbypheromoneandinspirationalsohasraIldomici够Sp

8、ecially，whenmescaleofproblemisla玛er，routeselectionusuallycostmoresearcmngtime．h1addition，becausepheromonemaybes仃en酉henedinanindiVidualroute，thealgorithwiUeaSilygetimolocaloptimalsolution．FirStly，恤thesisaIlalyzedtheadV撇gesanddisadVaIltagesofb撕cACo，studiedtheinfluenceofparameterS