Heuristics: Local search 1
not yet finished
Inhaltsverzeichnis
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 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 to another S’ 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. 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; 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.
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(c1,c2) + dist(c3,c4)>dist(c2,c3) + dist(c1,c4)
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 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.
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.
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 (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.
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.
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 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 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 N(m²). Probably the most common operator here is probably the 2-change (or 2-opt or inversion;k=2) operator.
vorher: 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 to as k-opt.
nachher: 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 to as k-opt.
eingefügt von Ikas: For solving a the k-opt method, espacially the 2-opt, there are 2 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 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 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 departments A-E is as followed:
Detailed Solution Process
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 als Bild] Now you 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. [1.+2. & 3.+4. Zeile der Tabelle mit rot markiertem Buchstaben die getauscht haben (B&C) als Bild & danach OR WIKI 3.jpg]
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 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.
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.
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 (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.
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.
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 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. [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]
...
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
