Spatial and Temporal Resource Allocation for Adaptive Parallel Genetic Algorithm

摘要

Adaptive parameter control in evolutionary computation is achieved by a method of computational resource allocation, both spatially and temporally. Spatially it is achieved for the parallel genetic algorithm by the partitioning of the search space into many subspaces. Search for solution is performed in each subspace by a genetic algorithm which domain of chromosomes is restricted inside 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 sub-spaces by genetic algorithm. In each subspace, temporal resource allocation is also made for different competing evolutionary algorithms, so that more CPU time is allocated to those algorithms which showed better performance in the past. This general idea is implemented in a new adaptive genetic algorithm using the formalism of mutation matrix, where the need for setting a survival probability is removed. The temporal resource allocation is introduced and implemented in a single computer using the quasi-parallel time sharing algorithm for the solution of the zero/one knapsack problem. 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. Two competing strategies of evolution, mutation by row (chromosome), and mutation by column (locus) are used for the competition of CPU time. Time sharing experiment on these two strategies is performed on a single computer in solving the knapsack problem. Based on the investment frontier of time allocation, the optimal configuration in solving the knapsack problem is found.