A Rigorous Complexity Analysis of the (1+1) Evolutionary Algorithm for Separable Functions with Boolean Inputs

被引：63

作者：

Droste, Stefan ^{[1
]}

Jansen, Thomas ^{[1
]}

Wegener, Ingo ^{[1
]}

机构：

[1] Univ Dortmund, FB Informat, D-44221 Dortmund, Germany

来源：

EVOLUTIONARY COMPUTATION | 1998年 / 6卷 / 02期

关键词：

Evolutionary algorithm; separable function; random walk; complexity analysis;

D O I：

10.1162/evco.1998.6.2.185

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Evolutionary algorithms (EAs) are heuristic randomized algorithms which, by many impressive experiments, have been proven to behave quite well for optimization problems of various kinds. In this paper a rigorous theoretical complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs is given. Different mutation rates are compared, and the use of the crossover operator is investigated. The main contribution is not the result that the expected run time of the (1 + 1) evolutionary algorithm is Theta(n ln n) for separable functions with n variables but the methods by which this result can be proven rigorously.

引用

页码：185 / 196

页数：12

共 15 条

[1]

BACK T, 1993, PROCEEDINGS OF THE FIFTH INTERNATIONAL CONFERENCE ON GENETIC ALGORITHMS, P2

[2]

Cormen T. H., 1990, INTRO ALGORITHMS

[3]

Feller W., 1968, INTRO PROBABILITY TH

[4]

Fogel D.B., 1995, EVOLUTIONARY COMPUTA

[5]

Goldberg D., 1989, GENETIC ALGORITHMS S

[6]

MOTWANI R., 1995, Randomized Algorithms

[7] Predictive Models for the Breeder Genetic Algorithm I. Continuous Parameter Optimization [J].

Muehlenbein, Heinz ;

Schlierkamp-Voosen, Dirk .

EVOLUTIONARY COMPUTATION, 1993, 1 (01) :25-49

[8]

Muhlenbein H., 1994, EVOLUTIONARY COMPUTA, V1, P335

[9]

Rechenberg I., 1994, Evolutionsstrategie'94

[10] Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms [J].

Salomon, R .

BIOSYSTEMS, 1996, 39 (03) :263-278

← 1 2 →