高级搜索

基于粒子群优化的地震应急物资多目标调度算法

唐红亮 吴柏林 胡旺 康承旭

引用本文: 唐红亮, 吴柏林, 胡旺, 康承旭. 基于粒子群优化的地震应急物资多目标调度算法[J]. 电子与信息学报, 2020, 42(3): 737-745. doi: 10.11999/JEIT190277 shu
Citation:  Hongliang TANG, Bolin WU, Wang HU, Chengxu KANG. Earthquake Emergency Resource Multiobjective Schedule Algorithm Based on Particle Swarm Optimization[J]. Journal of Electronics and Information Technology, 2020, 42(3): 737-745. doi: 10.11999/JEIT190277 shu

基于粒子群优化的地震应急物资多目标调度算法

    作者简介: 唐红亮: 男,1979年生,高级工程师,硕士生导师,研究方向为地震业务计算机应用及信息化服务、地震大数据分析;
    吴柏林: 男,1993年生,硕士生,研究方向为进化优化计算;
    胡旺: 男,1974年生,副教授,硕士生导师,研究方向为进化优化计算及计算机应用技术;
    康承旭: 男,1988年生,工程师,研究方向为地震应急及GIS应用、地震大数据分析
    通讯作者: 胡旺,huwang@uestc.edu.cn
  • 基金项目: 国家自然科学基金(61976046),中国地震局地震科技星火计划(XH201801)

摘要: 合理高效地优化调度救灾物资对提升地震应急救援效果具有重要意义。地震应急需要同时兼顾时效性、公平性和经济性等相互冲突的多个调度目标。该文对地震应急物资调度问题建立了带约束的3目标优化模型,并设计了基于进化状态评估的自适应多目标粒子群优化算法(AMOPSO/ESE)来求解Pareto最优解集。然后根据“先粗后精”的决策行为模式提出了由兴趣最优解集和邻域最优解集构成的Pareto前沿来辅助决策过程。仿真表明该算法能有效地获得优化调度方案,与其他算法相比,所得Pareto解集在收敛性和多样性上具有性能优势。

