Self-adaptive mutations may lead to premature convergence

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.