Heuristics: Local search 1

Inhaltsverzeichnis

1 Basic Approach
2 Theory
3 Example
4 Sources

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: