A Theoretical Investigation Of Termination Criteria For Evolutionary Algorithms

Jonathan Rowe*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We take a theoretical approach to analysing conditions for terminating evolutionary algorithms. After looking at situations where much is known about the particular algorithm and problem class, we consider a more generic approach. Schemes that depend purely on the previous time to improvement are shown not to work. An alternative criterion, the $\lambda$-parallel scheme, does terminate correctly (with high probability) for any randomised search heuristic algorithm on any problem, provided certain conditions on the improvement probabilities are met. A more natural and less costly approach is then presented based on the runtime so far. This is shown to work for the classes of monotonic and path problems (for Randomised Local Search). It remains an open question whether it works in a more general setting.
Original languageEnglish
Title of host publication Evolutionary Computation in Combinatorial Optimization
Subtitle of host publication24th European Conference, EvoCOP 2024, Held as Part of EvoStar 2024, Aberystwyth, UK, April 3–5, 2024, Proceedings
EditorsThomas Stützle, Markus Wagner
PublisherSpringer
Pages162–176
Edition1
ISBN (Electronic)9783031577123
ISBN (Print)9783031577116
DOIs
Publication statusPublished - 2 Jun 2024
Event Evolutionary Computation in Combinatorial Optimization –
24th European Conference, EvoCOP 2024
-
Duration: 3 Apr 20245 Apr 2024

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume14632
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference Evolutionary Computation in Combinatorial Optimization –
24th European Conference, EvoCOP 2024
Period3/04/245/04/24

Fingerprint

Dive into the research topics of 'A Theoretical Investigation Of Termination Criteria For Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this