Springer
Table of ContentsAuthor IndexSearch

Scalability of Selectorecombinative Genetic Algorithms for Problems with Tight Linkage

Kumara Sastry1,2 and David E. Goldberg1,3

1Illinois Genetic Algorithms Laboratory (IlliGAL)
2Department of Material Science & Engineering
3Department of General Engineering
University of Illinois at Urbana-Champaign
Urbana, IL
{ksastry,deg}@uiuc.edu

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. 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\left(2^km^{1.5}\right)$, where $k$ is the BB size, and $m$ is the number of BBs.

LNCS 2724, p. 1332 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003