Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2001 | Book

Introduction Read chapter Read first chapter

Efficient and Accurate Parallel Genetic Algorithms

Author: Erick Cantú-Paz

Publisher: Springer US

Book Series : Genetic Algorithms and Evolutionary Computation

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

As genetic algorithms (GAs) become increasingly popular, they are applied to difficult problems that may require considerable computations. In such cases, parallel implementations of GAs become necessary to reach high-quality solutions in reasonable times. But, even though their mechanics are simple, parallel GAs are complex non-linear algorithms that are controlled by many parameters, which are not well understood.
Efficient and Accurate Parallel Genetic Algorithms is about the design of parallel GAs. It presents theoretical developments that improve our understanding of the effect of the algorithm's parameters on its search for quality and efficiency. These developments are used to formulate guidelines on how to choose the parameter values that minimize the execution time while consistently reaching solutions of high quality.
Efficient and Accurate Parallel Genetic Algorithms can be read in several ways, depending on the readers' interests and their previous knowledge about these algorithms. Newcomers to the field will find the background material in each chapter useful to become acquainted with previous work, and to understand the problems that must be faced to design efficient and reliable algorithms. Potential users of parallel GAs that may have doubts about their practicality or reliability may be more confident after reading this book and understanding the algorithms better. Those who are ready to try a parallel GA on their applications may choose to skim through the background material, and use the results directly without following the derivations in detail. These readers will find that using the results can help them to choose the type of parallel GA that best suits their needs, without having to invest the time to implement and test various options. Once that is settled, even the most experienced users dread the long and frustrating experience of configuring their algorithms by trial and error. The guidelines contained herein will shorten dramatically the time spent tweaking the algorithm, although some experimentation may still be needed for fine-tuning.
Efficient and Accurate Parallel Genetic Algorithms is suitable as a secondary text for a graduate level course, and as a reference for researchers and practitioners in industry.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
Genetic algorithms are effective to solve many practical problems, but in some cases, they may take a long time to reach an acceptable solution. GAs are easy to implement on parallel computers, and indeed, parallel GAs are popular, but they are controlled by many parameters that are not well understood. The purpose of this book is to explore the effects of the parameters on the search quality and efficiency of parallel GAs, and provide guidelines on how to choose appropriate values for a particular situation.
This chapter presented a brief description of GAs and some concepts that will be used in the remainder of the book. ‘In particular, the next chapter uses the concepts of partitions and schemata to develop a model that relates the quality of the solution reached by a simple G A with the size of its population. This chapter also outlined the different types of parallel GAs that are explored in the rest of the book.
Erick Cantú-Paz
Chapter 2. The Gambler’s Ruin Problem and Population Sizing
Abstract
This chapter presented a solution to a long-standing problem in genetic algorithms: how to determine an adequate population size to reach a solution of a particular quality. The model is based on a random walk where the position of a particle on a bounded one-dimensional space represents the number of copies of the correct BBs in the population. The probability that the particle will be absorbed by the boundaries is well known, and it was used to derive an equation that relates the population size with the required solution quality and several domain-dependent parameters.
The accuracy of the model was verified with experiments using test problems that ranged from the very simple to the moderately hard. The results confirmed that the model is accurate, and that its predictions scale well with the difficulty of the domain. In addition, the basic model was extended to consider explicit noise in the fitness evaluation and different selection schemes.
A correctly-sized population is the first step toward competent and efficient genetic algorithms. The next chapter describes how to make single-population GAs faster by using multiple processors to evaluate the fitness of the population in parallel. Subsequent chapters extend the gambler’s ruin model to parallel GAs with multiple populations.
Erick Cantú-Paz
Chapter 3. Master-Slave Parallel Genetic Algorithms
Abstract
Master-slave parallel GAs are easy to implement, often yield considerable improvements in performance, and all the theory available for simple GAs can be used to choose adequate values for the search parameters. The analysis of this chapter showed that, for many applications, the reduction in computation time is sufficient to overcome the cost of communications. The calculations presented here should be useful to design fast master-slave GAs that utilize the computing resources in the best possible way.
The chapter discussed the similarities between asynchronous master-slave GAs and GAs with a generation gap. The chapter also presented a G A with a single distributed population. This algorithm is less efficient than the simple master-slave, but it is important because it resembles a GA with multiple communicating populations. The analysis of this algorithm reveals that the optimal number of processors is of the same order as the master-slave.
The main contribution of this chapter was to present a lower bound on the performance gains that are acceptable in any parallel GAs. More sophisticated single-population GAs or multi-population parallel GAs should do better than the simple case examined here or they should be abandoned. The calculations are simple and they are easy to calibrate to consider the hardware and the particular problem.
Erick Cantú-Paz
Chapter 4. Bounding Cases of Genetic Algorithms with Multiple Demes
Abstract
The calculations presented in this chapter recognize that the design of parallel GAs is a complex problem, and that the choices of topologies, migration rates, number of demes, and their size are intimately related. To make progress on the deme-sizing problem without ignoring the other choices, the analysis used bounds on the topologies and migration rates.
The starting point of the analysis was to calculate the relaxation of the target quality per deme. Then, for each bounding case, we computed the expected quality of the best deme, and used the gambler’s ruin model to derive deme-sizing equations. The sizing results were then used to estimate the execution time of the parallel GA.
The first result of this chapter is that if there is no communication between the demes, their sizes decrease very modestly, and the speedup is very small. On the other hand, when the demes communicate, there are great improvements in performance, because the deme sizes are much smaller. In this case, it is possible to estimate the number of demes and a corresponding deme size that maximize the speedup.
Moreover, the formulas for the optimal deme size and deme count can be adjusted to consider particular implementations and to predict the effect of improvements in hardware or software in the performance of parallel GAs. With these tools, it is possible to guide the developer to those aspects of the implementation that will make a greater impact on performance. The next chapters extend the analysis to consider multiple epochs, other topologies and reduced migration rates.
Erick Cantú-Paz
Chapter 5. Markov Chain Models of Multiple Demes
Abstract
This chapter presented models that predict the expected solution quality of parallel GAs with multiple populations after any number of epochs and for any choice of deme size, deme count, topology, or migration rate. The basic idea was to model the parallel GAs as Markov chains to determine the number of correct BBs that are present in the demes at the beginning of each epoch. Then, the gambler’s ruin model was used to predict the quality of the solutions.
The first algorithm that we examined was an upper bound on topologies and migration rates (the fully-connected case of the previous chapter). This case was the easiest to examine because all the demes have the same contributions to the next epoch. The second algorithm also had a fully-connected topology, but the analysis was extended to consider arbitrary migration rates. Finally, we examined arbitrary topologies and migration rates. The accuracy of the models was tested with computational experiments using one fully-deceptive test function and varying all the parameters of interest. In all cases, the predictions match closely the observed quality of the solutions after any number of epochs.
This chapter extended our understanding of multi-deme parallel G As in several ways. First, we observed that the greatest gain in quality always occurs after the second epoch. This reinforces the significance of the calculations of the previous chapter that showed how to derive approximate closed-form expressions for the deme sizes and how to manipulate them to minimize the execution time.
The second contribution of this chapter is that the models and experiments suggest that, in the long run, the parallel GAs reach solutions of the same quality as a simple GA with a population equivalent to the aggregate of the demes. Partitioning the population does not degrade or improve the solution quality, as long as the migration rate is not very low. Furthermore, it appears that only a few epochs are necessary to reach the same solution as the simple GA.
An important observation is that the quality improves with higher migration rates and more neighbors per deme. Since migrations occur after the demes converge, the cost of communications is independent of the migration rate. However, higher degrees raise the cost of communications, and result in a tradeoff between increasing the quality or making the algorithm slower. The tradeoff suggests that, for an expected fixed solution quality, there is an optimal configuration that minimizes the execution time. The next chapter shows how to find this optimal configuration.
Erick Cantú-Paz
Chapter 6. Migration Rates and Optimal Topologies
Abstract
This chapter extended the previous deme-sizing equations to consider configurations that are likely to be used by practitioners. The first part of the chapter described the relation between the deme size, the migration rate, and the topology’s degree with the probability of success after two epochs. It showed how to find the configuration that optimizes the execution time while reaching a predetermined target quality. These calculations were also used to find an alternate expression for the optimal number of fully-connected demes (which was calculated initially in Chapter 4). Although this topology cannot integrate many demes, it can reduce the execution time substantially, and it may be competitive with other optimally-configured topologies.
The second part of the chapter generalized the results to multiple epochs. After multiple epochs, the topology is important because a deme receives indirect contributions from varying number of demes. Section 2 showed that different topologies with the same degree reach almost identical solutions after any number of epochs. A simple approximate model was derived to explain the small differences, but most importantly, the equivalence of topologies with the same degree facilitated the derivation of a model of solution quality. The quality model was transformed into an accurate deme-sizing equation, which in turn was used to minimize the execution time.
When the topology is fixed and the algorithm is executed until all the populations converge to the same solution, the optimal number of populations was found to be, which is asymptotically the same as parallel versions of GAs with a single population. This result suggests that, regardless of their type, parallel GAs can integrate large numbers of processors and reduce significantly the execution time of many practical applications.
Erick Cantú-Paz
Chapter 7. Migration, Selection Pressure, and Superlinear Speedups
Abstract
The choice of migrants and the replacement of individuals are not often considered important parameters of parallel GAs. However, this chapter used two different methods to show that choosing the migrants or replacements according to their fitness increases the selection pressure. Some migration policies may cause the algorithm to converge significantly faster. The migration policy that accelerates convergence the most is to choose both the migrants and the replacements according to their fitness, which is also the most common policy.
The faster convergence may explain some of the claims of superlinear speedups in parallel GAs. This chapter showed an example where serial and parallel algorithms reached the same solution and used the same number of individuals, but the additional selection pressure resulted in superlinear speedups.
The chapter also included calculations of the higher moments of the distribution of fitness. These calculations showed that different combinations of the degree of the topology and the migration rate affect the population in different ways, even if they result in the same selection intensity.
Erick Cantú-Paz
Chapter 8. Fine-Grained and Hierarchical Parallel Genetic Algorithms
Abstract
This chapter treated fine-grained and hierarchical parallel GAs. It began with a brief review of fine-grained parallel GAs. The chapter identified some of the most salient design problems of this type of algorithms, and discussed some of the recent work on this area.
This chapter focused on hierarchical combinations of parallel GAs. The hierarchical algorithms are composed of multiple demes, and the demes themselves are parallel GAs. We identified three hierarchical algorithms, and we examined in closer detail one where the upper-level demes are master-slave GAs.
As before, we are interested in obtaining a solution in the shortest time possible, and this chapter introduced a method to distribute the available processors between upper-level demes and lower-level slaves to minimize the execution time. Finally, Section 4 presented a step-by-step example of the use of the theory of this book to a particular problem. The example assumed minimal knowledge about the problem, and showed how only simple experiments are necessary to calibrate the theory to obtain very accurate results.
Erick Cantú-Paz
Chapter 9. Summary, Extensions, and Conclusions
Abstract
The design of efficient and accurate parallel GAs is a complex problem. One must decide on a configuration among the many choices of topologies, migration rates, deme counts and sizes. Each parameter affects the quality of the search and the efficiency of the algorithm in non-linear ways, which makes the choices difficult. The ultimate goal is to determine the configuration that reaches a solution of the required quality as fast as possible. This book made some contributions towards this goal, and are summarized in this section.
The first part of this book considered GAs with one population, and reports two main results. The first is an accurate model of simple GA performance based on the gambler’s ruin problem. This model integrates previous knowledge of BB supply and correct decision making into an accurate predictor of solution quality. Chapter 2 presented empirical evidence that validates the accuracy of the predictions on various settings of practical interest. The model was successfully tested with functions of varying difficulty, with noisy fitness functions, and with different levels of selection pressure.
The second contribution is a lower bound on the benefits that should be expected from parallel GAs. The analysis of the simple master-slave GA in Chapter 3 showed that there is an optimal number of processors V* = y rf- that minimizes the execution time, and that the maximum parallel speedup is 0.5P*. The critical number of processors that maintain a desired efficiency was calculated, and it was used to determine that processors maintain a near-perfect efficiency of More sophisticated parallel GAs should be more efficient and produce higher speedups or be discarded.
In addition, Chapter 3 described a parallel implementation of a single-population GA that resembles a bounding case of multiple-deme GAs. Although this algorithm is less efficient than the simple master-slave, it has important theoretical implications. Straightforward calculations show that it can use processors to reduce the execution time, which is asymptotically the same number of processors that optimally-configured master-slaves can use.
Most of the book focused on parallel GAs with multiple populations. These algorithms have been very popular, but the effects of their parameters on the solution quality and algorithmic efficiency are not well understood. To begin making progress in the study of multi-deme GAs, Chapter 4 extended the gambler’s ruin model to calculate the expected quality of the best of r isolated or fully-connected demes. This chapter shows that distributing the population to multiple demes has two effects on the quality. The first is that the quality required of each deme may be reduced, because in a successful run only one of the demes has to reach the desired solution. The reduction in the target quality translates into smaller demes, which in turn represent a shorter execution time. However, the reduction is only” marginal.’ The second effect of using multiple demes has a greater impact on the quality and occurs when the populations communicate. After migration, the demes restart with more copies of BBs than when they are initialized randomly, and therefore are expected to reach solutions of higher quality.
One key idea introduced in Chapter 4 is to calculate how many copies of the correct BBs are present in the demes after migration. Then, the gambler’s ruin model is used to predict the outcome of the second epoch. The same idea is at the core of the more refined models in the remainder of the book.
The calculations in Chapter 4 showed that the isolated bounding case does not result in significant performance improvements, and should be avoided in practice. On the other extreme, the size of the fully-connected demes decreases substantially, thereby reducing considerably the time used by computations. However, the reduction in computations is paired with a rapidly increasing cost of communications. This tradeoff was used to find the deme size and deme count that together minimize the execution time.
Chapter 5 used Markov chains to extend the models of solution quality to consider multiple epochs. The first result of the modeling is that the major improvements in quality come after the second epoch, confirming that the results from the previous chapter are relevant and useful. This chapter also showed that the long-term search quality of r fully-connected demes of size n d is equivalent to a single GA with a population of size rn d when the migration rate is maximal. As the migration rate decreases, the quality deteriorates, but even moderate migration rates are sufficient to reach the same quality as a panmictic population. In any case, since the cost is independent of the migration rate (because migrations occur after convergence), there is no reason to avoid the highest values.
Chapter 5 also introduced the first model of arbitrary topologies. The model explicitly accounts for all the possible combinations of success and failure of the r demes, and therefore it is very accurate, but it is also impractical for large r. Nevertheless, the model showed that the influence of the topology on the solution quality is significant and should be examined further.
Chapter 6 continues the study of the topology. It presented simple approximate models that relate the deme size, the migration rate, and the degree of the topology with the quality and cost of the search. The models explain why demes with many neighbors are more likely to find the desired solution than sparsely-connected demes. The usual tradeoff between decreasing computations and increasing communications appears, and the analysis showed how to choose the degree of the topology that minimizes the total cost.
An important observation made in Chapter 6 is that the optimal degree, δ*, does not vary considerably as the number of demes is increased. Since the execution time largely depends on the degree, this observation implies that the execution times of optimally-configured topologies do not vary much either. Therefore, any optimally-configured topology would be a good choice to reduce the execution time. Previously, the fully-connected topology was optimized, and the results of Chapter 6 suggest that it may be an adequate choice, even though it cannot connect many demes. In fact, an optimal fully-connected topology uses fewer demes (r* = δ* +1) than any other optimally-configured topology, and therefore it is very efficient (in terms of )
This chapter also established that when the topology is fixed and the algorithm is executed until all the demes converge to the same solution, the optimal number of populations is , which asymptotically is the same as parallel versions of GAs with a single population. This result suggests that parallel GAs—regardless of whether they use a single or multiple populations—can integrate large numbers of processors and reduce significantly the execution time of many practical applications.
Chapter 7 studied the method used to choose migrants and the individuals that they replace in the receiving deme. The chapter showed that some migration policies may cause the algorithm to converge faster. The migration policy that accelerates convergence the most is to choose both the migrants and the replacements according to their fitness, which is a very common policy. The faster convergence may explain some of the controversial claims of superlinear speedups in parallel GAs. In addition, the chapter included calculations of the higher moments of the distribution of fitness. These calculations showed that the degree of the topology and the migration rate affect the population in different ways, even if they result in the same selection intensity.
Chapter 8 has a brief review of fine-grained parallel GAs. These algorithms have an interesting behavior, but have not been studied as much as the other types of parallel GAs. Fine-grained GAs can be used effectively by themselves or as a component of hierarchical algorithms. Chapter 8 described different types of hierarchical parallel GAs, and examined the question of how to choose the fastest configuration when multiple demes are combined with master-slaves. In an ideal situation, there would be enough processors available to use the optimal number of demes (r*) and the optimal number of slaves (S). In this case, the speedup of the best hybrid parallel G A would be the product of the speedup of the optimal master-slave GA by the speedup of the optimal multi-deme. More often, there are not enough processors to implement the best configuration, and those that are available have to be distributed carefully between demes and slaves to obtain the combination that minimizes the execution time. The chapter presented a method that integrates the theory introduced earlier to find the optimal distribution of processors.
When communications are expensive relative to computations, the best algorithm will have few slaves and many demes, because the master-slave GA communicates often. As computations become more costly, the best hierarchical configurations will likely have more slaves per deme.
The last chapter also contained a complete step-by-step example that illustrated how to apply the theory presented in this book to a particular problem. The example discussed how to determine the domain-dependent constants presen. in the equations, and it used the method described earlier to find the best combination of demes and slaves.
Erick Cantú-Paz
Backmatter
Metadata
Title
Efficient and Accurate Parallel Genetic Algorithms
Author
Erick Cantú-Paz
Copyright Year
2001
Publisher
Springer US
Electronic ISBN
978-1-4615-4369-5
Print ISBN
978-1-4613-6964-6
DOI
https://doi.org/10.1007/978-1-4615-4369-5