New Ripple-Spreading Algorithm for Multi-objective Path Optimization

doi:10.3778/j.issn.1002-8331.2103-0272

Abstract

Abstract:

This paper proposes a novel Ripple-Spreading Algorithm（RSA） to calculate the complete（not partial or approximated） Pareto front for Multi-Objective Path Optimization Problem（MOPOP）. Basically, the proposed RSA carries out a one-off ripple relay race in the route network, and then the complete Pareto front will be identified by backtracking those Pareto Non-Dominated Ripples（PNDRs） which reach the destination node. Like most other nature-inspired methods, RSA is actually an agent-based bottom-up simulation model. By defining micro agent behavior, i.e., how a node will generate a new ripple according to the Pareto dominance state of an incoming ripple, the complete Pareto front will emerge at the macro level of ripple relay race, with guaranteed optimality. All complete Pareto fronts of a one-to-all MOPOP can also be found in just a single run of ripple relay race. Since RSA exhibits a good capability of dealing with various complicated routing environments, such as time-window networks and dynamical networks, the reported method has a great potential of extending to many complicated MOPOPs. The effectiveness and efficiency of the proposed method is demonstrated by comparative experimental results.

Key words: ripple-spreading algorithm, multi-objective optimization, path optimization, complete Pareto front

摘要：

对于多目标路径优化问题（MOPOP），提出了一种求解完整（非部分或近似的）Pareto最优面的涟漪扩散算法（RSA）。新的涟漪扩散算法是在路网中模拟一场涟漪接力赛，通过对到达终点的涟漪进行回溯来确定完整的Pareto前沿。RSA类似于大多数受自然启发的方法，本质上是一个基于微观智体的自下而上的仿真模型。通过定义微观智体的行为，即路网中的节点根据到达的Pareto非占优涟漪产生新的涟漪，涟漪接力赛在宏观层面的表现为输出完整的Pareto前沿。而且，RSA仅需一次涟漪接力赛就可以找到一对多问题中每个MOPOP的完整Pareto前沿。实验结果验证了新的RSA方法的有效性和高效性。

关键词: 涟漪扩散算法, 多目标优化, 路径优化, 完整的Pareto前沿

HU Xiaobing, CHEN Shunian, ZHANG Yingfei, GU Shenghao. New Ripple-Spreading Algorithm for Multi-objective Path Optimization[J]. Computer Engineering and Applications, 2021, 57(23): 81-90.

胡小兵，陈树念，张盈斐，谷升豪. 求解多目标路径优化问题的涟漪扩散算法[J]. 计算机工程与应用, 2021, 57(23): 81-90.

References

