Journal of Computer Science

Strength Pareto Evolutionary Algorithm based Multi-Objective Optimization for Shortest Path Routing Problem in Computer Networks

Subbaraj Potti and Chitra Chinnasamy

DOI : 10.3844/jcssp.2011.17.26

Journal of Computer Science

Volume 7, Issue 1

Pages 17-26

Abstract

Problem statement: A new multi-objective approach, Strength Pareto Evolutionary Algorithm (SPEA), is presented in this paper to solve the shortest path routing problem. The routing problem is formulated as a multi-objective mathematical programming problem which attempts to minimize both cost and delay objectives simultaneously. Approach: SPEA handles the shortest path routing problem as a true multi-objective optimization problem with competing and noncommensurable objectives. Results: SPEA combines several features of previous multi-objective evolutionary algorithms in a unique manner. SPEA stores nondominated solutions externally in another continuously-updated population and uses a hierarchical clustering algorithm to provide the decision maker with a manageable pareto-optimal set. SPEA is applied to a 20 node network as well as to large size networks ranging from 50-200 nodes. Conclusion: The results demonstrate the capabilities of the proposed approach to generate true and well distributed pareto-optimal nondominated solutions.

Copyright

© 2011 Subbaraj Potti and Chitra Chinnasamy. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.