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

作者： Fellers, Justin C. University of Rhode Island

学位级别：M.S., Master of Science/Master of Surgery

The Vehicle Routing Problem (VRP) is a widely known NP-Hard operations research problem endowed with a wide range of heuristic algorithms generated from decades of global research. These heuristics provide solutions within a reasonable run time, but at some expense to optimality. The literature further suggests heuristic performance in one class of problems comes at a cost in performance to other classes. This study aimed to develop methods for selecting the best heuristic from a defined set to solve an arbitrary VRP instance. Known as the algorithm selection problem, this study implemented supervised machine learning techniques to construct prediction models based upon instance characteristics. These models were evaluated by metrics commonly found in both algorithm selection and machine learning studies. Built from a set of 23 features and a portfolio of four varied heuristics, the leading model correctly predicted the best algorithm with 79% accuracy despite the single best heuristic occurring only49% of the time. Models were constructed using a custom problem space of 5,000 VRP instances developed organically by novel methods adapted from the literature. Adequacy of the problem space, regarding its range of difficulties and sufficiency of size, was also explored. The results indicate the problem space was appropriately diverse and the prediction models, which were developed by learning algorithms using provided data, are unlikely to improve accuracy if given more data.

关键词： algorithm selection Machine learning Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Per-run algorithm selection with Warm-Starting Using Trajectory-Based Features 17th

Per-run Algorithm Selection with Warm-Starting Using Traject...

引用

17th International Conference on Parallel Problem Solving from Nature (PPSN)

作者： Kostovska, Ana Jankovic, Anja Vermetten, Diederick de Nobel, Jacob Wang, Hao Eftimov, Tome Doerr, Carola Jozef Stefan Inst Ljubljana Slovenia Jozef Stefan Int Postgrad Sch Ljubljana Slovenia Sorbonne Univ CNRS LIP6 Paris France Leiden Univ LIACS Leiden Netherlands

ISBN: (纸本)9783031147142;9783031147135

Per-instance algorithm selection seeks to recommend, for a given problem instance and a given performance criterion, one or several suitable algorithms that are expected to perform well for the particular setting. The selection is classically done offline, using openly available information about the problem instance or features that are extracted from the instance during a dedicated feature extraction step. This ignores valuable information that the algorithms accumulate during the optimization process. In this work, we propose an alternative, online algorithm selection scheme which we coin as "per-run" algorithm selection. In our approach, we start the optimization with a default algorithm, and, after a certain number of iterations, extract instance features from the observed trajectory of this initial optimizer to determine whether to switch to another optimizer. We test this approach using the CMA-ES as the default solver, and a portfolio of six different optimizers as potential algorithms to switch to. In contrast to other recent work on online per-run algorithm selection, we warm-start the second optimizer using information accumulated during the first optimization phase. We show that our approach outperforms static per-instance algorithm selection. We also compare two different feature extraction principles, based on exploratory landscape analysis and time series analysis of the internal state variables of the CMA-ES, respectively. We show that a combination of both feature sets provides the most accurate recommendations for our test cases, taken from the BBOB function suite from the COCO platform and the YABBOB suite from the Nevergrad platform.

关键词： algorithm selection Black-box optimization Exploratory landscape analysis Evolutionary computation

来源：评论

学校读者我要写书评

暂无评论

Cross-domain algorithm selection: algorithm selection across selection Hyper-heuristics

Cross-domain Algorithm Selection: Algorithm Selection across...

引用

IEEE Symposium Series on Computational Intelligence (IEEE SSCI)

作者： Misir, Mustafa Duke Kunshan Univ Div Nat & Appl Sci Kunshan Peoples R China

ISBN: (纸本)9781665487689

The present study introduces algorithm selection on selection hyper-heuristics. Hyper-heuristics are known as problem-independent methods utilized to solve different instances from varying problem domains. In the literature, there has been effective hyper-heuristic designs providing a certain level of generality in problem solving. Still, the relevant existing research indicates that there is no single hyper-heuristic which performs always the best on different problem solving scenarios. algorithm selection has been investigated essentially to address this issue, mainly for the problem-specific algorithms, by automatically identifying the (near) best algorithm(s) for each given problem instance. This paper performs algorithm selection on selection hyper-heuristics, for the first time, delivering crossdomain algorithm selection. For this purpose, a suite of problemindependent features is initially introduced. Then, algorithm selection is examined across 9 single-objective combinatorial optimization problems with 6 online selection hyper-heuristics. The experimental results carried out on these problems indicated that algorithm selection is effective for choosing hyper-heuristics while offering improved generality and robustness.

关键词： algorithm selection selection hyper-heuristics combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Improving Nevergrad's algorithm selection Wizard NGOpt Through Automated algorithm Configuration 17th

Improving Nevergrad's Algorithm Selection Wizard NGOpt Throu...

引用

17th International Conference on Parallel Problem Solving from Nature (PPSN)

作者： Trajanov, Risto Nikolikj, Ana Cenikj, Gjorgjina Teytaud, Fabien Videau, Mathurin Teytaud, Olivier Eftimov, Tome Lopez-Ibanez, Manuel Doerr, Carola Fac Comp Sci & Engn Skopje North Macedonia Jozef Stefan Inst Ljubljana Slovenia Jozef Stefan Int Postgrad Sch Ljubljana Slovenia Univ Littoral Cote dOpale Dunkerque France Facebook AI Res Paris France Univ Malaga ITIS Software Malaga Spain Sorbonne Univ LIP6 CNRS Paris France

ISBN: (纸本)9783031147142;9783031147135

algorithm selection wizards are effective and versatile tools that automatically select an optimization algorithm given high-level information about the problem and available computational resources, such as number and type of decision variables, maximal number of evaluations, possibility to parallelize evaluations, etc. State-of-the-art algorithm selection wizards are complex and difficult to improve. We propose in this work the use of automated configuration methods for improving their performance by finding better configurations of the algorithms that compose them. In particular, we use elitist iterated racing (irace) to find CMA configurations for specific artificial benchmarks that replace the hand-crafted CMA configurations currently used in the NGOpt wizard provided by the Nevergrad platform. We discuss in detail the setup of irace for the purpose of generating configurations that work well over the diverse set of problem instances within each benchmark. Our approach improves the performance of the NGOpt wizard, even on benchmark suites that were not part of the tuning by irace.

关键词： algorithm configuration algorithm selection Black-box optimization Evolutionary computation

来源：评论

学校读者我要写书评

暂无评论

algorithm selection for software validation based on graph kernels

引用

AUTOMATED SOFTWARE ENGINEERING 2020年第1-2期27卷 153-186页

作者： Richter, Cedric Huellermeier, Eyke Jakobs, Marie-Christine Wehrheim, Heike Paderborn Univ Paderborn Germany Tech Univ Darmstadt Dept Comp Sci Darmstadt Germany

algorithm selection is the task of choosing an algorithm from a given set of candidate algorithms when faced with a particular problem instance. algorithm selection via machine learning (ML) has recently been successfully applied for various problem classes, including computationally hard problems such as SAT. In this paper, we study algorithm selection for software validation, i.e., the task of choosing a software validation tool for a given validation instance. A validation instance consists of a program plus properties to be checked on it. The application of machine learning techniques to this task first of all requires an appropriate representation of software. To this end, we propose a dedicated kernel function, which compares two programs in terms of their similarity, thus making the algorithm selection task amenable to kernel-based machine learning methods. Our kernel operates on a graph representation of source code mixing elements of control-flow and program-dependence graphs with abstract syntax trees. Thus, given two such representations as input, the kernel function yields a real-valued score that can be interpreted as a degree of similarity. We experimentally evaluate our kernel in two learning scenarios, namely a classification and a ranking problem: (1) selecting between a verification and a testing tool for bug finding (i.e., property violation), and (2) ranking several verification tools, from presumably best to worst, for property proving. The evaluation, which is based on data sets from the annual software verification competition SV-COMP, demonstrates our kernel to generalize well and to achieve rather high prediction accuracy, both for the classification and the ranking task.

关键词： algorithm selection Software validation Machine learning Graph kernels Verification Testing

来源：评论

学校读者我要写书评

暂无评论

Machine learning-based algorithm selection for irregular three-dimensional packing in additive manufacturing

引用

EXPERT SYSTEMS WITH APPLICATIONS 2025年 287卷

作者： de Araujo, Luiz Jonata Pires Ozcan, Ender Atkin, Jason A. D. Baumers, Martin Drake, John H. Univ Lincoln Sch Comp Sci Machine Learning Grp Lincoln England Univ Nottingham Sch Comp Sci Computat Optimisat & Learning Lab Nottingham England Univ Nottingham Fac Engn Ctr Addit Mfg Nottingham England Univ Leicester Sch Comp & Math Sci Leicester England

In additive manufacturing (AM), a common problem is the efficient arrangement of arbitrary three-dimensional objects, subject to geometric constraints. This can be mapped to three-dimensional irregular packing (3DIP) problems, which have been systematically addressed by many academics and practitioners. This study demonstrates the utilisation of machine learning for algorithm selection to find efficient layout configurations during the design stage of the AM process. The choice of the most suitable approach to use, typically a packing algorithm, is not trivial, and depends on the non-obvious relationship between the characteristics of the instance in hand and the portfolio of algorithms available. The matching between problem features and algorithm performance forms the basis of the well-known algorithm selection problem. This study introduces the first empirical investigation of algorithm selection for 3DIP problems, conducting extensive experiments with hundreds of combinations of well-known supervised machine learning classifiers and different parameter settings to identify an initial state-of-the-art for this problem. We generate a comprehensive dataset, labelled with the performance of two of the most popular 3DIP algorithms, and analyse the features which can be used to support decision making when selecting a method to solve a 3DIP instance. Our results show that machine learning-based algorithm selection methods are able to outperform the results obtained by the individual constituent packing algorithms applied independently, with the best algorithm selection method obtaining a 1.48% higher average build volume utilisation over the 2000 problem instances tested.

关键词： Heuristics algorithm selection Machine learning Additive manufacturing Packing

来源：评论

学校读者我要写书评

暂无评论

Data-driven algorithm selection and tuning in optimization and signal processing

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2021年第7期89卷 711-735页

作者： De Loera, Jesus A. Haddock, Jamie Ma, Anna Needell, Deanna Univ Calif Davis Davis CA 95616 USA Univ Calif Los Angeles Los Angeles CA 90095 USA Univ Calif Irvine Irvine CA USA

Machine learning algorithms typically rely on optimization subroutines and are well known to provide very effective outcomes for many types of problems. Here, we flip the reliance and ask the reverse question: can machine learning algorithms lead to more effective outcomes for optimization problems? Our goal is to train machine learning methods to automatically improve the performance of optimization and signal processing algorithms. As a proof of concept, we use our approach to improve two popular data processing subroutines in data science: stochastic gradient descent and greedy methods in compressed sensing. We provide experimental results that demonstrate the answer is "yes", machine learning algorithms do lead to more effective outcomes for optimization problems, and show the future potential for this research direction. In addition to our experimental work, we prove relevant Probably Approximately Correct (PAC) learning theorems for our problems of interest. More precisely, we show that there exists a learning algorithm that, with high probability, will select the algorithm that optimizes the average performance on an input set of problem instances with a given distribution.

关键词： Automated machine learning Compressed sensing Neural networks algorithm selection Hyperparameter tuning

来源：评论

学校读者我要写书评

暂无评论

algorithm selection for solving educational timetabling problems

引用

EXPERT SYSTEMS WITH APPLICATIONS 2021年 174卷

作者： de la Rosa-Rivera, Felipe Nunez-Varela, Jose I. Ortiz-Bayliss, Jose C. Terashima-Marin, Hugo Univ Autonoma San Luis Potosi Fac Ingn San Luis Potosi 78290 San Luis Potosi Mexico Tecnol Monterrey Escuela Ingn & Ciencias Nuevo Leon 64849 Mexico

