Original scientific paper

Convergence Theory and Applications of the Factorized Distribution Algorithm

Heinz Muhlenbein ; RWCP Theoretical Foundation GMO Laboratory, GMO, Forschungszentrum lnlormationstechnik, St. Augustin
Thilo Mahnig ; RWCP Theoretical Foundation GMO Laboratory, GMO, Forschungszentrum lnlormationstechnik, St. Augustin

Abstract

The paper investigates the optimization of additively decomposable functions (ADF) by a new evolutionary algorithm called Factorized Distribution Algorithm (FDA). FDA is based on a factorization of the distribution to generate search points. First separable ADFs are considered. These are mapped to generalized linear functions with metavariables defined for multiple alleles. The mapping transforms FDA into an Univariate Marginal Frequency Algorithm (UMDA). For UMDA the exact equation for the response to selection is.computed under the assumption of proportionate selection. For truncation selection an approximate equation for the time to convergence is used, derived from an analysis of the OneMax function. FDA is also numerically investigated for non separable functions. The time to convergence is very similar to separable ADFs. FDA outpe1iorms the genetic algorithm with recombination of strings by far.

Keywords

response to selection; Fisher's Theorem; additively decomposed functions; genetic algorithm; factorized di stribution

Hrčak ID:

150197

URI

https://hrcak.srce.hr/150197

Publication date:

30.3.1999.

Visits: 1.235 *