Heuristics: Local search 1
not yet finished
Inhaltsverzeichnis
Theory
... Initial point of local search is to look at the local neighbors of a given solution si in the search space S. If a neighboring solutions has a better objective function value f (sj) as f (si), the current solution by a better solution is replaced and the search continues with the new solution sj.
Is to transform a given solution into a new solution, the neighborhood relation N ⊆ SxS used. This neighborhood relation depends posed by the problem and is defined at the top of local search by the modeler.
When choosing the neighborhood relation should be notedthis is the neighborhood generated neither too large nor too small.
Too many great neighborhoods to neighbors must be examined and evaluated at each step of the search, which in extreme cases the local search becomes a random search.
Too small neighborhoods, however, the probability is greaterthat the search is stuck in a local optimum from which the local search method can not escape.
Methods
... Methode: The k-opt method is a neighborhood relation which is based on edge-exchange operators, and probably represents the most prominent class of optimization methods for TSP. In a k-opt-neighborhood is created by the method,k that edges are replaced with k and then the other edge Tour is checked for improvement. Probably the most common operator here is probably the 2-change (or 2-opt or inversion) operator.
Process: Generating a random initial solution Si Generate a new solution Sj using the neighborhood relation If the new solution Sj is better (eg lower costs has) then replaced the solution Si (Si = Sj) and go to step 2
Applications
- 1 vertex cover problem
In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm. the target is to find a solution with a minimal number of nodes. Furthermore, the vertex cover problem is fixed-parameter tractable and a central problem in parameterized complexity theory. The minimum vertex cover problem can be formulated as a half-integral linear program whose dual linear program is the maximum matching problem.
- 2 travelling salesman problem
In the travelling salesman problem, a solution is a cycle containing all nodes of the graph and the target is to minimize the total length of the cycle. It asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
- 3 boolean satisfiability problem
This is a problem, in which a candidate solution is a truth assignment, and the target is to maximize the number of clauses satisfied by the assignment; in this case, the final solution is of use only if it satisfies all clauses
- 4 nurse scheduling problem
The Nurse scheduling problem (NSP) is the problem of determining a work schedule for nurses that is both reasonable (or fair) and efficient. It is all about assignment of shifts and holidays to nurses. A nurse has her/his wishes/restrictions. The problem is described as finding a schedule that both respects the constraints of the nurses and fulfills the objectives of the hospital. Conventionally a nurse can work 3 shifts because nursing is shift work: day shift night shift late night shift.
A solution is an assignment of nurses to shifts which satisfies all established constraints. Possible constraints may be A nurse doesn't work the day shift, night shift and late night shift on the same day (for obvious reasons). A nurse may go on a holiday and will not work shifts during this time. A nurse doesn't do a late night shift followed by a day shift the next day.
- 5 k-medoid clustering problem
Relevant also for other related facility location problems for which local search offers the best known approximation ratios from a worst-case perspective.
Examples
Traveling Salesman Problem - k-opt method In this case k=2, so it´s called 2-opt method.
A business man from town A has departments in towns B, C, D, and E. He plans to visit all departments and return home. His planned route ist A-B-C-D-E-A. Is this the shortest route? Please determine with Local Search applying the two-opt. The distance-matrix is as followed:
Presentation of the problem
A business man from town A has departments in towns B, C, D, and E. He wants to visit all departments and return home. His planned route ist A-B-C-D-E-A. Is this the shortest route, that covers each department and ends back at the start-department? Please determine with Local Search applying the two-opt. The 2-opt means, that you are only allowed to change two departments per each iterationstep. The soloution is optimal when the shortest roundtrip is reached. At this solution the iteration-process stops.
Detailed Solution Process
Sources
Internetsources
Literature
- Prof. Dr. Oliver Wendt: Operations Research Script, Summer Term 2013
