| 求解多目标路径优化问题的涟漪扩散算法 |
| |
| 引用本文： | 胡小兵,陈树念,张盈斐,谷升豪. 求解多目标路径优化问题的涟漪扩散算法[J]. 计算机工程与应用, 2021, 57(23): 81-90. DOI: 10.3778/j.issn.1002-8331.2103-0272 |
| |
| 作者姓名： | 胡小兵 陈树念 张盈斐 谷升豪 |
| |
| 作者单位： | 1.中国民航大学 电子信息与自动化学院,天津 3003002.中国民航大学 经济与管理学院,天津 3003003.中国民航大学 中欧航空工程师学院,天津 300300 |
| |
| 摘 要： | 对于多目标路径优化问题（MOPOP）,提出了一种求解完整（非部分或近似的）Pareto最优面的涟漪扩散算法（RSA）。新的涟漪扩散算法是在路网中模拟一场涟漪接力赛,通过对到达终点的涟漪进行回溯来确定完整的Pareto前沿。RSA类似于大多数受自然启发的方法,本质上是一个基于微观智体的自下而上的仿真模型。通过定义微观智体的行为,即路网中的节点根据到达的Pareto非占优涟漪产生新的涟漪,涟漪接力赛在宏观层面的表现为输出完整的Pareto前沿。而且,RSA仅需一次涟漪接力赛就可以找到一对多问题中每个MOPOP的完整Pareto前沿。实验结果验证了新的RSA方法的有效性和高效性。
|
| 关 键 词： | 涟漪扩散算法 多目标优化 路径优化 完整的Pareto前沿 |
New Ripple-Spreading Algorithm for Multi-objective Path Optimization |
| |
| 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. DOI: 10.3778/j.issn.1002-8331.2103-0272 |
| |
| Authors: | HU Xiaobing CHEN Shunian ZHANG Yingfei GU Shenghao |
| |
| Affiliation: | 1.College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China2.College of Economics and Managementc, Civil Aviation University of China, Tianjin 300300, China 3.Sino-European Institute of Aviation Engineering, Civil Aviation University of China, Tianjin 300300, China |
| |
| 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. |
| |
| Keywords: | ripple-spreading algorithm multi-objective optimization path optimization complete Pareto front |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
