基于改进多元优化算法的动态路径规划

《基于改进多元优化算法的动态路径规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、航空学报ActaAeronauticaetAstronauticaSinicaJul．252015VoI．36No．72319．2328ISSN1000-6893ON11-1929／Vhttp：Hhkxb．buaa．edu．cahkxb@buaa．edu．on基于改进多元优化算法的动态路径规划李宝磊1，施心陵1’*，李敬敬1，吕丹桔21．云南大学信息学院，昆明65009l2．西南林业大学计算机与信息学院，昆明650224摘要：为满足动态路径规划实时性强和动态跟踪精度高的需求，提出一种基于能够同时发现并追踪多条最优以及次优路径的改进多元优化算法(IMOA)的求解方法。首先，

2、通过利用贝赛尔曲线描述路径的方法把动态路径规划问题转化为动态优化问题；然后，把相似性检测操作引入到多元优化算法(MOA)中，增加算法同时跟踪多个不同最优以及次优解的概率；最后，用IMOA对贝赛尔曲线的控制点进行寻优。实验结果表明：当最优路径由于环境变化而变为非优或者不可行时，利用IMOA对多个最优以及次优解动态跟踪的特点，能够快速调整寻优策略对其他次优路径进行寻优以期望再次找到最优路径；其综合离线性能较其他方法也有一定的提高。因此，IMOA满足动态路径规划的实际需求，适用于解决动态环境中的路径规划问题。关键词：改进多元优化算法；动态路径规划；动态优化；贝赛尔曲线；多模态优

3、化；多群优化算法中图分类号：V448文献标识码：A文章编号：1000—6893(2015)07—2319—10在移动机器人[1]、无人作战飞机[2]、航班改行[3]和月球车[4]等工程应用中，动态环境中的路径规划是一项关键技术，路径规划算法的任务就是要找到从起点到终点能够避免一切障碍(静态和动态)碰撞和雷达威胁[5]的最佳路径。路径的最优性往往是指能源、资金和时间的损耗最小，或者能够避开静止和动态的危险区而安全地到达目标位置。尽管一些传统路径规划方法(如人工势场等)能够处理静态环境中的路径规划问题，但当地图尺寸大、分辨率高且障碍物分布复杂时，传统路径规划方法便会应用受限于

4、较高的计算复杂度[6]。而在障碍物会随时间快速移动的动态环境中[7]，路径规划的在线实时性要求更高，问题也变得更加复杂Es

5、。近年来，群智能优化算法由于搜索速度快、鲁棒性强和算法简单而被用于解决复杂动态环境中的路径规划问题，并且表现出了较传统方法更佳的稳定性和灵活性[9]。根据种群的数目，群智能优化算法可分为单群和多群两类。诸如蚁群算法、遗传算法(GA)以及粒子群优化算法(PSO)等这些经典的单群优化算法实时性较差，容易陷入多峰适应度面的局部最优解而无法收敛于全局最优解[1⋯。许多学者把针对该缺点而提出的改进算法应用于解决动态路径规划问题。其中，Tuncer和Yildir

6、im[1u提出了一种基于具有新型突变算子的改进遗传算法的动态路径规划方法。在Nasrollahy和Javadi[121提出的基于PSO的路径规划方法中，无效的粒子会受到相应的惩罚。另一种基于PSO的路径规划方法，通过收稿日期：2014—08-22；退修日期：2015-01·04；录用日期：2015-01-13；网络出版时间：2015-01-1614：43网络出版地址：WWW．cnki．net／kcms／detail／11．1929V．20150116．1443．001．htmI基金项目：国家自然科学基金(61261007)；云南省重点自然科学基金(2013FA008)*通

7、讯作者．Tel：0871-65033744E-mail：xlshi@ynu．educn琴I用格武#LiBL，ShiXL，LiJJ。eta1．DynamicpathplanningbasedonimprovedmultivariantoptimizationalgorithmfJJ．ActaAeronauticaetAstronauticaSinica，2015．36(7)：2319-2328．李宝磊．施心陵．李敬墩，等．基f改进多元优亿算法的动态路径规越[∞．航空学报。2015．36(7)：2319—2328．航空学报只使用有效粒子来快速确定路径规划问题的最优解[I3

8、。

9、尽管大多数单群优化算法都能规划出一条较优的路径，但却无法满足复杂动态场景中对路径规划问题提出的实时性强和计算效率高的需求[1引。原因在于静态以及动态障碍物分布复杂，容易引起适应度值面中出现多个移动的局部最优解，其对搜索个体向不同方向的吸引会误导搜索个体，使得搜索群在多个局部最优解之间震荡而无法找到全局最优解[15

10、。多群优化算法具有便于并行处理、全局寻优实时性强以及快速跳出局部最优解的特点，用于路径规划时具有独特的优势口6

11、。鉴于动态多群粒子群优化算法(DMS—PSO)适用于解决多局部最优解函数优化问题[1”，将其应用于解决路