---

Experimental Methods for the Analysis
of Optimization Algorithms

---

---

Thomas Bartz-Beielstein * Marco Chiarandini *
Luis Paquete * Mike Preuss
Editors
Experimental Methods
for the Analysis of
Optimization Algorithms
123

---

Editors
Prof. Dr. Thomas Bartz-Beielstein
Dr. Marco Chiarandini
Cologne University of Applied Sciences
University of Southern Denmark
Institute of Computer Science
Department of Mathematics and
Faculty of Computer and
Computer Science
Engineering Science
Campusvej 55
Campus Gummersbach
5230 Odense
Steinmullerallee 1
Denmark
51643 Gummersbach
marco@imada.sdu.dk
Germany
thomas.bartz-beielstein@fh-koeln.de
Dr. rer. nat. Luis Paquete
Mike Preuss
University of Coimbra
TU Dortmund
CISUC
Department of Computer Science
Department of Informatics Engineering
Algorithm Engineering
Polo II
Otto-Hahn-Str. 14
3030-290 Coimbra
44227 Dortmund
Portugal
Germany
paquete@dei.uc.pt
mike.preuss@tu-dortmund.de
ISBN 978-3-642-02537-2
e-ISBN 978-3-642-02538-9
DOI 10.1007/978-3-642-02538-9
Springer Heidelberg Dordrecht London New York
ACM Codes: G.1, G.3, F.2, I.2
c Springer-Verlag Berlin Heidelberg 2010
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting,
reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9,
1965, in its current version, and permission for use must always be obtained from Springer. Violations
are liable to prosecution under the German Copyright Law.
The use of general descriptive names, registered names, trademarks, etc. in this publication does not
imply, even in the absence of a specific statement, that such names are exempt from the relevant protective
laws and regulations and therefore free for general use.
Cover design: KuenkelLopka GmbH
Printed on acid-free paper
Springer is part of Springer Science+Business Media (www.springer.com)

---

Foreword
This book belongs on the shelf of anyone interested in carrying out experimental
research on algorithms and heuristics for optimization problems.
The editors have brought together expertise from diverse sources to address
methodological issues arising in this field. The presentation is wide-ranging, con-
taining "big picture" discussions as well as more focused treatment of specific sta-
tistical techniques and their application. The emphasis throughout is on careful pro-
cess and scientific rigor; the discussion is illuminated with many case studies, small
tutorials, and references to the literature on optimization.
Don't keep this book on the shelf: read it, and apply the techniques and tools
contained herein to your own algorithmic research project. Your experiments will
become more efficient and more trustworthy, and your experimental data will lead
to clearer and deeper insights about performance.
Amherst, Massachusetts, February 2010
Catherine C. McGeoch
v

---

---

Foreword
Once upon a time, more exactly nearly half a century ago, when the first cybernetic
machines, henceforth called computers, became available to academic institutions,
a few people seemed to have waited for their iterative power to perform otherwise
boring procedures like solving sets of linear equations, etc. Among other ideas to
make use of their tireless working through loops of instructions was the simulation
of organic evolution, the main subroutines of which are mutation, recombination,
and natural selection. It was only a small step to imagine that by means of the same
principles the design of technical devices, managerial tasks and other systems could
be stepwise improved, if not even optimized. Competing methods from numerical
mathematics were known, of course, but also their limitations to linear and quadratic
dependencies between decision variables and objectives. In so-called black box sit-
uations where much more complex dependencies prevail and nonlinear constraints,
stochastic disturbances, and the like hamper the search for optima, using evolu-
tionary variation and evaluation processes showed up their capacities. Evolutionary
algorithms thus were born during the 1960s, and they have matured ever since to
a powerful and broadly accepted tool within many disciplines. Together with two
other modern streams, artificial neural networks (NN) and fuzzy systems (FS), they
have been subsumed into the so-called computational intelligence (CI) field, at least
since 1994, when the first world congress on CI took place with its three subbranches
NN, FS, and EC (evolutionary computation).
In the beginning of EC one had to be happy if one could rerun a numerical exper-
iment a few times, for example with different seeds of the pseudo random generator
or different start positions in the search space. Gathering a whole set of statistical
data was unimaginable then, so that many open questions remained about the per-
formance of the algorithms. What are those questions? It's not only an average value
and its variance and skewness, or the best result out of a few runs that are interest-
ing. One wants to know whether the ultimate result, i.e. using the algorithm specific
stopping criterion, is always the same, whether and how it depends on the random
numbers and starting points used. Further it may happen or not that fatal execution
errors occur, like division by zero or extracting the square root of a negative num-
ber, or that the stopping criterion does not work properly - even if the optimum was
vii

---

viii
Foreword
found exactly. And what exactly does it mean to talk of four or eight precise dig-
its or even more (which may depend on the hardware and on the system software
handling real numbers, their mantissae and exponents)? Introducing common stop-
ping criteria to compare different methods can easily deliver controversial results
depending on the slopes of best (or average) intermediate results over the number of
objective function values. Such slopes can not only have one crossing, but even two
or more. Then the result depends heavily upon the number of admitted iterations,
one method being quicker at the beginning while finally delivering mediocre final
results, or the other way round, or even more complicated.
If you are interested in such questions, THIS is the book to look into. Here you
will find even more aspects that are treated scientifically by the experts in that excit-
ing domain offering their up-to-date know-how and even leading into philosophical
domains.
Dortmund, February 2010
Hans-Paul Schwefel