[1] BARR N.Economics of the welfare state[M].New York：Oxford University Press，2004：13-14.
[2] ISHIBUCHI H，SETOGUCHI Y，MASUDA H，et al.Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes[J].IEEE Transactions on Evolutionary Computation，2017，21（2）：169-190.
[3] 康斌，刘权，黄健，等.突发事件下多目标应急救援物资配送路径规划[J].科学技术与工程，2020，20（4）：1521-1527.
KANG Bin，LIU Quan，HUANG Jian，et al.Multi-objective emergency relief supplies distribution routes planning under emergency events[J].Science Technology and Engineering，2020，20（4）：1521-1527.
[4] FIGUEIRA J，GRECO S.Multiple criteria decision analysis：state of the art surveys[M].New York：Springer-Verlag，2005：652-655.
[5] 李笠，李广鹏，常亮，等.约束进化算法及其应用研究综述[J].计算机科学，2021，48（4）：1-13.
LI Li，LI Guangpeng，CHANG Liang，et al.Survey of constrained evolutionary algorithms and their applications[J].Computer Science，2021，48（4）：1-13.
[6] DAS I，DENNIS J E.Normal-boundary intersection：a new method for generating the Pareto surface in nonlinear multicriteria optimization problems[J].SIAM Journal on Optimization，1998，8：631-657.
[7] MEHARI M，DE POORTER E，COUCKUYT I，et al.Efficient identification of a multi-objective Pareto front on a wireless experimentation facility[J].IEEE Transactions on Wireless Communications，2016：6662-6675.
[8] 万逸飞，彭力.基于协同多目标算法的多机器人路径规划[J].信息与控制，2020，49（2）：139-146.
WAN Yifei，PENG Li.Multi-robot path planning based on cooperative multi-objective algorithm[J].Information and Control，2020，49（2）：139-146.
[9] ERFANI T，UTYUZHNIKOV S V.Directed search domain：a method for even generation of Pareto front in multiobjective optimization[J].Engineering Optimization，2011，43（5）：467-484.
[10] CRAFT D，HALABI T，SHIH H，et al.Approximating convex Pareto surfaces in multiobjective radiotherapy planning[J].Medical Physics，2006，33（9）：3399-3407.
[11] MARLER R T，ARORA J S.Survey of multi-objective optimization methods for engineering[J].Struct Multidisc Optim，2004，26：369-395.
[12] 雷瑞龙，侯立刚，曹江涛.基于多策略的多目标粒子群优化算法[J].计算机工程与应用，2016，52（8）：19-24.
LEI Ruilong，HOU Ligang，CAO Jiangtao.Multi-objective particle swarm optimization algorithm based on multi-strategy[J].Computer Engineering and Applications，2016，52（8）：19-24.
[13] SCHEEPERS C，ENGELBRECHT A P，CLEGHORN C W.Multi-guide particle swarm optimization for multi-objective optimization：empirical and stability analysis[J].Swarm Intelligence，2019，13（3/4）：245-276.
[14] HUSSAIN M M，FUJIMOTO N.GPU-based parallel multi-objective particle swarm optimization for large swarms and high dimensional problems[J].Parallel Computing，2020，92（4）：1-19.
[15] IJAZ S，HASHMI F A，ASGHAR S，et al.Vector based genetic algorithm to optimize predictive analysis in network security[J].Applied Intelligence，2018，48（5）：1086-1096.
[16] JEYADEVI S，BASKAR S，BABULAL C K，et al.Solving multiobjective optimal reactive power dispatch using modified NSGA-II[J].International Journal of Electrical Power & Energy Systems，2011，33（2）：219-228.
[17] LEONG W F，YEN G G.PSO-based multiobjective optimization with dynamic population size and adaptive local archives[J].IEEE Transactions on Systems，Man，and Cybernetics：Part B，2008，38（5）：1270-1293.
[18] ALI E S，ABD ELAZIM S M，ABDELAZIZ A Y.Ant lion optimization algorithm for renewable distributed generations[J].Energy，2016，116（1）：445-458.
[19] 鞠录岩，杨建军，张建兵，等.改进NSGA算法求解多目标柔性车间作业调度问题[J].计算机工程与应用，2019，55（13）：260-265.
JU Luyan，YANG Jianjun，ZHANG Jianbing，et al.Improved NSGA for multi-objective flexible job-shop scheduling problem[J].Computer Engineering and Applications，2019，55（13）：260-265.
[20] ZOU X F，CHEN Y，LIU M Z，et al.A new evolutionary algorithm for solving many-objective optimization problems[J].IEEE Trans on Systems，Man，and Cybernetics：Part B，2008，38（5）：1402-1412.
[21] HU X B，WANG M，DI PAOLO E.Calculating complete and exact pareto front for multi-objective optimization：a new deterministic approach for discrete problems[J].IEEE Transactions on Cybernetics，2013，43（3）：1088-1101.
[22] HU X B，WANG M，YE Q，et al.Multi-objective new product development by complete Pareto front and ripple-spreading algorithm[J].Neurocomputing，2014，142：4-15.
[23] HU X B，WANG M，YE T，et al.A new method for resource allocation optimization in disaster reduction and risk governance[J].International Journal of Disaster Risk Science，2016，7（2）：138-150.
[24] 赵星，吉康，林灏，等.基于多目标路径规划的应急资源配置模型[J].华南理工大学学报（自然科学版），2019，47（4）：76-82.
ZHAO Xing，JI Kang，LIN Hao，et al.Resource allocation model based on multi-objective path planning in emergency management[J].Journal of South China University of Technology（Natural Science Edition）2019，47（4）：76-82.
[25] PULIDO F J，MANDOW L，PEREZ-LA-CRUZ J L.Dimensionality reduction in multiobjective shortest path search[J].Computers & Operations Research，2015，64：60-70.
[26] 王树西，李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学，2014，41（6）：217-224.
WANG Shuxi，LI Anyu.Multi neighbor contact and multiple shortest path problem in Dijkstra algorithm[J].Computer Science，2014，41（6）：217-224.
[27] DUQUE D，LOZANO L，MEDAGLIA A.An exact method for the biobjective shortest path problem for large-scale road networks[J].European Journal of Operational Research，2015，242：788-797.
[28] HU X B，WANG M，LEESON M S，et al.Deterministic agent-based path optimization by mimicking the spreading of ripples[J].Evolutionary Computation，2016，24（2）：319-346.
[29] HU X B，ZHANG C，ZHANG G P，et al.Finding the k shortest paths by ripple-spreading algorithms[J].Engineering Applications of Artificial Intelligence，2020，87：103229.
[30] HU X B，ZHANG M K，ZHANG Q，et al.Co-evolutionary path optimization by ripple-spreading algorithm[J].Transportation Research：Part B，2017，106：411-432.
[31] WEN H Y，LIN Y F，WU J B.Co-evolutionary optimization algorithm based on the future traffic environment for emergency rescue path planning[J].IEEE Access，2020，8：148125-148135.