Combining exhaustive search with evolutionary computation via computational resource allocation

The division of the solution space into several subspaces and the subsequent search restricted to individual subspace have the advantage that effort in one subspace will not be repeated in the other subspace. This feature of exhaustive search is combined with evolutionary computation in each subspace via an adaptive allocation of computational resource to subspace search. A recent version of genetic algorithm, called MOGA[1], [2], [3] is used as the evolutionary computation. Chromosomes evolve in a given subspace only. The computational resource allocation will be based on the quality of the search results: the subspace expected to contain the true solution will be given more computational resource. In this way, a quasi-parallelism is provided to evolutionary computation in different subspace in terms of computational time[4]. Various ways of resource allocation have been tried on the knapsack problem and the Weierstrass´s function problem. Results show that in general, division of solution space into subspace provides a higher efficiency.