Heuristics: Representation of Search Space and Neighborhoods 2

1. Introduction

There are lots of Algorithms, heuristics and metaheuristics adressing search space problems. In this article we take a closer look on the variable-neighborhood-search heuristic, further shortend with "VNS". First we would like to show the common principles of heuristics and to point out the meaning of the search space and neighborhood. Then we like to present the idea of VNS and to formulate the problem and the algorithm mathematically. Finally we will show its work on a graphical example.

2. Common principles of heuristics In common, heuristics are an alternative to the "Brute-Force-Method" which solves the problem in an optimal way by computing every possible solution. Looking at complex industrial problems there are tasks which expend too much computing effort to try every possible solution. Heuristics are analytics methods to get "good" solutions while reducing the computing effort. That "good" solution does not necessarily have to be the optimal solution.

The Search Space "S" is the domain of the given task. So it is the amount of all possible solutions that satisfies all constraints.

The set "X" is the amount of all feasible solutions.

In order to improve the solution without computing every possibility one uses a local search. Using simple words it means to look at the neighborhood and the improve the solution from one neighbor to the other.

3. Basic idea of Variable Search Space heuristics

The Variable neighborhood search (VNS) is a methaheuristic based upon a systematic change of neighborhoods, aimed to solve combinatorial and global optimization problems and to find a local minimum. It does explore increasingly distant neighborhoods of the current solution and goes from this solution to the next new one but only if an improvement has been made. This assures that variables which are already at their optimal solutions are being kept and used to find neighboring solutions. Eventually this search routine will end in a local optima. To avoid this problem many extensions have been made to the original VNS heuristic, such as variable neighborhood decomposition search (VNDS) or skewed variable neighborhood search (SVNS). There are some perceptions, wich make it easier to understand how the heuristic works.

1. A local minimum is not always also a local minimum of another neighborhood structure.
2. A global minimum is a local minimum with respect to all possible neighborhoodstructures.
3. Often local minima with respect to some neighborhood structures are close to one another.

4. Mathematical formulation of the problem

Define deterministic optimization problem: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): min \{ f(x)\mid x \in X,X \subseteq S \}

$S$ = search space, $X$ = feasible solution set, $x$ = feasible solution, $f(x)$ = objetive function, $N_{k}(x)$ denotes $k^{th}$ neighborhood of the feasible solution $x$

solutions ${\bar {x}}$ are optimal if following inequation is satisfied: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f( \bar{x})\leq f(x)\forall x \in X

Often VNS-heuristics get stuck in a local minima,this problem can be shown as: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(\bar{x}) \leq f(x), \forall x \in N(\bar{x}) \cap X

5. Graphical example

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

Now, we like to give you a graphical example for a VNS algorithm. The Algorithm could be generally formulated as:

Initialization;

Select set of neighborhood structures $N_{k},k=1,...,k_{max}$ thath will be used in the search;

Find a starting solution $x$;

Select stopping condition;

Repeat the following steps untill stoppung condition is met

(1) Set Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k \leftarrow 1 ;

(2) Until $k=k_{max},$ repeat the follwing steps

(a) Shaking. Generate a point Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x^\prime

 at random from the $k^{th}$  neighborhood of  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x ,  x^\prime \in N_k(x) ; 

(b) Local search. Apply some local search method with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x^\prime

 as initial solution; denote with  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x^{ \prime\prime }
 the so obtained local optimum;

(c) Move or not. If Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x^{\prime\prime})\ge f(x)

 move there  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  ( x \leftarrow  x^{\prime\prime} ),  
and continue the search with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  N_1 ( k \leftarrow 1 );
otherwise, set Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k \leftarrow k + 1 ;

We now want to apply the general algorithm to the first step of our example.

In our example we start at our initial solution. We would search the $k=1^{st}$ neighborhood (the blue circle).

Because of finding no better solution than our starting solution, we set Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k \leftarrow k + 1

and search in the  $N_{2}$ neighborhood (red circle). Also finding no better 

solution, we set Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): k \leftarrow k + 1

and search in the  $N_{3}$ neighborhood (green circle). 

Here we find a better solution Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x^\prime , f(x^\prime) \ge f(x) . Because we have found a better solution we set Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \leftarrow x^\prime

and start the search again in the $N_{1}$ neighborhood. 

These steps will be repeated till our stopping condition is met. This could be e.g.the amount of iterations, the computing titme, getting stuck in an local minima, finding the global minima, etc.

6. External links

the links below should provide you with more detailed information on VNS and show some implementaion examples:

-more detailed information on VNS-heuristics: [1] or see [2] or see [3]

-some implementaion examples: [4] or see [5]