Convergence Analysis of Evolutionary Algorithms That Are Based on the Paradigm of Information Geometry
Evolutionary Computation · 2014-12 · 22 (4) · 679-709
DOI: 10.1162/evco_a_00132 ↗Kurz gefasst
Vergleichsstudie in der Zeitschrift Evolutionary Computation, 2014-12. Verfasst von Hans-Georg Beyer. Beteiligte Einrichtung: Department of Computer Science, Vorarlberg University of Applied Sciences, Hochschulstrasse 1, A-6850 Dornbirn, Austria. Hans-Georg.Beyer@fhv.at. Hauptthemen laut MEDLINE: Algorithms, Computing Methodologies, Information Theory, Models, Theoretical. Die Arbeit wurde bisher 48-mal zitiert (Crossref) und nennt 26 Literaturangaben.
Abstract (Originalsprache)
The convergence behaviors of so-called natural evolution strategies (NES) and of the information-geometric optimization (IGO) approach are considered. After a review of the NES/IGO ideas, which are based on information geometry, the implications of this philosophy w.r.t. optimization dynamics are investigated considering the optimization performance on the class of positive quadratic objective functions (the ellipsoid model). Exact differential equations describing the approach to the optimizer are derived and solved. It is rigorously shown that the original NES philosophy optimizing the expected value of the objective functions leads to very slow (i.e., sublinear) convergence toward the optimizer. This is the real reason why state of the art implementations of IGO algorithms optimize the expected value of transformed objective functions, for example, by utility functions based on ranking. It is shown that these utility functions are localized fitness functions that change during the IGO flow. The governing differential equations describing this flow are derived. In the case of convergence, the solutions to these equations exhibit an exponentially fast approach to the optimizer (i.e., linear convergence order). Furthermore, it is proven that the IGO philosophy leads to an adaptation of the covariance matrix that equals in the asymptotic limit—up to a scalar factor—the inverse of the Hessian of the objective function considered.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Department of Computer Science, Vorarlberg University of Applied Sciences, Hochschulstrasse 1, A-6850 Dornbirn, Austria. Hans-Georg.Beyer@fhv.at.
Zitieren
APA
Beyer, H. G. (2014). Convergence Analysis of Evolutionary Algorithms That Are Based on the Paradigm of Information Geometry. Evolutionary Computation, 22(4), 679-709. https://doi.org/10.1162/evco_a_00132
Vancouver
Beyer HG. Convergence Analysis of Evolutionary Algorithms That Are Based on the Paradigm of Information Geometry. Evolutionary Computation. 2014;22(4):679-709. doi:10.1162/evco_a_00132
BibTeX
@article{Beyer2014,
author = {Beyer, Hans-Georg},
title = {Convergence Analysis of Evolutionary Algorithms That Are Based on the Paradigm of Information Geometry},
journal = {Evolutionary Computation},
year = {2014},
volume = {22},
number = {4},
pages = {679--709},
doi = {10.1162/evco_a_00132}
}
EUVIMED