Heuristics: Local search 2: Unterschied zwischen den Versionen

Version vom 27. Juni 2013, 13:39 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)

Problem-setting

The local search metaheuristic can be applied to many multifarious problems.

Some examples are:

• The vertex cover problem, in which a solution is a vertex cover of a graph, and the target is to find a solution with a minimal number of nodes
• The travelling salesman problem, in which a solution is a cycle containing all nodes of the graph and the target is to minimize the total length of the cycle
• The boolean satisfiability 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
• The nurse scheduling problem where a solution is an assignment of nurses to shifts which satisfies all established constraints
• The k-medoid clustering problem and other related facility location problems for which local search offers the best known approximation ratios from a worst-case perspective

Applications

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

1. 2 travelling salesman problem

The travelling salesman problem (TSP) has its name from the original issue, which is a salesman, who has 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.

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