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

automated algorithm Selection: Survey and Perspectives

EVOLUTIONARY COMPUTATION 2019年第1期27卷 3-45页

作者： Kerschke, Pascal Hoos, Holger H. Neumann, Frank Trautmann, Heike Univ Munster Informat Syst & Stat D-48149 Munster Germany Leiden Univ Leiden Inst Adv Comp Sci NL-2333 CA Leiden Netherlands Univ Adelaide Optimisat & Logist Adelaide SA 5005 Australia

It has long been observed that for practically any computational problem that has been intensely studied, different instances are best solved using different algorithms. This is particularly pronounced for computationally hard problems, where in most cases, no single algorithm defines the state of the art;instead, there is a set of algorithms with complementary strengths. This performance complementarity can be exploited in various ways, one of which is based on the idea of selecting, from a set of given algorithms, for each problem instance to be solved the one expected to perform best. The task of automatically selecting an algorithm from a given set is known as the per-instance algorithm selection problem and has been intensely studied over the past 15 years, leading to major improvements in the state of the art in solving a growing number of discrete combinatorial problems, including propositional satisfiability and AI planning. Per-instance algorithm selection also shows much promise for boosting performance in solving continuous and mixed discrete/continuous optimisation problems. This survey provides an overview of research in automated algorithm selection, ranging from early and seminal works to recent and promising application areas. Different from earlier work, it covers applications to discrete and continuous problems, and discusses algorithm selection in context with conceptually related approaches, such as algorithm configuration, scheduling, or portfolio selection. Since informative and cheaply computable problem instance features provide the basis for effective per-instance algorithm selection systems, we also provide an overview of such features for discrete and continuous problems. Finally, we provide perspectives on future work in the area and discuss a number of open research challenges.

关键词： automated algorithm selection automated algorithm configuration combinatorial optimisation continuous optimisation machine learning metalearning feature-based approaches exploratory landscape analysis data streams

来源：评论

学校读者我要写书评

暂无评论

Continuous optimization algorithms for tuning real and integer parameters of swarm intelligence algorithms

引用

SWARM INTELLIGENCE 2012年第1期6卷 49-75页

作者： Yuan, Zhi de Oca, Marco A. Montes Birattari, Mauro Stuetzle, Thomas Univ Libre Bruxelles CoDE IRIDIA Brussels Belgium

The performance of optimization algorithms, including those based on swarm intelligence, depends on the values assigned to their parameters. To obtain high performance, these parameters must be fine-tuned. Since many parameters can take real values or integer values from a large domain, it is often possible to treat the tuning problem as a continuous optimization problem. In this article, we study the performance of a number of prominent continuous optimization algorithms for parameter tuning using various case studies from the swarm intelligence literature. The continuous optimization algorithms that we study are enhanced to handle the stochastic nature of the tuning problem. In particular, we introduce a new post-selection mechanism that uses F-Race in the final phase of the tuning process to select the best among elite parameter configurations. We also examine the parameter space of the swarm intelligence algorithms that we consider in our study, and we show that by fine-tuning their parameters one can obtain substantial improvements over default configurations.

关键词： automated algorithm configuration Parameter tuning Continuous optimization algorithm Swarm intelligence F-Race

来源：评论

学校读者我要写书评

暂无评论

Towards Feature-Free automated algorithm Selection for Single-Objective Continuous Black-Box Optimization

Towards Feature-Free Automated Algorithm Selection for Singl...

引用

IEEE Symposium Series on Computational Intelligence (IEEE SSCI)

作者： Prager, Raphael Patrick Seiler, Moritz Vinzent Trautmann, Heike Kerschke, Pascal Univ Munster Stat & Optimizat Munster Germany Tech Univ Dresden Big Data Analyt Transportat Dresden Germany

ISBN: (纸本)9781728190488

We propose a novel method for automated algorithm selection in the domain of single-objective continuous black-box optimization. In contrast to existing methods, we use convolutional neural networks as the selection apparatus which bases its decision on a so-called 'fitness map'. This fitness map is a 2D representation of a two dimensional search space where different gray scales indicate the quality of found solutions in certain areas. Our devised approach uses a modular CMA-ES framework which offers the option to create the conventional CMA-ES, CMA-ES with the alternate step-size adaptation and many other variants proposed over the years. In total, 4 608 different configurations are possible where most configurations are of complementary nature. In this proof-of-concept work, we consider a subset of 32 possible configurations. The developed method is evaluated against an excerpt of BBOB functions and its performance is compared against baselines that are commonly used in automated algorithm selection - the best standalone algorithm (configuration) and the best obtainable sequence of configurations. While the results indicate that the use of the fitness map is not superior on every benchmark problem, it indubitably shows its merit on more hard-to-solve problems. This offers a promising perspective for generalizing to other types of optimization problems and problem domains.