English

    1. [1]

      唐伟勤, 邹丽, 郭其云. 多应急点多需求点物资调度的灰色多目标规划[J]. 中国安全生产科学技术, 2016, 12(11): 148–152. doi: 10.11731/j.issn.1673-193x.2016.11.025
      TANG Weiqin, ZOU Li, and GUO Qiyun. Grey multi-objective programming for materials dispatching from multiple supply points to multiple demand points[J]. Journal of Safety Science and Technology, 2016, 12(11): 148–152. doi: 10.11731/j.issn.1673-193x.2016.11.025

    2. [2]

      范杰. 震后初期救灾物资两阶段调度优化研究[D]. [硕士论文], 北京交通大学, 2017.
      FAN Jie. Research on two-stage dispatching optimization of relief supplies early after the earthquake[D]. [Master dissertation], Beijing Jiaotong University, 2017.

    3. [3]

      KENNEDY J and EBERHART R. Particle swarm optimization[C]. ICNN'95-International Conference on Neural Networks, Perth, Australia, 1995: 1942–1948. doi: 10.1109/ICNN.1995.488968.

    4. [4]

      BONYADI M R and MICHALEWICZ Z. Particle swarm optimization for single objective continuous space problems: A review[J]. Evolutionary Computation, 2017, 25(1): 1–54. doi: 10.1162/EVCO_r_00180

    5. [5]

      COELLO C A C, PULIDO G T, and LECHUGA M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 256–279. doi: 10.1109/TEVC.2004.826067

    6. [6]

      AL MOUBAYED N, PETROVSKI A, and MCCALL J. D 2MOPSO: MOPSO based on decomposition and dominance with archiving using crowding distance in objective and solution spaces[J]. Evolutionary Computation, 2014, 22(1): 47–77. doi: 10.1162/EVCO_a_00104

    7. [7]

      WU Bolin, HU Wang, HE Zhenan, et al. A many-objective particle swarm optimization based on virtual Pareto front[C]. IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil, 2018: 1–8. doi: 10.1109/CEC.2018.8477802.

    8. [8]

      LI Li, WANG Wanliang, and XU Xinli. Multi-objective particle swarm optimization based on global margin ranking[J]. Information Sciences, 2017, 375: 30–47. doi: 10.1016/j.ins.2016.08.043

    9. [9]

      HU Wang and YEN G G. Adaptive multiobjective particle swarm optimization based on parallel cell coordinate system[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(1): 1–18. doi: 10.1109/tevc.2013.2296151

    10. [10]

      毕晓君, 张磊, 肖婧. 基于双种群的约束多目标优化算法[J]. 计算机研究与发展, 2015, 52(12): 2813–2823. doi: 10.7544/issn1000-1239.2015.20148025
      BI Xiaojun, ZHANG Lei, and XIAO Jing. Constrained multi-objective optimization algorithm based on dual populations[J]. Journal of Computer Research and Development, 2015, 52(12): 2813–2823. doi: 10.7544/issn1000-1239.2015.20148025

    11. [11]

      DEB K and JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I: Solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577–601. doi: 10.1109/TEVC.2013.2281535

    1. [1]

      张凯, 陈彬, 许志伟. 基于多目标进化策略算法的DNA核酸编码设计. 电子与信息学报, 2020, 42(6): 1365-1373.

    2. [2]

      吕敬祥, 罗文浪. 无线传感网络量化及能量优化策略. 电子与信息学报, 2020, 42(5): 1118-1124.

    3. [3]

      姚敏立, 王旭健, 张峰干, 戴定成. 基于动态参数差分进化算法的多约束稀布矩形面阵优化. 电子与信息学报, 2020, 42(5): 1281-1287.

    4. [4]

      高东, 梁子林. 基于能量效率的双层非正交多址系统资源优化算法. 电子与信息学报, 2020, 42(5): 1237-1243.

    5. [5]

      宋人杰, 张元东. 基于感兴趣区域的高性能视频编码帧内预测优化算法. 电子与信息学报, 2020, 42(0): 1-7.

    6. [6]

      达新宇, 张宏伟, 胡航, 潘钰, 井锦玲. 认知无人机网络中次级链路吞吐量优化研究. 电子与信息学报, 2020, 42(0): 1-8.

    7. [7]

      雷维嘉, 杨苗苗. 时间反转多用户系统中保密和速率优化的预处理滤波器设计. 电子与信息学报, 2020, 42(5): 1253-1260.

    8. [8]

      曹祥红, 李欣妍, 魏晓鸽, 李森, 黄梦溪, 李栋禄. 基于Dijkstra-ACO混合算法的应急疏散路径动态规划. 电子与信息学报, 2020, 42(6): 1502-1509.

    9. [9]

      唐伦, 魏延南, 谭颀, 唐睿, 陈前斌. H-CRAN网络下联合拥塞控制和资源分配的网络切片动态资源调度策略. 电子与信息学报, 2020, 42(5): 1244-1252.

    10. [10]

      陈家祯, 吴为民, 郑子华, 叶锋, 连桂仁, 许力. 基于虚拟光学的视觉显著目标可控放大重建. 电子与信息学报, 2020, 42(5): 1209-1215.

    11. [11]

      刘政怡, 刘俊雷, 赵鹏. 基于样本选择的RGBD图像协同显著目标检测. 电子与信息学报, 2020, 42(0): 1-8.

    12. [12]

      黄静琪, 胡琛, 孙山鹏, 高翔, 何兵. 一种基于异步传感器网络的空间目标分布式跟踪方法. 电子与信息学报, 2020, 42(5): 1132-1139.

    13. [13]

      姜文, 牛杰, 吴一戎, 梁兴东. 机载多通道SAR运动目标方位向速度和法向速度联合估计算法. 电子与信息学报, 2020, 42(6): 1542-1548.

    14. [14]

      张文明, 姚振飞, 高雅昆, 李海滨. 一种平衡准确性以及高效性的显著性目标检测深度卷积网络模型. 电子与信息学报, 2020, 42(5): 1201-1208.

  • 图 1  “多点—多点”的2级应急物资调度网络示意图

    图 2  两级最优解集示意图

    图 3  HV指标的箱线图

    图 4  3目标地震应急资源优化调度的Pareto最优方案集

    图 5  进化状态切换的最大停滞代数敏感性分析

    表 1  进化状态评估算

     算法1 进化状态评估算法
     输入:外部档案集A,到原点的历史最小距离Hmin,进化状态
        ES,计数器Counter,状态切换阈值T
     输出:更新后的进化状态${\rm ES}' $,计数器新值${\rm Counter}' $,更新后的
        历史最小距离$H{\rm min}' $。
     (1) 计算A中每个解i到原点之间的距离,AD[i];
     (2) 将距离矩阵AD中的最小值赋予Amin;
     (3) 若 ES为进化状态EXPLOITATION
     (4) 若Hmin ≤ Amin
     (5)  计数器Counter =Counter + 1;
     (6)  若计数器 Counter 大于状态切换阈T
     (7)  则${\rm ES}' $切换为进化状态EXPLORATION;
     (8) 否则,
     (9)  将Amin赋值给$H{\rm min}' $;
     (10)  计数器Counter 重置为0;
     (11) 否则
     (12) 若Hmin大于Amin
     (13)  计数器Counter置为 0;
     (14)  新进化状态${\rm ES}' $切换为EXPLOITATION;
     (15)  将Amin赋值给$H{\rm min}' $’;
     (16) 输出${\rm ES}' $, ${\rm Counter}' $, $H{\rm min}' $.
    下载: 导出CSV

    表 2  地震应急物资多目标粒子群优化调度算法

     算法2 地震应急物资多目标粒子群优化调度算法
     输入:(1) 物资供需参数:供应点和受灾点位置向量LSLd
        物资储备矩阵As,物资需求矩阵Ad,受灾点的优先系
        数向量μd
        (2) 算法控制参数:种群粒子数NP;外部档案AE容量
        NA;最大迭代次数G;邻域最优解个数NN.
     输出:两级地震应急物资最优调度方案:兴趣最优解集AI
        邻域最优解集AN.
     (1)   根据位置向量LsLd,以及灾后交通障碍信息计算供
         应点和受灾点之间最短运输时间矩阵At
     (2)   根据As和约束条件按3.1小节初始化种群P
     (3)   将AE, AIAN设置为空集Φ
     (4)   根据式(1),式(2)和式(3)中的多目标函数和At, As, Ad
         及μd计算种群中每个粒子的适应值;
     (5)   令迭代次数t = 0;
     (6)   While tG
        (a) 根据3.2小节的外部档案更新策略更新AE
        (b) 根据3.3小节的最优解选择策略更新每个粒子的个
        体最优解和种群的全局最优解;
        (c) 根据算法1评估进化状态,自适应调节惯性系数ω
        自我认知系数c1和社会认知系数c2,并根据粒子运动方
        程更新粒子速度和位置;
        (d) 根据式(1),式(2)和式(3)中的多目标函数和At, As,
        Adμd计算P 中每个粒子的适应值;
        (e) t = t + 1;
     (7)   End;
     (8)   根据邻域最优解个数NN和外部档案AE构造两级最优
         解集AIAN
     (9)   输出AIAN.
    下载: 导出CSV

    表 7  最好、平均和最差的HV值

    MOPSOMOPSO/vPFNSGAIIIAMOPSO/ESE
    最好0.3972720.4239440.28860.440747
    平均0.3802080.4104180.24590.433046
    最差0.3489030.3860970.19020.422297
    下载: 导出CSV

    表 3  物资供应点的储存量(t)

    供应点物资种类
    k1k2
    i1450432
    i2818751
    i3432617
    下载: 导出CSV

    表 4  受灾点的物资需求量(t)

    受灾点物资种类
    k1k2
    j1705880
    j2640820
    j3320760
    j4870485
    j5905555
    下载: 导出CSV

    表 5  受灾点的物资需求紧迫系数

    受灾点所在烈度(度)受灾点类别需求紧迫系数
    j16普通6
    j27普通7
    j38普通8
    j49医院10
    j510学校12
    下载: 导出CSV

    表 6  供应点到受灾点的运输时间(h)

    供应点受灾点
    j1j2j3j4j5
    i16.24.42.40.83.6
    i21.81.70.74.22.8
    i37.61.28.14.36.2
    下载: 导出CSV
  • 加载中
图(5)表(7)
计量
  • PDF下载量:  45
  • 文章访问数:  1274
  • HTML全文浏览量:  374
文章相关
  • 通讯作者:  胡旺, huwang@uestc.edu.cn
  • 收稿日期:  2019-04-22
  • 录用日期:  2019-10-30
  • 网络出版日期:  2019-11-11
  • 刊出日期:  2020-03-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章