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 language | English |
---|---|
Title of host publication | Evolutionary Computation in Combinatorial Optimization |
Subtitle of host publication | 24th European Conference, EvoCOP 2024, Held as Part of EvoStar 2024, Aberystwyth, UK, April 3–5, 2024, Proceedings |
Editors | Thomas Stützle, Markus Wagner |
Publisher | Springer |
Pages | 162–176 |
Edition | 1 |
ISBN (Electronic) | 9783031577123 |
ISBN (Print) | 9783031577116 |
DOIs | |
Publication status | Published - 2 Jun 2024 |
Event | Evolutionary Computation in Combinatorial Optimization – 24th European Conference, EvoCOP 2024 - Duration: 3 Apr 2024 → 5 Apr 2024 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 14632 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | Evolutionary Computation in Combinatorial Optimization – 24th European Conference, EvoCOP 2024 |
---|---|
Period | 3/04/24 → 5/04/24 |