Heuristics: Local search 2: Unterschied zwischen den Versionen

Version vom 27. Juni 2013, 13:03 Uhr

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)

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. 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.

1. 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.

1. 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

1. 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.

1. 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: Travelling salesman problem

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).