Abstract
Genetic algorithms imitate the collective learning paradigm found in living nature. They derive their power largely from their implicit parallelism gained by processing a population of points in the search space simultaneously. In this paper, we describe an extension of genetic algorithms making them also explicitly parallel. The advantages of the introduction of a population structure are twofold: firstly, we specify an algorithm which uses only local rules and local data making it massively parallel with an observed linear speedup on a transputer-based parallel system, and secondly, our simulations show that both convergence speed and final quality are improved in comparison to a genetic algorithm without population structure.
This material is based upon work done at GMD, Postfach 1240, D-5205 St. Augustin 1.
Preview
Unable to display preview. Download preview PDF.
References
J. J. Grefenstette (Ed.), Proceedings of the Second International Conference on Genetic Algorithms and their Applications, Lawrence Erlbaum Associates, Hillsdale (1987)
J. D. Schaffer (Ed.), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo (1989)
D. Macfarlane, I. East An Investigation of Several Parallel Genetic Algorithms, University of Buckingham, 1990, to be published
D. E. Goldberg, GA in Search, Optimization and Machine Learning, Addison-Wesley (1989)
P. Grosso, Computer simulation of genetic adaptation: Parallel subcomponent interaction in a multilocus model, Doctoral dissertation, University of Michigan, University Microfilms No. 8520908
M. Gorges-Schleuter, ASPARAGOS, in [2], 422–427
M. Gorges-Schleuter, Genetic Algorithms and Population Structures — A Massively Parallel Algorithm, Doctoral dissertation, University of Dortmund, 1990
H. Kwasnicka, W. Kwasnicki, The Importance of Recombination in Speciation and Evolution of the Higher Taxa, Symp. on Org. Constraints on the Dyn. of Evolution, Budapest, Hungary (1987)
G. von Laszewski, H. Mühlenbein, A Parallel GA for the Graph Part. Problem, this proceedings
H. Mühlenbein, M. Gorges-Schleuter, O. Krämer, Evolution Algorithm in Combinatorial Optimization, Parallel Computing 7 (1988), 65–88
H. Mühlenbein, Parallel GAs, Population Genetics, and Comb. Optimization, in [2], 416–422
W. Padberg, G. Rinaldi, Optimization of a 532-City TSP, Operation Res.Lett. 6, 1–7 (1987)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gorges-Schleuter, M. (1991). Explicit parallelism of genetic algorithms through population structures. In: Schwefel, HP., Männer, R. (eds) Parallel Problem Solving from Nature. PPSN 1990. Lecture Notes in Computer Science, vol 496. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029746
Download citation
DOI: https://doi.org/10.1007/BFb0029746
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54148-6
Online ISBN: 978-3-540-70652-6
eBook Packages: Springer Book Archive