Title: A novel multi-objective evolutionary algorithm for shortest path routing problem

Authors: C. Chitra, Subbaraj Potti, P. Subbaraj

Addresses: Department of Electronics and Communication Engineering, Arulmigu Kalasalingam College of Engineering, Krishnankoil – 626-190, Tamilnadu, India. ' Professor Department of Electronics and Communication Engineering Arulmigu Kalasalingam College of Engineering, Krishnankoil 626 190, Tamilnadu, India. ' Theni Kammavar Sangam College of Technology, Theni – 625-534, Tamilnadu, India

Abstract: This paper presents an application of non-dominated sorting genetic algorithm-II (NSGA-II) technique for solving shortest path routing problems in computer networks. The problem is formulated as a non-linear constrained multi-objective optimisation problem. NSGA-II is applied to handle shortest path routing problem as a true multi-objective optimisation problem (MOOP) with competing and non-commensurable objectives. A priority-based encoding scheme is employed for population initialisation. Priorities are assigned to all the edges and NSGA-II is implemented to find the optimal solution. It is noted that this approach can find a diverse set of solutions and is converging near the true Pareto-optimal set. Results for a sample test network have been presented to demonstrate the capabilities of the NSGA-II algorithm to generate well-distributed Pareto-optimal solutions of shortest path routing problem in one single run. The results obtained by NSGA-II are compared with single objective weighting factor method for which genetic algorithm (GA) is applied.

Keywords: shortest path routing; non-dominated sorting genetic algorithm-II; NSGA-II; genetic algorithms; GAs; communication networks; weighted sum method; multi-objective optimisation.

DOI: 10.1504/IJCNDS.2011.042384

International Journal of Communication Networks and Distributed Systems, 2011 Vol.7 No.3/4, pp.355 - 374

Received: 20 Apr 2010
Accepted: 10 Oct 2010
Published online: 26 Feb 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article