Heuristics: Local search 2

Basic Approach

The local search algorithm is a metaheuristic to solve problems in the fields of engineering, operations research and mathematics. It can be applied to optimization problems, whose aim is to find an optimal solution for a particular criterion within a reasonable amount of possible candidate solutions. A starting solution is altered slightly into a so-called neighbour solution, which is then checked for being a better solution than the starting solution. If that's the case, the neighbour solution is used as a new starting solution. This process is being repeated until an optimal solution is found or a previously defined time span is passed.

Examples of practical utilization

Physics

• simulated annealing

• particle swarm optimization

Biology

• artificial neural networks

• artificial immune systems

• ant colony optimization

Evolution (multiple parallel solutions)

• evolutionary algorithms (GA’s, GP)

Problem-setting

The local search metaheuristic can be applied to many multifarious problems.

Some examples are:

• The vertex cover problem

The aim of the vertex cover problem is to connect a given amount of nodes with each other by using the minimum amount of edges.

• The travelling salesman problem

The travelling salesman problem (TSP) has its name from the original issue, where a salesman had to visit a previously defined amount of places. According to human nature, he wants to spend as little time as possible, so he wants to minimize the length of the connecting links.

• The boolean satisfiability problem

The boolean satifiability problem describes a situation, in which a particular list of requirements has to be met.

• The nurse scheduling problem

The NSP is used to plan schedules for workers or problems with a similar structure.

• The k-medoid clustering problem

This problem attempts to minimize the distance between points labeled to be in a cluster and a point designated as the center of that cluster.

Example

Travelling salesman problem

To demonstrate how the local search can be used to solve a practical problem, an constructed example can be found below:

A business man from A has departments in B, C,D und E. He plans to visit all departments and return home. His planned route ist A-B-D-C-E-A. We want to improve this route with a local search heuristic.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Presentation of the problem

....

Detailed Solution Process

~ with explanation

Sources

Literature

• Prof. Dr. Oliver Wendt: Operations Research Script, Summer Term 2013

• Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag.
• Hoos, H.H. and Stutzle, T. (2005) Stochastic Local Search: Foundations and Applications, Morgan Kaufmann.
• Vijay Arya and Naveen Garg and Rohit Khandekar and Adam Meyerson and Kamesh Munagala and Vinayaka Pandit, (2004): Local Search Heuristics for k-Median and Facility Location Problems, Siam Journal of Computing 33(3).