What is Local Search

The simplest optimization algorithms are the local optimization algorithms. These are so called because they only search “locally”, in a small part of the search space, at any given time. [1]

A local optimisation algorithm generally starts at a candidate solution and iterates through neighbour solutions. This is only possible if the connection between candidate solution and neighbourhood solutions is defined on the search space.

Techniques Utilising Local Search

Hill Climbing

hill climbing is a optimization technique belonging to the local search family. It operates by starting with an arbitrary solution and progressively iterating through changes to the solution, If the change produces a better solution, the solution makes a new change and iterates, and so on until no further improvements can be found.

Hill climbing finds optimal solutions for convex problems – for other problems it will find only local optima (solutions that cannot be improved upon by any neighboring configurations), which are not necessarily the best possible solution (the global optimum) out of all possible solutions (the search space). Examples of algorithms that solve convex problems by hill-climbing include the simplex algorithm for linear programming and binary search. [2]

Tabu Search

Tabu Search is a Global Optimization algorithm and a Metaheuristic or Meta-strategy for controlling an embedded heuristic technique. Tabu Search is a parent for a large family of derivative approaches that introduce memory structures in Metaheuristics, such as Reactive Tabu Search and Parallel Tabu Search. [3]

The objective in a Tabu Search is to constrain the search from returning to recently visited areas of the search space, the intention of this procedure is to produce a short term memory of recent moves in the search space and prevent future moves from undoing these changes.

Bibliography

[1] G.N. Yannakakis and J. Togelius, Artificial Intelligence and Games, Springer, 2018.

[2] Skiena, Steven. The Algorithm Design Manual. (2nd ed.). Springer, 2010.

[3] J. Brownlee. Tabu Search [Online]. Available: http://www.cleveralgorithms.com/nature-inspired/stochastic/tabu_search.html