Anytime algorithm - an algorithm that can be stopped at any time and still return reasonable results.
Aspiration criterion - the set of conditions under which moving to a solution forbidden by tabu list is allowed. A generally used criterion grants such exception if the forbidden solution is better than the best one found so far.
Energy - target function in the context of simulated annealing, subject to minimization.
Fitness function - target function in the context of genetic algorithm, subject to maximization.
Local Search - an algorithm that iteratively moves to a better neighbour of the current solution until no such neighbour can be found. Possible search strategies are:
- First improvement: visit the neighbours until an improvement has been found
- Best improvement: visit all neighbours, pick the best one
Metaheuristic - an optimization algorithm applicable to various distinct problems. Metaheuristics act on solutions and related data structures by means of operators. The solution data type and the operators can be fixed (Differential Evolution, Particle Swarm Optimization) or user-defined (Genetic Algorithm). Apart from the fixed set of operators, a metaheuristic has no access to the solutions or problem-specific knowledge. Metaheuristics usually have the following distinct traits:
- Randomized
- No guarantees regarding the quality of the obtained solutions
- Inspired by natural processes (genetic algorithm, simulated annealing)
- Complexity per iteration polynomial in problem size (depends on the operators)
- Local search
- Tabu search
- Simulated annealing
- Genetic algorithm
- Estimation of distribution
Move - an operation or a data structure specifying an operation that transforms a solution into one of its neighbours.
Neighbor - a solution that can be obtained from another solution by an elementary modification.
Neighborhood - a collection of neighbours of a solution.
Operator - a function acting on solutions or related data structures (e. g. crossover, mutation). Metaheuristics interact with solutions exclusively via operators.
Optimization problem - a problem of finding a solution that maximizes or minimizes a target function.
Solution - a data structure whose quality can be evaluated by a target function.
Tabu list - data structure used by tabu search to store information about already visited solutions to avoid visiting similar solutions in the near future. Usually implemented as a list or an array of forbidden elements along with the corresponding tabu tenures.
Tabu search - local search with best improvement strategy extended with a memory structure (tabu list) storing already visited states. Revisiting these states is forbidden for a number of iterations (tabu tenure), which forces the algorithm to explore new regions. Visiting a tabu state is sometimes allowed under exceptional conditions (aspiration criterion).
Tabu tenure - the number of iterations during which and element from the tabu list is forbidden. A randomized tenure with mean decreasing with time is generally recommended.
Target function - a function defined over the set of solutions, subject to optimization. Synonyms include fitness function, energy and score.
Variable neighborhood search - a local search acceleration technique starting with a small neighborhood and switching to larger ones when improvement can no longer be found.