Influence of a neighborhood shape on the efficiency of continuous variable neighborhood search

Abstract

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 ℓp, 1 ≤ p ≤ ∞ metric, we tested the ℓ1, ℓ2, and ℓ∞ 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, ℓ∞ ball shape of neighborhoods performed the worst, and much better efficiency was obtained with ℓ1 and ℓ2.