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

Realtime gray-box algorithm configuration using cost-sensitive classification

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2025年第1期93卷 109-130页

作者： Weiss, Dimitri Tierney, Kevin Bielefeld Univ Decis & Operat Technol Grp Univ Str 25 D-33615 Bielefeld NRW Germany

A solver's runtime and the quality of the solutions it generates are strongly influenced by its parameter settings. Finding good parameter configurations is a formidable challenge, even for fixed problem instance distributions. However, when the instance distribution can change over time, a once effective configuration may no longer provide adequate performance. Realtime algorithm configuration (RAC) offers assistance in finding high-quality configurations for such distributions by automatically adjusting the configurations it recommends based on instances seen so far. Existing RAC methods treat the solver as a black box, meaning the solver is given a configuration as input, and it outputs either a solution or runtime as an objective function for the configurator. However, analyzing intermediate output from the solver can enable configurators to avoid wasting time on poorly performing configurations. We propose a gray-box approach that utilizes intermediate output during evaluation and implement it within the RAC method Contextual Preselection with Plackett-Luce (CPPL blue). We apply cost-sensitive machine learning with pairwise comparisons to determine whether ongoing evaluations can be terminated to free resources. We compare our approach to a black-box equivalent on several experimental settings and show that our approach reduces the total solving time in several scenarios and improves solution quality in an additional scenario.

关键词： algorithm configuration Cost-sensitive learning SAT MILP CVRP 9005 9008

来源：评论

学校读者我要写书评

暂无评论

MaxSAT by improved instance-specific algorithm configuration

引用

ARTIFICIAL INTELLIGENCE 2016年 235卷 26-39页

作者： Ansotegui, Carlos Gabas, Joel Malitsky, Yuri Sellmann, Meinolf Univ Lleida Dept Comp Sci Lleida Spain IBM Watson Res Ctr Yorktown Hts NY 10598 USA

Our objective is to boost the state-of-the-art performance in MaxSAT solving. To this end, we employ the instance-specific algorithm configurator ISAC, and improve it with the latest in portfolio technology. Experimental results on SAT show that this combination marks a significant step forward in our ability to tune algorithms instance-specifically. We then apply the new methodology to a number of MaxSAT problem domains and show that the resulting solvers consistently outperform the best existing solvers on the respective problem families. In fact, the solvers presented here were independently evaluated at the 2013 and 2014 MaxSAT Evaluations where they won several categories. (C) 2016 Elsevier B.V. All rights reserved.

关键词： algorithm configuration algorithm selection MaxSAT

来源：评论

学校读者我要写书评

暂无评论

Metamodel-based dynamic algorithm configuration using artificial neural networks

引用

INTERNATIONAL JOURNAL OF GENERAL SYSTEMS 2024年第1期53卷 41-71页

作者： Dunke, Fabian Nickel, Stefan Karlsruhe Inst Technol Inst Operat Res Discrete Optimizat & Logist Karlsruhe Germany

We consider the problem of configuring algorithms dynamically by selecting algorithm parameter values adaptively. The research is motivated by the time dependency of system parameters throughout algorithm runtime in servicing systems: Depending on the customer arrival rate, switching algorithm parameters may be advisable to maintain quality of service. To this end, we develop a metamodel-based methodology for dynamic algorithm configuration: We first record algorithm performance under static system parameters. This knowledge is then translated into an artificial neural network (ANN) predicting performance for given system and algorithm parameters. The ANN finally serves as a metamodel determining optimal algorithm parameters dynamically when there is system parameter variation. Overall, the developed generic methodology for dynamic algorithm control facilitates a structured model-based approach to suitably respond to changing system conditions. The outline is adept to practical instantiation as demonstrated in two service systems where control parameters are adjusted adaptively to customer arrival rates.

关键词： algorithm configuration artificial neural network simulation metamodeling dynamic decision making

来源：评论

学校读者我要写书评

暂无评论

Automatic construction of parallel portfolios via algorithm configuration

引用

ARTIFICIAL INTELLIGENCE 2017年 244卷 272-290页

作者： Lindauer, Marius Hoos, Holger Leyton-Brown, Kevin Schaub, Torsten Univ Freiburg Freiburg Germany Univ British Columbia Vancouver BC Canada Univ Potsdam Potsdam Germany INRIA Rennes Rennes France

