A Nondominated Sorting Genetic Algorithm for Shortest Path Routing Problem

Authors: C. Chitra, P. Subbaraj

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 Sorting Genetic Algorithm, Routing, Weighted sum.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078581

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, vol. 1, pp. 477-484, 2006.
[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, "Generalized Shortest Path Problem in Uncertain Environment Based on PSO," Journal of Computer Science, vol. 4, No. 4, pp. 349-352, 2008.
[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, vol.1, pp.1-6, 2007.
[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.