Finding Multi-Objective Shortest Paths Using Memory-Efficient Stochastic Evolution Based Algorithm
Finding Multi-Objective Shortest Paths Using Memory-Efficient Stochastic Evolution Based Algorithm
复制标题
DOI：
10.1109/icnc.2012.35
复制
发表时间：
2012-12
期刊：
影响因子：
--
通讯作者：
U. F. Siddiqi;Y. Shiraishi;Mona Abo El Dahb;S. M. Sait
中科院分区：
文献类型：
--
作者：
U. F. Siddiqi;Y. Shiraishi;Mona Abo El Dahb;S. M. Sait
多目标最短路径（MOSP）计算是许多应用中的关键操作。MOSP问题的目的是寻找网络中源节点和目的节点之间的最优路径。本文提出了一种基于随机进化（StocE）的算法来求解MOSP问题。该算法适用于一个单一的解决方案，是内存效率比进化算法（EA）的工作人口的解决方案。该算法以解中的不同子路径为特征，逐代用好的子路径代替坏的子路径。该算法与非支配排序遗传算法-II（NSGA-II），微遗传算法（MicroGA），多目标模拟退火（MOSA），和一个直接的StocE。比较结果表明，该算法通常比其他算法，工作在一个单一的解决方案（即MOSA和直接StocE），也很少比工作在一个人口的解决方案（即NSGA-II和MicroGA）的算法表现得更好。因此，我们所提出的算法是适合于解决MOSP在嵌入式系统中，有有限的内存量。
Multi-objective shortest path (MOSP) computation is a critical operation in many applications. MOSP problem aims to find optimal paths between source and destination nodes in a network. This paper presents a stochastic evolution (StocE) based algorithm for solving the MOSP problem. The proposed algorithm works on a single solution and is memory efficient than the evolutionary algorithms (EAs) that work on a population of solutions. In the proposed algorithm, different sub-paths in the solution are considered as its characteristics and bad sub paths are replaced by good sub-paths from generation to generation. The proposed algorithm is compared with non-dominated sorting genetic algorithm-II (NSGA-II), micro genetic algorithm (MicroGA), multi-objective simulated annealing (MOSA), and a straight-forward StocE. The comparison results show that the proposed algorithm generally performs better than the other algorithms that works on a single solution (i.e. MOSA and straight-forward StocE) and also infrequently performs better than the algorithms that work on a population of solutions (i.e. NSGA-II and MicroGA). Therefore, our proposed algorithm is suitable to solve MOSP in embedded systems that have a limited amount of memory.