A new analysis method for evolutionary optimization of dynamic and noisy objective functions
| Autor: | Gautier Izacard, Dorian Nogneng, Benjamin Doerr, Thibault Dardinier, Raphaël Dang-Nhu |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
education.field_of_study
Mathematical optimization Computer science Offspring Population Evolutionary algorithm Contrast (statistics) 0102 computer and information sciences 02 engineering and technology Function (mathematics) 01 natural sciences Noise 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Benchmark (computing) 020201 artificial intelligence & image processing education Heuristics |
| Zdroj: | GECCO |
| DOI: | 10.1145/3205455.3205563 |
| Popis: | Evolutionary algorithms, being problem-independent and randomized heuristics, are generally believed to be robust to dynamic changes and noisy access to the problem instance. We propose a new method to obtain rigorous runtime results for such settings. In contrast to many previous works, our new approach mostly relies on general parameters of the dynamics or the noise models, such as the expected change of the dynamic optimum or the probability to have a dynamic change in one iteration. Consequently, we obtain bounds which are valid for large varieties of such models. Despite this generality, for almost all particular models regarded in the past our bounds are stronger than those given in previous works. As one particular result, we prove that the (1 + λ) EA can optimize the OneMax benchmark function efficiently despite a constant rate of 1-bit flip noise. For this, a logarithmic size offspring population suffices (the previous-best result required a super-linear value of λ). Our results suggest that the typical way to find the optimum in such adverse settings is not via a steady approach of the optimum, but rather via an exceptionally fast approach after waiting for a rare phase of low dynamic changes or noise. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|