%T Accurate Calculation of Deme Sizes for a Parallel Genetic Scheduling Algorithm
%A  M. Moore
%E  Jan F. Broenink,  Gerald H. Hilderink
%B Communicating Process Architectures 2003
%X 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\[`u]\-Paz\[rs] serial
   population sizing calculation based on the gambler\[rs]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.