In this paper, we rely on previous work proposing a modularized version of CMA-ES, which captures several alterations to the conventional CMA-ES developed in recent years. Each alteration provides significant advantag...
详细信息
ISBN:
(纸本)9781728125473
In this paper, we rely on previous work proposing a modularized version of CMA-ES, which captures several alterations to the conventional CMA-ES developed in recent years. Each alteration provides significant advantages under certain problem properties, e.g., multi-modality, high conditioning. These distinct advancements are implemented as modules which result in 4 608 unique versions of CMA-ES. Previous findings illustrate the competitive advantage of enabling and disabling the afrorementioned modules for different optimization problems. Yet, this modular CMA-ES is lacking a method to automatically determine when the activation of specific modules is auspicious and when it is not. We propose a well-performing instance-specific algorithm configuration model which selects an (almost) optimal configuration of modules for a given problem instance. In addition, the structure of this configuration model is able to capture inter-dependencies between modules, e.g., two (or more) modules might only be advantageous in unison for some problem types, making the orchestration of modules a crucial task. This is accomplished by chaining multiple random forest classifiers together into a so-called Classifier Chain based on a set of numerical features extracted by means of Exploratory Landscape Analysis (ELA) to describe the given problem instances.
Comparing the performance of two configurations of a given algorithm plays a critical role in algorithm configuration and performance optimisation, be it automated or manual, and requires substantial computational res...
详细信息
Comparing the performance of two configurations of a given algorithm plays a critical role in algorithm configuration and performance optimisation, be it automated or manual, and requires substantial computational resources. Time is often wasted on less promising configurations but also on instances that require a long running time regardless of the configuration. Prior work has shown that by running an algorithm on carefully selected instances, the time required to accurately decide the better of two given algorithms can be significantly reduced. In this work, we explore ways to apply a similar selection process to compare two configurations of the same algorithm. We adapted four selection methods from the literature to work with the performance model used in model-based configurators and evaluated them on six benchmarks. Our experimental evaluation shows that, depending on the problem instances and their running time distribution, a decision can be reached 5 to 3000 times faster than with random sampling, the method used in current state-of-the-art configurators.
Per-instance algorithm configuration (PIAC) is an important task in which, given a base problem instance, a recommendation model indicates the best configuration to solve it. Whereas typical Automated algorithm Config...
详细信息
ISBN:
(纸本)9783031216855;9783031216862
Per-instance algorithm configuration (PIAC) is an important task in which, given a base problem instance, a recommendation model indicates the best configuration to solve it. Whereas typical Automated algorithm configuration (AAC) prescribes configurations for a fixed set of instances, in PIAC, a model is trained using problem features and past experience in solving the base problem and is tested individually on new instances. This work proposes a novel formulation for PIAC called Multi-Objective Automated algorithm configuration based on Decomposition (MOAAC/D). Unlike other PIAC approaches, it decomposes the problem space by associating different instance sets with each objective. Using a particular implementation called iMOEA/D, we show an efficient search with irace as a local search of the Multi-objective algorithm based on Decomposition (MOEA/D). Experiments on 6,480 base problem instances show that our proposal is general and performs well on flowshop, a well-studied combinatorial optimization problem with many variants addressed as real-world applications. During the training phase, iMOEA/D searches for good configurations by tuning Iterated Local Search with Iterated Greedy operators. The testing phase uses the generated Pareto front to recommend parameters for new flowshop instances. The results show that the proposed approach outperforms a random selection baseline, a generalist solution provided by irace, and is an alternative to a meta-learning-based approach. We believe the proposed MOAAC/D formulation has the potential to open up a novel research area: multi-objective tuners capable of providing specialist and generalist configurations simultaneously.
The stochastic nature of iterative optimization heuristics leads to inherently noisy performance measurements. Since these measurements are often gathered once and then used repeatedly, the number of collected samples...
详细信息
ISBN:
(纸本)9781450392372
The stochastic nature of iterative optimization heuristics leads to inherently noisy performance measurements. Since these measurements are often gathered once and then used repeatedly, the number of collected samples will have a significant impact on the reliability of algorithm comparisons. We show that care should be taken when making decisions based on limited data. Particularly, we show that the number of runs used in many benchmarking studies, e.g., the default value of 15 suggested by the COCO environment, can be insufficient to reliably rank algorithms on well-known numerical optimization benchmarks. Additionally, methods for automated algorithm configuration are sensitive to insufficient sample sizes. This may result in the configurator choosing a "lucky" but poor-performing configuration despite exploring better ones. We show that relying on mean performance values, as many configurators do, can require a large number of runs to provide accurate comparisons between the considered configurations. Common statistical tests can greatly improve the situation in most cases but not always. We show examples of performance losses of more than 20%, even when using statistical races to dynamically adjust the number of runs, as done by irace. Our results underline the importance of appropriately considering the statistical distribution of performance values.
In this paper we investigate the impact of automated configuration techniques on the ArgSemSAT solver-runner-up of the ICCMA 2015-for solving the enumeration of preferred extensions. Moreover, we introduce a fully aut...
详细信息
ISBN:
(纸本)9781614996866
In this paper we investigate the impact of automated configuration techniques on the ArgSemSAT solver-runner-up of the ICCMA 2015-for solving the enumeration of preferred extensions. Moreover, we introduce a fully automated method for varying how argumentation frameworks are represented in the input file, and evaluate how the joint configuration of frameworks and ArgSemSAT parameters can have a remarkable impact on performance. Our findings suggest that automated configuration techniques lead to improved performances in argumentation solvers, an important message for participants to the forthcoming competition.
It is well known that different solution strategies work well for different types of instances of hard combinatorial problems. As a consequence, most solvers for the propositional satisfiability problem (SAT) expose p...
详细信息
It is well known that different solution strategies work well for different types of instances of hard combinatorial problems. As a consequence, most solvers for the propositional satisfiability problem (SAT) expose parameters that allow them to be customized to a particular family of instances. In the international SAT competition series, these parameters are ignored: solvers are run using a single default parameter setting (supplied by the authors) for all benchmark instances in a given track. While this competition format rewards solvers with robust default settings, it does not reflect the situation faced by a practitioner who only cares about performance on one particular application and can invest some time into tuning solver parameters for this application. The new Configurable SAT Solver Competition (CSSC) compares solvers in this latter setting, scoring each solver by the performance it achieved after a fully automated configuration step. This article describes the CSSC in more detail, and reports the results obtained in its two instantiations so far, CSSC 2013 and 2014. (C) 2016 Elsevier B.V. All rights reserved.
Many fields of computational science advance through improvements in the algorithms used for solving key problems. These advancements are often facilitated by benchmarks and competitions that enable performance compar...
详细信息
Many fields of computational science advance through improvements in the algorithms used for solving key problems. These advancements are often facilitated by benchmarks and competitions that enable performance comparisons and rankings of solvers. Simultaneously, meta-algorithmic techniques, such as automated algorithm selection and configuration, enable performance improvements by utilizing the complementary strengths of different algorithms or configurable algorithm components. In fact, meta-algorithms have become major drivers in advancing the state of the art in solving many prominent computational problems. However, meta-algorithmic techniques are complex and difficult to use correctly, while their incorrect use may reduce their efficiency, or in extreme cases, even lead to performance losses. Here, we introduce the Sparkle platform, which aims to make meta-algorithmic techniques more accessible to nonexpert users, and to make these techniques more broadly available in the context of competitions, to further enable the assessment and advancement of the true state of the art in solving challenging computational problems. To achieve this, Sparkle implements standard protocols for algorithm selection and configuration that support easy and correct use of these techniques. Following an experiment, Sparkle generates a report containing results, problem instances, algorithms, and other relevant information, for convenient use in scientific publications.
This paper describes applications of non-parametric and parametric methods for estimating forest growing stock volume using Landsat images on the basis of data measured in the field, integrated with ancillary informat...
详细信息
This paper describes applications of non-parametric and parametric methods for estimating forest growing stock volume using Landsat images on the basis of data measured in the field, integrated with ancillary information. Several k-Nearest Neighbors (k-NN) algorithm configurations were tested in two study areas in Italy belonging to Mediterranean and Alpine ecosystems. Field data were acquired by the regional forest inventory and forest management plans, and satellite images are from Landsat 5 TM and Landsat 7 ETM+. The paper describes the data used, the methodologies adopted and the results achieved in terms of pixel level accuracy of forest growing stock volume estimates. The results show that several factors affect estimation accuracy when using the k-NN method. For the two test areas a total of 3500 different configurations of the k-NN algorithm were systematically tested by changing the number and type of spectral and ancillary input variables, type of multidimensional distance measures, number of nearest neighbors and methods for spectral feature extraction using the leave-one-out (LOO) procedure. The best k-NN configurations were then used for pixel level estimation;the accuracy was estimated with a bootstrapping procedure;and the results were compared to estimates obtained using parametric regression methods implemented on the same data set. The best k-NN growing stock volume pixel level estimates in the Alpine area have a Root Mean Square Error (RMSE) ranging between 74 and 96 m(3) ha(-1) (respectively, 22% and 28% of the mean measured value) and between 106 and 135 m(3) ha(-1) (respectively, 44% and 63% of the mean measured value) in the Mediterranean area. On the whole, the results cast a promising light on the use of non-parametric techniques for forest attribute estimation and mapping with accuracy high enough to support forest planning activities in such complex landscapes. The results of the LOO analyses also highlight the importance of a local empiri
The optimization of algorithm (hyper-)parameters is crucial for achieving peak performance across a wide range of domains, ranging from deep neural networks to solvers for hard combinatorial problems. However, the pro...
详细信息
The optimization of algorithm (hyper-)parameters is crucial for achieving peak performance across a wide range of domains, ranging from deep neural networks to solvers for hard combinatorial problems. However, the proper evaluation of new algorithm configuration (AC) procedures (or configurators) is hindered by two key hurdles. First, AC scenarios are hard to set up, including the target algorithm to be optimized and the problem instances to be solved. Second, and even more significantly, they are computationally expensive: a single configurator run involves many costly runs of the target algorithm. Here, we propose a benchmarking approach that uses surrogate scenarios, which are computationally cheap while remaining close to the original AC scenarios. These surrogate scenarios approximate the response surface corresponding to true target algorithm performance using a regression model. In our experiments, we construct and evaluate surrogate scenarios for hyperparameter optimization as well as for AC problems that involve performance optimization of solvers for hard combinatorial problems. We generalize previous work by building surrogates for AC scenarios with multiple problem instances, stochastic target algorithms and censored running time observations. We show that our surrogate scenarios capture overall important characteristics of the original AC scenarios from which they were derived, while being much easier to use and orders of magnitude cheaper to evaluate.
暂无评论