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.




References:
[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.