关键词： Deep Learning Feature-Free automated algorithm configuration Black-Box Optimization CMA-ES

来源：评论

学校读者我要写书评

暂无评论

Golden Parameter Search Exploiting Structure to Quickly Configure Parameters in Parallel

Golden Parameter Search Exploiting Structure to Quickly Conf...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Pushak, Yasha Hoos, Holger H. Univ British Columbia Dept Comp Sci Vancouver BC Canada Leiden Univ LIACS Leiden Netherlands

ISBN: (纸本)9781450371285

automated algorithm configuration procedures such as SMAC, GGA++ and irace can often find parameter configurations that substantially improve the performance of state-of-the-art algorithms for difficult problems - e.g., a three-fold speedup in the running time required by EAX, a genetic algorithm, to find optimal solutions to a set of widely studied TSP instances. However, it is usually recommended to provide these methods with running time budgets of one or two days of wall-clock time as well as dozens of CPU cores. Most general-purpose algorithm configuration methods are based on powerful meta-heuristics that are designed for challenging and complex search landscapes;however, recent work has shown that many algorithms appear to have parameter configuration landscapes with a relatively simple structure. We introduce the golden parameter search (GPS) algorithm, an automatic configuration procedure designed to exploit this structure while optimizing each parameter semi-independently in parallel. We compare GPS to several state-of-the-art algorithm configurators and show that it often finds similar or better parameter configurations using a fraction of the computing time budget across a broad range of scenarios spanning TSP, SAT and MIP.

关键词： automated algorithm configuration Parallel algorithm configuration Parameter Turning Hyper-Parameter Optimization

来源：评论

学校读者我要写书评

暂无评论

How Much Data Is Sufficient to Learn High-Performing algorithms? Generalization Guarantees for Data-Driven algorithm Design 2021

How Much Data Is Sufficient to Learn High-Performing Algorit...

引用

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Balcan, Maria-Florina DeBlasio, Dan Dick, Travis Kingsford, Carl Sandholm, Tuomas Vitercik, Ellen Carnegie Mellon Univ Pittsburgh PA 15213 USA Univ Texas El Paso El Paso TX 79968 USA Univ Penn Philadelphia PA 19104 USA Ocean Genom Inc Pittsburgh PA USA Strateg Machine Inc Pittsburgh PA USA Strategy Robot Inc Pittsburgh PA USA Optimized Markets Inc Pittsburgh PA USA

ISBN: (纸本)9781450380539

algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit meaningful worst-case bounds, so the parameters are made available for the user to tune. Alternatively, parameters may be tuned implicitly within the proof of a worst-case guarantee. Worst-case instances, however, may be rare or nonexistent in practice. A growing body of research has demonstrated that data-driven algorithm design can lead to significant improvements in performance. This approach uses a training set of problem instances sampled from an unknown, application-specific distribution and returns a parameter setting with strong average performance on the training set. We provide a broadly applicable theory for deriving generalization guarantees that bound the difference between the algorithm's average performance over the training set and its expected performance on the unknown distribution. Our results apply no matter how the parameters are tuned, be it via an automated or manual approach. The challenge is that for many types of algorithms, performance is a volatile function of the parameters: slightly perturbing the parameters can cause a large change in behavior. Prior research (e.g., Gupta and Roughgarden, SICOMP'17;Balcan et al., COLT'17, ICML'18, EC'18) has proved generalization bounds by employing case-by-case analyses of greedy algorithms, clustering algorithms, integer programming algorithms, and selling mechanisms. We uncover a unifying structure which we use to prove extremely general guarantees, yet we recover the bounds from prior research. Our guarantees, which are tight up to logarithmic factors in the worst case, apply whenever an algorithm's performance is a piecewise-constant, -linear, or-more generally-piecewise-structured function of its parameters. Our theory also implies novel bounds for voting mechanisms and dynamic programming algorithms from computational bio

关键词： automated algorithm design data-driven algorithm design automated algorithm configuration machine learning theory computational biology mechanism design

来源：评论

学校读者我要写书评

暂无评论

Expressiveness and Robustness of Landscape Features 19

Expressiveness and Robustness of Landscape Features

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Renau, Quentin Dreo, Johann Doerr, Carola Doerr, Benjamin THALES Res & Technol Palaiseau France Sorbonne Univ CNRS Paris France Ecole Polytech Palaiseau France

ISBN: (纸本)9781450367486

