Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
- Rigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-hard Knapsack problem, certain classes thereof have been studied in recent works. In this article, we present a dynamic model of optimizing linear functions under uniform constraints. Starting from an optimal solution with respect to a given constraint bound, we investigate the runtimes that different evolutionary algorithms need to recompute an optimal solution when the constraint bound changes by a certain amount. The classical (1+1) EA and several population-based algorithms are designed for that purpose, and are shown to recompute efficiently. Furthermore, a variant of the (1+(λ,λ))GA for the dynamic optimization problem is studied, whose performance is better when the change of the constraint bound is small.
Verfasserangaben: | Feng ShiORCiD, Friedrich Martin SchirneckORCiDGND, Tobias FriedrichORCiDGND, Timo KötzingORCiD, Frank NeumannORCiD |
---|---|
URN: | urn:nbn:de:kobv:517-opus4-605295 |
DOI: | https://doi.org/10.1007/s00453-020-00739-x |
ISSN: | 0178-4617 |
ISSN: | 1432-0541 |
Titel des übergeordneten Werks (Englisch): | Algorithmica : an international journal in computer science |
Verlag: | Springer |
Verlagsort: | New York |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 10.05.2018 |
Erscheinungsjahr: | 2018 |
Datum der Freischaltung: | 11.01.2024 |
Band: | 82 |
Ausgabe: | 10 |
Seitenanzahl: | 7 |
Erste Seite: | 3117 |
Letzte Seite: | 3123 |
Organisationseinheiten: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer Review: | Referiert |