基于粒子群優(yōu)化的地震應急物資多目標調度算法
doi: 10.11999/JEIT190277
-
1.
湖南省地震局 長沙 410004
-
2.
電子科技大學計算機科學與工程學院 成都 611731
Earthquake Emergency Resource Multiobjective Schedule Algorithm Based on Particle Swarm Optimization
-
1.
Hunan Earthquake Agency, Changsha 410004, China
-
2.
School of Computer Science and Engineering, University of Electronic Science and Technology, Chengdu 611731, China
-
摘要:
合理高效地優(yōu)化調度救災物資對提升地震應急救援效果具有重要意義。地震應急需要同時兼顧時效性、公平性和經濟性等相互沖突的多個調度目標。該文對地震應急物資調度問題建立了帶約束的3目標優(yōu)化模型，并設計了基于進化狀態(tài)評估的自適應多目標粒子群優(yōu)化算法(AMOPSO/ESE)來求解Pareto最優(yōu)解集。然后根據(jù)“先粗后精”的決策行為模式提出了由興趣最優(yōu)解集和鄰域最優(yōu)解集構成的Pareto前沿來輔助決策過程。仿真表明該算法能有效地獲得優(yōu)化調度方案，與其他算法相比，所得Pareto解集在收斂性和多樣性上具有性能優(yōu)勢。
-
關鍵詞:
- 粒子群優(yōu)化 /
- 多目標優(yōu)化 /
- 地震應急 /
- 物資調度
Abstract:It is of great significance to optimize emergency resource schedule for earthquake emergency rescue. The conflicting multiple schedule goals, such as time, fairness, and cost, should be taken into consideration together in an earthquake emergency resource schedule. A three-objective optimization model with constraints is constructed according to earthquake emergency resource schedule problems. An Adaptive MultiObjective Particle Swarm Optimization (PSO) based on Evolutionary State Evaluation (AMOPSO/ESE) is proposed to optimize this model for obtaining the Pareto optimal set. At the same time, based on the decision behavior pattern of "macro first and micro later", the two-level optimal solution sets consisting of an interest optimal solution set and their neighborhood optimal solution sets are proposed to represent the Pareto front roughly, which can simplify the decision-making process. The simulation results show that the multiobjective resource schedules can be effectively obtained by the AMOPSO/ESE algorithm, and the performance of the proposed algorithm is better than that of the chosen competed algorithms in terms of convergence and diversity.
-
表 1 進化狀態(tài)評估算
算法1 進化狀態(tài)評估算法 輸入：外部檔案集A，到原點的歷史最小距離Hmin，進化狀態(tài)
ES，計數(shù)器Counter，狀態(tài)切換閾值T。輸出：更新后的進化狀態(tài)${\rm ES}' $，計數(shù)器新值${\rm Counter}' $，更新后的
歷史最小距離$H{\rm min}' $。(1) 計算A中每個解i到原點之間的距離，AD[i]； (2) 將距離矩陣AD中的最小值賦予Amin； (3) 若 ES為進化狀態(tài)EXPLOITATION (4) 若Hmin ≤ Amin (5) 計數(shù)器Counter =Counter + 1； (6) 若計數(shù)器 Counter 大于狀態(tài)切換閾T (7) 則${\rm ES}' $切換為進化狀態(tài)EXPLORATION； (8) 否則， (9) 將Amin賦值給$H{\rm min}' $； (10) 計數(shù)器Counter 重置為0； (11) 否則 (12) 若Hmin大于Amin (13) 計數(shù)器Counter置為 0； (14) 新進化狀態(tài)${\rm ES}' $切換為EXPLOITATION； (15) 將Amin賦值給$H{\rm min}' $’； (16) 輸出${\rm ES}' $, ${\rm Counter}' $, $H{\rm min}' $. 
下載: 導出CSV
表 2 地震應急物資多目標粒子群優(yōu)化調度算法
算法2 地震應急物資多目標粒子群優(yōu)化調度算法 輸入：(1) 物資供需參數(shù)：供應點和受災點位置向量LS和Ld，
物資儲備矩陣As，物資需求矩陣Ad，受災點的優(yōu)先系
數(shù)向量μd；(2) 算法控制參數(shù)：種群粒子數(shù)NP；外部檔案AE容量
NA；最大迭代次數(shù)G；鄰域最優(yōu)解個數(shù)NN.輸出：兩級地震應急物資最優(yōu)調度方案：興趣最優(yōu)解集A I和
鄰域最優(yōu)解集AN.(1) 根據(jù)位置向量Ls和Ld，以及災后交通障礙信息計算供
應點和受災點之間最短運輸時間矩陣At；(2) 根據(jù)As和約束條件按3.1小節(jié)初始化種群P； (3) 將AE, AI和AN設置為空集Φ； (4) 根據(jù)式(1)，式(2)和式(3)中的多目標函數(shù)和At, As, Ad
及μd計算種群中每個粒子的適應值；(5) 令迭代次數(shù)t = 0； (6) While t ≤ G (a) 根據(jù)3.2小節(jié)的外部檔案更新策略更新AE； (b) 根據(jù)3.3小節(jié)的最優(yōu)解選擇策略更新每個粒子的個
體最優(yōu)解和種群的全局最優(yōu)解；(c) 根據(jù)算法1評估進化狀態(tài)，自適應調節(jié)慣性系數(shù)ω，
自我認知系數(shù)c1和社會認知系數(shù)c2，并根據(jù)粒子運動方
程更新粒子速度和位置；(d) 根據(jù)式(1)，式(2)和式(3)中的多目標函數(shù)和At, As,
Ad和μd計算P 中每個粒子的適應值；(e) t = t + 1； (7) End； (8) 根據(jù)鄰域最優(yōu)解個數(shù)NN和外部檔案AE構造兩級最優(yōu)
解集AI和AN；(9) 輸出AI和AN.
下載: 導出CSV
表 7 最好、平均和最差的HV值
MOPSO MOPSO/vPF NSGAIII AMOPSO/ESE 最好 0.397272 0.423944 0.2886 0.440747 平均 0.380208 0.410418 0.2459 0.433046 最差 0.348903 0.386097 0.1902 0.422297
下載: 導出CSV
-
唐偉勤, 鄒麗, 郭其云. 多應急點多需求點物資調度的灰色多目標規(guī)劃[J]. 中國安全生產科學技術, 2016, 12(11): 148–152. doi: 10.11731/j.issn.1673-193x.2016.11.025TANG 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 范杰. 震后初期救災物資兩階段調度優(yōu)化研究[D]. [碩士論文], 北京交通大學, 2017.FAN Jie. Research on two-stage dispatching optimization of relief supplies early after the earthquake[D]. [Master dissertation], Beijing Jiaotong University, 2017. 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. 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 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 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 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. 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 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 畢曉君, 張磊, 肖婧. 基于雙種群的約束多目標優(yōu)化算法[J]. 計算機研究與發(fā)展, 2015, 52(12): 2813–2823. doi: 10.7544/issn1000-1239.2015.20148025BI 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 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 -
計量
- 文章訪問數(shù): 3452
- HTML全文瀏覽量: 1094
- PDF下載量: 126
- 被引次數(shù): 0
下載:
