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

Optimal decision trees for the algorithm selection problem: integer programming based approaches

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2021年第5期28卷 2759-2781页

作者： Vilas Boas, Matheus Guedes Santos, Haroldo Gambini de Campos Merschmann, Luiz Henrique Vanden Berghe, Greet Univ Fed Ouro Preto Dept Comp St Diogo Vasconcelos 328 BR-35400000 Ouro Preto MG Brazil Univ Fed Lavras Dept Comp Sci POB 3037 BR-37200000 Lavras MG Brazil Univ KU Leuven Comp Sci Technol Campus B-9000 Ghent Belgium

Even though it is well known that for most relevant computational problems, different algorithms may perform better on different classes of problem instances, most researchers still focus on determining a single best algorithmic configuration based on aggregate results such as the average. In this paper, we propose integer programming-based approaches to build decision trees for the algorithm selection problem. These techniques allow the automation of three crucial decisions: (a) discerning the most important problem features to determine problem classes, (b) grouping the problems into classes, and (c) selecting the best algorithm configuration for each class. To evaluate this new approach, extensive computational experiments were executed using the linear programming algorithms implemented in the COIN-OR branch-and-cut solver across a comprehensive set of instances, including all MIPLIB benchmark instances. The results exceeded our expectations. While selecting the single best parameter setting across all instances decreased the total running time by 22%, our approach decreased the total running time by 40% on average across 10-fold cross-validation experiments. These results indicate that our method generalizes quite well and does not overfit.

关键词： algorithm selection problem feature-based parameter tuning decision trees data mining integer programming variable neighborhood search COIN-OR branch and cut

来源：评论

学校读者我要写书评

暂无评论

Missing Data and Their Effect on algorithm selection for the Bin Packing problem 16th

Missing Data and Their Effect on Algorithm Selection for the...

引用

16th Mexican Conference on Pattern Recognition (MCPR)

作者： Carlos Ortiz-Bayliss, Jose Karen Garate-Escamilla, Anna Terashima-Marin, Hugo Tecnol Monterrey Sch Engn & Sci Monterrey 64849 Mexico

ISBN: (纸本)9783031628351;9783031628368

When multiple algorithms are available to solve a particular problem, deciding which to use may be challenging. Depending on the problem at hand and the available algorithms, choosing the wrong solver might represent significant performance losses. Machine learning has emerged as a paramount tool for implementing algorithm selectors. Regardless of their success in various applications, how incomplete information on the individual solvers' performance may affect the overall quality of the decisions remains unexplored. This work uses Neural Networks (multi-layer perceptron) to implement algorithm selectors for the one-dimensional bin packing problem. We explore situations involving missing values and their treatment to observe their impact on the algorithm selectors generated. Our results suggest that the algorithm selectors may be more sensitive to missing values than expected.

关键词： algorithm selection problem Bin Packing problem Missing Values Neural Networks

来源：评论

学校读者我要写书评

暂无评论

A machine learning approach for predicting the best heuristic for a large scaled Capacitated Lotsizing problem

引用

OR SPECTRUM 2025年 1-43页

作者： Kaercher, Jens Meyr, Herbert Univ Hohenheim Dept Supply Chain Management D-70593 Stuttgart Germany

For some NP-hard lotsizing problems, many different heuristics exist, but they have different solution qualities and computation times depending on the characteristics of the instance. The computation times of the individual heuristics increase significantly with the problem size, so that testing all available heuristics for large instances requires extensive time. Therefore, it is necessary to develop a method that allows a prediction of the best heuristic for the respective instance without testing all available heuristics. The Capacitated Lotsizing problem (CLSP) is chosen as the problem to be solved, since it is a fundamental model in the field of lotsizing, well researched and several different heuristics exist for it. The CLSP addresses the problem of determining lotsizes on a production line given limited capacity, product-dependent setup costs, and deterministic, dynamic demand for multiple products. The objective is to minimize setup and inventory holding costs. Two different forecasting methods are presented. One of them is a two-layer neural network called CLSP-Net. It is trained on small CLSP instances, which can be solved very fast with the considered heuristics. Due to the use of a fixed number of wisely chosen features that are relative, relevant, and computationally efficient, and which leverage problem-specific knowledge, CLSP-Net is also capable of predicting the most suitable heuristic for large instances.

关键词： algorithm selection problem Machine learning Neural network Heuristics Capacitated lotsizing problem Mixed-integer linear programming

来源：评论

学校读者我要写书评

暂无评论

Improving the state-of-the-art in the Traveling Salesman problem: An Anytime Automatic algorithm selection

引用

EXPERT SYSTEMS WITH APPLICATIONS 2022年第0期187卷 115948-115948页

作者： Huerta, Isaias I. Neira, Daniel A. Ortega, Daniel A. Varas, Vicente Godoy, Julio Asin-Acha, Roberto Univ Concepcion Fac Ingn Dept Ingn Informat & Cs Comp Concepcion Chile Univ Concepcion Fac Ingn Dept Ingn Ind Concepcion Chile

This work presents a new metaheuristic for the euclidean Traveling Salesman problem (TSP) based on an Anytime Automatic algorithm selection model using a portfolio of five state-of-the-art solvers. We introduce a new spatial representation of nodes, in the form of a matrix grid, avoiding costly calculation of features. Furthermore, we use a new compact staggered representation for the ranking of algorithms at each time step. Then, we feed inputs (matrix grid) and outputs (staggered representation) into a classifying convolutional neural network to predict the ranking of the solvers at a given time. We use the available datasets for TSP and generate new instances to augment their number, reaching 6,689 instances, distributed into training and test sets. Results show that the time required to predict the best solver is drastically reduced in comparison to previous traditional feature selection and machine learning methods. Furthermore, the prediction can be obtained at any time and, on average, the metasolver is better than running all the solvers separately on all the datasets, obtaining 79.8% accuracy.

关键词： Combinatorial optimization TSP algorithm selection problem Anytime behavior approach

来源：评论

学校读者我要写书评

暂无评论

Applying instance space analysis for metaheuristic selection to the 0-1 multidemand multidimensional knapsack problem

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 170卷

作者： Scherer, Matthew E. Hill, Raymond R. Lunday, Brian J. Cox, Bruce A. White, Edward D. Air Force Inst Technol 2950 Hobson Way Wright Patterson AFB OH 45433 USA

The empirical testing of metaheuristic solution methods for optimization applications should consider the effect of the underlying structure of the optimization problem test instances employed. This paper presents a methodology for analyzing the performance of metaheuristics applied to the 0-1 multidemand multidimensional knapsack problem (MDMKP) specifically considering problem structure. This research leverages instance space analysis (ISA) to graphically depict both the multidimensional problem structure and metaheuristic performance. A new instance generation method augments the existing set of test instances;in doing so, it introduces correlation structure into the problem and helps ensure MDMKP instance feasibility. Testing compares four metaheuristics from the literature and trains an interpretable machine learning model to select a metaheuristic for a given instance based on that problem's meta-features. The results show that the correlation structure meta-features are significant factors affecting metaheuristic performance and that a decision tree model can provide interpretable insights into the algorithm selection problem. This work demonstrates the usefulness of ISA for rigorous empirical testing to enhance understanding the performance of metaheuristics applied to the MDMKP.

关键词： problem Instance space analysis Metaheuristics algorithm selection problem

来源：评论

学校读者我要写书评

暂无评论

MPI collective algorithm selection and quadtree encoding

引用

PARALLEL COMPUTING 2007年第9期33卷 613-623页

作者： Pjesivac-Grbovic, Jelena Bosilca, George Fagg, Graham E. Angskun, Thara Dongarra, Jack J. Univ Tennessee Dept Comp Sci Innovat Comp Lab Knoxville TN 37996 USA

We explore the applicability of the quadtree encoding method to the run-time MPI collective algorithm selection problem. Measured algorithm performance data was used to construct quadtrees with different properties. The quality and performance of generated decision functions and in-memory decision systems were evaluated. Experimental data shows that in some cases, a decision function based on a quadtree structure with a mean depth of three, incurs on average as little as a 5% performance penalty. In all cases, experimental data can be fully represented with a quadtree containing a maximum of six levels. Our results indicate that quadtrees may be a feasible choice for both processing of the performance data and automatic decision function generation. (C) 2007 Elsevier B.V. All rights reserved.

关键词： MPI collective operations performance optimization algorithm selection problem quadtree encoding performance evaluation

来源：评论

学校读者我要写书评

暂无评论

algorithm portfolio based scheme for dynamic optimization problems

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS 2015年第4期8卷 667-689页

作者： Fajardo Calderin, Jenny Masegosa, Antonio D. Pelta, David A. Polytech Higher Inst Jose A Echeverria Dept Artificial Intelligence & Infrastruct & Syst Havana Cuba Univ Deusto Deusto Inst Technol Bilbao Spain Basque Fdn Sci Ikerbasque Bilbao Spain Univ Granada Dept Comp Sci & AI Res Ctr ICT CITIC UGR Granada Spain

