Anatomy of the Attraction Basins: Breaking with the Intuition
Evolutionary Computation · 2019-09 · 27 (3) · 435-466
DOI: 10.1162/evco_a_00227 ↗Kurz gefasst
Fachartikel in der Zeitschrift Evolutionary Computation, 2019-09. Verfasst von Leticia Hernando und 2 weiteren Autor:innen. Beteiligte Einrichtung: Intelligent Systems Group, Department of Computer Science and Artificial Intelligence, University of the Basque Country UPV/EHU, 20018 San Sebastián,…. Hauptthemen laut MEDLINE: Algorithms. Die Arbeit wurde bisher 13-mal zitiert (Crossref) und nennt 55 Literaturangaben.
Abstract (Originalsprache)
Solving combinatorial optimization problems efficiently requires the development of algorithms that consider the specific properties of the problems. In this sense, local search algorithms are designed over a neighborhood structure that partially accounts for these properties. Considering a neighborhood, the space is usually interpreted as a natural landscape, with valleys and mountains. Under this perception, it is commonly believed that, if maximizing, the solutions located in the slopes of the same mountain belong to the same attraction basin, with the peaks of the mountains being the local optima. Unfortunately, this is a widespread erroneous visualization of a combinatorial landscape. Thus, our aim is to clarify this aspect, providing a detailed analysis of, first, the existence of plateaus where the local optima are involved, and second, the properties that define the topology of the attraction basins, picturing a reliable visualization of the landscapes. Some of the features explored in this article have never been examined before. Hence, new findings about the structure of the attraction basins are shown. The study is focused on instances of permutation-based combinatorial optimization problems considering the 2-exchange and the insert neighborhoods. As a consequence of this work, we break away from the extended belief about the anatomy of attraction basins.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Intelligent Systems Group, Department of Computer Science and Artificial Intelligence, University of the Basque Country UPV/EHU, 20018 San Sebastián, Spain leticia.hernando@ehu.eus.
- Intelligent Systems Group, Department of Computer Architecture and Technology, University of the Basque Country UPV/EHU, 20018 San Sebastián, Spain alexander.mendiburu@ehu.eus.
- Intelligent Systems Group, Department of Computer Science and Artificial Intelligence, University of the Basque Country UPV/EHU, 20018 San Sebastián, Spain Basque Center for Applied Mathematics (BCAM), 48009 Bilbao, Spa…
Zitieren
APA
Hernando, L., Mendiburu, A., & Lozano, J. A. (2019). Anatomy of the Attraction Basins: Breaking with the Intuition. Evolutionary Computation, 27(3), 435-466. https://doi.org/10.1162/evco_a_00227
Vancouver
Hernando L, Mendiburu A, Lozano JA. Anatomy of the Attraction Basins: Breaking with the Intuition. Evolutionary Computation. 2019;27(3):435-466. doi:10.1162/evco_a_00227
BibTeX
@article{Hernando2019,
author = {Hernando, Leticia and Mendiburu, Alexander and Lozano, Jose A},
title = {Anatomy of the Attraction Basins: Breaking with the Intuition},
journal = {Evolutionary Computation},
year = {2019},
volume = {27},
number = {3},
pages = {435--466},
doi = {10.1162/evco_a_00227}
}
EUVIMED