Since 2004, increases in computational power described by Moore's law have substantially been realized in the form of additional cores rather than through faster clock speeds. To make effective use of modern hardware when solving hard computational problems, it is therefore necessary to employ parallel solution strategies. In this work, we demonstrate how effective parallel solvers for propositional satisfiability (SAT), one of the most widely studied NP-complete problems, can be produced automatically from any existing sequential, highly parametric SAT solver. Our Automatic Construction of Parallel Portfolios (ACPP) approach uses an automatic algorithm configuration procedure to identify a set of configurations that perform well when executed in parallel. Applied to two prominent SAT solvers, Lingeling and clasp, our ACPP procedure identified 8-core solvers that significantly outperformed their sequential counterparts on a diverse set of instances from the application and hard combinatorial category of the 2012 SAT Challenge. We further extended our ACPP approach to produce parallel portfolio solvers consisting of several different solvers by combining their configuration spaces. Applied to the component solvers of the 2012 SAT Challenge gold medal winning SAT Solver pfolioUZK, our ACPP procedures produced a significantly better-performing parallel SAT solver. (C) 2016 Elsevier B.V. All rights reserved.

关键词： algorithm configuration Parallel SAT solving algorithm portfolios Programming by optimization Automated parallelization

来源：评论

学校读者我要写书评

暂无评论

A filtering method for algorithm configuration based on consistency techniques

引用

KNOWLEDGE-BASED SYSTEMS 2014年第Apr.期60卷 73-81页

作者： Araya, Ignacio Riff, Maria-Cristina Univ Tecn Federico Santa Maria Dept Informat V Reg Chile

Heuristic based algorithms are typically constructed following an iterative process in which the designer gradually introduces or modifies components or strategies whose performance is then tested by empirical evaluation on one or more sets of benchmark problems. This process often starts with some generic or broadly applicable problem solving method (e.g., metaheuristics, backtracking search), a new algorithmic idea or even an algorithm suggested by theoretical considerations. Then, through an iterative process, various combinations of components, methods and strategies are implemented/improved and tested. Even experienced designers often have to spend substantial amounts of time exploring and experimenting with different alternatives before obtaining an effective algorithm for a given problem. In this work, we are interested in assisting the designer in this task. Considering that components, methods and strategies are generally associated with parameters and parameter values, we propose a method able to detect, through a fine-tuning process, ineffective and redundant components/strategies of an algorithm. The approach is a model-free method and applies simple consistency techniques in order to discard values from the domain of the parameters. We validate our approach with two algorithms for solving SAT and MIP problems. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Parameter tuning Constraint satisfaction problems Consistency techniques algorithm configuration algorithm design

来源：评论

学校读者我要写书评

暂无评论

Boosting evolutionary algorithm configuration

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2022年第7-9期90卷 715-734页

作者： Ansotegui, Carlos Pon, Josep Sellmann, Meinolf Univ Lleida Log & Optimizat Grp LOG Lleida Spain Gen Elect Boston MA USA

algorithm configuration has emerged as an essential technology for the improvement of high-performance solvers. We present new algorithmic ideas to improve state-of-the-art solver configurators automatically by tuning. Particularly, we introduce 1. a forward-simulation method to improve parallel performance, 2. an improvement to the configuration process itself, and 3. a new technique for instance-specific solver configuration. Extensive experimental results show that the new solver configurator compares very favorably with the state-of-the-art in automatic configuration for combinatorial solvers.

关键词： Genetic algorithms algorithm configuration algorithm portfolios 68

来源：评论

学校读者我要写书评

暂无评论

Characteristic feature analysis of continuous optimization problems based on Variability Map of objective function for optimization algorithm configuration

引用

OPEN COMPUTER SCIENCE 2020年第1期10卷 97-111页

作者： Agasiev, Taleh Bauman Moscow State Tech Univ Moscow Russia

Advanced optimization algorithms with a variety of configurable parameters become increasingly difficult to apply effectively to solving optimization problems. Appropriate algorithm configuration becomes highly relevant, still remaining a computationally expensive operation. Development of machine learning methods allows to model and predict the efficiency of different solving strategies and algorithm configurations depending on properties of optimization problem to be solved. The paper suggests the Dependency Decomposition approach to reduce computational complexity of modeling the efficiency of optimization algorithm, also considering the amount of computational resources available for optimization problem solving. The approach requires development of explicit Exploratory Landscape Analysis methods to assess a variety of significant characteristic features of optimization problems. The results of feature assessment depend on the number of sample points analyzed and their location in the design space, on top of that some of methods require additional evaluations of objective function. The paper proposes new landscape analysis methods based on given points without the need of any additional objective function evaluations. An algorithm of building a so-called Full Variability Map is suggested based on informativeness criteria formulated for groups of sample points. The paper suggests Generalized Information Content method for analysis of Full Variability Map which allows to get accurate and stable estimations of objective function features. The Sectorization method of Variability Map analysis is proposed to assess characteristic features reflecting such properties of objective function that are critical for optimization algorithm efficiency. The resulting features are invariant to the scale of objective function gradients which positively affects the generalizing ability of problems classification algorithm. The procedure of the comparative study of effectiveness of

关键词： global optimization continuous optimization problem meta-optimization algorithm configuration parameter tuning dependency decomposition approach characteristic features exploratory landscape analysis variability map generalized information content sectorization method

来源：评论

学校读者我要写书评

暂无评论

Candidate Selection and Instance Ordering for Realtime algorithm configuration

引用

FUNDAMENTA INFORMATICAE 2019年第2期166卷 141-166页

作者： Fitzgerald, Tadhg O'Sullivan, Barry Univ Coll Cork Dept Comp Sci Insight Ctr Data Analyt Western Rd Cork Ireland

Many modern combinatorial solvers have a variety of parameters through which a user can customise their behaviour. algorithm configuration is the process of selecting good values for these parameters in order to improve performance. Time and again algorithm configuration has been shown to significantly improve the performance of many algorithms for solving challenging computational problems. Automated systems for tuning parameters regularly out-perform human experts, sometimes but orders of magnitude. Online algorithm configurators, such as ReACTR, are able to tune a solver online without incurring costly offline training. As such ReACTR's main focus is on runtime minimisation while solving combinatorial problems. To do this ReACTR adopts a one-pass methodology where each instance in a stream of instances to be solved is considered only as it arrives. As such ReACTR's performance is sensitive to the order in which instances arrive. It is still not understood which instance orderings positively or negatively effect the performance of ReACTR. This paper investigates the effect of instance ordering and grouping by empirically evaluating different instance orderings based on difficulty and feature values. Though the end use is generally unable to control the order in which instances arrive it is important to understand which orderings impact ReACTR's performance and to what extent. This study also has practical benefit as such orderings can occur organically. For example as business grows the problems it may encounter, such as routing or scheduling, often grow in size and difficulty. ReACTR's performance also depends strongly configuration selection procedure used. This component controls which configurations are selected to run in parallel from the internal configuration pool. This paper evaluates various ranking mechanisms and different ways of combining them to better understand how the candidate selection procedure affects realtime algorithm configuration. We show t

关键词： Constraint Satisfaction Boolean Satisfiability algorithm configuration

来源：评论

学校读者我要写书评

暂无评论

Feature Filtering for Instance-Specific algorithm configuration

Feature Filtering for Instance-Specific Algorithm Configurat...

引用

23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI)

作者： Kroer, Christian Malitsky, Yuri IT Univ Copenhagen Copenhagen Denmark Brown Univ Dept Comp Sci Providence RI USA

ISBN: (纸本)9780769545967

Instance-Specific algorithm configuration (ISAC) is a novel general technique for automatically generating and tuning algorithm portfolios. The approach has been very successful in practice, but up to now it has been committed to using all the features it was provided. However, traditional feature filtering techniques are not applicable, requiring multiple computationally expensive tuning steps during the evaluation stage. To this end, we show three new evaluation functions that use precomputed runtimes of a collection of untuned solvers to quickly evaluate subsets of features. One of our proposed functions even shows how to generate such an effective collection of solvers when only one highly parameterized solver is available. Using these new functions, we show that the number of features used by ISAC can be reduced to less than a quarter of the original number while often providing significant performance gains. We present numerical results on both SAT and CP domains.

关键词： feature selection algorithm configuration SAT CP

来源：评论

学校读者我要写书评

暂无评论

Per Instance algorithm configuration of CMA-ES with Limited Budget 17

Per Instance Algorithm Configuration of CMA-ES with Limited ...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Belkhir, Nacim Dreo, Johann Saveant, Pierre Schoenauer, Marc Inria Saclay Orsay France Thales Res & Technol Palaiseau France

ISBN: (纸本)9781450349208

Per Instance algorithm configuration (PIAC) relies on features that describe problem instances. It builds an Empirical Performance Model (EPM) from a training set made of (instance, parameter configuration) pairs together with the corresponding performance of the algorithm at hand. This paper presents a case study in the continuous black-box optimization domain, using features proposed in the literature. The target algorithm is CMA-ES, and three of its hyper-parameters. Special care is taken to the computational cost of the features. The EPM is learned on the BBOB benchmark, but tested on independent test functions gathered from the optimization *** results demonstrate that the proposed approach can outperform the default setting of CMA-ES with as few as 30 or 50 time the problem dimension additional function evaluations for feature computation.

关键词： algorithm configuration problem features empirical study numerical black box optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：