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

Version vom 29. Juni 2013, 15:56 Uhr

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: See below.
• 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 Spaces

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

Finite Search Spaces

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.

Infinite Search Spaces

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.

Solution Spaces

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.

As you can see below, the problem space can be portrayed as a non-directed graph.

Problem Spaces

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.

As you can see below, the problem space can be portrayed as a spanning tree.

Neighborhoods in General (Mathematically)

In directed Graphs

Let Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): G= \left ( V, R, \alpha, \omega \right )

be the directed graph 

with the functions Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \alpha: R \rightarrow V

and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \omega: R \rightarrow V
which define starting and end node

Let Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v \in V

be a node of ${\displaystyle G}$, then you could define:

• Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \delta_{G}^{+}(v) = \left \{ r \in R \mid \alpha(r) = v \right \}

set of outgoing arcs of ${\displaystyle v}$

• Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \delta_{G}^{-}(v) = \left \{ r \in R \mid \omega(r) = v \right \}

set of incoming arcs of ${\displaystyle v}$

• Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): N_{G}^{+}(v) = \left \{ \omega(r)\mid r \in \delta_{G}^{+}(v) \right \}

set of successors of ${\displaystyle v}$

• Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): N_{G}^{-}(v) = \left \{ \alpha(r)\mid r \in \delta_{G}^{-}(v) \right \}

set of predecessors of ${\displaystyle v}$

Two nodes Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u,v \in V

are called adjacent also known as neighbored if there exists an arc with ${\displaystyle \alpha (r)=u}$ and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \omega(r)=v
or ${\displaystyle \alpha (r)=v}$ and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \omega(r)=u

. Therefore you could declare the Neighbordhood of ${\displaystyle v}$ as Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): N(v) = N_{G}^{+}(v) + N_{G}^{-}(v)

In undirected Graphs

Let ${\displaystyle G=(V,E,\gamma )}$ bet the undirected graph with the function Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \gamma : E \rightarrow V * V

which defines the two end nodes of the edge

Two nodes Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u,v \in V

are called adjacent also known as neighbored if there exists an edge with ${\displaystyle \gamma (e)=\left\{u,v\right\}}$.

Therefore you could declare the Neighbordhood of ${\displaystyle v}$ as Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): N(v) = \{ u \in V \mid \gamma(e) = \{ u, v \}\} .

Conclusion

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
• 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

The Nearest-Neighbor-Algorithm

In General

Let ${\displaystyle G=(V,E,\gamma )}$ be the undirected and weigthed graph and ${\displaystyle T=\{marked}$ ${\displaystyle nodes\}}$

1. Set ${\displaystyle T=\{starting}$ ${\displaystyle node\}}$
2. Regarding the Neighborhood of the nodes of T: Chose the edge ${\displaystyle e=\{u,v\}}$ with a minimum of weight from Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): v \in V \setminus T

to Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): u \in T
the node you have chosen least

1. Add ${\displaystyle v}$ to ${\displaystyle T}$
2. Repeat step (2) and (3) until ${\displaystyle T=\{all}$ ${\displaystyle nodes\}}$
3. Take the edge which connects the starting node with the last node you have chosen

Example

The Search Problem in reference to the example

• Search Space S: All nodes {A,B,C,D,E,F} - therefore it is a finite Problem Space
• Set of valid transition operators: Take the nearest neighbor of the current node, which has not been visited yet. Otherwise if all nodes have been visited, go back to the starting node E.
• Initial state from set S: E
• Subset of goal states in S: You have a round trip {E,C,A,B,D,F,E} through all nodes.

Initial state

Here we have a classic (strongly simplified) Traveling Salesman Problem which we want to solve or rather which we want to simplify by using the nearest neighbor heuristic. As the nearest neighbor heuristic is just an opening procedure, we will not get a particularly good value of the objective function and therefore no particularly good travelling route itself. But the solution we are going to find will be a more or less good foundation from which one could further improve the solution by using improving procedures. There are no weights on the edges between the nodes shown yet despite them existing already.

initial situation

Iteration steps

Here, we randomly pick on of the nodes (in this case node E) to be our starting node from which we will iterate further. The edges from E to any other node is now presented by the lines and the weights are shown as numbers above them. As you can see, the weights differ from edge to edge and because we want to find a preferably short route through all the edges we choose the edge with the smalles weight from E to another node. We are confronted by a special case of the nearest neighbor heuristic: Two edges share the smallest weight. As the algorithm is not particularly foreshadowing we can now choose randomly between the two smallest edges.

after choosing the first node

We chose node C and are now confronted by new edges between C and all other nodes we have not been to yet. The shortest route beginning from C would now be to A.

iteration 2

Iterate the last steps:

iteration 3	iteration 4
iteration 5	iteration 6

This goes on until we reach the final node that has not been visited yet, in this case node F. Now, as we have a Travelling Salesman Problem, we just need to close the cycle by connecting the last node with the start node.

final solution

Summary

With this, the algorithm from the nearest neighbor heuristic has ended and we found an opening travelling route from which we can further improve our route. The last step would now be the accumulation of the weights on the travelled edges and we got the value of our route.

In this case: 2+2+3+5+1+6 = 19

The solution we want to present is: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): E\rightarrow C \rightarrow A \rightarrow B \rightarrow D \rightarrow F\rightarrow E

Sources

Scripts:

• Operations Research - Prof. Dr. Oliver Wendt (SS 2013)
• Introduction to Network Optimization - Clemens Thielen (SS 2013)

Books:

• Optimierung, Operations Research, Spieltheorie - Karl Heinz Borgwardt
• Lineare Optimierung und Netzwerkoptimierung - Horst W. Hamacher und Kathrin Klamroth
• Einführung in Operations Research - W. Domschke und A. Drexl

Internet:

• Wikipedia-Entry "Repräsentation des Suchraums"
• Wikipedia-Entry "Suchproblem"
• Wikipedia-Entry "Suchraum"
• Wikipedia-Entry "Suchverfahren"
• Wikipedia-Entry "Nearest-Neighbor-Heuristik"
• Wikipedia-Entry "TSP"