Abstract
While evolutionary algorithms (EAs) have many advantages, they have to evaluate a relatively large number of candidate solutions before producing good results, which directly translates into a substantial demand for computing power. This disadvantage is somewhat compensated by the ease of parallelizing EAs. While only few people have access to a dedicated parallel computer, recently, it also became possible to distribute an algorithm over any bunch of networked computers, using a paradigm called “grid computing”. However, unlike dedicated parallel computers with a number of identical processors, the computers forming a grid are usually quite heterogeneous. In this paper, we look at the effect of this heterogeneity, and show that standard parallel variants of evolutionary algorithms are significantly less efficient when run on a heterogeneous rather than on a homogeneous set of computers. Based on that observation, we propose and compare a number of new migration schemes specifically for heterogeneous computer clusters. The best found migration schemes for heterogeneous computer clusters are shown to be at least competitive with the usual migration scheme on homogeneous clusters. Furthermore, one of the proposed migration schemes also significantly improves performance on homogeneous clusters.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alba, E., Nebro, A., Troya, J.: Heterogeneous computing and parallel genetic algorithms. Journal of Parallel and Distributed Computing, 1362–1385 (2002)
Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary Computation 6(5), 443–461 (2002)
Arenas, M., Collet, P., Eiben, A., Jelasity, M., Merelo, J., Paechter, B., Preuß, M., Schoenauer, M.: A framework for distributed evolutionary algorithms. In: Parallel Problem Solving from Nature, pp. 665–675. Springer, Heidelberg (2002)
Buyya, R., Branson, K., Gidy, J., Abramson, D.: The virtual laboratory: a toolset to enable distributed molecular modelling for drug design on the world-wide grid. Concurrency and Computation: Practice and Experience 15, 1–25 (2003)
Cantu-Paz, E.: Efficient and Accurate Parallel Genetic Algorithms. Kluwer, Dordrecht (2000)
Chong, F.S.: Java based distributed genetic programming on the internet. Technical report, School of Computer Science, University of Birmingham, B15 2TT, UK (1999)
Foster, I., Kesselman, C. (eds.): The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, San Francisco (1999)
Liu, P., Lau, F., Lewisand, J., Wang, C.: Asynchronous parallel evolutionary algorithm for function optimization. In: Parallel Problem Solving from Nature, pp. 405–409. Springer, Heidelberg (2002)
Munetomo, M., Takai, Y., Sato, Y.: An efficient migration scheme for subpopulation-based asynchronously parallel genetic algorithms. In: Forrest, S. (ed.) International Conference on Genetic Algorithms, p. 649. Morgan Kaufmann, San Francisco (1993)
Schmeck, H., Kohlmorgen, U., Branke, J.: Parallel implementations of evolutionary algorithms. In: Zomaya, A., Ercal, F., Olariu, S. (eds.) Solutions to Parallel and Distributed Computing Problems, pp. 47–66. Wiley, Chichester (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Branke, J., Kamper, A., Schmeck, H. (2004). Distribution of Evolutionary Algorithms in Heterogeneous Networks. In: Deb, K. (eds) Genetic and Evolutionary Computation – GECCO 2004. GECCO 2004. Lecture Notes in Computer Science, vol 3102. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24854-5_93
Download citation
DOI: https://doi.org/10.1007/978-3-540-24854-5_93
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22344-3
Online ISBN: 978-3-540-24854-5
eBook Packages: Springer Book Archive