Heuristics: Local search 2: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Detailed Solution Process)
 
(46 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
−
==Theory==
+
==Basic Approach==  
−
+
  
−
The local search algorithm is used to solve problems in the fields of engineering, operations research and mathematics.
 
−
Technically it is a metaheuristic method to solve optimization problems. Local search can be applied to problems, which can be reduced to finding a maximizing criterion within a number of possible candidate solutions. The algorithm of Local search travels from solution to solution in the space of candidate solutions by applying local changes, until an optimal solution is found or a certain timespan is over.
 
  
 +
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 for practical utilization====
 
−
=====Physics=====
 
  
 +
====Examples of practical utilization====
 +
=====Physics=====
  
 
* simulated annealing
 
* simulated annealing
  
 
* particle swarm optimization
 
* particle swarm optimization
−
 
  
 
=====Biology=====
 
=====Biology=====
Zeile 22: Zeile 20:
  
 
* ant colony optimization
 
* ant colony optimization
−
 
  
 
=====Evolution (multiple parallel solutions)=====
 
=====Evolution (multiple parallel solutions)=====
Zeile 28: Zeile 25:
 
* evolutionary algorithms (GA’s, GP)
 
* evolutionary algorithms (GA’s, GP)
  
−
==Methods==
 
  
−
...
+
==Problem-setting==
−
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:
+
The local search metaheuristic can be applied to many multifarious problems.
−
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==
+
Some examples are:
  
−
#1 '''vertex cover problem'''
+
* The '''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 aim of the vertex cover problem is to connect a given amount of nodes with each other by using the minimum amount of edges.  
−
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'''
+
* The '''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.''
+
The travelling salesman problem (TSP) has its name from the original issue, where a salesman had 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.
  
−
#3 boolean satisfiability problem
+
* The '''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 boolean satifiability problem describes a situation, in which a particular list of requirements has to be met.
−
''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
+
* The '''nurse scheduling problem'''
−
A nurse doesn't work the day shift, night shift and late night shift on the same day (for obvious reasons).
+
The NSP is used to plan schedules for workers or problems with a similar structure.  
−
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'''
+
* The '''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.''
+
This problem attempts to minimize the distance between points labeled to be in a cluster and a point designated as the center of that cluster.
  
 +
==Example==
  
−
==Examples==
+
====Travelling salesman problem====
  
−
'''Example'''
+
To demonstrate how the local search can be used to solve a practical problem, a constructed example can be found below:
  
−
'''Example'''
 
  
 +
A business man from A has departments in B, C,D and E. He plans to visit all departments and return
 +
home. His planned route ist A-B-D-C-E-A. We want to improve this route with help of a local search heuristic.
 +
 +
The distances between the places can be extracted from the tables below:
 +
 +
 +
[[Datei:Local_Seach_Tablet_1.png]]
 +
[[Datei:Local Search Solution1.JPG]]
 +
 +
A-B-D-C-E-A=1275
  
  
−
==Presentation of the problem==
 
−
....
 
  
 
==Detailed Solution Process==
 
==Detailed Solution Process==
−
~ with explanation
+
[[Datei:Solution1.png]]
 +
[[Datei:Solution2.png]]
 +
 
 +
 
 +
Explanation of the image:
 +
 
 +
The purple marked cities are those which have been exchanged. The arrows in each tablet mark the optimal solution.
 +
 
 +
Firstly a starting route has to be chosen. The chosing process can be totally random, as it does not matter in findig the correct solution.
 +
After the starting route has been chosen, an exchange of exactly 2 edges is performed (hence the name of the algorithm "2-opt method"); but it is only allowed to alter the startroute. However it is forbidden to exchange the start and end point of the route.
 +
 
 +
Then the distance of the new route has to be calculated. After repeatedly altering the startroute until every possible combination has been calculated, the optimal solution is found by looking which distance is the shortest.
 +
After that, the whole process has to be repeated with the first optimal solution as starting route. This is necessary in order to ensure that the first solution is really optimal and there is actually no better route. If a shorter route is found, then it is the new optimal solution; if not the old route stays optimal.
 +
 
 +
 
 +
"Any solution has exactly n(n-3) neighbors (for symmetric TSP: n(n-3)/2)." This formula shows how many rows the tablet can maximally have. In this case we have a route with 5 stops which equals a maximum of 10 rows 5*(5-3)=10. As seen in the tablet on top.
  
 
==Sources==
 
==Sources==

Aktuelle Version vom 2. Juli 2013, 11:51 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

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.

  • The travelling salesman problem

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

  • The boolean satisfiability problem

The boolean satifiability problem describes a situation, in which a particular list of requirements has to be met.

  • The nurse scheduling problem

The NSP is used to plan schedules for workers or problems with a similar structure.

  • The k-medoid clustering problem

This problem attempts to minimize the distance between points labeled to be in a cluster and a point designated as the center of that cluster.

Example

Travelling salesman problem

To demonstrate how the local search can be used to solve a practical problem, a constructed example can be found below:


A business man from A has departments in B, C,D and E. He plans to visit all departments and return home. His planned route ist A-B-D-C-E-A. We want to improve this route with help of a local search heuristic.

The distances between the places can be extracted from the tables below:


Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

A-B-D-C-E-A=1275


Detailed Solution Process

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden


Explanation of the image:

The purple marked cities are those which have been exchanged. The arrows in each tablet mark the optimal solution.

Firstly a starting route has to be chosen. The chosing process can be totally random, as it does not matter in findig the correct solution. After the starting route has been chosen, an exchange of exactly 2 edges is performed (hence the name of the algorithm "2-opt method"); but it is only allowed to alter the startroute. However it is forbidden to exchange the start and end point of the route.

Then the distance of the new route has to be calculated. After repeatedly altering the startroute until every possible combination has been calculated, the optimal solution is found by looking which distance is the shortest. After that, the whole process has to be repeated with the first optimal solution as starting route. This is necessary in order to ensure that the first solution is really optimal and there is actually no better route. If a shorter route is found, then it is the new optimal solution; if not the old route stays optimal.


"Any solution has exactly n(n-3) neighbors (for symmetric TSP: n(n-3)/2)." This formula shows how many rows the tablet can maximally have. In this case we have a route with 5 stops which equals a maximum of 10 rows 5*(5-3)=10. As seen in the tablet on top.

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).
Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Heuristics:_Local_search_2&oldid=6617“