Influence of a neighborhood shape on the efficiency of continuous variable neighborhood search
DOI:
https://doi.org/10.2298/YJOR190115004DKeywords:
global optimization, continuous optimization, metaheuristic algorithms, variable neighbourhood searchAbstract
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.References
Mladenović, N., Hansen, P., Variable neighborhood search, Computers & Operations Research, 24 (1997) 1097-1100.
Hansen, P., Mladenović, N., An introduction to variable neighborhood search, Meta heuristics, Springer, Boston, MA, 1999 (433-458).
Brimberg, J., Hansen, P., Mladenović, N., Taillard, E., Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem, Operations Research, 48 (3) (2000) 444-460.
Mladenović, N., Petrović, J., Kovačević-Vujčić, V., Čangalović, M., Solving spread spectrum radar polyphase code design problem by tabu search and variable neighborhood search, European Journal of Operational Research, 151 (2003) 389-399.
Dražić, M., Kovačević-Vujčić, V., Čangalović, M., Mladenović, N., GLOB a new VNS based software for global optimization, Global optimization, Springer, Boston, MA, 2006 (135-154).
Dražić, M., Lavor, C., Maculan, N., Mladenović, N., A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule, European Journal of Operational Research, 185 (3) (2008) 1265-1273.
Mladenović, N., Dražić, M., Kovačević-Vujčić, V., Čangalović, M., General variable neighborhood search for the continuous optimization, European Journal of Operational Research, 191 (3) (2008) 753-770.
Carrizosa, E., Dražić, M., Dražić, Z., Mladenović, N., Gaussian variable neighborhood search for continuous optimization, Computers & Operations Research, 39 (9) (2012) 2206-2213.
Trefethen, L., A hundred-dollar, hundred-digit challenge, SIAM news, 35 (1) (2002) 01-02.
Audet, C., Bechard, V., Digabel, S., Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search, Journal of Global Optimization, 41 (2) (2008) 299-318.
http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar files/TestGO files/Page295.htm.
http://tracer.lcc.uma.es/problems/ackley/ackley.html.
Lavor, C., Maculan, N., A function to test methods applied to global minimization of potential energy of molecules, Numerical algorithms, 35(2) (2004) 287-300.
Haarala, M., Miettinen, K., Makela, M., New limited memory bundle method for large scale nonsmooth optimization, Optimization Methods and Software, 19 (6) (2004) 673-692.
Dražic, M., Dražic, Z., Mladenović, N., Urošević, D., Zhao, Q., Continuous variable neighbourhood search with modified Nelder-Mead for non-differentiable optimization, IMA Journal of Management Mathematics, 27 (1) (2014) 75-88.
Downloads
Published
Issue
Section
License
Copyright (c) 2020 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
