Multiobjective optimization solution for shortest path routing problem

Autor: Chitra Chinnasamy, Subbaraj, P.
Předmět:
Zdroj: Scopus-Elsevier
Popis: 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":["George N. Rouskas and Ilia Baldine, \"Multicast Routing with End-to-\nEnd Delay and Delay Variation Constraints,\" IEEE Journal on Selected\nAreas in Communications, vol.15, No.3, pp.346-356, 1997.","Jose Craveirinha, Rita Girao-Silva and Joao Climaco, \"A meta-model\nfor multiobjective routing in MPLS networks,\" Central European\nJournal of Operation Research (Springer), vol.16, No.1, pp.79-105,\n2008.","Sriram, R., Manimaran, G., and Siva Ram Murthy, C., \"Preferred link\nbased delay-constrained least-cost routing in wide area networks,\"\nComputer Communications, vol. 21, pp. 1655-1669, 1998.","Aluizio F. R. Araujo, Cicero Garrozi, Andre R. G. A. Leitao and Maury\nM. Gouvea Jr., \"Multicast Routing Using Genetic Algorithm Seen as a\nPermutation Problem\", 20th International Conference on Advanced\nInformation Networking and Applications (AINA-06), Vienna, 2006,\nvol. 1, pp. 477-484.","Chang Wook and Ramakrishna, R.S., \"A genetic algorithm for shortest\npath routing problem and the sizing of populations\", IEEE Transactions\non Evolutionary Computation, vol.6, No.6, pp.566-579, 2002.","Ha Chen and Baolin Sun, \"Multicast Routing Optimization Algorithm\nwith Bandwidth and Delay Constraints Based on GA,\" Journal of\nCommunication and Computer, vol. 2, No.5, pp.63-67, 2005.","Hayder A. Mukhef, Ekhlas M. Farhan and Mohammed R. Jassim (2008)\n\"Generalized Shortest Path Problem in Uncertain Environment Based\non PSO,\" Journal of Computer Science, vol. 4, No. 4, pp. 349-352.","Abido, M. A., \"A novel multiobjective evolutionary algorithm for\nenvironmental/economic power dispatch,\" Electric Power Systems\nResearch, vol. 65, No. 1, pp 71-81, 2003.","Kalyanmoy Deb and Santosh Tiwari, \"Omni-optimizer: A generic\nevolutionary algorithm for single and multiobjective optimization,\"\nEuropean Journal of Operational Research, vol. 185, No. 3, pp. 1062-\n1087, 2008.\n[10] Srinivas, N. and Deb, K., \"Multiobjective Optimization using Nondominated\nSorting in Genetic Algorithm,\" Evolutionary Computation,\nvol. 2, No. 3, pp. 221-248, 1994.\n[11] Kalyanmoy Deb, Multiobjective Optimization using Evolutionary\nAlgorithms. New York: John Wiley & Sons., 2001, ch. 5.\n[12] Omar Al Jadaan, Lakishmi Rajamani, C. R. Rao, \"Non-dominated\nranked genetic algorithm for Solving multiobjective optimization\nProblems: NRGA\", Journal of Theoretical and Applied Information\nTechnology, pp. 60-67, 2008.\n[13] K. Rath and S. N. Dehuri, \"Non-dominated Sorting Genetic Algorithms\nfor heterogeneous Embedded System Design\", Journal of Computer\nScience, 2 (3), pp. 288-291, 2006.\n[14] N. Srinivas and Kalyanmoy Deb, \"Muiltiobjective Optimization Using\nnondominated Sorting in Genetic Algorithms,\" Evolutionary\ncomputation, vol. 2, No. 3, pp. 221-248, 2007.\n[15] Jose Maria A. Pangilinan and Gerrit K. Janssens, \"Evolutionary\nAlgorithms for the Multiobjective Shortest Path Problem,\" World\nAcademy of Science, Engineering and Technology, vol. 25, pp. 205-210,\n2007.\n[16] Salman Yussof and Ong Hang See, \"Finding Multi-Constrained Path\nUsing Genetic Algorithm,\" Proc. IEEE International Conference on\nTelecommunications and Malaysia International Conference on\nCommunications, Penang, 2007, vol.1, pp.1-6.\n[17] Salman Yussof and Ong Hang See, \"QoS Routing for Multiple\nAdditive QoS Parameters using Genetic Algorithm,\" Proc. International\nConference on Communication, vol.1, pp.99-104, 2005."]}
Databáze: OpenAIRE
Externí odkaz: