检索结果-内蒙古大学图书馆

Anatomy of the Attraction Basins: Breaking with the Intuition

EVOLUTIONARY COMPUTATION 2019年第3期27卷 435-466页

作者： Hernando, Leticia Mendiburu, Alexander Lozano, Jose A. Univ Basque Country UPV EHU Intelligent Syst Grp Dept Comp Sci & Artificial Intelligence San Sebastian 20018 Spain BCAM Bilbao 48009 Spain

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.

关键词： permutation-based combinatorial optimization problems local optima attraction basins local search landscape visualization

来源：评论

学校读者我要写书评

暂无评论

A mathematical analysis of EDAs with distance-based exponential models

引用

MEMETIC COMPUTING 2022年第3期14卷 305-334页

作者： Unanue, Imanol Merino, Maria Lozano, Jose A. Univ Basque Country UPV EHU Dept Comp Sci & Artificial Intelligence Lardizabal Ibilbidea 1 Gipuzkoa 20018 Spain Univ Basque Country UPV EHU Dept Math Barrio Sarriena S-N Leioa 48940 Spain Basque Ctr Appl Math BCAM Alameda Mazarredo 14 Bilbao 48009 Bizkaia Spain

Estimation of Distribution Algorithms have been successfully used to solve permutation-based combinatorial optimization problems. In this case, the algorithms use probabilistic models specifically designed for codifying probability distributions over permutation spaces. One class of these probability models are distance-based exponential models, and one example of this class is the Mallows model. In spite of its practical success, the theoretical analysis of Estimation of Distribution Algorithms for permutation-based combinatorial optimization problems has not been developed as extensively as it has been for binary problems. With this motivation, this paper presents a first mathematical analysis of the convergence behavior of Estimation of Distribution Algorithms based on Mallows models. The model removes the randomness of the algorithm in order to associate a dynamical system to it. Several scenarios of increasing complexity with different fitness functions and initial probability distributions are analyzed. The obtained results show: a) the strong dependence of the final results on the initial population, and b) the possibility to converge to non-degenerate distributions even in very simple scenarios, which has not been reported before in the literature.

关键词： Estimation of Distribution Algorithms permutation-based combinatorial optimization problems Mathematical Modeling Dynamical Systems Mallows Model

来源：评论

学校读者我要写书评

暂无评论

Journey to the Center of the Linear Ordering Problem

Journey to the Center of the Linear Ordering Problem

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Hernando, Leticia Mendiburu, Alexander Lozano, Jose A. Univ Basque Country UPV EHU Leioa Spain Univ Basque Country UPV EHU Donostia San Sebastian Spain Basque Ctr Appl Math BCAM Bilbao Spain

ISBN: (纸本)9781450371285

A number of local search based algorithms have been designed to escape from the local optima, such as, iterated local search or variable neighborhood search. The neighborhood chosen for the local search as well as the escape technique play a key role in the performance of these algorithms. Of course, a specific strategy has a different effect on distinct problems or instances. In this paper, we focus on a permutation-based combinatorial optimization problem: the linear ordering problem. We provide a theoretical landscape analysis for the adjacent swap, the swap and the insert neighborhoods. By making connections to other different problems found in the Combinatorics field, we prove that there are some moves in the local optima that will necessarily return a worse or equal solution. The number of these non-better solutions that could be avoided by the escape techniques is considerably large with respect to the number of neighbors. This is a valuable information that can be included in any of those algorithms designed to escape from the local optima, increasing their efficiency.

关键词： permutation-based combinatorial optimization problems Linear Ordering Problem Local Optima Landscape Analysis

来源：评论

学校读者我要写书评

暂无评论

On the Use of Second Order Neighbors to Escape from Local Optima 23

On the Use of Second Order Neighbors to Escape from Local Op...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Torralbo, Manuel Hernando, Leticia Contreras-Torres, Ernesto Lozano, Jose A. Vicomtech Fdn BRTA San Sebastian Spain Univ Basque Country UPV EHU Leioa Spain Basque Ctr Appl Math BCAM Bilbao Spain Univ Basque Country UPV EHU San Sebastian Spain

ISBN: (纸本)9798400701191

Designing efficient local search based algorithms requires to consider the specific properties of the problems. We introduce a simple and efficient strategy, the Extended Reach, that escapes from local optima obtained from a best improvement local search and apply it to the linear ordering problem (LOP), the traveling salesperson problem (TSP) and the quadratic assignment problem (QAP). This strategy is based on two landscape properties observed in the literature. First, it considers that a local optimum is usually located in the frontier of its own attraction basin, and thus, it is enough to inspect the second order neighbors to reach a (better) solution inside an attraction basin of a better local optimum. Second, taking into account that for the LOP and specific neighborhoods it is possible to discard solutions without the need of being evaluated, we extend this result to the TSP with the 2-opt neighborhood to avoid the unnecessary evaluation of solutions. Efficient ways of evaluating the second order neighbors are also presented, based on the cost differences, reducing significantly the computation cost. Experimental results on random and benchmark instances show that our strategy, indeed, escapes from local optima despite its simplicity.

关键词： permutation-based combinatorial optimization problems EscapingNLocal Optima Second Order Neighborhood Linear Ordering Problem Travelling Salesperson Problem Quadratic Assignment Problem

来源：评论

学校读者我要写书评

暂无评论

A Mathematical Analysis of EDAs with Distance-based Exponential Models 19

A Mathematical Analysis of EDAs with Distance-based Exponent...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Unanue, Imanol Merino, Maria Lozano, Jose A. Univ Basque Country UPV EHU Donostia San Sebastian Spain Univ Basque Country UPV EHU Leioa Spain Univ Basque Country Basque Ctr Appl Math BCAM UPV EHU Leioa Spain

ISBN: (纸本)9781450367486

Estimation of Distribution Algorithms have been successfully used for solving many combinatorial optimization problems. One type of problems in which Estimation of Distribution Algorithms have presented strong competitive results are permutation-based combinatorial optimization problems. In this case, the algorithms use probabilistic models specifically designed for codifying probability distributions over permutation spaces. One class of these probability models is distance-based exponential models, and one example of this class is the Mallows model. In spite of the practical success, the theoretical analysis of Estimation of Distribution Algorithms for permutation-based combinatorial optimization problems has not been extensively developed. With this motivation, this paper presents a first mathematical analysis of the convergence behavior of Estimation of Distribution Algorithms based on the Mallows model by using an infinite population to associate a dynamical system to the algorithm. Several scenarios, with different fitness functions and initial probability distributions of increasing complexity, are analyzed obtaining unexpected results in some cases.

关键词： Estimation of Distribution Algorithm permutation-based combinatorial optimization problems Mathematical Modeling Theoretical Analysis Mallows model

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：