Source-linked AI summary
Benchmarking in Optimization: Best Practice and Open Issues
Thomas Bartz-Beielstein, Carola Doerr, Daan van den Berg, Jakob Bossek, Sowmya Chandrasekaran, Tome Eftimov, Andreas Fischbach, Pascal Kerschke, William La Cava, Manuel Lopez-Ibanez, Katherine M. Malan, Jason H. Moore, Boris Naujoks, Patryk Orzechowski, Vanessa Volz, Markus Wagner, Thomas Weise
TL;DR
Optimization benchmarking lacks consistently adopted standards despite its central role in evaluating algorithms. This survey synthesizes guidance across benchmark goals, problems, algorithms, measures, analysis, design, reporting, and reproducibility, while presenting itself as an evolving starting point for improving practice.
Problem
Benchmarking practice lacks generally agreed methodology, and sound studies are complicated by statistical and design pitfalls.
Method
The survey compiles multidisciplinary recommendations covering benchmark design, performance measurement, analysis, reporting, and reproducibility.
Results
The paper proposes transparent, broadly accepted standards that ask authors to explain their goals and justify their chosen measures, tools, and designs.
Takeaways & Limitations
The survey provides a starting point for activities intended to improve benchmark-study quality in evolutionary computation and related fields.
Takeaways & Limitations
The survey is a snapshot and mainly focuses on single-objective, unconstrained optimization, so evolving methods and other domains may require updates or different measures.
Abstract
from arXiv · showhide
This survey compiles ideas and recommendations from more than a dozen researchers with different backgrounds and from different institutes around the world. Promoting best practice in benchmarking is its main goal. The article discusses eight essential topics in benchmarking: clearly stated goals, well-specified problems, suitable algorithms, adequate performance measures, thoughtful analysis, effective and efficient designs, comprehensible presentations, and guaranteed reproducibility. The final goal is to provide well-accepted guidelines (rules) that might be useful for authors and reviewers. As benchmarking in optimization is an active and evolving field of research this manuscript is meant to co-evolve over time by means of periodic updates.
1 Introduction
Benchmarking is treated as central to optimization research because algorithm performance depends on the tested problems, algorithms, and performance measures. The survey proposes best-practice guidance while recognizing theoretical, statistical, and field-evolution challenges.
- Benchmark studies should specify their goals because the goals shape the problem instances, algorithm instances, performance criteria, and statistics.
- No single algorithm is expected to dominate universally, so performance claims should be tied to the tested problem classes or instances.
- Every benchmark study must choose performance measures, problem instances, and algorithm instances.
- Benchmarking practice remains difficult because sound studies involve complex statistical considerations and lack generally agreed methodology in evolutionary computation.
- Because optimization theory, algorithms, and performance measures evolve, each version of the survey is explicitly a snapshot.
- The survey is a starting point focused mainly on single-objective, unconstrained optimization, with findings intended to transfer to other domains while performance measures may differ.
2 Goals of Benchmarking Activities
Benchmarking can assess algorithm behavior, compare algorithms, characterize problems, test invariances, and study parameter or component effects. These goals determine the experimental design and the practical meaning of statistical findings.
- Benchmarking goals range from basic performance assessment and algorithm comparison to problem assessment, search-behavior illustration, invariance testing, and parameter analysis.
- Comparing algorithms can reveal strengths and weaknesses across problem types and optimization stages, supporting selection of suitable algorithm instances.
- Benchmarking can test whether algorithms exhibit desired invariances, including invariance to scaling, translation, dimensional changes, or search-space rotation.
- Offline parameter tuning finds configurations for a given problem instance and should precede comparisons of viable method configurations.
- Benchmarking can be used to understand how parameters or algorithmic components influence performance, using tools such as analysis of variance or regression.
3 Problem Instances
Problem-instance selection strongly influences benchmark conclusions, so useful suites should represent relevant difficulties, provide diversity and tunability, and support transparent evaluation. Existing suites and quality-assessment methods remain accompanied by concerns about artificiality and overfitting.
- Problem sets should represent the real-world scenario under investigation, because their representativeness constrains the generality of benchmark conclusions.
- A good benchmark suite spans difficulties and problem characteristics so it can expose different algorithms’ strengths and weaknesses.
- Tunable suites can vary dimensions, variable dependence, and objective counts, while known optima or best-known performances facilitate performance measurement.
- Problem-set diversity can be evaluated through feature spaces and performance spaces, although aggregate statistics may fail to distinguish structurally different algorithms.
- Public benchmark resources include competition suites, combinatorial libraries, and artificial discrete, real-parameter, and mixed-representation problems.
- Open Issues: Test suites provide objective comparisons but may be artificial, encourage tuning to fixed instances, and require complex statistical analysis.
4 Algorithms
Algorithm portfolios should match the benchmarked problem types and include suitable diversity, current methods, fair tuning, and controlled experimental conditions. Comparisons remain sensitive to budgets, stopping criteria, initialization, and implementation details.
- Algorithm portfolios should include different families to assess distinct algorithmic ideas, while recognizing that hybridization makes family classifications subjective.
- The benchmarked problem’s structure, available information, decision-space type, and variable interactions should guide algorithm selection.
- Budget constraints influence portfolio composition, with surrogate-assisted methods tending to suit small budgets and evolution strategies tending to suit larger ones.
- Comparisons should include state-of-the-art algorithms rather than relying only on outdated methods.
- Algorithms require properly tuned hyperparameters because configurations that work under one budget may perform worse under another.
- Shared starting points and careful control of repetitions, instances, and randomization help prevent initialization-driven performance bias.
- Different stopping criteria and implementations may bias results when algorithms do not perform the specified number of objective-function evaluations.
5 How to Measure Performance?
Benchmark performance can be measured through solution quality, consumed budget, anytime behavior, and robustness, with time and quality objectives offering complementary perspectives. The survey recommends reporting measures that balance machine-independent comparability with practical runtime relevance.
- 5. How to Measure Performance?: Fixed-budget analysis asks what solution quality algorithms achieve within a given budget, whereas fixed-target analysis asks how quickly they reach a target quality.These correspond to vertical and horizontal cuts in performance diagrams.
- 5. How to Measure Performance?: Anytime analysis evaluates an algorithm through its complete time-quality performance curve rather than a single budget or target value.
- 5.1 Measuring Time: Function evaluations are machine-independent and widely accepted, but they can misrepresent runtime when algorithms have different evaluation costs.
- 5.1 Measuring Time: Best practice is to report both function evaluations and CPU time, separating expensive evaluations from algorithm overhead when necessary.This distinction is especially important for surrogate-based optimization, where model complexity can grow over time.
- 5.2 Measuring Quality: Quality measures should be normalized against known optima, lower bounds, best-known solutions, or clearly specified heuristics when raw objective values are difficult to interpret.
- 5.3 Measuring Robustness: Robustness analyses must distinguish algorithm stochasticity, noisy problems, and landscape ruggedness because each creates different sources of performance volatility.
6 How to Analyze Results?
The analysis of benchmark results should match the study’s goal and distinguish single-problem from multiple-problem comparisons. A recommended three-level approach begins with exploratory data analysis before subsequent inferential analysis.
- 6. How to Analyze Results?: Benchmark analysis distinguishes single-problem analysis from comparisons across multiple benchmark problems.Single-problem analysis uses repeated runs on one instance, whereas multiple-problem analysis compares algorithms over a problem set.
- 6. How to Analyze Results?: The recommended three-level analysis starts with Exploratory Data Analysis, followed by confirmatory analysis and further procedures for drawing conclusions.
6.2 Exploratory Data Analysis
Exploratory Data Analysis uses descriptive and graphical tools to reveal patterns, validate assumptions, and generate hypotheses before formal statistical testing. Its outputs can inform analysis but do not always provide definitive answers.
- 6.2. Exploratory Data Analysis: EDA must precede statistical testing to assess distributional assumptions such as normality and independence.
- 6.2.1 Motivation: EDA combines visual tools, descriptive statistics, and inductive reasoning to identify patterns, outliers, and hypotheses without fixed preconceptions.
- 6.2.2 The Glorious Seven: Descriptive statistics summarize central tendency and variability, but means and standard deviations are sensitive to outliers, missing data, and biased samples.
- 6.2.3 Graphical Tools: Histograms and boxplots visualize final-result distributions, while convergence plots show performance dynamics against function evaluations.
- 6.2.3 Graphical Tools: Performance profiles compare algorithms through cumulative distributions of ratios to the best observed metric, whereas data profiles target fixed-budget comparisons.
6.3 Confirmatory Analysis
Confirmatory analysis tests hypotheses with inferential statistics after exploratory analysis, while test selection depends on assumptions, pairing, and the comparison design. Post-hoc procedures identify which algorithms differ after an omnibus test rejects the null hypothesis.
- 6.3. Confirmatory Analysis: Confirmatory analysis uses inferential statistics and probability models to test hypotheses for a specific experimental design.
- 6.3.2 Assumptions for the Safe Use of Parametric Tests: Selecting a statistical test requires checking normality, independence, homoscedasticity, and whether samples are paired or unpaired.
- 6.3.3 Statistical Tests: Common pairwise choices are the t test or Mann-Whitney U test for single-problem comparisons and the Wilcoxon signed rank test for paired multiple-problem comparisons.
- Multiple-problem analysis.: Mean and median provide representative values across runs, but both can overlook small distributional differences that Deep Statistical Comparison evaluates using the whole distribution.
- Post-hoc procedures: When an omnibus test finds significance among more than two algorithms, post-hoc testing determines which pairs contribute to that significance.
6.4 Relevance Analysis
Statistical significance does not guarantee practical relevance in optimization benchmarking. The section presents CRS4EA and pDSC as approaches for assessing meaningful differences across multiple problems.
- 6.4.1 Motivation: Statistically significant differences can be practically meaningless when their magnitude is below real-world measurement precision.The section emphasizes evaluating whether observed differences matter for the specific application rather than treating statistical significance as sufficient.
- 6.4.2 Statistical Relevance: Severity provides a post-data evaluation of how well data support decisions made through classical hypothesis testing.It directly addresses dependence on sample size and the problem of large n.
- 6.4.3 Multiple-Problem Analysis: CRS4EA ranks evolutionary algorithms through a chess-tournament model in which pairwise performance comparisons form games.A user-defined draw limit determines when two performance values are treated as equal, and algorithm ratings support confidence-interval analysis.
- 6.4.3 Multiple-Problem Analysis: pDSC preprocesses performance data using a user-specified practical level before applying DSC to identify relevant differences.The approach is presented as a modification of DSC for testing meaningful differences in multiple-problem settings.
6.5 Open Issues
The document leaves problem analysis and landscape visualization as open issues. These tools could improve understanding of problem structure and algorithm search behavior, but current evaluations often treat visualization inadequately.
- 6.5 Open Issues: Benchmarking still lacks a fully addressed analysis of the structural characteristics and most relevant information of benchmark problems.The open questions concern how to investigate, automatically extract, and interpret problem structure.
- 6.5 Open Issues: Landscape visualizations can reveal challenges such as multimodality and help examine algorithm search behavior, yet most empirical work handles them poorly.The discussion covers continuous landscapes and approximate tours for TSP instances.
7 Experimental Design
Sound experimental design makes optimization comparisons more transparent and objective. The recommended framework specifies goals, problems, algorithms, factors, tuning, validation, analysis, presentation, and reproducibility while favoring multifactor designs over OFAT.
- 7 Experimental Design: Experimental design addresses basic design omissions by providing an algorithmic procedure for transparent, objective benchmarking.DOE helps determine which and how many algorithm runs should be performed.
- 7 Experimental Design: Factorial or space-filling designs are recommended over OFAT because OFAT is inefficient and cannot identify factor interactions.The section specifically recommends multifactorial designs when several factors are involved.
- 7 Experimental Design: Benchmark studies combine problem and algorithm designs, with performance measures and reproducibility choices forming additional design requirements.Problem factors include objectives, resources, and dimension; algorithm factors include parameters such as population size.
- 7 Experimental Design: A benchmark plan should explicitly define its goals, test problems, algorithm count, tuning procedure, validation, analysis, presentation, and randomization.These decisions determine how the experiment is executed and interpreted.
- 7 Experimental Design: Fair comparisons require tuning decisions to be handled consistently, ideally by searching each algorithm’s parameters on each problem when code and resources permit.When full tuning is too costly, limited space-filling parameter searches can reduce misconfiguration.
- 7.6 Open Issues: Design quality remains unresolved when it depends on assumptions about an unknown objective function or on settings with multiple objectives.The document identifies open questions about which design characteristics matter and how to measure design quality in these settings.
8 How to Present Results?
The section recommends reporting benchmark results through explicit goals, measures, designs, analyses, and conclusions. It emphasizes reproducibility, complete specification, transparent structure, negative results, and maintaining experiment records.
- 8.1 General Recommendations: Reports should present statistical support for performance claims, preserve planning quality despite deadlines, and include instances where algorithms fail.Negative results are identified as a key component of a good scientific report.
- 8.2 Reporting Methodologies: A structured experimental report moves from goals and performance measures through experiment design, execution, analysis, and conclusions.This methodology separates the main stages of empirical evaluation.
- 8.1 General Recommendations: Eight reporting guidelines emphasize reproducibility, influential-factor specification, precise measures and parameters, experimental design, comparisons, reduced variability, and comprehensive results.The guidelines include code and computing environment among the influential factors to report.
- 8.2 Reporting Methodologies: A complete report specifies problem and algorithm designs, parameters, performance measures, and computational environment sufficiently for replication.The recommended specification includes hardware, software, packages, and libraries.
- 8.2 Reporting Methodologies: Reporting should distinguish observations, analysis, and subjective conclusions so readers can draw different conclusions from the same results.The authors recommend making this structure visible with labels rather than claiming that the parts are absent from current good reports.
- 8.2 Reporting Methodologies: Maintaining a journal of individual experiments supports later reference, improves oversight, and helps prevent repeated tests.The recommendation applies even when an experiment is never published.
- 8.3 Open Issues: Negative results document what failed, prevent duplicated effort, and expose limitations, but remain poorly accepted for publication.The section contrasts their scientific value with publication practices that favor improvements and outperforming results.
9 How to Guarantee Reproducibility?
The survey distinguishes repeatability, reproducibility, and replicability by whether teams and experimental setups remain the same or change. Achieving replicability is especially difficult because it requires accepted statistical guidelines for evidence under different but similar conditions.
- Reproducibility concepts: Repeatability means the same team can reliably repeat a computation using the same procedure, system, conditions, and location.
- Reproducibility concepts: Reproducibility means a different team can obtain the same result using the authors’ artifacts and the same experimental setup.
- Reproducibility concepts: Replicability requires an independent team to obtain the same result using independently developed artifacts under a different experimental setup.This is distinguished from reproducibility, which uses the authors’ artifacts and the same experimental setup.
- Practical support: Practical support includes code versioning, data repositories, reproducible documents, and reproducible software environments.
- Open issues: Replicability remains difficult because sufficient evidence must be defined for similar, rather than identical, experimental conditions.What counts as similar conditions depends on the experiment, and benchmarking algorithms offers no simple answer.
- Open issues: Preregistration can reduce spurious results from adaptive data analysis, but computational experiments are easier to rerun before registration than randomized controlled trials.
10 Summary and Outlook
The survey proposes eight topics and a practical guide for improving benchmark studies, while emphasizing explanation and transparency rather than mandated statistical methods or designs. It presents recommendations, examples, open issues, and future activities aimed at supporting authors, reviewers, and the wider research community.
- Scope and structure: The survey organizes benchmarking best practice around eight topics: goals, problems, algorithms, performance, analysis, design, presentation, and reproducibility.
- Scope and structure: The guide offers recommendations, best-practice examples, and open issues rather than explaining every approach as a textbook would.
- Future directions: Future activities include tutorials, workshops, explanatory videos, software tools, beginner-oriented checklists, and discussion sections for controversial topics.
- Checklist: The proposed checklist asks whether goals, problem instances, competitors, performance measures, statistical standards, experimental design, presentation, and data or code availability are adequately addressed.
- Future directions: The final goal is well-accepted benchmarking guidelines useful to authors, reviewers, and others.
- Standards and review: The authors recommend that researchers explain why they selected particular measures, tools, and designs, and clearly state the study goal.
Glossary
The glossary expands abbreviations used throughout the survey, covering organizations, benchmark suites, optimization methods, metrics, problem classes, and reproducibility-related tools.
- Organizations and methods: Organizational abbreviations include AAAI, ACM, CEC, and IEEE, while optimization methods include ES, PSO, SANN, BFGS, and EDAlgo.
- Benchmarking and optimization: The glossary defines major optimization and benchmarking abbreviations, including BBOB, COCO, CMA-ES, ERT, FE, and NFLT.
- Analysis and design: It also defines analysis and experimental-design terms such as EDA, ELA, DACE, OFAT, CRN, and pDSC.
- Configuration and selection: The glossary covers algorithm configuration and selection tools including irace, ParamILS, SMAC, SPOT, and ASlib.
- Problem classes: It includes problem and application abbreviations such as MAX-SAT, SAT, TSP, PBO, and MOO.