Kumara Sastry

Scalability of selectorecombinative genetic algorithms for problems with tight linkage

Sastry, K., Goldberg, D. E. (2003). Proceedings of the Genetic and Evolutionary Computation Conference. 1332—1334. (Nominated for best paper in GA track). [Full paper - PDF] [Full paper - PS] [Presentation slides].

Abstract:
Ensuring building-block (BB) mixing is critical to the success of genetic and evolutionary algorithms. This study develops facetwise models to predict the BB mixing time and the population sizing dictated by BB mixing for single-point crossover. Empirical results are used to validate these models. The population-sizing model suggests that for moderate-to-large problems, BB mixing—instead of BB decision making and BB supply—bounds the population size required to obtain a solution of constant quality. Furthermore, the population sizing for single-point crossover scales as O(2^km^1.5), where k is the BB size and m is the number of BBs.

Related Posts:

• How well does a single-point crossover mix building blocks with tight linkage?
• Scalability of genetic programming and probabilistic incremental program evolution
• A survey of linkage learning techniques in genetic and evolutionary algorithms
• Limits of scalability of multiobjective estimation of distribution algorithms
• Analysis of ideal recombination on random decomposable problems

Comments are closed.