WoTUG - The place for concurrent processes

Paper Details

Accurate Calculation of Deme Sizes for a Parallel Genetic Scheduling Algorithm

Authors: Moore, M.

Abstract:

The accuracies of three equations to determine the size of populations for serial and parallel genetic algorithms are evaluated when applied to a parallel genetic algorithm that schedules tasks on a cluster of computers connected via shared bus. This NP-complete problem is representative of a variety of optimisation problems for which genetic algorithms (GAs) have been shown to effectively approximate the optimal solution. However, empirical determination of parameters needed by both serial and parallel GAs is time-consuming, often impractically so in production environments. The ability to predetermine parameter values mathematically eliminates this difficulty. The parameter that exerts the most influence over the solution quality of a parallel genetic algorithm is the population size of the demes. Comparisons here show that the most accurate equation for the scheduling application is Cantú-Paz' serial population sizing calculation based on the gambler's ruin model [1]. The study presented below is part of an ongoing analysis of the effectiveness of parallel genetic algorithm parameter value computations based on schema theory. The study demonstrates that the correct deme size can be predetermined quantitatively for the scheduling problem presented here, and suggests that this may also be true for similar optimisation problems. This work is supported by NASA Grant NAG9-140.

Proceedings:

Communicating Process Architectures 2003, Jan F. Broenink, Gerald H. Hilderink, 2003, pp 305 - 313 published by IOS Press, Amsterdam

Files: PDF

This record in other formats:

Web page: BibTEX, Refer
Plain text: BibTEX, Refer

If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.

Pages © WoTUG, or the indicated author. All Rights Reserved.
Comments on these web pages should be addressed to: www at wotug.org

Valid HTML 4.01!