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.
The methods used to define functional regions for public statistics and policy purposes need to establish several parameter values. This is typically achieved using expert knowledge based on qualitative judgements and...
详细信息
The methods used to define functional regions for public statistics and policy purposes need to establish several parameter values. This is typically achieved using expert knowledge based on qualitative judgements and lengthy consultations with local stakeholders. We propose to support this process by using an optimization algorithm to calibrate any regionalization method by identifying the parameter values that produce the best regionalization for a given quantitative indicator. The approach is exemplified by using a grid search and a genetic algorithm to configure the official methods employed in the UK and Sweden for the definition of their respective official concepts of local labour markets.
algorithms in robotics typically tend to expose several parameters for the user to configure. This allows both reusability and fine tuning of the algorithm to a particular setup, but at the expense of significant effo...
详细信息
ISBN:
(纸本)9781509062348
algorithms in robotics typically tend to expose several parameters for the user to configure. This allows both reusability and fine tuning of the algorithm to a particular setup, but at the expense of significant effort in tuning, since this task is typically done manually. However, recent results in parameter optimization have shown to be quite successful, namely in automatic configuration of boolean satisfiability problem solvers, contributing to a significant increase in scalability. In this paper we address the applicability of these methods to the area of mobile robot localization. In particular, we applied a sequential model-based optimization method to the automatic parameter tuning of the well-known Adaptive Monte Carlo Localization algorithm. Our results show a statistically significant improvement over the default algorithm values. We also contribute with an open source experimental setup, based on the popular Robot Operating System ROS, which can be easily adapted to other algorithms.
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 ...
详细信息
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.
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.
We consider a multi-neighborhood local search framework with a large number of possible neighborhoods. Each neighborhood is accompanied by a weight value which represents the probability of being chosen at each iterat...
详细信息
ISBN:
(纸本)9783319503493;9783319503486
We consider a multi-neighborhood local search framework with a large number of possible neighborhoods. Each neighborhood is accompanied by a weight value which represents the probability of being chosen at each iteration. These weights are fixed before the algorithm runs, and can be tuned by off-the-shelf off-line automated algorithm configuration tools (e.g., SMAC). However, the large number of parameters might deteriorate the tuning tool's efficiency, especially in our case where each run of the algorithm is not computationally cheap, even when the number of parameters has been reduced by some intuition. In this work, we propose a systematic method to characterize each neighborhood's behaviours, representing them as a feature vector, and using cluster analysis to form similar groups of neighborhoods. The novelty of our characterization method is the ability of reflecting changes of behaviours according to hardness of different solution quality regions based on simple statistics collected during any algorithm runs. We show that using neighborhood clusters instead of individual neighborhoods helps to reduce the parameter configuration space without misleading the search of the tuning procedure. Moreover, this method is problem-independent and potentially can be applied in similar contexts.
The real-time railway traffic management problem consists of selecting appropriate train routes and schedules for minimizing the propagation of delay in case of traffic perturbation. In this paper, we tackle this prob...
详细信息
The real-time railway traffic management problem consists of selecting appropriate train routes and schedules for minimizing the propagation of delay in case of traffic perturbation. In this paper, we tackle this problem by introducing RECIFE-MILP, a heuristic algorithm based on a mixed-integer linear programming model. RECIFE-MILP uses a model that extends one we previously proposed by including additional elements characterizing railway reality. In addition, it implements performance boosting methods selected among several ones through an algorithm configuration tool. We present a thorough experimental analysis that shows that the performances of RECIFE-MILP are better than the ones of the currently implemented traffic management strategy. RECIFE-MILP often finds the optimal solution to instances within the short computation time available in real-time applications. Moreover, RECIFE-MILP is robust to its configuration if an appropriate selection of the combination of boosting methods is performed.
Many different models for the analysis of high-dimensional survival data have been developed over the past years. While some of the models and implementations come with an internal parameter tuning automatism, others ...
详细信息
Many different models for the analysis of high-dimensional survival data have been developed over the past years. While some of the models and implementations come with an internal parameter tuning automatism, others require the user to accurately adjust defaults, which often feels like a guessing game. Exhaustively trying out all model and parameter combinations will quickly become tedious or infeasible in computationally intensive settings, even if parallelization is employed. Therefore, we propose to use modern algorithm configuration techniques, e.g. iterated F-racing, to efficiently move through the model hypothesis space and to simultaneously configure algorithm classes and their respective hyperparameters. In our application we study four lung cancer microarray data sets. For these we configure a predictor based on five survival analysis algorithms in combination with eight feature selection filters. We parallelize the optimization and all comparison experiments with the BatchJobs and BatchExperiments R packages.
For many computer vision and machine learning problems, large training sets are key for good performance. However, the most computationally expensive part of many computer vision and machine learning algorithms consis...
详细信息
For many computer vision and machine learning problems, large training sets are key for good performance. However, the most computationally expensive part of many computer vision and machine learning algorithms consists of finding nearest neighbor matches to high dimensional vectors that represent the training data. We propose new algorithms for approximate nearest neighbor matching and evaluate and compare them with previous algorithms. For matching high dimensional features, we find two algorithms to be the most efficient: the randomized k-d forest and a new algorithm proposed in this paper, the priority search k-means tree. We also propose a new algorithm for matching binary features by searching multiple hierarchical clustering trees and show it outperforms methods typically used in the literature. We show that the optimal nearest neighbor algorithm and its parameters depend on the data set characteristics and describe an automated configuration procedure for finding the best algorithm to search a particular data set. In order to scale to very large data sets that would otherwise not fit in the memory of a single machine, we propose a distributed nearest neighbor matching framework that can be used with any of the algorithms described in the paper. All this research has been released as an open source library called fast library for approximate nearest neighbors (FLANN), which has been incorporated into OpenCV and is now one of the most popular libraries for nearest neighbor matching.
暂无评论