改进蚁群算法及在路径规划问题的应用研究

《改进蚁群算法及在路径规划问题的应用研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、I．／ll。l／11．／ll。l／18lll8／llllll／2llll改进蚁群算法及在路径规划问题的应用研究学位论文完成同期指导教师签字答辩委员会成员签字。也扭趣丛丝丝之丝旌骜≥彖型独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者躲匀撅字嗍跏年J月刁日学位论文版权使用授权书

2、本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学位论文的全部或部分内容编八有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息研究所将本学位论文收录到《中国学位论文全文数据库》，并通过网络向社会公众提供信息服务。(保密的学位论文在解密后适用本授权书)学位论文储魏亿许祆靳酶加九签字同期：a。投年J月司日签字R期：。n，z年丁月习同‘：；1、改进蚁群算法及在路径规划问题的应用研究摘要路径规

3、划问题是组合优化和运筹学领域研究的热点问题之～，具有重要的理论和现实意义。蚁群优化算法是受蚁群觅食行为启发而提出的一类群智能优化算法，该算法能有效地解决具有NP—Hard特性的组合优化问题。由于蚁群算法在求解离散问题的优势和对路径的敏感性，使它对路径规划问题的求解一直各受关注。本文针对旅行售货员问题、多智能体的编队控制问题、车辆路由问题以及智能体路径规划问题，分别提出改进的蚁群算法进行求解。主要的研究内容和创新点如下：1提出了～种求解旅行售货员问题的改进蚁群算法。该算法在信息素更新过程中，使用一种信息素局部更新和全局动态更新结合的方

4、法，使当前最优路径上的信息黍能够根据当前最优解动态地进行调配，避免算法陷入停滞状态。在局部搜索过程中，仅对部分走山更优路径的售货员使用2-opt方法，提高了求解的精度，加快了最优解的收敛速度。仿真实验验证了算法的有效性，与其它算法相比，算法在求解质量和收敛速度上都显示出了良好的性能。2提出了一种多智能体编队控制问题的改进蚁群算法。针对多智能体在编队过程中的晟短编队距离问题，使用改进的蚁群算法对其求解。该算法每次迭代时．会给每个智能体一个随机的初始位置，以增强搜索的多样性。在搜索过程巾．使用智能体当前位置与日标位置距离的倒数作为启发式

5、信息，以引导智能体向路径更短的目标位置进行移动。局部搜索过程采用一种交换搜索的方式，能够扩大搜索的范1猢，加快是优解的收敛速度。仿真实验验证了算法的有效性。3提出种带容量约束车辆路山问题的改进蚁群算法。馥算法使用一种新的乍辆位置韧始化方式，增加了车辆止出最优路径的可能性。在搜索过程中，使用客户之叫路径的节省量作为启发式信息．以引导车辆向路径至节省的客户移动。信息素更新采用种动态更新的方法，能够根据当前车辆所构建路径的情况对信息素进行更新，避免算法陷入停滞状态。局部搜索除使用2-opt方法外，针对不同车辆访问的客户，还增加了交换搜索和

6、插^搜索，以扩大搜索的范围。仿真实验验证了算法的有效性。4．提出了一种静态环境下智能体路径规划问题的端点逼近蚁群算法，该算法使用栅格法对智能体的工作环境进行建模。算法使用折返迭代的方式对目标进行搜索。在搜索过程中，以移动方向上一定范围内最大信息素和目标引导函数作为启发式因子。并且，采用两种信息秉对蚂蚁进行引导。根据蚂蚁对栅格访问和信息素散播的特点，提出一种端点(起始点与目标点)逼近的方法，它能够使起始点和目标点在迭代过程中逐步地相向移动，缩短了起始点和目标点之间的距离，加快了最优解的收敛速度。仿真实验验证了算法的有效性。关键词：蚁群

7、优化算法：组合优化：旅行售货员问题；智能体；车辆路由问题路径规划：编队控制ResearchanImprovedAntColonyAlgorithmsandApplicationsforPathPlanningProblemsAbstractPathplanningproblemshavebecomeoneofhotresearchareasinthefieldofcombinatorialoptimizationandoperationsresearchTheresearchesinthisareahaveimporlamsigni

8、ficanceoiltheoryandpracticeAntcolonyoptimization(ACo)jsanovelnature—inspiredmetaheuristicalgorithmbasedonrealantsfora