Local Search

The local search metaheuristic is an iterative improvement heuristic, since every move is only applied if the result is better than the current solution. The algorithm stops as soon as it finds a local minimum.

Algorithm

1. GenerateInitialSolution

2. while(improvement possible)

   1. Improve the solution until no possible improvement is found

Example

The traveling salesman problem: A salesman has to go to N doors to sell his goods. What is the shortest path that he can take?

* Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison