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

Version vom 19. Juni 2013, 17:10 Uhr

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 like to present the idea of vns, then we formulate the problem and the algorithm mathematically and show its implementation in the travelling salesman problem. We also like to point out the meaning of the search space and neighborhood.

2. 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 has 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 makes it easier to understand how the heuristics 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.

3. 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 \}

${\displaystyle S}$=solution space, ${\displaystyle X}$=feasible solution set, ${\displaystyle x}$= feasible solution, ${\displaystyle f(x)}$= objetive function, ${\displaystyle N(x)}$ denotes a neighborhood of the feasible solution ${\displaystyle x}$

solutions ${\displaystyle {\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}) \cup X

4. Graphical example

5. External links

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

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

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