Files in this item



application/pdf9952979.pdf (8MB)Restricted to U of Illinois
(no description provided)PDF


Title:Designing Efficient and Accurate Parallel Genetic Algorithms
Author(s):Cantu-Paz, Erick
Doctoral Committee Chair(s):Goldberg, David E.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract: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.
Issue Date:1999
Description:153 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1999.
Other Identifier(s):(MiAaPQ)AAI9952979
Date Available in IDEALS:2015-09-25
Date Deposited:1999

This item appears in the following Collection(s)

Item Statistics