Heuristics: Local search 1: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Sources)
 
(24 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
−
not yet finished
 
−
 
 
==Basic Approach==
 
==Basic Approach==
  
−
local search is a metaheuristic method for solving computationally hard 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. Local search algorithms move from solution to solution in the ''search'' space S of candidate solutions s(i) ''(the search space)''. From a starting point they apply local changes, until a solution deemed optimal is found or a time bound is elapsed. Therefore every found soloution, better than the former one gets the new startingpoint for a next iteration. ''The search space, also called solve space, contains all possible solutions of a problem. The different to the problem space is that a problem space would be solved by cutting the problem into several problems (grafic: tree; optimal solution by A*- algorithm).''
+
Local search is a metaheuristic method for solving optimization problems. The main purpose is to find a "best" soloution among a number of possible candidates through maximizing or minimizing set criteria. Local search algorithms move from solution to solution in the '''search space S''' of candidate '''solutions s(i)'''. From a starting point they apply local changes, until a solution deemed optimal is found or a time bound is elapsed. Therefore every found solution, better than the former one gets the new startingpoint for a next iteration. The search space contains all possible solutions of a problem.  
 
Local search algorithms are widely applied to problems from computer science, mathematics, operations research, engineering, and bioinformatics.
 
Local search algorithms are widely applied to problems from computer science, mathematics, operations research, engineering, and bioinformatics.
−
 
  
 
==Theory==
 
==Theory==
  
−
Local search is an iterative algorithm that moves from one solution S to another S’ according to some neighbourhood structure.
+
Local search is an iterative algorithm that moves from one solution '''s(i)''' to another '''s(j)''' according to some neighbourhood structure.
−
Most problems can be formulated in terms of search space and target in several different manners. For example, for the travelling salesman problem a solution can be a cycle and the criterion to maximize is a combination of the number of nodes and the length of the cycle. But a solution can also be a path, and being a cycle is part of the target.
+
Different problems with different aims are possible: For example, for the travelling salesman problem a solution can be a roundtrip and the criterion to maximize/minimize is a combination of the number of nodes and the length of the cycle. Also paths are imaginable soloutions or different order-restrictions on the order could be to consider. A local search algorithm starts from a candidate solution and then iteratively moves to a neighbor solution. This is only possible if a neighborhood relation is defined on the search space. According to that, one simple problem can have more than one different neighborhood defined. Typically, every candidate solution has more than one neighbor solution; to choose wether you take one soloution or an other depends only on informations about the solutions in the neighborhood of the current one, hence the name local search. Global informations about the neighborhoods further neighbours are unattended. When no improving configurations are present in the neighborhood, local search is stuck at a locally optimal point but not necessarily at a optimal soloution. This local-optima problem can be cured by repeating local search with different initial conditions and startingpoints (if allowed).
−
A local search algorithm starts from a candidate solution and then iteratively moves to a neighbor solution. This is only possible if a neighborhood relation is defined on the search space.. The same problem may have multiple different neighborhoods defined on it;
+
Another termination of local search can be based on a time bound, which is quite equal to termination through a given maximum number of iterationsteps. Local search is an anytime algorithm, what means that it can return a valid solution even if it's interrupted at any time before it ends. As a following consequence local search algorithms are approximations or incomplete algorithms, as the search may stop even if the best solution found by the algorithm is not optimal.  
−
Typically, every candidate solution has more than one neighbor solution; the choice of which one to move to is taken using only information about the solutions in the neighborhood of the current one, hence the name local search. When the choice of the neighbor solution is done by taking the one locally maximizing the criterion, the metaheuristic takes the name hill climbing. When no improving configurations are present in the neighborhood, local search is stuck at a locally optimal point ''("only local minima no optimal solution")'' This local-optima problem can be cured by using restarts (repeated local search with different initial conditions)
+
−
Termination of local search can be based on a time bound. Another common choice is to terminate when the best solution found by the algorithm has not been improved in a given number of steps. Local search is an anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends. Local search algorithms are typically approximation or incomplete algorithms, as the search may stop even if the best solution found by the algorithm is not optimal. This can happen even if termination is due to the impossibility of improving the solution, as the optimal solution can lie far from the neighborhood of the solutions crossed by the algorithms.
+
  
  
Zeile 28: Zeile 23:
 
''3. Acceptance Test:''
 
''3. Acceptance Test:''
 
Test whether to accept the move from S to S’. If the move is accepted, then S’ replaces S as the current solution;  
 
Test whether to accept the move from S to S’. If the move is accepted, then S’ replaces S as the current solution;  
−
otherwise S is retained as the current solution. ''dist(c1,c2) + dist(c3,c4)>dist(c2,c3) + dist(c1,c4)''
+
otherwise S is retained as the current solution (dist(a1,a2) + dist(a3,a4)>dist(a2,a3) + dist(a1,a4))
  
 
''4. Termination Test:''
 
''4. Termination Test:''
Zeile 39: Zeile 34:
 
''1. vertex cover problem''
 
''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.
+
In the mathematical discipline of graph theory, a vertex cover of a graph is a subset of nodes in a graph with every edge contacting at least one of these nodes. The problem is to find a minimum vertex cover, so  the target would be a solution with a minimal number of nodes.  
−
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 german: Problem des Handlungsreisenden (PdH) ''  
 
''2. travelling salesman problem (in german: Problem des Handlungsreisenden (PdH) ''  
  
−
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.
+
In the travelling salesman problem, a solution is a roundtrip containing all nodes of the graph with one node being as well starting- as endingpoint. The target is to minimize the total length of theroundtrip. It has it name throughout the praxis, as 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?  
  
 
''3. boolean satisfiability problem''
 
''3. boolean satisfiability problem''
Zeile 52: Zeile 46:
 
''4. nurse scheduling problem''
 
''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:
+
The Nurse scheduling problem (NSP) is the problem of determining a work schedule for nurses that is both reasonable and efficient. Main topic is to order shifts and holidays to nurses. A nurse has wishes that are restrictions to the given situation or problem as well as emergencies or other aunexpected events that have to planned with, in any way. The problem is described as finding a schedule that both respects the constraints of the nurses and fulfills the objectives of the hospital.
−
day shift
+
Possible constraints may be
−
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 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 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.
 
A nurse doesn't do a late night shift followed by a day shift the next day.
 +
 +
Every shedule that satisfies the constraints is feasible although it might be not optimal as there can be e.g. personal wishes that constraint each other and can´t be realized at the same time.
  
 
''5. k-medoid clustering problem''
 
''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.
+
The k-median problem is the problem of finding '''k centers''' such that the clusters formed by them are the most compact. In a given set of data points '''x''', the k centers '''c(i)''' are to be chosen that the sum of the distances from each x to the nearest ci is minimal.
−
 
+
  
 
==Example==
 
==Example==
  
−
'''k-opt method'''  
+
==='''k-opt method'''===
−
The k-opt method is a neighborhood relation ''N⊆SxS'' (search space S) 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. ''So a tour is k-optimal if it '''feature (evtl anderes wort?)''' minimal length in its k-opt-neighborhood. It exists <math>m*(m-3)</math>
+
−
possible 2-opt changes with m counted nodes (for symmetric TSP: <math>(m*(m-3))/2</math>). So the neighborhood relation has got a dimension of N(m²).'' Probably the most common operator here is probably the 2-change (or 2-opt or inversion;''k=2'') operator.
+
  
−
As an example, the neighborhood of a vertex cover is another vertex cover only differing by one node. For boolean satisfiability, the neighbors of a truth assignment are usually the truth assignments only differing from it by the evaluation of a variable
+
The k-opt method is a neighborhood relation N⊆SxS (search space S) which is based on edge-exchange operators, and probably represents the most prominent class of optimization methods for TSP.
−
local optimization with neighborhoods that involve changing up to k components of the solution is often referred to as k-opt.
+
In a k-opt-neighborhood k edges are replaced with k and then the other edge Tour is checked for improvement. So a tour is k-optimal if it features minimal length in its k-opt-neighborhood. Probably the most common operator here is probably the 2-change (or 2-opt or inversion; k=2) operator, first proposed by Croes (1958), the basic move only 2 years earlier by Flood (1956). It exists <math>m*(m-3)</math> possible 2-opt changes with m counted nodes (for symmetric TSP: <math>(m*(m-3))/2</math>). So the neighborhood relation has got a dimension of O(m²).
  
−
''For solving a the k-opt method, espacially the 2-opt, there are 2 systematic strategies:
+
As an example, the neighborhood of a vertex cover is another vertex cover only differing by one node. For boolean satisfiability, the neighbors of a truth assignment are usually the truth assignments only differing from it by the evaluation of a variable local optimization with neighborhoods that involve changing up to k components of the solution is often referred.  
−
'''lexicographical:''' Solving iterativ on base of the names of the towns. You observe all alternatives for a new tour.
+
−
'''sequential:''' You change alternately the edge-exchange. At the end of the edge-exchange you add a new edge. The end of edge-adding is the beginning of next edge-exchange.''
+
  
 +
For solving the k-opt method, espacially the 2-opt, there are two systematic strategies:
  
−
''Presentation of the problem''  
+
''lexicographical:'' Solving iterativ on base of the names of the towns. You observe all alternatives for a new tour.  
−
In our example ''a business man / salesman'' from town A ''has departments in / wants to visit the'' towns B, C, D, and E ''and returns back to town A after visiting each town once. / He wants to visit all departments and return
+
−
home.'' His planned route ist A-B-C-D-E-A.
+
−
Is this the shortest route, that covers each department and ends back at the start-department? Please determine with Local Search applying the 2-opt. '''The 2-opt means, that you are only allowed to change two departments per each iterationstep.''' The solution is ''optimal/local minima'' when the shortest roundtrip is reached. At this solution the iteration-process stops. The topic is now to calculate the lenghts of every possible route (by changing only 2 departments) and to find the shortest one ''(lexicographical strategy)''. By reason of the formel <math>m*(m-3)</math> with m=5 (A,B,C,D,E) we have <math>5*(5-3)= 10</math> possible tours.
+
−
The distance-matrix between the departments A-E is as followed:
+
  
−
[[Datei:OR WIKI 1.jpg]]
+
''sequential:'' You change alternately the edge-exchange. At the end of the edge-exchange you add a new edge. The end of edge-adding is the beginning of next edge-exchange.
  
−
First the tour A-B-C-D-E-A has got a length of X. This tour is a random choose.
 
−
''[1.+2. Zeile der Tabelle]''
 
−
Now you began with the edge-exchange: In the following graphic you can see that first we replace ''AB, CD with AC, BD [keine Ahnung ob die Buchstaben jetzt stimmen, nur als Bsp hingeschrieben]''. In the tablet this becomes noticeable if ''B and D'' change their place.
 
−
''[1.+2. & 3.+4. Zeile der Tabelle mit rot markiertem Buchstaben die getauscht haben]''
 
  
−
'''...'''
+
==='''Presentation of the problem'''===
−
[[Datei:OR WIKI 2.jpg]]
+
 +
In our example a salesman from town A wants to visit the towns B, C, D, and E. He returns back to town A after visiting each town once. His planned route ist A-B-C-D-E-A.
 +
Is this the shortest route? We determine with Local Search applying the 2-opt. The 2-opt means, that you are only allowed to change two departments per each iterationstep. The solution is local minimum when the shortest roundtrip is reached. At this solution the iteration-process stops. The topic is now to calculate the lenghts of every possible route and to find the shortest one (lexicographical strategy). By reason of the result of the formel <math>m*(m-3)</math> with m=5 (A,B,C,D,E) we have <math>5*(5-3)= 10</math> possible tours.
 +
The distance-matrix between the towns A-E is as followed:
  
−
[[Datei:OR WIKI 3.jpg]]
 
  
−
+
[[Datei:OR WIKI 1.jpg]]
−
+
−
+
−
+
  
 +
==='''Detailed Solution Process'''===
  
 +
First the tour A-B-C-D-E-A has got a length of 27. This tour is a random choose.
  
−
'''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 [kann weg oder? bei procedure bereits erwähnt!]'''
 
  
−
==Applications==
+
[[Datei:DW OR WIKI 2.jpg]]
  
−
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.
+
Now we began with the edge-exchange: In the following graphic you can see that first we replace AB, CD with AC, BD. In the tablet this becomes noticeable if B and C change their places.  
−
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 german: Problem des Handlungsreisenden (PdH)'' '''
 
  
−
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.
+
[[Datei:DW OR WIKI 3.jpg]]
  
−
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
+
[[Datei:DW OR WIKI 10.jpg]]
  
−
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:
+
In the next step we have to check for improvement. The new tour A-C-B-D-E-A has got a length of 31, so no improvement. We do our next random edge-exchange with 2-opt method. On base of our starting solution we replace now BC, DE with BD, CE. In the tablet C and D change their places.  
−
day shift
+
 
−
night shift
+
 
−
late night shift.
+
[[Datei:DW OR WIKI 4.jpg]]
  
−
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'''
+
[[Datei:DW OR WIKI 11.jpg]]
  
−
Relevant also for other related facility location problems for which local search offers the best known approximation ratios from a worst-case perspective.
+
Now we have got an improvement: The new tour (25) is shorter than our starting solution (27).
 +
Next edge-exchange is BD, DC for BC, ED. This give us no improvement and so on. On based of our starting solution we got five iterations, the shortest one is A-D-C-B-E-A (21). This tour is the base for next five steps.
  
−
==Presentation of the problem==
 
  
−
A business man from town A ''has departments in / wants to visit the'' towns B, C, D, and E ''and returns back to town A after visiting each town once. / He wants to visit all departments and return
+
[[Datei:DW OR WIKI 6.jpg]]
−
home.'' His planned route ist A-B-C-D-E-A.
+
−
Is this the shortest route, that covers each department and ends back at the start-department? Please determine with Local Search applying the two-opt. The 2-opt means, that you are only allowed to change two departments per each iterationstep. The soloution is optimal when the shortest roundtrip is reached. At this solution the iteration-process stops. The topic is now to calculate the lenghts of every possible route (by changing only 2 departments) and to find the shortest one.
+
  
−
==Detailed Solution Process==
 
  
−
First the tour A-B-C-D-E-A has got a length of X. This tour is a random choose.
+
On this way we go on until the tenth tour.
−
''[1.+2. Zeile der Tabelle]''
+
−
Now you began with the edge-exchange: In the following graphic you can see that first we replace ''AB, CD with AC, BD [keine Ahnung ob die Buchstaben jetzt stimmen, nur als Bsp hingeschrieben]. In the tablet this becomes noticeable if ,''B and D'' change their place.
+
−
''[1.+2. & 3.+4. Zeile der Tabelle mit rot markiertem Buchstaben die getauscht haben]''
+
  
−
'''...'''
 
−
[[Datei:OR WIKI 2.jpg]]
 
  
−
[[Datei:OR WIKI 3.jpg]]
+
[[Datei:DW OR WIKI 7.jpg]]
 +
 
 +
 
 +
The tours give us no improvement. So the shortest tour for our traveling salesman problem is A-D-C-B-E-A with a length of 21.
  
 
==Sources==
 
==Sources==
Zeile 166: Zeile 128:
 
:* http://en.wikipedia.org/wiki/Local_search_(optimization)
 
:* http://en.wikipedia.org/wiki/Local_search_(optimization)
 
:* http://de.wikipedia.org/wiki/K-Opt-Heuristik
 
:* http://de.wikipedia.org/wiki/K-Opt-Heuristik
 +
:* https://bisor.wiwi.uni-kl.de/orwiki/Lokale_Suche
  
 
'''Literature'''
 
'''Literature'''
 
:* Prof. Dr. Oliver Wendt: ''Operations Research Script, Summer Term 2013''
 
:* Prof. Dr. Oliver Wendt: ''Operations Research Script, Summer Term 2013''
 
:* Christian Viergutz: ''Complex Scheduling Problems, Vorlesung im SS 2009, Folien 8'', Universität Osnabrück, Institut für Informatik
 
:* Christian Viergutz: ''Complex Scheduling Problems, Vorlesung im SS 2009, Folien 8'', Universität Osnabrück, Institut für Informatik
−
:* Takafumi Matsuura, Thoru Ikeguchi, ''Artificial Neural Networks - ICANN 2008'', p. 587-596
+
:* Takafumi Matsuura, Thoru Ikeguchi: ''Artificial Neural Networks - ICANN 2008'', p. 587-596
−
:* Amanur Rahman Saiyed, ''The Traveling Salesman Problem'', Indiana State University, 11.04.2009
+
:* Amanur Rahman Saiyed: ''The Traveling Salesman Problem'', Indiana State University, 11.04.2009
 +
:* Birger Funke: ''Effiziente Lokale Suche für Vehicle Routing und Scheduling Probleme mit Ressourcenbeschränkung'', Dissertation an der Rheinisch-Westfälischen Technischen Hochschule Aachen
 +
 
 +
'''Additional Information'''
 +
:* Christian Viergutz: ''Complex Scheduling Problems, Vorlesung im SS 2009, Folien 8'', Universität Osnabrück, Institut für Informatik (http://www.informatik.uni-osnabrueck.de/kombalg/lehre/csp09/csp09_folien_08.pdf (sheet 11))

Aktuelle Version vom 1. Juli 2013, 10:59 Uhr

Basic Approach

Local search is a metaheuristic method for solving optimization problems. The main purpose is to find a "best" soloution among a number of possible candidates through maximizing or minimizing set criteria. Local search algorithms move from solution to solution in the search space S of candidate solutions s(i). From a starting point they apply local changes, until a solution deemed optimal is found or a time bound is elapsed. Therefore every found solution, better than the former one gets the new startingpoint for a next iteration. The search space contains all possible solutions of a problem. Local search algorithms are widely applied to problems from computer science, mathematics, operations research, engineering, and bioinformatics.

Theory

Local search is an iterative algorithm that moves from one solution s(i) to another s(j) according to some neighbourhood structure. Different problems with different aims are possible: For example, for the travelling salesman problem a solution can be a roundtrip and the criterion to maximize/minimize is a combination of the number of nodes and the length of the cycle. Also paths are imaginable soloutions or different order-restrictions on the order could be to consider. A local search algorithm starts from a candidate solution and then iteratively moves to a neighbor solution. This is only possible if a neighborhood relation is defined on the search space. According to that, one simple problem can have more than one different neighborhood defined. Typically, every candidate solution has more than one neighbor solution; to choose wether you take one soloution or an other depends only on informations about the solutions in the neighborhood of the current one, hence the name local search. Global informations about the neighborhoods further neighbours are unattended. When no improving configurations are present in the neighborhood, local search is stuck at a locally optimal point but not necessarily at a optimal soloution. This local-optima problem can be cured by repeating local search with different initial conditions and startingpoints (if allowed). Another termination of local search can be based on a time bound, which is quite equal to termination through a given maximum number of iterationsteps. Local search is an anytime algorithm, what means that it can return a valid solution even if it's interrupted at any time before it ends. As a following consequence local search algorithms are approximations or incomplete algorithms, as the search may stop even if the best solution found by the algorithm is not optimal.


Procedure

Local search procedure usually consists of the following four steps.

1. Initialisation: Choose an initial schedule S to be the current solution and compute the value of the objective function F(S).

2. Neighbour Generation: Select a neighbour S’ of the current solution S and compute F(S’).

3. Acceptance Test: Test whether to accept the move from S to S’. If the move is accepted, then S’ replaces S as the current solution; otherwise S is retained as the current solution (dist(a1,a2) + dist(a3,a4)>dist(a2,a3) + dist(a1,a4))

4. Termination Test: Test whether the algorithm should terminate. If it terminates, output the best solution generated; otherwise, return to the neighbour generation step.


Applications

1. vertex cover problem

In the mathematical discipline of graph theory, a vertex cover of a graph is a subset of nodes in a graph with every edge contacting at least one of these nodes. The problem is to find a minimum vertex cover, so the target would be a solution with a minimal number of nodes.

2. travelling salesman problem (in german: Problem des Handlungsreisenden (PdH)

In the travelling salesman problem, a solution is a roundtrip containing all nodes of the graph with one node being as well starting- as endingpoint. The target is to minimize the total length of theroundtrip. It has it name throughout the praxis, as 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?

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 and efficient. Main topic is to order shifts and holidays to nurses. A nurse has wishes that are restrictions to the given situation or problem as well as emergencies or other aunexpected events that have to planned with, in any way. The problem is described as finding a schedule that both respects the constraints of the nurses and fulfills the objectives of the hospital. 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.

Every shedule that satisfies the constraints is feasible although it might be not optimal as there can be e.g. personal wishes that constraint each other and can´t be realized at the same time.

5. k-medoid clustering problem

The k-median problem is the problem of finding k centers such that the clusters formed by them are the most compact. In a given set of data points x, the k centers c(i) are to be chosen that the sum of the distances from each x to the nearest ci is minimal.

Example

k-opt method

The k-opt method is a neighborhood relation N⊆SxS (search space S) which is based on edge-exchange operators, and probably represents the most prominent class of optimization methods for TSP. In a k-opt-neighborhood k edges are replaced with k and then the other edge Tour is checked for improvement. So a tour is k-optimal if it features minimal length in its k-opt-neighborhood. Probably the most common operator here is probably the 2-change (or 2-opt or inversion; k=2) operator, first proposed by Croes (1958), the basic move only 2 years earlier by Flood (1956). It exists Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): m*(m-3) 

possible 2-opt changes with m counted nodes (for symmetric TSP: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (m*(m-3))/2

). So the neighborhood relation has got a dimension of O(m²).

As an example, the neighborhood of a vertex cover is another vertex cover only differing by one node. For boolean satisfiability, the neighbors of a truth assignment are usually the truth assignments only differing from it by the evaluation of a variable local optimization with neighborhoods that involve changing up to k components of the solution is often referred.

For solving the k-opt method, espacially the 2-opt, there are two systematic strategies:

lexicographical: Solving iterativ on base of the names of the towns. You observe all alternatives for a new tour.

sequential: You change alternately the edge-exchange. At the end of the edge-exchange you add a new edge. The end of edge-adding is the beginning of next edge-exchange.


Presentation of the problem

In our example a salesman from town A wants to visit the towns B, C, D, and E. He returns back to town A after visiting each town once. His planned route ist A-B-C-D-E-A. Is this the shortest route? We determine with Local Search applying the 2-opt. The 2-opt means, that you are only allowed to change two departments per each iterationstep. The solution is local minimum when the shortest roundtrip is reached. At this solution the iteration-process stops. The topic is now to calculate the lenghts of every possible route and to find the shortest one (lexicographical strategy). By reason of the result of the formel Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): m*(m-3) 

with m=5 (A,B,C,D,E) we have Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 5*(5-3)= 10
possible tours.

The distance-matrix between the towns A-E is as followed:


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

Detailed Solution Process

First the tour A-B-C-D-E-A has got a length of 27. This tour is a random choose.


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


Now we began with the edge-exchange: In the following graphic you can see that first we replace AB, CD with AC, BD. In the tablet this becomes noticeable if B and C change their places.


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


In the next step we have to check for improvement. The new tour A-C-B-D-E-A has got a length of 31, so no improvement. We do our next random edge-exchange with 2-opt method. On base of our starting solution we replace now BC, DE with BD, CE. In the tablet C and D change their places.


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

Now we have got an improvement: The new tour (25) is shorter than our starting solution (27). Next edge-exchange is BD, DC for BC, ED. This give us no improvement and so on. On based of our starting solution we got five iterations, the shortest one is A-D-C-B-E-A (21). This tour is the base for next five steps.


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


On this way we go on until the tenth tour.


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


The tours give us no improvement. So the shortest tour for our traveling salesman problem is A-D-C-B-E-A with a length of 21.

Sources

Internetsources

Literature

  • Prof. Dr. Oliver Wendt: Operations Research Script, Summer Term 2013
  • Christian Viergutz: Complex Scheduling Problems, Vorlesung im SS 2009, Folien 8, Universität Osnabrück, Institut für Informatik
  • Takafumi Matsuura, Thoru Ikeguchi: Artificial Neural Networks - ICANN 2008, p. 587-596
  • Amanur Rahman Saiyed: The Traveling Salesman Problem, Indiana State University, 11.04.2009
  • Birger Funke: Effiziente Lokale Suche für Vehicle Routing und Scheduling Probleme mit Ressourcenbeschränkung, Dissertation an der Rheinisch-Westfälischen Technischen Hochschule Aachen

Additional Information

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Heuristics:_Local_search_1&oldid=6157“