nach oben

2010 | Buch

Experimental Methods for the Analysis of Optimization Algorithms

herausgegeben von: Thomas Bartz-Beielstein, Marco Chiarandini, Luís Paquete, Mike Preuss

Verlag: Springer Berlin Heidelberg

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

In operations research and computer science it is common practice to evaluate the performance of optimization algorithms on the basis of computational results, and the experimental approach should follow accepted principles that guarantee the reliability and reproducibility of results. However, computational experiments differ from those in other sciences, and the last decade has seen considerable methodological research devoted to understanding the particular features of such experiments and assessing the related statistical methods.

This book consists of methodological contributions on different scenarios of experimental analysis. The first part overviews the main issues in the experimental analysis of algorithms, and discusses the experimental cycle of algorithm development; the second part treats the characterization by means of statistical distributions of algorithm performance in terms of solution quality, runtime and other measures; and the third part collects advanced methods from experimental design for configuring and tuning algorithms on a specific class of instances with the goal of using the least amount of experimentation. The contributor list includes leading scientists in algorithm design, statistical design, optimization and heuristics, and most chapters provide theoretical background and are enriched with case studies.

This book is written for researchers and practitioners in operations research and computer science who wish to improve the experimental assessment of optimization algorithms and, consequently, their design.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

Theory and experiments are complementary ways to analyze optimization algorithms. Experiments can also live a life of their own and produce learning without need to follow or test a theory. Yet, in order to make conclusions based on experiments trustworthy, reliable, and objective a systematic methodology is needed. In the natural sciences, this methodology relies on the mathematical framework of statistics. This book collects the results of recent research that focused on the application of statistical principles to the specific task of analyzing optimization algorithms.

Thomas Bartz-Beielstein, Marco Chiarandini, Luís Paquete, Mike Preuss

Overview

Frontmatter

Chapter 2. The Future of Experimental Research

Abstract

In the experimental analysis of metaheuristic methods, two issues are still not sufficiently treated. Firstly, the performance of algorithms depends on their parametrizations—and of the parametrizations of the problem instances. However, these dependencies can be seen as means for understanding an algorithm’s behavior. Secondly, the nondeterminism of evolutionary and other metaheuristic methods renders result distributions, not numbers.

Based on the experience of several tutorials on the matter, we provide a comprehensive, effective, and very efficient methodology for the design and experimental analysis of metaheuristics such as evolutionary algorithms. We rely on modern statistical techniques for tuning and understanding algorithms from an experimental perspective. Therefore, we make use of the sequential parameter optimization (SPO) method that has been successfully applied as a tuning procedure to numerous heuristics for practical and theoretical optimization problems.

Thomas Bartz-Beielstein, Mike Preuss

Chapter 3. Design and Analysis of Computational Experiments: Overview

Abstract

This chapter presents an overview of the design and analysis of computational experiments with optimization algorithms. It covers classic designs and their corresponding (meta)models; namely, Resolution-III designs including fractional factorial two-level designs for first-order polynomial models, Resolution-IV and Resolution-V designs for two-factor interactions, and designs including central composite designs for second-degree polynomials. It also reviews factor screening in experiments with very many factors, focusing on the sequential bifurcation method. Furthermore, it reviews Kriging models and their designs. Finally, it discusses experiments aimed at the optimization of the parameters of a given optimization algorithm, allowing multiple random experimental outputs. This optimization may use either generalized response surface methodology or Kriging combined with mathematical programming; the discussion also covers Taguchian robust optimization.

Jack P.C. Kleijnen

Chapter 4. The Generation of Experimental Data for Computational Testing in Optimization

Abstract

This chapter discusses approaches to generating synthetic data for use in scientific experiments. In many diverse scientific fields, the lack of availability, high cost or inconvenience of the collection of real-world data motivates the generation of synthetic data. In many experiments, the method chosen to generate synthetic data can significantly affect the results of an experiment. Unfortunately, the scientific literature does not contain general protocols for how synthetic data should be generated. The purpose of this chapter is to rectify that deficiency. The protocol we propose is based on several generation principles. These principles motivate and organize the data generation process. The principles are operationalized by generation properties. Then, together with information about the features of the application and of the experiment, the properties are used to construct a data generation scheme. Finally, we suggest procedures for validating the synthetic data generated. The usefulness of our protocol is illustrated by a discussion of numerous applications of data generation from the optimization literature. This discussion identifies examples of both good and bad data generation practice as it relates to our protocol.

Nicholas G. Hall, Marc E. Posner

Chapter 5. The Attainment-Function Approach to Stochastic Multiobjective Optimizer Assessment and Comparison

Abstract

This chapter presents the attainment-function approach to the assessment and comparison of stochastic multiobjective optimizer (MO) performance. Since the random outcomes of stochastic MOs, such as multiobjective evolutionary algorithms, are sets of nondominated solutions, analyzing their performance is challenging in that it involves studying the distribution of those sets. The attainment function, so named because it indicates the probability of an MO attaining an arbitrary goal, is related to results from random closed-set theory which cast it as a kind of mean for the distribution of the optimizer outcomes in objective space. Higher-order versions of the attainment function can also address other aspects of this distribution, and may even lead to a full distributional characterization. This approach to the experimental assessment and comparison of MO performance is based on statistical inference methodology, in particular, estimation and hypothesis testing.

Viviane Grunert da Fonseca, Carlos M. Fonseca

Chapter 6. Algorithm Engineering: Concepts and Practice

Abstract

Over the last years the term algorithm engineering has become wide spread synonym for experimental evaluation in the context of algorithm development. Yet it implies even more. We discuss the major weaknesses of traditional “pen and paper” algorithmics and the ever-growing gap between theory and practice in the context of modern computer hardware and real-world problem instances. We present the key ideas and concepts of the central algorithm engineering cycle that is based on a full feedback loop: It starts with the design of the algorithm, followed by the analysis, implementation, and experimental evaluation. The results of the latter can then be reused for modifications to the algorithmic design, stronger or input-specific theoretic performance guarantees, etc. We describe the individual steps of the cycle, explaining the rationale behind them and giving examples of how to conduct these steps thoughtfully. Thereby we give an introduction to current algorithmic key issues like I/O-efficient or parallel algorithms, succinct data structures, hardware-aware implementations, and others. We conclude with two especially insightful success stories—shortest path problems and text search—where the application of algorithm engineering techniques led to tremendous performance improvements compared with previous state-of-the-art approaches.

Markus Chimani, Karsten Klein

Characterizing Algorithm Performance

Frontmatter

Chapter 7. Algorithm Survival Analysis

Abstract

Algorithm selection is typically based on models of algorithm performance,learned during a separate offline training sequence, which can be prohibitively expensive. In recent work, we adopted an online approach, in which models of the runtime distributions of the available algorithms are iteratively updated and used to guide the allocation of computational resources, while solving a sequence of problem instances. The models are estimated using survival analysis techniques, which allow us to reduce computation time, censoring the runtimes of the slower algorithms. Here, we review the statistical aspects of our online selection method, discussing the bias induced in the runtime distributions (RTD) models by the competition of different algorithms on the same problem instances.

Matteo Gagliolo, Catherine Legrand

Chapter 8. On Applications of Extreme Value Theory in Optimization

Abstract

We present a statistical study of the distribution of the objective value of solutions (outcomes) obtained by stochastic optimizers, applied for continuous objective functions. We discuss the application of extreme value theory for the optimization procedures. A short review of the extreme value theory is presented to understand the investigations. In this chapter three optimization procedures are compared in this context: the random search and two evolution strategies. The outcomes of these optimizers applied to three objective functions are discussed in the context of extreme value theory and the performances of the procedures investigated, analytically and by simulations. In particular, we find that the estimated extreme value distributions and the fit to the outcomes characterize the performance of the optimizer in one single instance.

Jürg Hüsler

Chapter 9. Exploratory Analysis of Stochastic Local Search Algorithms in Biobjective Optimization

Abstract

This chapter introduces two Perl programs that implement graphical tools for exploring the performance of stochastic local search algorithms for biobjective optimization problems. These tools are based on the concept of the empirical attainment function (EAF), which describes the probabilistic distribution of the outcomes obtained by a stochastic algorithm in the objective space. In particular, we consider the visualization of attainment surfaces and differences between the first-order EAFs of the outcomes of two algorithms. This visualization allows us to identify certain algorithmic behaviors in a graphical way. We explain the use of these visualization tools and illustrate them with examples arising from practice.

Manuel López-Ibáñez, Luís Paquete, Thomas Stützle

Algorithm Configuration and Tuning

Frontmatter

Chapter 10. Mixed Models for the Analysis of Optimization Algorithms

Abstract

