The Termination Criteria of A Heuristic Algorithm
Some commonly used termination criteria in literature
When using a heuristic algorithm to solve an optimization problem, if the algorithm is an improvement heuristic (as opposed to constructive heuristic), one element that need to be specified is the termination criterion of the algorithm.
1. What is termination criterion
Termination criterion, as its name suggests, is the criterion of stopping the algorithm. As improvement heuristic algorithms are based on the search to improve the solution, this search has to be stoped at some point. Otherwise, the algorithm could go on forever.
The condition that allows the search to stop is often when meeting a specified requirement, and this requirement is the termination criterion of the algorithm.
2. Misunderstandings of termination criterion
The termination criterion sounds easy to understand. But when I was reading literature, I sometimes found that there are some misunderstands about it. Some algorithm implementations, like the algorithm is to be stopped after the solution is improved a certain number of iterations, will occasionally lead to infinite loop.
So there is necessity to know some commonly used (and correct) termination criteria.
3. Four commonly used termination criteria
In the following, I will introduce four commonly used termination criteria.
(1) Stop after a fixed number of iterations
The algorithm is to be stopped after a fixed number of iterations. This criterion is commonly used in the genetic algorithm implementations.
(2) Stop after a fixed account of CPU time
The algorithm is to be stopped after a fixed account of CPU time. This criterion is often used in comparative study in which the performance of an algorithm is compared against other algorithms.
(3) Stop after some number of iterations without an improvement in the objective function value
The algorithm is to be stopped after the number of iterations without an improvement in the objective function value. This criterion is used in many algorithm implementations.
(4) Stop when the objective reaches a pre-specific threshold value
The algorithm is to be stopped when the objective value reaches a pre-specific threshold value. This criterion is used in some algorithm implementations.
4. More complex implementations
In some complex algorithm implementations, the search is usually stopped after completing a sequence of phases, the duration of each phase being determined by one of the above criteria [1].
For example, in local search-based heuristic algorithms, the algorithm itself has to be stopped when meeting a criterion, while the local search in each iteration of the algorithm has to be stopped when meeting a criterion. The former criterion could be after a fixed amount of CPU time, and the latter could be after some number of iterations without an improvement in the objective function value.
Reference
1. Glover, F. W., & Kochenberger, G. A. (Eds.). (2003). Handbook of metaheuristics (Vol. 57). Springer Science & Business Media.