An Investigation on the Effect of Migration Strategy on Parallel GA-Based Shortest Path Routing Algorithm

Salman Yussof, Rina Azlin Razali

Department of Systems and Networking, College of Information Technology, Universiti Tenaga Nasional, Kajang, Malaysia.

DOI: 10.4236/cn.2012.42013                

Abstract

Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.

Keywords

Parallel Genetic Algorithm; Shortest Path Routing; Migration Strategy

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. F. Kurose and K. W. Ross, “Computer Networking: A Top-Down Approach Featuring the Internet,” 4th Edition, Addison-Wesley, Boston, 2007.
[2]	M. Munetomo, N. Yamaguchi, K. Akama and Y. Sato, “Empirical Investigations on the Genetic Adaptive Routing Algorithm in the Internet,” Proceedings of the Congress on Evolutionary Computation, Seoul, 27-30 May 2001, pp. 1236-1243.
[3]	C. W. Ahn and R. S. Ramakrishna, “A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 6, 1999, pp. 1-7.
[4]	W. Liu and L. Wang, “Solving the Shortest Path Routing Problem Using Noisy Hopfield Neural Networks,” International Conference on Communications and Mobile Computing, Kunming, 6-8 January 2009, pp. 299-302. doi:10.1109/CMC.2009.366
[5]	H. A. Mukhef, E. M. Farhan and M. R. Jassim, “Generalized Shortest Path Problem in Uncertain Environment Based on PSO,” Journal of Computer Science, Vol. 4, No. 4, 2008, pp. 349-352.
[6]	M. Yusoff, J. Ariffin and A. Mohamed, “A Discrete Particle Swarm Optimization with Random Selection Solution for the Shortest Path Problem,” International Conference of Soft Computing and Pattern Recognition, Paris, 7-10 December 2010, pp. 133-138. doi:10.1109/SOCPAR.2010.5685867
[7]	A. A. A. Zakzouk, H. M. Zaher and R. A. Z. El-Deen, “An Ant Colony Optimization Approach for Solving Shortest Path Routing Problem with Fuzzy Constraints,” 7th International Conference on Informatics and Systems, Cairo, 28-30 March 2010, p. 1.
[8]	S. Yussof and H. S. Ong, “A Robust GA-based QoS Routing Algorithm for Solving Multi-Constrained Path Routing Problem,” Journal of Computers, Vol. 5, No. 9, 2010, pp. 1322-1334. doi:10.4304/jcp.5.9.1322-1334
[9]	S. Yussof, R. A. Razali and H. S. Ong, “An Investigation of Using Parallel Genetic Algorithm for Shortest Path Routing Problem,” Journal of Computer Science, Vol. 7, No. 2, 2011, pp. 206-215. doi:10.3844/jcssp.2011.206.215
[10]	S.-C. Lin, E. D. Goodman and W. F. Punch, “Investigating Parallel Genetic Algorithms on Job Shop Scheduling Problems,” Lecture Notes in Computer Science, Vol. 1213, 1997, pp. 383-393.
[11]	Y. J. Cao, “Application of Parallel Genetic Algorithms to Economic Dispatch—Effects on Routing Strategies on Algorithms’ Performances,” Automation of Electric Power System, Vol. 26, No. 13, 2002, pp. 20-24.
[12]	D. E. Goldberg, “Genetic Algorithm in Search, Optimization and Machine Learning,” Addison-Wesley, Boston, 1989.
[13]	E. C. Paz and D. E. Goldberg, “Efficient and Accurate Parallel Genetic Algorithms,” Kluwer Academic Publications, Dordrecht, 2001.
[14]	B. M. Waxman, “Routing for Multipoint Connections,” IEEE Journal on Selected Areas in Communications, Vol. 6, No. 9, 1998, pp. 1617-1622. doi:10.1109/49.12889