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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Model-Based algorithm configuration with Adaptive Capping and Prior Distributions 1

引用

19th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Bleukx, Ignace Berden, Senne Coenen, Lize Decleyre, Nicholas Guns, Tias Katholieke Univ Leuven Leuven Belgium

ISBN: (数字)9783031080111

ISBN: (纸本)9783031080111;9783031080104

Many advanced solving algorithms for constraint programming problems are highly configurable. The research area of algorithm configuration investigates ways of automatically configuring these solvers in the best manner possible. In this paper, we specifically focus on algorithm configuration in which the objective is to decrease the time it takes the solver to find an optimal solution. In this setting, adaptive capping is a popular technique which reduces the overall runtime of the search for good configurations by adaptively setting the solver's timeout to the best runtime found so far. Additionally, sequential model-based optimization (SMBO)-in which one iteratively learns a surrogate model that can predict the runtime of unseen configurations-has proven to be a successful paradigm. Unfortunately, adaptive capping and SMBO have thus far remained incompatible, as in adaptive capping, one cannot observe the true runtime of runs that time out, precluding the typical use of SMBO. To marry adaptive capping and SMBO, we instead use SMBO to model the probability that a configuration will improve on the best runtime achieved so far, for which we propose several decomposed models. These models also allow defining prior probabilities for each hyperparameter. The experimental results show that our DeCaprio method speeds up hyperparameter search compared to random search and the seminal adaptive capping approach of ParamILS.

关键词： algorithm configuration Adaptive capping Sequential model-based optimization Prior distributions

来源：评论

学校读者我要写书评

暂无评论

Instance-specific algorithm configuration via unsupervised deep graph clustering

引用

ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE 2023年第1期125卷

作者： Song, Wen Liu, Yi Cao, Zhiguang Wu, Yaoxin Li, Qiqiang Shandong Univ Inst Marine Sci & Technol Jinan Peoples R China Shandong Univ Sch Control Sci & Engn Jinan Peoples R China Singapore Management Univ Sch Comp & Informat Syst Singapore Singapore Eindhoven Univ Technol Fac Ind Engn & Innovat Sci Eindhoven Netherlands

Instance-specific algorithm configuration (AC) methods are effective in automatically generating high-quality algorithm parameters for heterogeneous NP-hard problems from multiple sources. However, existing works rely on manually designed features to describe training instances, which are simple numerical attributes and cannot fully capture structural differences. Targeting at Mixed-Integer Programming (MIP) solvers, this paper proposes a novel instances-specific AC method based on end-to-end deep graph clustering. By representing an MIP instance as a bipartite graph, a random walk algorithm is designed to extract raw features with both numerical and structural information from the instance graph. Then an auto-encoder is designed to learn dense instance embeddings unsupervisedly, which facilitates clustering heterogeneous instances into homogeneous clusters for training instance-specific configurations. Experimental results on multiple benchmarks show that the proposed method can improve the solving efficiency of CPLEX on highly heterogeneous instances, and outperform existing instance specific AC methods.

关键词： algorithm configuration Unsupervised graph embedding Mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：