A novel multi-objective evolutionary algorithm for shortest path routing problem. (1st January 2011)

• Record Type: Journal Article
• Authors: Chitra, C.; Subbaraj, P.
• Is Part Of: International journal of communication networks and distributed systems. Volume 7:Number 3/4(2011)
• Page Start: 355
• Page End: 374
• Publication Date: 2011-01-01
• Subjects: shortest path routing -- non-dominated sorting genetic algorithm-II -- communication network -- weighted sum method -- multi-objective optimisation; Computer networks -- Periodicals; Telecommunication systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; 004.6
• DOI: 10.1504/IJCNDS.2011.042384
• Languages: English
• ISSNs: 1754-3916

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.