Heuristics: Local search 2
Inhaltsverzeichnis
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, a constructed example can be found below:
A business man from A has departments in B, C,D and 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 help of a local search heuristic.
The distances between the places can be extracted from the tables below:
A-B-D-C-E-A=1275
Detailed Solution Process
Explanation of the image:
The purple marked cities are those which have been exchanged. The arrows in each tablet mark the optimal solution.
Firstly a starting route has to be chosen. The chosing process can be totally random, as it does not matter in findig the correct solution. After the starting route has been chosen, an exchange of exactly 2 edges is performed (hence the name of the algorithm "2-opt method"); but it is only allowed to alter the startroute. However it is forbidden to exchange the start and end point of the route.
Then the distance of the new route has to be calculated. After repeatedly altering the startroute until every possible combination has been calculated, the optimal solution is found by looking which distance is the shortest. After that, the whole process has to be repeated with the first optimal solution as starting route. This is necessary in order to ensure that the first solution is really optimal and there is actually no better route. If a shorter route is found, then it is the new optimal solution; if not the old route stays optimal.
"Any solution has exactly n(n-3) neighbors (for symmetric TSP: n(n-3)/2)." This formula shows how many rows the tablet can maximally have. In this case we have a route with 5 stops which equals a maximum of 10 rows 5*(5-3)=10. As seen in the tablet on top.
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).
