Finding Multi-Objective Shortest Paths Using Memory-Efficient Stochastic Evolution Based Algorithm

摘要

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.