Heuristics: Local search 1: Unterschied zwischen den Versionen

Version vom 23. Juni 2013, 11:40 Uhr

not yet finished

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

Examples

Example

Example

Presentation of the problem

Detailed Solution Process

~ with explanation

Sources

Internetsources

• http://en.wikipedia.org/wiki/Local_search_(optimization)

Literature

• Prof. Dr. Oliver Wendt: Operations Research Script, Summer Term 2013