Authors

Citation

G. Rudolph, Self-adaptive mutations may lead to premature convergence, IEEE T EV C, 5(4), 2001, pp. 410-414

Citations number

13

Language

INGLESE

art.tipo

Article

Categorie Soggetti

AI Robotics and Automatic Control

Journal title

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION

ISSN journal

1089-778X
→ ACNP

Volume

5

Issue

4

Year of publication

2001

Pages

410 - 414

Database

ISI

SICI code

1089-778X(200108)5:4<410:SMMLTP>2.0.ZU;2-Q

Abstract

Self-adaptive mutations are known to endow evolutionary algorithms (EAs) wi
th the ability of locating local optima quickly and accurately, whereas it
was unknown whether these local optima are finally global optima provided t
hat the EA runs long enough. In order to answer this question, it is assume
d that the (1 + 1)-EA with self-adaptation is located in the vicinity P of
a local solution with objective function value epsilon. In order to exhibit
convergence to the global optimum with probability one, the EA must genera
te an offspring that is an element of the lower level set S containing all
solutions (including a global one) with objective function value less than
epsilon. In case of multimodal objective functions, these sets P and S are
generally not adjacent, i.e., min{\ \x - y \ \: x is an element of P, y is
an element of S} > 0, so that the EA has to surmount the barrier of solutio
ns with objective function values larger than epsilon by a lucky mutation.
It will be proven that the probability of this event is less than one even
under an infinite time horizon. This result implies that the EA can get stu
ck at a nonglobal optimum with positive probability. Some ideas of how to a
void this problem are discussed as well.