Abstract
In this paper we demonstrate that parallel genetic algorithms can profit from performing periodic centralized selections of distributed populations. With this combination, implementations can benefit from the variety of environments provided by distributed approaches, while periodically being able to consider the population as a whole and disregard very unfit individuals. We study four different parallel genetic algorithm implementation strategies; each of them striking a different balance between centralization and distribution. These strategies are applied to several well-known benchmark problems. Our results show that the implementations using periodic centralized selections exhibit remarkable robustness in terms of their search quality, while keeping running time overheads under control. Our main conclusion is that performing centralized selections represents an improvement to the traditional population distribution approaches, which are susceptible to somewhat inefficient search.
This is a preview of subscription content, log in via an institution to check access.
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
S. Baluja. Structure and performance of fine-grain parallelism in genetic search. In Proc. of the 5th Int. Conf. on Genetic Algorithms and their Applications, pages 155–162, 1993.
R. Bianchini and C. Brown. Parallel genetic algorithms on distributed-memory architectures. In Transputer: Research and Applications, May 1993.
J. P. Cohoon, W. N. Martin, and D. S. Richards. A multi-population genetic algorithm for solving the k-partition problem on hyper-cubes. In Proc. of the 3rd Int. Conf. on Genetic Algorithms and their Applications, 1989.
R. J. Collins and D. R. Jefferson. Selection in massively parallel genetic algorithms. In Proc. of the 4th Int. Conf. on Genetic Algorithms and their Applications, pages 249–256, 1991.
R. J. Fowler and L. I. Kontothanassis. Mercury: Object-affinity scheduling and continuation passing on multiprocessors. In Parallel Architectures and Languages Europe (PARLE)’94, June 1994.
D. E. Goldberg. Genetic Algorithms in search, optimization and machine learning. Addison-Wesley, 1989.
J. J. Grefenstette. Parallel adaptive algorithms for function optimization. Technical Report CS-81-19, Nashville: Vanderbilt University. Computer Science Dept., 1981.
K. A. De Jong. Analysis of the Behavior of a Class of Genetic Algorithms. PhD thesis, University of Michigan, 1975.
V. Kommu and I. Pomeranz. Effect of communication in a parallel genetic algorithm. In Proc. of the 1992 Int. Conf. on Parallel Processing, pages III:310–317, 1992.
P. Neuhaus. Solving the mapping-problem — experiences with a genetic algorithm. In Parallel Problem Solving from Nature, pages 170–175. Springer-Verlag, 1991.
H. A. Taha. Integer Programming — Theory, Applications and Computations. Academic Press, 1975.
R. Tanese. Distributed genetic algorithms. In Proc. of the 3rd Int. Conf. on Genetic Algorithms and their Applications, 1989.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag/Wien
About this paper
Cite this paper
Bianchini, R., Brown, C.M., Cierniak, M., Meira, W. (1995). Combining Distributed Populations and Periodic Centralized Selections in Coarse-Grain Parallel Genetic Algorithms. In: Artificial Neural Nets and Genetic Algorithms. Springer, Vienna. https://doi.org/10.1007/978-3-7091-7535-4_125
Download citation
DOI: https://doi.org/10.1007/978-3-7091-7535-4_125
Publisher Name: Springer, Vienna
Print ISBN: 978-3-211-82692-8
Online ISBN: 978-3-7091-7535-4
eBook Packages: Springer Book Archive