Illinois Genetic Algorithms Laboratory

Lobo, F.G., Goldberg, D.E., Pelikan, M. (2000)
TR No.: 2000015 | Download PDF | Download PS

Abstract:
This paper gives a theoretical and empirical analysis of the time
complexity of genetic algorithms (GAs) on problems with exponentially scaled
building blocks. It is important to study GA performance on this type of
problems because one of the difficulties that GAs are generally faced with
is due to the low scaling or low salience of some building blocks.

The paper is an extension of the model introduced by Thierens, Goldberg,
and Pereira (1998) for the case of building blocks rather than single
genes, and the main result is that under the assumption of perfect building
block mixing, both population size and time to convergence grow linearly
with the problem length, giving an overall quadratic time complexity in
terms of fitness function evaluations.

With traditional simple GAs, the assumption of perfect mixing only
occurs when the user has knowledge about the structure of the problem
(which is usually not true). However, the assumption is well approximated
for advanced GAs that are able to automatically learn gene linkage.