Heuristics: Local search 2
Inhaltsverzeichnis
Theory
Local search algorithms used to solve problems, in the engineering, the operations research and the mathematics area. Examples of local search algorithms is for example the 2-opt algorithm for the Traveling Salesman Problem. Local search is a metaheuristic method for solving optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. The algorithm of Local search goes from solution to solution in the space of candidate solutions by applying local changes, until an optimal solution is found or a certain is over.
Examples for use in praxis
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)
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
Example
Example
Presentation of the problem
....
Detailed Solution Process
~ with explanation
Sources
Internetsources
Literature
- Prof. Dr. Oliver Wendt: Operations Research Script, Summer Term 2013
