Heuristics: Local search 2: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
(→Applications) |
(→Problem-setting) |
||
| Zeile 32: | Zeile 32: | ||
Some examples are: | Some examples are: | ||
| − | * '''vertex cover problem''' | + | * 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 aim of the vertex cover problem is to connect a given amount of nodes with each other by using the minimum amount of edges. | ||
| − | * '''travelling salesman problem''' | + | * 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 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. | ||
| − | * '''boolean satisfiability problem''' | + | * The '''boolean satisfiability problem''' |
The boolean satifiability problem describes a situation, in which a particular list of requirements has to be met. | The boolean satifiability problem describes a situation, in which a particular list of requirements has to be met. | ||
| − | * '''nurse scheduling problem''' | + | * The '''nurse scheduling problem''' |
The NSP is used to plan schedules for workers or problems with a similar structure. | The NSP is used to plan schedules for workers or problems with a similar structure. | ||
| − | * '''k-medoid clustering problem''' | + | * 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. | 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. | ||
| − | |||
| − | |||
==Examples== | ==Examples== | ||
Version vom 27. Juni 2013, 13:59 Uhr
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.
Examples
Example: Travelling salesman problem
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. Is this the shortest route? Please determine with local search applying the two-opt.
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).
