Intelligent Systems Group, Department of Computer Science and Artificial Intelligence, University of the Basque Country UPV/EHU, 20018 San Sebastián, Spain
Intelligent Systems Group, Department of Computer Architecture and Technology, University of the Basque Country UPV/EHU, 20018 San Sebastián, Spain
Evol Comput. 2019 Fall;27(3):435-466. doi: 10.1162/evco_a_00227. Epub 2018 May 22.
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.
有效地解决组合优化问题需要开发考虑问题特定属性的算法。从这个意义上说，局部搜索算法是在部分考虑这些属性的邻域结构上设计的。考虑到一个邻域，空间通常被解释为一个自然景观，有山谷和山脉。在这种观念下，人们普遍认为，如果是最大化问题，位于同一山脉的斜坡上的解属于同一个吸引盆地，而山峰则是局部最优解。不幸的是，这是对组合景观的一种普遍错误的可视化。因此，我们的目的是澄清这一方面，首先详细分析涉及高原的局部最优解的存在，其次是定义吸引盆地拓扑结构的属性，以可靠地可视化景观。本文探讨的一些特征以前从未被研究过。因此，展示了关于吸引盆地结构的新发现。这项研究集中在基于排列的组合优化问题的实例上，考虑了 2-交换和插入邻域。这项工作的结果是，我们打破了关于吸引盆地解剖结构的扩展信念。
