Influence of a Neighborhood Shape on the Efficiency of Continuous Variable Neighborhood Search

Milan Dražić

The efficiency of a Variable neighborhood search metaheuristic for continuous global optimization problems greatly depends on geometric shape of neighborhood structures used by the algorithm. Among the neighborhoods defined by balls in $l_p$, $1 \le p \le \infty$ metric, we tested the $l_1$, $l_2$ and $l_{\infty}$ ball shape neighborhoods, for which there exist efficient algorithms for obtaining uniformly distributed points. On many challenging high-dimensional problems, our exhaustive testings showed that, popular and the easiest for implementation, $l_{\infty}$ ball shape of neighborhoods performed the worst, and much better efficiency was obtained with $l_1$ and $l_2$.