基于多目标模因算法的路径规划

《基于多目标模因算法的路径规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号TP学校代码10590UDC620密级公开深圳大学硕士学位论文基于多目标模因算法的路径规划学位申请人姓名肖骏专业名称模式识别与智能系统学院（系、所）计算机与软件学院指导教师姓名朱泽轩教授基于多目标模因算法的路径规划摘要路径规划目前是自主机器人、GPS导航、物流车辆调度、通信路由规划等领域的研究热点。解决路径规划问题具有广阔应用前景和重大科研价值，而路径规划算法研究是其中的核心内容。实际路径规划问题往往需要同时优化多个目标，为路径规划算法带来巨大挑战。传统的路径规划算法往往只能解决单一目标优化并存在耗时长、容易陷

2、入局部最优等缺陷。多目标演化算法（Multi-objectiveEvolutionaryAlgorithm,MOEA）具有较好的鲁棒性、扩展性、多目标全局寻优能力可以弥补传统方法的缺点，已被广泛运用于多目标路径规划问题；但演化算法由于缺乏局部定位能力，在解决复杂问题时也存在全局搜索收敛慢的缺陷。多目标模因算法（Multi-objectiveMemeticAlgorithm,MOMA）在多目标演化算法的基础上加入模因算子（局部搜索），对全局搜索获得的个体进行局部优化让它们更快局部收敛，可以充分结合全局搜索和局部搜索的优

3、点提高多目标路径规划问题寻优效率。本文研究多目标模因算法在路径规划方面的应用，主要工作为以下两个方面：(1)针对移动机器人的全局路径规划问题提出两种多目标模因算法MOMA-D和MOMA-E。MOMA-D和MOMA-E都是基于多目标演化计算框架，分别使用非支配解排序策略和分解策略同时优化路径长度和转弯角度两个不同的目标。本文提出新型路径编码方案、路径修正操作和进化算子操作，以加强算法的搜索效率并同时保证路径合法性。在模拟和真实环境的实验结果表明两种多目标模因算法都可以在复杂环境中同时优化两个目标并最终得到一系列有效路径

4、方案。(2)针对物流中一到多到一的动态收发货问题（One-to-Many-to-OneDynamicPickup-and-DeliveryProblem,1-M-1DPDP）提出一种多目标模因算法LSH-MOMA。LSH-MOMA混合多目标演化算法和基于位置敏感哈希算法（LocalSensitivityHash,LSH）的局部搜索，同时优化路径长度、响应时间和收发货量三个不同目标。在算法每次进化迭代中应用了基于LSH的路径修正和局部搜索算子来修正和优化备选路径方案。在四种不同的动态收发货问题测试中，LSH-MOMA展

5、现出同时优化三个目标并最终获得折衷最优解的高效性。本文针对移动机器人的全局路径规划问题和物流中1-M-1DPDP问题分别提出I基于多目标模因算法的路径规划不同的多目标模因算法，能够同时优化多个目标并最终获得一系列的有效路径方案，为后续相关路径规划算法的实际应用提供了经验和借鉴。关键词：路径规划；演化算法；模因算法；多目标优化IIMulti-objectivememeticalgorithmsforpathplanningAbstractPathplanningproblemisthehotspotinmanyrese

6、archareas,suchasautonomousrobotics,GPSnavigation,vehicleschedulinginlogistics,androutingprobleminnetworkcommunication.Solvingpathplanningproblemisofgreatapplicationpotentialsandresearchvalues,whereplanningalgorithmsplayapivotalrole.Real-worldpathplanningproblem

7、softencallforoptimizingmultipleobjectivessimultaneouslywhichposesgreatchallengestopathplanningalgorithm.Thetraditionalpathplanningalgorithmsweremainlydesignedtosolvesingleobjectiveproblem,andtendtobetime-consumingandgettrappedinlocaloptimalespeciallyinthecomple

8、xenvironments.Multi-objectiveevolutionaryalgorithms(MOEAs)cancompletewiththetraditionalmethodsthankstotheirrobustness,extensibilityandcapabilityofsolvingmulti-objectiveoptim