Heuristics: Representation of Search Space and Neighborhoods 2: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
Goetza (Diskussion | Beiträge) |
Goetza (Diskussion | Beiträge) |
||
| Zeile 16: | Zeile 16: | ||
Define deterministic optimization problem: <math> min \{ f(x)\mid x \in X,X \subseteq S \} </math> | Define deterministic optimization problem: <math> min \{ f(x)\mid x \in X,X \subseteq S \} </math> | ||
| − | <math>S</math>=solution space, <math>X</math>=feasible solution set, <math>x</math>= feasible solution, <math>f(x)</math>= objetive function, | + | <math>S</math> = solution space, <math>X</math> = feasible solution set, <math>x</math> = feasible solution, <math>f(x)</math> = objetive function, |
<math> N(x) </math> denotes a neighborhood of the feasible solution <math>x</math> | <math> N(x) </math> denotes a neighborhood of the feasible solution <math>x</math> | ||
Version vom 19. Juni 2013, 17:24 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 \}
= solution space, = feasible solution set, = feasible solution, = objetive function,
denotes a neighborhood of the feasible solution
solutions 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
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 see [3]
