Heuristics: Representation of Search Space and Neighborhoods 1: Unterschied zwischen den Versionen

Version vom 26. Juni 2013, 17:43 Uhr

Datei:Https://bisor.wiwi.uni-kl.de/orwiki/images/f/f2/919361 589381654429546 1413982397 o.jpg Medium:https://bisor.wiwi.uni-kl.de/orwiki/images/f/f2/919361_589381654429546_1413982397_o.jpg [1] [[2]]

Heuristics: Representation of Search Space and Neighborhoods

Search Problems in General

The goal of a search problem is not to minimize/maximize an objective function (in contrary to optimization problems) but rather to find the best solution which belongs to the minimized/maximized objective function. Search spaces are defined by the following: - Search Space S: All nodes which have to be travelled to. - Set of valid transition operators: Function which describes the valid sub-solutions for the following steps. - Initial state from set S: The starting point from which the problem begins to unfold. - Subset of goal states in S: Describes the boundaries of a valid solution.

Search Space: There are multiple definitions of the Search Space. You can divide it into infinite and finite search spaces and in solution and problem spaces.

The finite search space

Though we will not look further into, one can use algorithms to find the best solution if one has a finite search space. Heuristics would work also, but as algorithms can deliver better solutions it would not be efficient to use heuristics.

The infinite search space

If we would use algorithms in infinite search spaces, they would not terminate, as there are infinite possibilites to form a solution. As heuristics do not compute every last possibility but rather tries to narrow down the good solutions, we use heuristics to handle with infinite search spaces.

The solution space

In the solution space, the objective function defines a preference order over the solutions shown. There are already potential solutions ( e.g. valid tours of a TSP) which are resembled by the nodes of the graph. The edges between the nodes visualize the transition from a given solution to a new (neighboring) solution.

[ Insert random pic here ] As you can see, the problem space can be portrayed as a non-directed graph.

The problem space

In the problem space the nodes resemble the problems and sub-problems. The root of the tree is the initial problem while the interim nodes are the subproblems. The leaves represent the solutions. The edges are the decomposition of a problem into a simpler sub-problem.

[ Insert second random pic here ] As you can see, the problem space can be portrayed as a spanning tree.

Neighborhoods in General (Mathematically)

In direceted graphs: Let G=(V,R,α,ω) be the directed graph with the functions α:R→ V & ω:R→V which define starting and end node Let v∈V be a node of G, then you could define: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 〖δ^+〗_G (v)≔{r∈R ┤| α(r)=v}

set of outgoing arcs of v

〖δ^-〗_G (v)≔{r∈R ┤| ω(r)=v} set of incoming arcs of v 〖N^+〗_G (v)≔{ω(r)┤|r∈〖δ^+〗_G (v)} set of successors of v 〖N^-〗_G (v)≔{α(r)┤|r∈〖δ^-〗_G (v)} set of predecessors of v Two nodes u,v ∈V are called adjacent also known as neighbored if there exists an arc with α(r)=u & ω(r)=v or α(r)=v & ω(r)=u. Therefore you could declare the Neighbordhood of v as N(v) ∶= 〖N^+〗_G (v)+ 〖N^-〗_G (v).

In undirected graphs: Let G=(V,E,γ)bet the undirected graph with the function γ:E→V×V which defines the two end nodes of the edge Two nodes u,v ∈V are called adjacent also known as neighbored if there exists an edge with γ(e)={u,v}. Therefore you could declare the Neighbordhood of v as N(v) ∶={u∈V┤| γ(e)={u,v}}.

Summed up: Two nodes are neighbored if there is an arc respectively an edge which connects both nodes. If you want the neighborhood of a set of nodes you take a look at the neighborhoods of single nodes and sum them up.

Heuristics in reference to Search Space and Neighborhoods

Opening and improving procedures

Opening procedures construct a feasible solution with the help from heuristics. Improving procedures take these feasible solutions and try to further improve them.

A few examples for opening procedures: - Nearest Neighbor - Double-sided nearest Neighbor - K-Nearest Neighbor - Nearest Addition - Nearest Insert - Cheapest Insert - Farthest Insert

A few examples for improving procedures:

- 2-Opt - 3-Opt - R-Opt - 2-Nodes-Opt

Nearest-Neighbor Algorithm Let G=(V,E,γ) be the undirected and weigthed graph and T∶={marked nodes} Set T={starting node} Regarding the Neighborhood of the nodes of T : Chose the edge e={u,v} with a minimum of weight from v ∈V\T to u∈T the node you have chosen least Add v to T Repeat step (2) and (3) until T={all nodes} Take the edge which connects the starting node with the last node you have chosen