Abstract
The static shortest path (SP) problem has been well addressed using intelligent optimization techniques, e.g., artificial neural networks, genetic algorithms (GAs), particle swarm optimization, etc. However, with the advancement in wireless communications, more and more mobile wireless networks appear, e.g., mobile ad hoc network (MANET), wireless mesh network, etc. One of the most important characteristics in mobile wireless networks is the topology dynamics, that is, the network topology changes over time due to energy conservation or node mobility. Therefore, the SP problem turns out to be a dynamic optimization problem in mobile wireless networks. In this paper, we propose to use multi-population GAs with immigrants scheme to solve the dynamic SP problem in MANETs which is the representative of new generation wireless networks. The experimental results show that the proposed GAs can quickly adapt to the environmental changes (i.e., the network topology change) and produce good solutions after each change.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Ali, M.K., Kamoun, F.: Neural networks for shortest path computation and routing in computer networks. IEEE Trans. on Neural Networks 4(6), 941–954 (1993)
Ahn, C.W., Ramakrishna, R.S., Kang, C.G., Choi, I.C.: Shortest path routing algorithm using hopfield neural network. Electronics Letters 37(19), 1176–1178 (2001)
Ahn, C.W., Ramakrishna, R.S.: A genetic algorithm for shortest path routing problem and the sizing of populations. IEEE Trans. on Evol. Comput. 6(6), 566–579 (2002)
Branke, J., Kaußler, T., Schmidt, C., Schmeck, H.: A multi-population approach to dynamic optimization problems. In: Proc. 4th Int. Conf. on Adaptive Computing in Design and Manufacture, pp. 299–308 (2000)
Grefenstette, J.J.: Genetic algorithms for changing environments. In: Proc. 2nd Int. Conf. on Parallel Problem Solving from Nature, pp. 137–144 (1992)
Lee, S., Soak, S., Kim, K., Park, H., Jeon, M.: Statistical properties analysis of real world tournament selection in genetic algorithms. Applied Intell. 28(2), 195–205 (2008)
Mohemmed, A.W., Sahoo, N.C., Geok, T.K.: Solving shortest path problem using particle swarm optimization. Applied Soft Comput. 8(4), 1643–1653 (2008)
Oh, S., Ahn, C., Ramakrishna, R.: A genetic-inspired multicast routing optimization algorithm with bandwidth and end-to-end delay constraints. In: Proc. 13th Int. Conf. on Neural Information Processing, pp. 807–816 (2006)
Oppacher, F., Wineberg, M.: The shifting balance genetic algorithm: improving the GA in a dynamic environment. In: Proc. Genetic and Evol. Comput. Conf., pp. 504–510 (1999)
Parsa, M., Zhu, Q., Garcia-Luna-Aceves, J.: An iterative algorithm for delay-constrained minimum-cost multicasting. IEEE/ACM Trans. on Networking 6(4), 461–474 (1998)
Perkins, C.E. (ed.): Ad Hoc Networking. Addison-Wesley, London (2001)
Tsutsui, S., Fujimoto, Y., Ghosh, A.: Forking genetic algorithms: GAs with search space division schemes. Evol. Comput. 5(1), 61–80 (1997)
Yang, S., Yao, X.: Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Comput. 9(11), 815–834 (2005)
Yang, S., Yao, X.: Population-based incremental learning with associative memory for dynamic environments. IEEE Trans. on Evol. Comput. 12(5), 542–561 (2008)
Yang, S.: Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evol. Comput. 16(3), 385–416 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cheng, H., Yang, S. (2010). Multi-population Genetic Algorithms with Immigrants Scheme for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Networks. In: Di Chio, C., et al. Applications of Evolutionary Computation. EvoApplications 2010. Lecture Notes in Computer Science, vol 6024. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12239-2_58
Download citation
DOI: https://doi.org/10.1007/978-3-642-12239-2_58
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12238-5
Online ISBN: 978-3-642-12239-2
eBook Packages: Computer ScienceComputer Science (R0)