In this paper, we present the construction process of a per-instance algorithm selection model to improve the initial solutions of Curriculum-Based Course Timetabling (CB-CTT) instances. Following the meta-learning framework, we apply a hybrid approach that integrates the predictions of a classifier and linear regression models to estimate and compare the performance of four meta-heuristics across different problem sub-spaces described by seven types of features. Rather than reporting the average accuracy, we evaluate the model using the closed SBS-VBS gap, a performance measure used at international algorithm selection competitions. The experimental results show that our model obtains a performance of 0.386, within the range obtained by perinstance algorithm selection models in other combinatorial problems. As a result of the process, we conclude that the performance variation between the meta-heuristics has a significant role in the effectiveness of the model. Therefore, we introduce statistical analyses to evaluate this factor within per-instance algorithm portfolios.

关键词： algorithm selection Meta-learning Educational timetabling Meta-heuristic

来源：评论

学校读者我要写书评

暂无评论

algorithm selection of Anytime algorithms

Algorithm Selection of Anytime Algorithms

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Jesus, Alexandre D. Liefooghe, Arnaud Derbel, Bilel Paquete, Luis Univ Lille INRIA Cent Lille CNRSUMR 9189 CRIStAL F-59000 Lille France Univ Tokyo JFLI CNRS IRL 3527 Tokyo Japan Univ Coimbra CISUC DEI Coimbra Portugal

ISBN: (纸本)9781450371285

Anytime algorithms for optimization problems are of particular interest since they allow to trade off execution time with result quality. However, the selection of the best anytime algorithm for a given problem instance has been focused on a particular budget for execution time or particular target result quality. Moreover, it is often assumed that these anytime preferences are known when developing or training the algorithm selection methodology. In this work, we study the algorithm selection problem in a context where the decision maker's anytime preferences are defined by a general utility function, and only known at the time of selection. To this end, we first examine how to measure the performance of an anytime algorithm with respect to this utility function. Then, we discuss approaches for the development of selection methodologies that receive a utility function as an argument at the time of selection. Then, to illustrate one of the discussed approaches, we present a preliminary study on the selection between an exact and a heuristic algorithm for a bi-objective knapsack problem. The results show that the proposed methodology has an accuracy greater than 96% in the selected scenarios, but we identify room for improvement.

关键词： algorithm selection Anytime algorithms Anytime Performance Measure

来源：评论

学校读者我要写书评

暂无评论

Adaptive local landscape feature vector for problem classification and algorithm selection

引用

APPLIED SOFT COMPUTING 2022年 131卷

作者： Li, Yaxin Liang, Jing Yu, Kunjie Chen, Ke Guo, Yinan Yue, Caitong Zhang, Leiyu Zhengzhou Univ Sch Elect Engn Zhengzhou 450001 Peoples R China China Univ Min & Technol Beijing 100084 Peoples R China

Fitness landscape analysis is a data-driven technique to study the relationship between problem characteristics and algorithm performance by characterizing the landscape features in the search space of an optimization problem. However, most of the existing landscape features still face poor in classifying the problems and low accuracy in selecting the most appropriate algorithm for a given problem. In this study, an adaptive local landscape feature vector (ALLFV) is proposed for problem classification and algorithm selection. Specifically, an adaptive discretization scheme is designed to calculate adaptive related parameters and construct the sequence between the fitness values of the search point and its nearest neighbors. By considering the frequencies of the same sequence values, the spatial structural information for the fitness landscape is computed as a feature vector according to the feature vector calculation mechanism. The experimental results tested on various problems demonstrate the excellence of ALLFV in terms of accuracy, stability, and computational cost. Moreover, ALLFV has shown superior practicality and reliability in the application of algorithm selection for numerical optimization problems. Consequently, ALLFV is well suited as an alternative for problem classification, as well as algorithm selection under excessive candidate optimization algorithms and limited prior knowledge of problems.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Continuous optimization Population-based algorithm Fitness landscape Problem classification algorithm selection

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：