Insights on characteristics of an optimization problem is highly important in order to select and configure the right algorithm. Some techniques called features are defined for analyzing the fitness landscape of a problem. Despite their successes, our understanding of which features are actually relevant for the discrimination between different optimization problems is rather weak, since in most applications the features are used in a black-box manner. Another aspect that has been ignored in the exploratory landscape analysis literature is the robustness of the feature computation against the randomness of sample points from which the feature values are estimated. Moreover, the influence of the number of sample points from which the feature values are estimated is also an aspect ignored by the literature. In this paper, we study these three aspects: the robustness against the random sampling, the influence of the number of sample points, and the expressiveness in terms of ability to discriminate problems. We perform such an analysis for 7 out of the 17 features sets covered by the flacco package. Our test bed are the 24 noiseless BBOB functions. We show that some of these features seems very well-fitted for the discrimination of the problems and quite robust whereas others lack robustness and/or expressiveness, and are therefore less suitable for an automated landscape-aware algorithm selection/configuration approach.

关键词： Exploratory Landscape Analysis Black-Box Optimization automated algorithm configuration

来源：评论

学校读者我要写书评

暂无评论

automated configuration of Negotiation Strategies 20

Automated Configuration of Negotiation Strategies

引用

Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems

作者： Bram M. Renting Holger H. Hoos Catholijn M. Jonker Delft University of Technology Delft Netherlands Leiden University Leiden Netherlands Delft University of Technology & Leiden University Delft Netherlands

ISBN: (纸本)9781450375184

Bidding and acceptance strategies have a substantial impact on the outcome of negotiations in scenarios with linear additive and nonlinear utility functions. Over the years, it has become clear that there is no single best strategy for all negotiation settings, yet many fixed strategies are still being developed. We envision a shift in the strategy design question from: What is a good strategy?, towards: What could be a good strategy? For this purpose, we developed a method leveraging automated algorithm configuration to find the best strategies for a specific set of negotiation settings. By empowering automated negotiating agents using automated algorithm configuration, we obtain a flexible negotiation agent that can be configured automatically for a rich space of opponents and negotiation *** critically assess our approach, the agent was tested in an ANAC-like bilateral automated negotiation tournament setting against past competitors. We show that our automatically configured agent outperforms all other agents, with a 5.1% increase in negotiation payoff compared to the next-best agent. We note that without our agent in the tournament, the top-ranked agent wins by a margin of only 0.01%.

关键词： automated negotiation automated algorithm configuration negotiation strategy

来源：评论

学校读者我要写书评

暂无评论

Exact stochastic constraint optimisation with applications in network analysis

引用

ARTIFICIAL INTELLIGENCE 2022年 304卷 103650-103650页

作者： Latour, Anna L. D. Babaki, Behrouz Fokkinga, Daniel Anastacio, Marie H. Hoos, Holger H. Nijssen, Siegfried Leiden Univ LIACS POB 9512 NL-2300 RA Leiden Netherlands Polytech Montreal Montreal PQ H3T 1J4 Canada Univ British Columbia Vancouver BC V6T 1Z4 Canada UCLouvain ICTEAM Pl St Barbe 2Bte L5-02-01 B-1348 Louvain La Neuve Belgium

We present an extensive study of methods for exactly solving stochastic constraint (optimisation) problems (SCPs) in network analysis. These problems are prevalent in science, governance and industry. The first method we study is generic and decomposes stochastic constraints into a multitude of smaller local constraints that are solved using a constraint programming (CP) or mixed-integer programming (MIP) solver. However, many SCPs are formulated on probability distributions with a monotonic property, meaning that adding a positive decision to a partial solution to the problem cannot cause a decrease in solution quality. The second method is specifically designed for solving global stochastic constraints on monotonic probability distributions (SCMDs) in CP. Both methods use knowledge compilation to obtain a decision diagram encoding of the relevant probability distributions, where we focus on ordered binary decision diagrams (OBDDs). We discuss theoretical advantages and disadvantages of these methods and evaluate them experimentally. We observed that global approaches to solving SCMDs outperform decomposition approaches from CP, and perform complementarily to MIPbased decomposition approaches, while scaling much more favourably with instance size. Both methods have many alternative design choices, as both knowledge compilation and constraint solvers are used in a single pipeline. To identify which configurations work best, we apply programming by optimisation. Specifically, we show how an automated algorithm configurator can be used to find optimised configurations of our pipeline. After configuration, our global SCMD solving pipeline outperforms its closest competitor (a MIPbased decomposition pipeline) on all test sets we considered by up to two orders of magnitude in terms of PAR10 scores. (c) 2021 The Author(s). Published by Elsevier B.V.

关键词： Constraint programming Probabilistic inference Stochastic constraints Ordered binary decision diagrams Monotonic probability distributions Global constraints automated algorithm configuration Probabilistic networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：