Adaptive Spatial Allocation of Resource for Parallel Genetic Algorithm

Spatial allocation of resource for parallel genetic algorithm is achieved by the partitioning of the search space into many subspaces. Search for solution is performed in each subspace by a genetic algorithm with chromosomes defined in that particular subspace. This spatial allocation of computational resource takes the advantage of exhaustive search which avoids duplicate effort, and combine it with the parallel nature of the search for solution in disjoint subspaces by genetic algorithm. The division of the solution space is performed intelligently using loci statistics of the chromosomes in past generations. The time when this division takes place is determined by monitoring the performance of the evolutionary computation using mean and variance. This general idea is implemented in an adaptive genetic algorithm using the new formalism of mutation matrix, where the need for setting a survival probability is removed. The mutation matrix

M(t)

is constructed using the locus statistics and the fitness distribution in a population

A(t)

with N rows and L columns, where N is the size of the population and L is the length of the encoded chromosomes. The mutation matrix is parameter free and adaptive as it is time dependent and captures the accumulated information in the past generation. Example illustrating the efficiency of this adaptive spatial allocation of resource is the zero/one knapsack problem.