Multiobjective Optimization Solution for Shortest Path Routing Problem
The shortest path routing problem is a multiobjective
nonlinear optimization problem with constraints. This problem has
been addressed by considering Quality of service parameters, delay
and cost objectives separately or as a weighted sum of both
objectives. Multiobjective evolutionary algorithms can find multiple
pareto-optimal solutions in one single run and this ability makes them
attractive for solving problems with multiple and conflicting
objectives. This paper uses an elitist multiobjective evolutionary
algorithm based on the Non-dominated Sorting Genetic Algorithm
(NSGA), for solving the dynamic shortest path routing problem in
computer networks. A priority-based encoding scheme is proposed
for population initialization. Elitism ensures that the best solution
does not deteriorate in the next generations. Results for a sample test
network have been presented to demonstrate the capabilities of the
proposed approach to generate well-distributed pareto-optimal
solutions of dynamic routing problem in one single run. The results
obtained by NSGA are compared with single objective weighting
factor method for which Genetic Algorithm (GA) was applied.
[1] George N. Rouskas and Ilia Baldine, "Multicast Routing with End-to-
End Delay and Delay Variation Constraints," IEEE Journal on Selected
Areas in Communications, vol.15, No.3, pp.346-356, 1997.
[2] Jose Craveirinha, Rita Girao-Silva and Joao Climaco, "A meta-model
for multiobjective routing in MPLS networks," Central European
Journal of Operation Research (Springer), vol.16, No.1, pp.79-105,
2008.
[3] Sriram, R., Manimaran, G., and Siva Ram Murthy, C., "Preferred link
based delay-constrained least-cost routing in wide area networks,"
Computer Communications, vol. 21, pp. 1655-1669, 1998.
[4] Aluizio F. R. Araujo, Cicero Garrozi, Andre R. G. A. Leitao and Maury
M. Gouvea Jr., "Multicast Routing Using Genetic Algorithm Seen as a
Permutation Problem", 20th International Conference on Advanced
Information Networking and Applications (AINA-06), Vienna, 2006,
vol. 1, pp. 477-484.
[5] Chang Wook and Ramakrishna, R.S., "A genetic algorithm for shortest
path routing problem and the sizing of populations", IEEE Transactions
on Evolutionary Computation, vol.6, No.6, pp.566-579, 2002.
[6] Ha Chen and Baolin Sun, "Multicast Routing Optimization Algorithm
with Bandwidth and Delay Constraints Based on GA," Journal of
Communication and Computer, vol. 2, No.5, pp.63-67, 2005.
[7] Hayder A. Mukhef, Ekhlas M. Farhan and Mohammed R. Jassim (2008)
"Generalized Shortest Path Problem in Uncertain Environment Based
on PSO," Journal of Computer Science, vol. 4, No. 4, pp. 349-352.
[8] Abido, M. A., "A novel multiobjective evolutionary algorithm for
environmental/economic power dispatch," Electric Power Systems
Research, vol. 65, No. 1, pp 71-81, 2003.
[9] Kalyanmoy Deb and Santosh Tiwari, "Omni-optimizer: A generic
evolutionary algorithm for single and multiobjective optimization,"
European Journal of Operational Research, vol. 185, No. 3, pp. 1062-
1087, 2008.
[10] Srinivas, N. and Deb, K., "Multiobjective Optimization using Nondominated
Sorting in Genetic Algorithm," Evolutionary Computation,
vol. 2, No. 3, pp. 221-248, 1994.
[11] Kalyanmoy Deb, Multiobjective Optimization using Evolutionary
Algorithms. New York: John Wiley & Sons., 2001, ch. 5.
[12] Omar Al Jadaan, Lakishmi Rajamani, C. R. Rao, "Non-dominated
ranked genetic algorithm for Solving multiobjective optimization
Problems: NRGA", Journal of Theoretical and Applied Information
Technology, pp. 60-67, 2008.
[13] K. Rath and S. N. Dehuri, "Non-dominated Sorting Genetic Algorithms
for heterogeneous Embedded System Design", Journal of Computer
Science, 2 (3), pp. 288-291, 2006.
[14] N. Srinivas and Kalyanmoy Deb, "Muiltiobjective Optimization Using
nondominated Sorting in Genetic Algorithms," Evolutionary
computation, vol. 2, No. 3, pp. 221-248, 2007.
[15] Jose Maria A. Pangilinan and Gerrit K. Janssens, "Evolutionary
Algorithms for the Multiobjective Shortest Path Problem," World
Academy of Science, Engineering and Technology, vol. 25, pp. 205-210,
2007.
[16] Salman Yussof and Ong Hang See, "Finding Multi-Constrained Path
Using Genetic Algorithm," Proc. IEEE International Conference on
Telecommunications and Malaysia International Conference on
Communications, Penang, 2007, vol.1, pp.1-6.
[17] Salman Yussof and Ong Hang See, "QoS Routing for Multiple
Additive QoS Parameters using Genetic Algorithm," Proc. International
Conference on Communication, vol.1, pp.99-104, 2005.
[1] George N. Rouskas and Ilia Baldine, "Multicast Routing with End-to-
End Delay and Delay Variation Constraints," IEEE Journal on Selected
Areas in Communications, vol.15, No.3, pp.346-356, 1997.
[2] Jose Craveirinha, Rita Girao-Silva and Joao Climaco, "A meta-model
for multiobjective routing in MPLS networks," Central European
Journal of Operation Research (Springer), vol.16, No.1, pp.79-105,
2008.
[3] Sriram, R., Manimaran, G., and Siva Ram Murthy, C., "Preferred link
based delay-constrained least-cost routing in wide area networks,"
Computer Communications, vol. 21, pp. 1655-1669, 1998.
[4] Aluizio F. R. Araujo, Cicero Garrozi, Andre R. G. A. Leitao and Maury
M. Gouvea Jr., "Multicast Routing Using Genetic Algorithm Seen as a
Permutation Problem", 20th International Conference on Advanced
Information Networking and Applications (AINA-06), Vienna, 2006,
vol. 1, pp. 477-484.
[5] Chang Wook and Ramakrishna, R.S., "A genetic algorithm for shortest
path routing problem and the sizing of populations", IEEE Transactions
on Evolutionary Computation, vol.6, No.6, pp.566-579, 2002.
[6] Ha Chen and Baolin Sun, "Multicast Routing Optimization Algorithm
with Bandwidth and Delay Constraints Based on GA," Journal of
Communication and Computer, vol. 2, No.5, pp.63-67, 2005.
[7] Hayder A. Mukhef, Ekhlas M. Farhan and Mohammed R. Jassim (2008)
"Generalized Shortest Path Problem in Uncertain Environment Based
on PSO," Journal of Computer Science, vol. 4, No. 4, pp. 349-352.
[8] Abido, M. A., "A novel multiobjective evolutionary algorithm for
environmental/economic power dispatch," Electric Power Systems
Research, vol. 65, No. 1, pp 71-81, 2003.
[9] Kalyanmoy Deb and Santosh Tiwari, "Omni-optimizer: A generic
evolutionary algorithm for single and multiobjective optimization,"
European Journal of Operational Research, vol. 185, No. 3, pp. 1062-
1087, 2008.
[10] Srinivas, N. and Deb, K., "Multiobjective Optimization using Nondominated
Sorting in Genetic Algorithm," Evolutionary Computation,
vol. 2, No. 3, pp. 221-248, 1994.
[11] Kalyanmoy Deb, Multiobjective Optimization using Evolutionary
Algorithms. New York: John Wiley & Sons., 2001, ch. 5.
[12] Omar Al Jadaan, Lakishmi Rajamani, C. R. Rao, "Non-dominated
ranked genetic algorithm for Solving multiobjective optimization
Problems: NRGA", Journal of Theoretical and Applied Information
Technology, pp. 60-67, 2008.
[13] K. Rath and S. N. Dehuri, "Non-dominated Sorting Genetic Algorithms
for heterogeneous Embedded System Design", Journal of Computer
Science, 2 (3), pp. 288-291, 2006.
[14] N. Srinivas and Kalyanmoy Deb, "Muiltiobjective Optimization Using
nondominated Sorting in Genetic Algorithms," Evolutionary
computation, vol. 2, No. 3, pp. 221-248, 2007.
[15] Jose Maria A. Pangilinan and Gerrit K. Janssens, "Evolutionary
Algorithms for the Multiobjective Shortest Path Problem," World
Academy of Science, Engineering and Technology, vol. 25, pp. 205-210,
2007.
[16] Salman Yussof and Ong Hang See, "Finding Multi-Constrained Path
Using Genetic Algorithm," Proc. IEEE International Conference on
Telecommunications and Malaysia International Conference on
Communications, Penang, 2007, vol.1, pp.1-6.
[17] Salman Yussof and Ong Hang See, "QoS Routing for Multiple
Additive QoS Parameters using Genetic Algorithm," Proc. International
Conference on Communication, vol.1, pp.99-104, 2005.
@article{"International Journal of Electrical, Electronic and Communication Sciences:55551", author = "C. Chitra and P. Subbaraj", title = "Multiobjective Optimization Solution for Shortest Path Routing Problem", abstract = "The shortest path routing problem is a multiobjective
nonlinear optimization problem with constraints. This problem has
been addressed by considering Quality of service parameters, delay
and cost objectives separately or as a weighted sum of both
objectives. Multiobjective evolutionary algorithms can find multiple
pareto-optimal solutions in one single run and this ability makes them
attractive for solving problems with multiple and conflicting
objectives. This paper uses an elitist multiobjective evolutionary
algorithm based on the Non-dominated Sorting Genetic Algorithm
(NSGA), for solving the dynamic shortest path routing problem in
computer networks. A priority-based encoding scheme is proposed
for population initialization. Elitism ensures that the best solution
does not deteriorate in the next generations. Results for a sample test
network have been presented to demonstrate the capabilities of the
proposed approach to generate well-distributed pareto-optimal
solutions of dynamic routing problem in one single run. The results
obtained by NSGA are compared with single objective weighting
factor method for which Genetic Algorithm (GA) was applied.", keywords = "Multiobjective optimization, Non-dominated SortingGenetic Algorithm, Routing, Weighted sum.", volume = "4", number = "1", pages = "122-9", }