Since their first appearance in 1997 in the prestigious journal Science, algorithm portfolios have become a popular approach to solve static problems. Nevertheless and despite that success, they have not received much attention in Dynamic Optimization problems (DOPs). In this work, we aim at showing these methods as a powerful tool to solve combinatorial DOPs. To this end, we propose a new algorithm portfolio for this type of problems that incorporates a learning scheme to select, among the metaheuristics that compose it, the most appropriate solver or solvers for each problem, configuration and search stage. This method was tested over 5 binary-coded problems (dynamic variants of OneMax, Plateau, RoyalRoad, Deceptive and Knapsack) and compared versus two reference algorithms for these problems (Adaptive Hill Climbing Memetic algorithm and Self Organized Random Immigrants Genetic algorithm). The results showed the importance of a good design of the learning scheme, the superiority of the algorithm portfolio against the isolated version of the metaheuristics that integrate it, and the competitiveness of its performance versus the reference algorithms.

关键词： learning algorithm portfolio algorithm selection problem combinatorial problems dynamic optimization problems

来源：评论

学校读者我要写书评

暂无评论

Anytime automatic algorithm selection for knapsack

引用

EXPERT SYSTEMS WITH APPLICATIONS 2020年 158卷 113613-113613页

作者： Huerta, Isaias I. Neira, Daniel A. Ortega, Daniel A. Varas, Vicente Godoy, Julio Asin-Acha, Roberto Univ Concepcion Dept Ingn Informat Edmundo Larenas 219 Concepcion Chile Univ Concepcion Dept Ingn Ind Edmundo Larenas 219 Concepcion Chile

In this paper, we present a new approach for Automatic algorithm selection. In this new procedure, we feed the predictor of the best algorithm choice with a runtime limit for the solvers. Hence, the machine learning model should consider and learn from the Anytime Behavior of the solvers, together with features characterizing each instance. For this purpose, we propose a general Framework and apply it to the Knapsack problem. Thus, we created a large and diverse dataset of 15, 000 instances, recorded the anytime behavior of 8 solvers on them and trained and tested three machine learning strategies, collecting the results for different machine learning algorithms. Our results show that, for the majority of the tuples , the solver that computes the best objective value can be predicted. We also make this data publicly available, as a challenge for the community to work in this problem and propose new and better machine learning models and solvers. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： Knapsack algorithm selection problem Machine learning techniques Anytime behaviour approach

来源：评论

学校读者我要写书评

暂无评论

Models of performance of time series forecasters

引用

NEUROCOMPUTING 2013年 122卷 375-385页

作者： Graff, Mario Jair Escalante, Hugo Cerda-Jacobo, Jaime Avalos Gonzalez, Alberto Univ Michoacana Fac Ingn Elect Div Estudios Postgrado Mexico City DF Mexico Inst Nacl Astrofis Opt & Electr Dept Comp Sci Mexico City DF Mexico

One of the first steps when approaching any machine learning task is to select, among all the available procedures, which one is the most adequate to solve a particular problem;in automated problem solving this is known as the algorithm selection problem. Of course, this problem is also present in the field of time series forecasting, there, one needs to select the forecaster that makes the most accurate predictions. Generally, this selection task is manually performed by analyzing the characteristics of the time series, thus relying on the expertise that one has on the available forecasters. In this paper, we propose an automatic procedure to choose a forecaster given a set of candidates, i.e., to solve the algorithm selection problem on this domain. To do so, we follow two paths. Firstly, we propose to model the performance of the forecasters using a linear combination of features that were previously used to assess the problem difficulty of evolutionary algorithms, together with a set of features we propose in this paper. Then, this model is used to predict the performance of the forecasters and based on these predictions the forecaster is selected. Our second approach is to treat this algorithm selection process as a classification task where the descriptors of each time series are the proposed features. To show the capabilities of our approach, we test the forecasters on the time series of the M1 and M3 time series competitions and used three different forecasters. In all the cases tested, our proposals outperform the performance of the three forecasters indicating the viability of our approach. (C) 2013 Elsevier B.V. All rights reserved.

关键词： algorithm selection problem Time series Time series features Forecasting Performance prediction

来源：评论

学校读者我要写书评

暂无评论

Wind speed forecasting using a portfolio of forecasters

引用

RENEWABLE ENERGY 2014年 68卷 550-559页

作者： Graff, Mario Pena, Rafael Medina, Aurelio Jair Escalante, Hugo Univ Michoacana Fac Ingn Elect Div Estudios Postgrad Morelia Michoacan Mexico Univ Autonoma San Luis Potosi Fac Ingn San Luis Potosi Mexico Inst Nacl Astrofis Opt & Electr Dept Comp Sci Puebla Mexico

This contribution presents the application of a portfolio of forecasters to the problem of wind speed forecasting. This portfolio is created using a single time series and it is based on a number of time series characteristics, previously proposed, and a set of novel time series features. The results show that the proposed portfolio produces accurate predictions, and, has better performance than the forecasters composing it. In addition to this, the forecast values are used to determine the power generation capacity of a wind turbine driven a permanent magnet synchronous generator. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： algorithm portfolio algorithm selection problem Time series forecasting Power generation capacity Wind turbines

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：