We review linear statistical models for the analysis of computational experiments on optimization algorithms. The models offer the mathematical framework to separate the effects of algorithmic components and instance features included in the analysis. We regard test instances as drawn from a population and we focus our interest not on those single instances but on the whole population. Hence, instances are treated as a random factor. Overall these experimental designs lead to mixed effects linear models. We present both the theory to justify these models and a computational example in which we analyze and comment on several possible experimental designs. The example is a component-wise analysis of local search algorithms for the 2-edge-connectivity augmentation problem. We use standard statistical software to perform the analysis and report the R commands. Data sets and the analysis in SAS are available in an online compendium.

Marco Chiarandini, Yuri Goegebeur

Chapter 11. Tuning an Algorithm Using Design of Experiments

Abstract

This chapter is a tutorial on using a design of experiments approach for tuning the parameters that affect algorithm performance. A case study illustrates the application of the method and interpretation of its results.

Enda Ridge, Daniel Kudenko

Chapter 12. Using Entropy for Parameter Analysis of Evolutionary Algorithms

Abstract

Evolutionary algorithms (EA) form a rich class of stochastic search methods that share the basic principles of incrementally improving the quality of a set of candidate solutions by means of variation and selection (Eiben and Smith 2003, De Jong 2006). Such variation and selection operators often require parameters to be specified. Finding a good set of parameter values is a nontrivial problem in itself. Furthermore, some EA parameters are more relevant than others in the sense that choosing different values for them affects EA performance more than for the other parameters. In this chapter we explain the notion of entropy and discuss how entropy can disclose important information about EA parameters, in particular, about their relevance. We describe an algorithm that is able to estimate the entropy of EA parameters and we present a case study, based on extensive experimentation, to demonstrate the usefulness of this approach and some interesting insights that are gained.

Selmar K. Smit, Agoston E. Eiben

Chapter 13. F-Race and Iterated F-Race: An Overview

Abstract

Algorithms for solving hard optimization problems typically have several parameters that need to be set appropriately such that some aspect of performance is optimized. In this chapter, we review F-Race, a racing algorithm for the task of automatic algorithm configuration. F-Race is based on a statistical approach for selecting the best configuration out of a set of candidate configurations under stochastic evaluations. We review the ideas underlying this technique and discuss an extension of the initial F-Race algorithm, which leads to a family of algorithms that we call iterated F-Race. Experimental results comparing one specific implementation of iterated F-Race to the original F-Race algorithm confirm the potential of this family of algorithms.

Mauro Birattari, Zhi Yuan, Prasanna Balaprakash, Thomas Stützle

Chapter 14. The Sequential Parameter Optimization Toolbox

Abstract

The sequential parameter optimization toolbox (SPOT) is one possible implementation of the SPO framework introduced in Chap. 2. It has been successfully applied to numerous heuristics for practical and theoretical optimization problems. We describe the mechanics and interfaces employed by SPOT to enable users to plug in their own algorithms. Furthermore, two case studies are presented to demonstrate how SPOT can be applied in practice, followed by a discussion of alternative metamodels to be plugged into it.We conclude with some general guidelines.

Thomas Bartz-Beielstein, Christian Lasarczyk, Mike Preuss

Chapter 15. Sequential Model-Based Parameter Optimization: an Experimental Investigation of Automated and Interactive Approaches

Abstract

This work experimentally investigates model-based approaches for optimizing the performance of parameterized randomized algorithms. Such approaches build a response surface model and use this model for finding good parameter settings of the given algorithm. We evaluated two methods from the literature that are based on Gaussian process models: sequential parameter optimization (SPO) (Bartz-Beielstein et al. 2005) and sequential Kriging optimization (SKO) (Huang et al. 2006). SPO performed better “out-of-the-box,” whereas SKO was competitive when response values were log transformed. We then investigated key design decisions within the SPO paradigm, characterizing the performance consequences of each. Based on these findings, we propose a new version of SPO, dubbed SPO+, which extends SPO with a novel intensification procedure and a log-transformed objective function. In a domain for which performance results for other (modelfree) parameter optimization approaches are available, we demonstrate that SPO+ achieves state-of-the-art performance. Finally, we compare this automated parameter tuning approach to an interactive, manual process that makes use of classical

Frank Hutter, Thomas Bartz-Beielstein, Holger H. Hoos, Kevin Leyton-Brown, Kevin P. Murphy

Backmatter

Titel: Experimental Methods for the Analysis of Optimization Algorithms
herausgegeben von: Thomas Bartz-Beielstein
Marco Chiarandini
Luís Paquete
Mike Preuss
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-02538-9
Print ISBN: 978-3-642-02537-2
DOI: https://doi.org/10.1007/978-3-642-02538-9