---

Preface
Optimization algorithms are used to solve problems that arise in relevant research
and application areas such as operations research, computer science, and engineer-
ing. During recent decades the experimental approach has been recognized and
accepted in the analysis of these algorithms and a considerable body of research
has been devoted to the development and establishment of an adequate scientific
methodology for pursuing this kind of analysis. Statistical tools have become more
and more popular. This book is written for researchers and practitioners of opera-
tions research and computer science who wish to improve the experimental assess-
ment of their optimization algorithms with the final goal of improving their design.
It collects prominent methodological works on different scenarios of experimental
analysis.
The book consists of an introduction and 4 chapters written by the editors plus
11 chapters (including an appendix) written by invited contributors. All together the
project involved 30 authors of 16 world-wide academic institutions.
The first part of the book lays the basis giving an all-round view of the issues
involved in the experimental analysis of algorithms. The second part treats the char-
acterization by means of statistical distributions of the algorithm performance in
terms of solution quality, run-time, and other measures. The third part collects ad-
vanced methods from experimental design for configuring and tuning algorithms
on a specific class of instances with the goal of using the least amount of experi-
mentation and attaining sound conclusions. Several chapters are enriched with case
studies.
Acknowledgments
We are indebted to many people, especially to the contributors of this volume.
The book is the result of an inspiring and fruitful cooperation among the editors.
First contacts were established during the Metaheuristic International Conference
in Vienna in 2005 -- followed by research visits and meetings during conferences.
ix

---

Document Outline

• Cover
• Experimental Methods for the Analysis of Optimization Algorithms
• Copyright
  • 9783642025372
• Foreword
• Preface
• Contents
• List of Contributors
• 1 Introduction
  • 1.1 Optimization Algorithms
  • 1.2 Analysis of Algorithms
    • 1.2.1 Theoretical Analysis
    • 1.2.2 Experimental Analysis
  • 1.3 Bridging the Gap Between Theoretical and Empirical Analysis
  • 1.4 The Need for Statistics
  • 1.5 Book Contents
  • References
• Part I - Overview
  • 2 The Future of Experimental Research
    • 2.1 Introduction
    • 2.2 Experimental Goals in Computer Science
      • 2.2.1 Improving the Performance
      • 2.2.2 Understanding
    • 2.3 Problems
      • 2.3.1 Problems Related to the Experimental Setup
      • 2.3.2 Problems Related to the Significance of Experimental Results
      • 2.3.3 Problems Related to High-Level Theory
    • 2.4 The New Experimentalism
    • 2.5 Experimental Models
      • 2.5.1 The Role of Models in Science
      • 2.5.2 Representational Models
      • 2.5.3 A Framework of Models
      • 2.5.4 Mayos Learning Model
      • 2.5.5 Sequential Parameter Optimization
      • 2.5.6 The Large n Problem Revisited
    • 2.6 Pitfalls of Experimentation with Randomized Algorithms
      • 2.6.1 Floor and Ceiling Effects
      • 2.6.2 Confounded Effects
      • 2.6.3 Fairness in Parameter Settings
      • 2.6.4 Failure Reasons and Prevention
    • 2.7 Tools: Measures and Reports
      • 2.7.1 Measures
      • 2.7.2 Reporting Experiments
    • 2.8 Methodology, Open Issues, and Development
    • 2.9 Summary
    • References
  • 3 Design and Analysis of Computational Experiments: Overview
    • 3.1 Introduction
    • 3.2 Classic Designs and Metamodels
    • 3.3 Screening: Sequential Bifurcation
    • 3.4 Kriging
      • 3.4.1 The Kriging Predictor Variance
      • 3.4.2 Designs for Kriging
    • 3.5 Optimization
      • 3.5.1 Response Surface Methodology (RSM)
      • 3.5.2 Kriging and Mathematical Programming
      • 3.5.3 Taguchian Robust Optimization
    • 3.6 Conclusions
    • References
  • 4 The Generation of Experimental Data for Computational Testing in Optimization
    • 4.1 Introduction
    • 4.2 A Protocol
      • 4.2.1 Generation Principles and Properties
      • 4.2.2 Features of the Model
      • 4.2.3 Validating the Data
    • 4.3 Applications to Optimization
      • 4.3.1 Generalized Assignment and Knapsack
      • 4.3.2 Supply Chains
      • 4.3.3 Scheduling
      • 4.3.4 Graphs and Networks
      • 4.3.5 Routing
      • 4.3.6 Data Mining
      • 4.3.7 Stochastic Programming
      • 4.3.8 Intractable Problems
    • 4.4 Concluding Remarks
    • References
  • 5 The Attainment-Function Approach to Stochastic Multiobjective Optimizer Assessment and Comparison
    • 5.1 Introduction
    • 5.2 Statistics and the Attainment-Function Approach
      • 5.2.1 Stochastic Optimizers as Statistical Estimators
      • 5.2.2 Optimizer Performance as Statistical Estimator Performance
      • 5.2.3 Performance Assessment via Estimation and Hypothesis Testing
    • 5.3 Multiobjective Optimizer Outcomes
      • 5.3.1 Random Nondominated Point Sets
      • 5.3.2 Alternative View: The Attained Set
    • 5.4 Multiobjective Optimizer Performance
      • 5.4.1 Distribution of a General Random Closed Set: The Capacity Functional
      • 5.4.2 Distribution of a Random Nondominated Point Set: The K-th-Order Attainment Function
    • 5.5 Partial Aspects of Multiobjective Optimizer Performance
      • 5.5.1 Distribution Location: The First-Order Attainment Function
      • 5.5.2 Distribution Spread: The Variance Function
      • 5.5.3 Inter-Point Dependence Structures: Second and Higher-Order Attainment Functions
    • 5.6 Multiobjective Optimizer Performance Assessment: Estimation
    • 5.7 Multiobjective Optimizer Performance Comparison: Hypothesis Testing
      • 5.7.1 Two-Sided Test Problem
      • 5.7.2 Permutation Test Procedure
      • 5.7.3 Multistage Testing
      • 5.7.4 One-Sided Tests
    • 5.8 Discussion and Future Perspectives
    • References
  • 6 Algorithm Engineering: Concepts and Practice
    • 6.1 Why Algorithm Engineering?
      • 6.1.1 Early Days and the Pen-and-Paper Era
      • 6.1.2 Errors
    • 6.2 The Algorithm Engineering Cycle
    • 6.3 Current Topics and Issues
      • 6.3.1 Properties of and Structures in the Input
      • 6.3.2 Large Datasets
      • 6.3.3 Memory Efficiency
      • 6.3.4 Distributed Systems and Parallelism
      • 6.3.5 Approximations and Heuristic Algorithms
      • 6.3.6 Succinct Data Structures
      • 6.3.7 Time-Critical Settings
      • 6.3.8 Robustness
    • 6.4 Success Stories
      • 6.4.1 Shortest Path Computation
      • 6.4.2 Full-Text Indexes
    • 6.5 Summary and Outlook
    • References
