- Authors:
- Ricardo Bianchini,
- Christopher M. Brown
The implementation of parallel genetic algorithms raises many important issues. These issues can be divided into two main classes: genetic search quality and execution performance. In the context of parallel genetic algorithms on distributed-memory computers, performance considerations have always driven the design of implementations. Thus, centralized implementations have almost always been excluded from any consideration for distributed-memory architectures. .pp The work we present here defines a set of genetic algorithm implementation alternatives for distributed-memory computers, in which strategies with some centralization are included. Each of our implementation alternatives uses a different level of distribution of the population, from the single logically centralized population to a totally distributed set of subpopulations. .pp The design alternatives we define can be applied to the implementation of any parallel genetic algorithm. As an example of such an implementation, we study the quality of the search and the execution performance of our strategies on the 0-1 Integer Linear Programming problem, on a Transputer network. Our results show that implementations incurring higher overheads can produce as good or better solutions faster than than very "efficient" implementations, depending on the characteristics of the problem at hand. More specifically, in some cases, utilizing more centralized parallel genetic search strategies results in the fastest convergence towards the optimal solution, therefore reducing the number of generations needed by the algorithm.
Cited By
- Ruciński M, Izzo D and Biscani F (2018). On the impact of the migration topology on the Island Model, Parallel Computing, 36:10-11, (555-571), Online publication date: 1-Oct-2010.
- Sullivan K, Luke S, Larock C, Cier S and Armentrout S Opportunistic evolution Proceedings of the 10th annual conference companion on Genetic and evolutionary computation, (2227-2232)
- Cussat-Blanc S, Viale F, Luga H, Duthen Y and Caromel D Genetic algorithms and grid computing for artificial embryogeny Proceedings of the 10th annual conference on Genetic and evolutionary computation, (281-282)
- Talbi E (2019). A Taxonomy of Hybrid Metaheuristics, Journal of Heuristics, 8:5, (541-564), Online publication date: 1-Sep-2002.
- Ponnuswamy S, Amin M, Jha R and Castañon D (1997). A C3I Parallel Benchmark Based on Genetic Algorithms-Implementation and Performance Analysis, Journal of Parallel and Distributed Computing, 47:1, (23-38), Online publication date: 25-Nov-1997.
Recommendations
A framework for parallel genetic algorithms for distributed memory architectures
ScalA '14: Proceedings of the 5th Workshop on Latest Advances in Scalable Algorithms for Large-Scale SystemsGenetic algorithms are metaheuristic search methods, based on the principles of biological evolution and genetics. Through a heuristic search they are able to find good solutions in acceptable time. However, with the increase of the complexity of the ...
Scalable Parallel Genetic Algorithms
Genetic algorithms, search algorithms based on the genetic processes observed in natural evolution, have been used to solve difficult problems in many different disciplines. When applied to very large-scale problems, genetic algorithms exhibit high ...
Gradual distributed real-coded genetic algorithms
A major problem in the use of genetic algorithms is premature convergence. One approach for dealing with this problem is the distributed genetic algorithm model. Its basic idea is to keep, in parallel, several subpopulations that are processed by ...