A Theoretical Investigation of Termination Criteria for Evolutionary Algorithms

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.