Research Article Open Access

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

Subbaraj Potti and Chitra Chinnasamy

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.

Journal of Computer Science
Volume 7 No. 1, 2011, 17-26

DOI: https://doi.org/10.3844/jcssp.2011.17.26

Submitted On: 29 November 2010 Published On: 16 December 2010

How to Cite: Potti, S. & Chinnasamy, C. (2011). Strength Pareto Evolutionary Algorithm based Multi-Objective Optimization for Shortest Path Routing Problem in Computer Networks. Journal of Computer Science, 7(1), 17-26. https://doi.org/10.3844/jcssp.2011.17.26

  • 3,676 Views
  • 3,915 Downloads
  • 7 Citations

Download

Keywords

  • Shortest path routing problem
  • evolutionary algorithm
  • multi-objective optimization
  • clustering
  • strength pareto evolutionary algorithm
  • Genetic Algorithm (GA)
  • Particle Swarm Optimization (PSO)
  • Non-dominated Sorting Genetic Algorithm (NSGA)
  • Quality of Service (QoS)
  • dynamic programming
  • communication networks