Strength Pareto Evolutionary Algorithm based Multi-Objective Optimization for Shortest Path Routing Problem in Computer Networks
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.
DOI: https://doi.org/10.3844/jcssp.2011.17.26
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.
- 4,170 Views
- 4,146 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