求解多目标路径优化问题的涟漪扩散算法

摘要

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