Influence of a neighborhood shape on the efficiency of Continuous Variable Neighborhood Search

Abstract

The efficiency of Variable neighborhood search metaheuristic for continuous global optimization problems greatly depends on the geometric shape of neighborhood structures used by the algorithm. Among the neighborhoods defined by balls in `p, 1 p 1 metric, we tested the `1, `2, and `1 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, `1 ball shape of neighborhoods performed the worst, and much better efficiency was obtained with `1 and `2.