• Part II - Characterizing Algorithm Performance
  • 7 Algorithm Survival Analysis
    • 7.1 Introduction
    • 7.2 Modeling Runtime Distributions
      • 7.2.1 Basic Quantities and Concepts
      • 7.2.2 Censoring
      • 7.2.3 Estimation in Survival Analysis
      • 7.2.4 Competing Risks
    • 7.3 Model-Based Algorithm Selection
      • 7.3.1 RTD of an Algorithm Portfolio
      • 7.3.2 Model-Based Time Allocators
      • 7.3.3 Algorithms as Competing Risks
    • 7.4 Experiments
    • 7.5 Related Work
    • 7.6 Summary and Outlook
    • References
  • 8 On Applications of Extreme Value Theory in Optimization
    • 8.1 Introduction
    • 8.2 Extreme Value Theory
      • 8.2.1 Extreme Value Theory for Minima
      • 8.2.2 Peaks Over Threshold Method (POT) for Minima
      • 8.2.3 Assessment of an Optimizer
    • 8.3 Experiments Using Random Search
      • 8.3.1 Samples with Simulations Near the Optimum
      • 8.3.2 Samples with Simulations Away from the Optimum
    • 8.4 Analytical Results
    • 8.5 Experiments Using Evolution Strategies
    • 8.6 Summary
    • References
  • 9 Exploratory Analysis of Stochastic Local Search Algorithms in Biobjective Optimization
    • 9.1 Introduction
    • 9.2 Stochastic Local Search for Multiobjective Problems
    • 9.3 Examination of the Attainment Surfaces
      • 9.3.1 The eafplot.pl Program
      • 9.3.2 Example Application of eafplot.pl
    • 9.4 Examining the Differences Between EAFs
    • 9.5 Examples
      • 9.5.1 Effect of Problem Structure
      • 9.5.2 Differences in Algorithmic Performance
      • 9.5.3 Biased Behavior
    • 9.6 Summary and Outlook
    • References
• Part III - Algorithm Configuration and Tuning
  • 10 Mixed Models for the Analysis of Optimization Algorithms
    • 10.1 Introduction
    • 10.2 Experimental Designs and Statistical Modeling
      • 10.2.1 Case : Random-Effects Design
      • 10.2.2 Case : Mixed-Effects Design
      • 10.2.3 Case : Nested-Effects Design
      • 10.2.4 Case : General Mixed-Effects Design
    • 10.3 An Application Example in Optimization Heuristic Design
      • 10.3.1 Definitions and Problem Formulation
      • 10.3.2 Local Search Algorithms
      • 10.3.3 Problem Instances
    • 10.4 Numerical Examples
      • 10.4.1 Case : Random-Effects Design
      • 10.4.2 Case : Mixed-Effects Design
      • 10.4.3 Case : Nested Design
      • 10.4.4 Case