基于迭代局部捜索的路径规划蚁群算法摘要：针对蚁群算法易早熟及局部搜索能力欠佳的缺陷,将迭代局部搜索策略引入蚁群算法。新算法的基本思想是：从初始解出发，用蚁群算法进行局部搜索，如陷入局部最优，则产生一个摄动解作为新的初始解再进行局部搜索，根据接受规则决定进入下一步迭代的局部最优解。将改进算法应用于二维路径规划，数值实验表明，改进算法相比基本蚁群算法有更佳的局部收敛性，可获得比基本蚁群算法结果更优路径。关键词：蚁群算法；迭代局部搜索；局部收敛性；路径规划DOIDOI：10.11907/rjdk.173181中图分类号：TP312文献标识码：A文章编号：1672-7800(2018)008-0031-04英文摘要Abstract：Antcolonyalgorithmiseasytoprema-tureandtheabilityoflocalsearchispoor.Theiterativelo-calsearchstrategyisintroducedintoantcolonyalgorith-m.Thebasicideaofthenewalgorithmisthatthenewalgorithm-startsfromtheinitial---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---solutionanduseantcolonyalgorithmforlocalsearch・Aper-turbationsolutionisgeneratedasanewinitialsolution,andthenthelocalsearchiscarriedoutifitfallsintothelocalop-timum,andthelocaloptimalsolutionofthenextiterationis-determinedaccordingtotheacceptancerule・Theimprovedal-gorithmisappliedtotwo-dimensionalpathplanning,andthenumericalexperi-mentsshowthattheimprovedalgorithmhasbetterlocalconver-gencethanthebasicantcolonyalgorithm,anditcanobtainbet-terpaththanthatofthebasicantcolonyalgorithm・英文关键词KeyWords：antcolonyalgorithm；iterativelo-calsearch；localconvergence；pathplanning0引言路径规划是指在有障碍物的环境中寻找一条从起点到终点无碰撞地绕过所有障碍物的运动路径。路径规划算法众多，基本可分为局部路径规划和全局路径规划两类。其中，局部路径规划算法主要有人工势场法；全局路径规划算法包括栅格划归法、顶点图像法、广义锥方法和位形空间法。考虑到路径规划---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---算法目前已成为求解路径规划问题的主流方法,如蚁群算法往往是包含复杂约束的大规模优化问题，因此启发式智能优化---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除------本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---力解决优化问题。蚁群算法具有正反馈、自组织、分布式等突粒子群算法、模拟退火算法、遗传算法等。早在1998年，Patche讥1］就讨论了路径规划问题中的关键优化技术及其复杂性;Dong［2］、Zheng［3］和Nikolos等⑷系统研究了路径规划中进化算法的优化原理。蚁群算法(AntColonyOptimization,ACO)是由意大利学者MDorigo［5］于1992年首先提出的一种新型智能进化算法，其基本思想是通过模拟蚁群在搜索食物过程中的寻优能出优点，缺陷是收敛速度慢，易陷于局部最优解。迭代局部搜索(IteratedLocalSearch,ILS)最早由Lourenco等［6］于2002年提出，是一种简单而有效的元启发式算法，主要通过摄动的方法改善算法局部搜索能力。迭代局部搜索一经提出，立即被用于求解TSP问题［7］和调度问题［8］,并取得了良好的效果。目前，对迭代局部搜索的应用研究已取得了一系列成果。张志强［9］较早将迭代局部搜索策略应用于蚁群算法；王海斌［10］在粒子群优化算法中引入了迭代局部搜索；高超等［11-14］系统地研究了迭代局部搜索，并将其应用于车辆路径规划问题。本文提岀一种基于图论和迭代局部搜索的二维路径规划蚁群算法(ILS-ACO),并根据数值实验对该算法进行性能测试。1二维路径规划问题的空间模型与dijkstra算法1.1MAKLINK图本文通过构建MAKLINK图的方法建立二维路径规划空间模型［15---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---］。MAKLINK图是指两个障碍物之间不与障碍物相交顶点之间的连线，以及障碍物顶点与边界相交的连线，主要作用是生成二维路径规划的初始可行空间。图1即为本文实例...