高级搜索

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

唐红亮 吴柏林 胡旺 康承旭

引用本文: 唐红亮, 吴柏林, 胡旺, 康承旭. 基于粒子群优化的地震应急物资多目标调度算法[J]. 电子与信息学报, 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, 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]

      吕增威, 魏振春, 韩江洪, 孙仁浩, 夏成凯. 基于多目标优化的无线传感器网络移动充电及数据收集算法. 电子与信息学报,

    2. [2]

      庄雷, 田帅魁, 和孟佯, 宋玉, 王国卿, 刘文覃, 马岭. 基于滑动区域的粒子群虚拟网节能映射算法. 电子与信息学报,

    3. [3]

      董书琴, 张斌. 基于深度特征学习的网络流量异常检测方法. 电子与信息学报,

    4. [4]

      钱亚冠, 卢红波, 纪守领, 周武杰, 吴淑慧, 云本胜, 陶祥兴, 雷景生. 基于粒子群优化的对抗样本生成算法. 电子与信息学报,

    5. [5]

      殷礼胜, 唐圣期, 李胜, 何怡刚. 基于整合移动平均自回归和遗传粒子群优化小波神经网络组合模型的交通流预测. 电子与信息学报,

    6. [6]

      杨善超, 田康生, 刘仁争, 郑玉军. 基于价值优化的相控阵雷达任务调度算法. 电子与信息学报,

    7. [7]

      丛雯珊, 余岚, 沃江海. 基于粒子群算法的宽带真延时方向图栅瓣抑制方法. 电子与信息学报,

    8. [8]

      魏嘉琪, 张磊, 刘宏伟, 盛佳恋. 曲线交叠外推的微动多目标宽带分辨算法. 电子与信息学报,

    9. [9]

      余东平, 郭艳, 李宁, 刘杰, 杨思星. 基于多维测量信息的压缩感知多目标无源被动定位算法. 电子与信息学报,

    10. [10]

      余东平, 郭艳, 李宁, 杨思星, 宋晓祥. 压缩感知多目标无源定位中的字典适配方法. 电子与信息学报,

    11. [11]

      和孟佯, 庄雷, 龙卫兵, 王国卿. 基于纳什议价的虚拟网多目标映射算法. 电子与信息学报,

    12. [12]

      赵凤, 张咪咪, 刘汉强. 区域信息驱动的多目标进化半监督模糊聚类图像分割算法. 电子与信息学报,

    13. [13]

      陈树新, 洪磊, 吴昊, 刘卓崴, 岳龙华. 学生 t 混合势均衡多目标多伯努利滤波器. 电子与信息学报,

    14. [14]

      金松坡, 庄珊娜. 基于序列优化的认知雷达稳健旁瓣抑制方法. 电子与信息学报,

    15. [15]

      赵星, 彭建华, 游伟. 基于Lyapunov优化的隐私感知计算卸载方法. 电子与信息学报,

    16. [16]

      张颖, 高灵君. 基于格拉布斯准则和改进粒子滤波算法的水下传感网目标跟踪. 电子与信息学报,

    17. [17]

      徐少毅, 高帅. 机器对机器通信中一种基于能量效率与系统容量的多目标无线资源管理算法. 电子与信息学报,

    18. [18]

      黄容兰, 刘云, 李啟尚, 唐文. 基于非正交多址接入中继通信系统的功率优化. 电子与信息学报,

    19. [19]

      兰巨龙, 于倡和, 胡宇翔, 李子勇. 基于深度增强学习的软件定义网络路由优化机制. 电子与信息学报,

    20. [20]

      景小荣, 陶红宝. 一种稀疏码本多址接入码本优化设计方法. 电子与信息学报,

  • 图 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下载量:  14
  • 文章访问数:  307
  • HTML全文浏览量:  83
文章相关
  • 通讯作者:  胡旺, huwang@uestc.edu.cn
  • 收稿日期:  2019-04-22
  • 录用日期:  2019-10-30
  • 网络出版日期:  2019-11-11
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章