留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

多种群合作学习的多模态多目标路径规划算法

赵萌 路辉 王诗琪 杨思旖 王赞

赵萌,路辉,王诗琪,等. 多种群合作学习的多模态多目标路径规划算法[J]. 北京航空航天大学学报,2023,49(3):606-616 doi: 10.13700/j.bh.1001-5965.2021.0274
引用本文: 赵萌,路辉,王诗琪,等. 多种群合作学习的多模态多目标路径规划算法[J]. 北京航空航天大学学报,2023,49(3):606-616 doi: 10.13700/j.bh.1001-5965.2021.0274
ZHAO M,LU H,WANG S Q,et al. A multimodal multi-objective path planning algorithm based on multi-swarm cooperative learning[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(3):606-616 (in Chinese) doi: 10.13700/j.bh.1001-5965.2021.0274
Citation: ZHAO M,LU H,WANG S Q,et al. A multimodal multi-objective path planning algorithm based on multi-swarm cooperative learning[J]. Journal of Beijing University of Aeronautics and Astronautics,2023,49(3):606-616 (in Chinese) doi: 10.13700/j.bh.1001-5965.2021.0274

多种群合作学习的多模态多目标路径规划算法

doi: 10.13700/j.bh.1001-5965.2021.0274
基金项目: 国家自然科学基金(61671041);陕西省组合与智能导航重点实验室开放基金(SKLIIN-20190201)
详细信息
    通讯作者:

    E-mail:mluhui@buaa.edu.cn

  • 中图分类号: TP181

A multimodal multi-objective path planning algorithm based on multi-swarm cooperative learning

Funds: National Natural Science Foundation of China (61671041); The Foundation of Shaanxi Key Laboratory of Integrated and Intelligent Navigation (SKLIIN-20190201)
More Information
  • 摘要:

    为同时规划出满足多种目标需求的多条可行路径,提高规划路径的鲁棒性与实用性,提出一种基于多种群合作学习的路径规划算法。基于粒子群算法的基本思想,先针对单一种群在多维目标空间内搜索时容易陷入局优的问题,提出基于多目标分解的子种群划分策略,平衡算法在目标空间内各个维度上的搜索能力。再依据地图中栅格点的出入度信息提取关键路径点。在编码阶段,根据关键路径点提供的维度信息,利用实数编码的方式初始化种群,降低解空间大小;在解码阶段,提出利用精英解的解码经验指导可行解的快速搜索,使解码经验能够被有效传递,降低解码的不确定性,提高了算法的寻优能力。最后,将多个种群的搜索结果进行非支配排序,得到满足优化目标的所有路径。实验结果表明:与标准粒子群算法相比,基于解码经验表指导的多种群合作学习算法具有更强的搜索能力和寻优能力,能够解决多模态多目标路径规划问题。

     

  • 图 1  多种群合作学习算法框架

    Figure 1.  Framework of the proposed algorithm

    图 2  关键路径点的提取

    Figure 2.  Extraction of key path points

    图 3  有3个优化目标时单一种群的粒子群寻优过程

    Figure 3.  Optimization process of particles when there are three objectives to be optimized

    图 4  有3个优化目标时基于子种群划分策略的粒子群寻优过程

    Figure 4.  Optimization process of particles when there are three objectives to be optimized

    图 5  粒子的寻优过程

    Figure 5.  The optimization process of the particles.

    图 6  解码经验表

    Figure 6.  Decoding experience table

    图 7  一个多模态多目标路径规划问题的应用实例

    Figure 7.  An application example of MMOPP problem

    图 8  多种群合作学习算法流程

    Figure 8.  Flowchart of multi-swarm cooperative learning algorithm

    图 9  种群(路径码)初始化结果

    Figure 9.  Result of initialing particle swarm (path codes)

    图 10  以种群1为例的路径解码过程

    Figure 10.  Path decoding process of the first sub-swarm that is responsible for optimizing path length

    图 11  第1类MMOPP测试问题实例

    Figure 11.  An example of the first kind of MMOPP test problem

    图 12  第2类MMOPP测试问题实例

    Figure 12.  An example of the second kind of MMOPP test problem

    图 13  第3类MMOPP测试问题实例

    Figure 13.  An example of the third kind of MMOPP test problem

    图 14  不同算法搜索到的最优路径数量

    Figure 14.  Number of the optimal paths searched by different algorithms

    图 15  不同算法规划路径所需时间

    Figure 15.  Time used in path planning for different algorithms

    表  1  实验参数

    Table  1.   Experimental parameters

    参数数值测试问题迭代次数
    ${c_1}$2TP15
    ${c_2}$2TP210
    ${v_{\min }}$0.4TP315
    ${v_{\max }}$0.9TP410
    ${x_{\min }}$0TP5150
    ${x_{\max }}$1TP610
    $\alpha $0.9TP750
    $\gamma $0.1TP8300
    $\varepsilon $0.5TP9300
    $\delta $100TP10300
    $\beta $10TP1110
    $n$50TP12300
    下载: 导出CSV

    表  2  不同算法的求解时间

    Table  2.   Solving time of different algorithms

    测试问题求解时间/s
    PSOPSOKPSODMSCL
    TP10.070.070.110.13
    TP20.160.180.270.36
    TP30.260.290.430.63
    TP40.180.200.300.41
    TP52.893.266.348.09
    TP60.140.150.210.25
    TP70.790.901.521.47
    TP88.219.0521.9916.60
    TP911.3011.8135.3521.66
    TP1024.3225.6360.5240.94
    TP110.180.200.310.33
    TP125.416.2110.8812.05
    下载: 导出CSV

    表  3  不同算法搜索到的路径数量

    Table  3.   Number of paths searched by different algorithms

    测试问题路径数量
    PSOPSOKPSODMSCL
    TP17.087.248.568.66
    TP28.147.8610.4412.02
    TP33.523.485.863.56
    TP45.385.567.287.78
    TP55.385.111.2616.86
    TP64.54.544.624.62
    TP715.3215.3212.9815.58
    TP844.3445.0233.6644.1
    TP973.3274.5451.6481.68
    TP10111108.8150.02215.42
    TP113.98444
    TP127.887.6210.512
    下载: 导出CSV

    表  4  不同算法的搜索到的最优路径数量对比

    Table  4.   Number of optimal paths searched by different algorithms

    测试问题最优路径数量
    PSOPSOKPSODMSCL
    TP15.725.827.487.78
    TP26.746.829.8211.62
    TP30.540.582.142.58
    TP43.23.467.087.34
    TP53.42.7610.4815.28
    TP64.44.344.564.5
    TP715.115.1612.0815.38
    TP830.5231.4822.3237.74
    TP968.4869.2648.5479.98
    TP1073.8272.78109.16179.56
    TP113.96444
    TP125.645.089.811.94
    下载: 导出CSV

    表  5  不同算法搜索到的最优路径占比

    Table  5.   Proportion of optimal paths in paths searched by different algorithms

    测试问题最优路径占比/%
    PSOPSOKPSODMSCL
    TP163.5664.6783.1186.44
    TP251.8552.4675.5489.38
    TP313.5014.5053.5064.50
    TP440.0043.2588.5091.75
    TP517.8914.5355.1680.42
    TP688.0086.8091.2090.00
    TP794.3894.7575.5096.13
    TP863.5865.5846.5078.63
    TP965.2265.9646.2376.17
    TP104.964.897.3412.08
    TP1199.00100.00100.00100.00
    TP1240.2936.2970.0085.29
    下载: 导出CSV

    表  6  测试问题难度等级分析

    Table  6.   Analysis of difficulty level of test problems

    测试
    问题
    目标
    数量
    地图边
    长/格
    编码
    维度
    最优路径
    数量
    求解难度
    等级
    TP33507141
    TP62404551
    TP12404592
    TP43506382
    TP234046133
    TP734046164
    TP5384139195
    TP845071485
    TP9550631055
    TP1078413914876
    下载: 导出CSV
  • [1] DEB K. Multi-objective genetic algorithms: Problem difficulties and construction of test problems[J]. Evolutionary Computation, 1999, 7(3): 205-230. doi: 10.1162/evco.1999.7.3.205
    [2] FENG G, KORKMAZ T. Finding multi-constrained multiple shortest paths[J]. IEEE Transactions on Computers, 2015, 64(9): 2559-2572. doi: 10.1109/TC.2014.2366762
    [3] 王树西, 李安渝. Dijkstra算法中的多邻接点与多条最短路径问题[J]. 计算机科学, 2014, 41(6): 217-224. doi: 10.11896/j.issn.1002-137X.2014.06.043

    WANG S X, LI A Y. Multi-adjacent-vertexes and multi-shortest-paths problem of Dijkstra algorithm[J]. Computer Science, 2014, 41(6): 217-224(in Chinese). doi: 10.11896/j.issn.1002-137X.2014.06.043
    [4] HAYAT S, YANMAZ E, BROWN T X, et al. Multi-objective UAV path planning for search and rescue[C]//IEEE International Conference on Robotics and Automation. Piscataway: IEEE Press, 2017, 5569-5574.
    [5] 马小铭, 靳伍银. 基于改进蚁群算法的多目标路径规划研究[J]. 计算技术与自动化, 2020, 39(4): 100-105. doi: 10.16339/j.cnki.jsjsyzdh.202004018

    MA X M, JIN W Y. Multi-objective path planning based on improved and colony algorithm[J]. Computing Technology and Automation, 2020, 39(4): 100-105(in Chinese). doi: 10.16339/j.cnki.jsjsyzdh.202004018
    [6] DENG Y T, RONG D C, SHANGGUAN W, et al. Multi-objective path optimization method in terminal building based on improved genetic algorithm[C]//Chinese Automation Congress. 2020, 3181-3186.
    [7] NAZARAHARI M, KHANMIRZA E, DOOSTIE S. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm[J]. Expert Systems with Applications, 2018, 115: 106-120.
    [8] LI Z J, LIU Y, YANG Z. An effective kernel search and dynamic programming hybrid heuristic for a multimodal transportation planning problem with order consolidation[J]. Transportation Research Part E:Logistics and Transportation Review, 2021, 152: 102408. doi: 10.1016/j.tre.2021.102408
    [9] WANG Z Z, ZHANG M H, CHU R J, et al. Modeling and planning multimodal transport paths for risk and energy efficiency using AND/OR graphs and discrete ant colony optimization[J]. IEEE Access, 2020, 8: 132642-132654.
    [10] 张启钱, 许卫卫, 张洪海, 等. 复杂低空物流无人机路径规划[J]. 北京航空航天大学学报, 2020, 46(7): 1275-1286. doi: 10.13700/j.bh.1001-5965.2019.0455

    ZHANG Q Q, XU W W, ZHANG H H, et al. Plan planning for logistics UAV in complex low-altitude airspace[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(7): 1275-1286(in Chinese). doi: 10.13700/j.bh.1001-5965.2019.0455
    [11] MIAO C, GHEN G, YAN C, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J]. Computers & Industrial Engineering, 2021, 156: 107230.
    [12] ZHOU X, WANG X, GU X. Welding robot path planning problem based on discrete MOEA/D with hybrid environment selection[J]. Neural Computing and Applications, 2021, 4: 12881-12903.
    [13] 肖博. 基于多目标优化的震后应急物流路径规划研究[D]. 西安: 长安大学, 2019: 10-14.

    XIAO B. Study on post-earthquake emergency logistics path planning based on multi-objective optimization[D]. Xi’an: Chang’an University, 2019: 10-14(in Chinese).
    [14] CHOU Y T, HSIA S Y, LAN C H. A hybrid approach on multi-objective route planning and assignment optimization for urban lorry transportation[C]//International Conference on Applied System Innovation. Piscataway: IEEE Press, 2017: 1006-1009.
    [15] 蒋强, 易春林, 张伟, 等. 基于蚁群算法的移动机器人多目标路径规划[J]. 计算机仿真, 2021, 38(2): 318-325. doi: 10.3969/j.issn.1006-9348.2021.02.068

    JIANG Q, YI C L, ZHANG W, et al. The multi-objective path planning for mobile robot based on ant colony algorithm[J]. Computer Simulation, 2021, 38(2): 318-325(in Chinese). doi: 10.3969/j.issn.1006-9348.2021.02.068
    [16] 王晨宇. 基于智能优化算法的多目标路径规划方法研究[D]. 桂林: 桂林电子科技大学, 2020: 18-27.

    WANG C Y. Research on multi-objective path planning method based on intelligent optimization algorithm[D]. Guilin: Guilin University of Electronic Technology, 2020: 18-27(in Chinese).
    [17] 熊昕霞, 何利力. 基于混合粒子群算法的移动机器人路径规划[J]. 计算机系统应用, 2021, 30(4): 153-159. doi: 10.15888/j.cnki.csa.007865

    XIONG X X, HE L L. Path planning for mobile robot based on improved particle swarm optimization algorithm[J]. Computer Systems & Applications, 2021, 30(4): 153-159(in Chinese). doi: 10.15888/j.cnki.csa.007865
    [18] GUL F, RAHIMAN W, ALHADY S S N, et al. Meta-heuristic approach for solving multi-objective path planning for autonomous guided robot using PSO-GWO optimization algorithm with evolutionary programming[J]. Journal of Ambient Intelligence and Humanized Computing, 2021, 12: 7873-7890. doi: 10.1007/s12652-020-02514-w
    [19] HIDALGO-PANIAGUA A, VEGA-RODRÍGUEZ M A, FERRUZ J, et al. Solving the multi-objective path planning problem in mobile robotics with a firefly-based approach[J]. Soft Computing, 2017, 21(4): 1-16.
    [20] 段益琴. 基于多目标优化的多机器人路径规划研究[D]. 重庆: 重庆邮电大学, 2020: 23-34.

    DUAN Y Q. Research on multi-robot path planning based on multi-objective optimization[D]. Chongqing: Chongqing University of Posts and Telecommunications, 2020: 23-34(in Chinese).
    [21] 樊娇, 雷涛, 董南江, 等. 基于改进NSGA-Ⅱ算法的多目标无人机路径规划[J]. 火力与指挥控制, 2022, 47(2): 43-48. doi: 10.3969/j.issn.1002-0640.2022.02.008

    FAN J, LEI T, DONG N J, et al. Multi-objective UAV path planning based on an improved NSGA-Ⅱ[J]. Fire Control & Command Control, 2022, 47(2): 43-48(in Chinese). doi: 10.3969/j.issn.1002-0640.2022.02.008
    [22] DHIKARI D, KIM E, REZA H. A fuzzy adaptive differential evolution for multi-objective 3D UAV path optimization[C]//IEEE Congress on Evolutionary Computation. Piscataway: IEEE Press, 2017: 2258-2265.
    [23] SHI Y, EBERHART R. A modified particle swarm optimizer[C]//IEEE World Congress on Computational Intelligence. Piscataway: IEEE Press, 1998: 69-73.
    [24] EBERHART R, KENNEDY J. A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Piscataway: IEEE Press, 1995: 39-43.
    [25] LIANG J, YUE C, LI G, et al. Problem definitions and evaluation criteria for the CEC 2021 on multimodal multiobjective path planning optimization[EB/OL]. (2020-12)[2021-05-24]. https://cec2021.mini.pw.edu.pl/en/program/competitions-C-8.
  • 加载中
图(15) / 表(6)
计量
  • 文章访问数:  535
  • HTML全文浏览量:  113
  • PDF下载量:  84
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-05-27
  • 录用日期:  2021-08-22
  • 网络出版日期:  2021-09-29
  • 整期出版日期:  2023-03-30

目录

    /

    返回文章
    返回
    常见问答