| Parallel implementations of genetic algorithms (GAs) are common, and, in most cases, they succeed to reduce the time required to find acceptable solutions. However, the effect of the parameters of parallel GAs on the quality of their search and on their efficiency are not well understood. This insufficient knowledge limits our ability to design fast and accurate parallel GAs that reach the desired solutions in the shortest time possible. The goal of this dissertation is to advance the understanding of parallel GAs and to provide rational guidelines for their design. The research reported here considered three major types of parallel GAs: simple master-slave algorithms with one population, more sophisticated algorithms with multiple populations, and a hierarchical combination of the first two types. The investigation formulated simple models that predict accurately the quality of the solutions with different parameter settings. The quality predictors were transformed into population-sizing equations, which in turn were used to estimate the execution time of the algorithms. The primary tradeoff between decreasing computations and increasing communications was identified and it was used to find the optimal configuration of each algorithm that minimized the execution time. The investigation is mainly theoretical, but experimental evidence using test functions of varying difficulty is included to illustrate the accuracy of the theory. The results of this investigation enable practitioners to determine what algorithm is the most beneficial for their particular domain and to allocate the resources available in the most efficient manner. |
