An application of stochastic differential equations to evolutionary algorithms

T. Paixao, J. Pérez Heredia, in:, ACM, 2017, pp. 3–11.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
;
Department
Series Title
Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
Abstract
There has been renewed interest in modelling the behaviour of evolutionary algorithms by more traditional mathematical objects, such as ordinary differential equations or Markov chains. The advantage is that the analysis becomes greatly facilitated due to the existence of well established methods. However, this typically comes at the cost of disregarding information about the process. Here, we introduce the use of stochastic differential equations (SDEs) for the study of EAs. SDEs can produce simple analytical results for the dynamics of stochastic processes, unlike Markov chains which can produce rigorous but unwieldy expressions about the dynamics. On the other hand, unlike ordinary differential equations (ODEs), they do not discard information about the stochasticity of the process. We show that these are especially suitable for the analysis of fixed budget scenarios and present analogs of the additive and multiplicative drift theorems for SDEs. We exemplify the use of these methods for two model algorithms ((1+1) EA and RLS) on two canonical problems(OneMax and LeadingOnes).
Publishing Year
Date Published
2017-01-12
Page
3 - 11
Conference
FOGA: Foundations of Genetic Algorithms
Conference Location
Copenhagen, Denmark
Conference Date
2017-01-12 – 2017-01-15
IST-REx-ID

Cite this

Paixao T, Pérez Heredia J. An application of stochastic differential equations to evolutionary algorithms. In: ACM; 2017:3-11. doi:10.1145/3040718.3040729
Paixao, T., & Pérez Heredia, J. (2017). An application of stochastic differential equations to evolutionary algorithms (pp. 3–11). Presented at the FOGA: Foundations of Genetic Algorithms, Copenhagen, Denmark: ACM. https://doi.org/10.1145/3040718.3040729
Paixao, Tiago, and Jorge Pérez Heredia. “An Application of Stochastic Differential Equations to Evolutionary Algorithms,” 3–11. ACM, 2017. https://doi.org/10.1145/3040718.3040729.
T. Paixao and J. Pérez Heredia, “An application of stochastic differential equations to evolutionary algorithms,” presented at the FOGA: Foundations of Genetic Algorithms, Copenhagen, Denmark, 2017, pp. 3–11.
Paixao T, Pérez Heredia J. 2017. An application of stochastic differential equations to evolutionary algorithms. FOGA: Foundations of Genetic Algorithms, Proceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms , 3–11.
Paixao, Tiago, and Jorge Pérez Heredia. An Application of Stochastic Differential Equations to Evolutionary Algorithms. ACM, 2017, pp. 3–11, doi:10.1145/3040718.3040729.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search