Benchmarking in Optimization: Best Practice and Open Issues

Motivation

• Benchmarking has long accompanied evolutionary-computation algorithms, while modern computational resources enable hundreds or thousands of runs and sophisticated suites such as COCO and Nevergrad.Benchmarking asks both how well an algorithm performs on a problem and why it succeeds or fails there.Source: §1 · p. 4

Benchmark foundations

• A benchmark’s goal shapes its problem instances, algorithm instances, performance criteria, and statistics, making goal specification as important as the study itself.Every benchmark must address performance measures, problems, and algorithms.Source: §1 · pp. 4–5

Scope of conclusions

• No-free-lunch results require algorithm-performance claims to be bound to tested problem instances, with caution against generalizing across instances, classes, or domains.The survey also notes that tuning an algorithm for one subset of problems can worsen performance on another, while qualifying broad class-based formulations.Source: §1 · p. 4

Need for guidance

• Benchmarking practice remains unsatisfactory because evolutionary computation lacks an agreed general methodology and studies face complex statistical pitfalls, motivating practical best-practice guidelines.The paper is a joint initiative that compiles examples and references across disciplines to address missing guidance.Source: §1 · p. 5

Scope and limitations

• The paper primarily addresses single-objective, unconstrained optimization but states that most guidance transfers to multi-objective and constrained domains with potentially different measures.It presents a starting point rather than exhaustive coverage, and recognizes that the field, algorithms, theory, and measures continue evolving.Source: §1 · p. 5

Survey structure

• The survey covers eight aspects of benchmark studies: goals, problems, algorithms, performance, analysis, design, presentation, and reproducibility.These topics organize the subsequent sections, from selecting suitable problems and algorithm portfolios to guaranteeing scientifically sound, comparable results.Source: §1 · p. 6

2 Goals of Benchmarking Activities

• The survey’s goal categories are a time-dependent snapshot whose relevance may change as benchmarking practices and scientific priorities evolve.The authors present the categorization as an attempt to represent objectives across the broader scientific community, not as a unique classification.Source: §2 · p. 6, §2.6 · p. 11

2.1 Visualization and Basic Assessment of Algorithms and Problems

• Benchmarking primarily assesses individual algorithms and compares alternatives to reveal performance, search behavior, strengths, weaknesses, and suitable choices for problem instances.It also helps visualize problem characteristics and optimization processes, including stochasticity and effects difficult to grasp mathematically.Source: §2.1 · pp. 7–8

2.2 Sensitivity of Performance in Algorithm Design and Problem Characteristics

• Benchmarking tests desired invariances, supports parameter tuning, and analyzes how algorithmic components and problem features influence performance.Tuning requires appropriate experiments, performance measures, and repetitions, while characterization links features such as dimensionality, separability, or ruggedness to algorithm performance.Source: §2.2 · pp. 8–9

2.3 Benchmarking as Training: Performance Extrapolation

• Benchmark data can support performance extrapolation to unseen instances and derive human-interpretable or automated rules for algorithm design, selection, and configuration.Reliable extrapolation depends on selecting suitable test instances and, for supervised approaches, appropriate feature-extraction methods.Source: §2.3 · p. 10

2.4 Theory-Oriented Goals

• Benchmarking complements theoretical bounds with concrete behavior and exposes unexpected empirical effects that can inspire new theoretical studies, linking mathematical and empirical optimization communities.It can extend analysis to small dimensions or regimes not covered by asymptotic results [Auger and Doerr, 2011, Doerr and Neumann, 2020, Neumann and Witt, 2010].Source: §2.4 · p. 10

2.5 Benchmarking in Algorithm Development

• In algorithm development, benchmarking validates source code on instances with known properties and identifies weaknesses or promising ideas for iterative empirical and theoretical improvement.Early observations that dynamic parameter choices can outperform static ones stimulated further empirical evaluation and theoretical investigation.Source: §2.5 · p. 11

2.6 Open Issues and Challenges

• Benchmarking studies should begin with a clear research question and an experimental design that directly supports the claims, while shared data standards remain needed for comparability and reuse.Existing tools such as IOHanalyzer support multiple formats, including Nevergrad and COCO.Source: §2.6 · p. 11

3.1 Desirable Characteristics of a Problem Set

• Benchmark suites should represent real-world problem classes, span diverse difficulties and characteristics, and be continually updated to reduce over-tuning.Tunable dimensions such as problem size, variable dependence, and number of objectives can further broaden coverage.Source: §3 · p. 11, §3.1 · p. 12

3.2 Evaluating the Quality of a Problem Set

• Problem-set quality can be assessed through feature-space coverage, performance-space discrimination, and instance-space visualizations linking problem characteristics to algorithm difficulty.Targeted instance generation can expose algorithm differences, fill gaps in instance space, or create diverse collections.Source: §3.2 · pp. 12–13

3.3 Available Benchmark Sets

• Available resources span artificial discrete, real-parameter, mixed-representation, constrained, dynamic, expensive, multimodal, interdependent, and real-world optimization problems.Many suites provide online documentation and code, while dynamic benchmarks should allow changes such as severity and frequency to be configured.Source: §3.3 · pp. 13–14

3.4 Open Issues

• Benchmarking faces too few reusable real-world instances, limited availability of diverse instances and source code, and risks that benchmark-tuned performance will not generalize.Fixed or artificial test suites can encourage tuning to a small instance set, while single-shot real-world problems hinder generalizable conclusions.Source: §3.4 · p. 16
• Noisy real-world evaluations may be non-normal, time-varying, or state-dependent, requiring validation mechanisms beyond repeated runs and robust exploration–exploitation strategies.The section also urges researchers to qualify claims by the benchmark suite and learn about both problems and algorithms.Source: §3.4 · p. 16

4.1 Algorithm Families

• Comparing algorithm instances from different families is useful for assessing the quality of different algorithmic ideas, although classifications are fuzzy and subjective because hybridization is common [Birattari et al., 2003, Boussa¨ıd et al., 2013, Stork et al., 2020].Source: §4.1 · pp. 16–17

4.2 Challenges and Guidelines for the Practitioner

• Select the portfolio according to problem information, including gradients, decision-space type, variable interactions, objective-landscape shape, and prior landscape or performance evidence [Kerschke et al., 2019].Benchmark data repositories can support the collection and use of this information [Wang et al., 2020].Source: §4.2 · p. 17
• Match algorithm choices and comparisons to computational budget, current state of the art, and properly tuned hyperparameters, because outdated methods, budget-dependent performance, or poor configurations can bias results [Beiranvand et al., 2017, Eiben and Smit, 2011].Surrogate-assisted methods tend to suit small budgets, whereas evolution strategies tend to be more competitive for medium and large budgets; automated tuning is highly recommended.Source: §4.2 · pp. 17–18
• Control initialization and stopping criteria carefully: shared starting points help prevent seed-related bias, while unsupported or ignored stopping limits can substantially bias evaluation.Initialization effects depend on random seeds, starting points, sampling strategy, and problem-instance difficulty; implementations may not respect objective-function evaluation limits.Source: §4.2 · pp. 18–19

4.3 Challenges and Open Issues

• Benchmarking needs common data formats, interfaces, and compatible software, alongside more complete algorithm descriptions and accessible implementations, especially for complex surrogate-assisted heuristics.Identifying relevant algorithms, datasets, and papers is laborious, and missing parameter or component details remain a major bottleneck.Source: §4.3 · p. 19

5 How to Measure Performance?

• Performance can be assessed by how quickly algorithms reach a target, what quality they reach within a budget, or their entire anytime time-quality curve.Fixed-budget results are well-defined, whereas fixed-target statements are often easier to interpret; unsuccessful fixed-target runs require explicit treatment. The appropriate perspective depends on the application.Source: §5 · p. 19

5.1 Measuring Time

• Best practice is to report both Function Evaluations (FEs) and CPU time, separating expensive evaluation time from algorithm time when necessary.CPU time is hardware- and implementation-sensitive, while FEs are machine-independent but can misrepresent elapsed time when algorithms have different evaluation complexity; domain-specific step counts may help. In surrogate-based optimization, separate timing reveals whether FEs remain the limiting factor.Source: §5.1 · p. 20

5.2 Measuring Solution Quality

• Solution quality is more interpretable when normalized against an optimum, lower bound, best-known solution, or specified heuristic rather than reported as raw objective values.Relative excess over the optimum is generally preferred to scale-dependent absolute differences, although continuous optimization benchmarks such as BBOB commonly focus on absolute differences; constraint optimization can sum absolute violations [Hellwig and Beyer, 2019, Kumar et al., 2020].Source: §5.2 · p. 21

5.3 Measuring Robustness

• Robustness analysis should distinguish noisy outcomes from algorithmic stochasticity and aggregate repeated, ideally independent runs using ERT, PAR/PAR10/PAR2, PQR, success probability, and feasibility rate.ERT computes consumed budget summed across all runs divided by successful runs [Auger and Hansen, 2005, Price, 1997], whereas PAR penalizes unsuccessful runs and PQR aggregates penalized runtimes using quantiles.Source: §5.3 · pp. 21–22

5.4 Open Issues

• Open issues include measuring quality and time jointly, integrating constraint-violation costs, quantifying uncertainty and multimodal spread, and capturing proximity to local or global optima.Although domains have established preferred metrics, anytime comparisons remain underused and may be valuable depending on the use case.Source: §5.4 · p. 22

6.1 Three-Level Approach

• The analysis targets algorithm comparison and competition among multiple algorithms after performance data have been collected.Source: §6.1 · p. 22
• Single-problem analysis requires many runs because stochastic algorithms can produce different results and solution paths across runs.It supports conclusions about which algorithm performs best on the specific problem instance.Source: §6.1 · p. 23
• Multiple-problem analysis compares algorithms across a benchmark problem set, with representative-value selection addressed as a separate best-practice issue.Source: §6.1 · p. 23
• The proposed three-level approach applies to both single-problem and multiple-problem analyses.Source: §6.1 · pp. 22–23
• Exploratory Data Analysis (EDA) is the first listed step in the three-level approach for analyzing experimental results.Source: §6.1 · p. 23
• The section advocates descriptive, graphical, statistical, and ELA-based methods to evaluate algorithms and address which algorithm is best or suitable for a real-world problem.These practices are presented as standard tools for stringent evaluation and potentially broader acceptance of empirically tested algorithms.Source: §6.1 · p. 23

6.2.1 Motivation

• EDA should precede statistical techniques by checking assumptions such as normality and independence, identifying patterns, and generating hypotheses for confirmatory analysis.Visual and inductive analysis lets the data suggest questions, but it does not always provide definitive answers and can introduce bias through overfitting.Source: §6.2.1 · p. 23

6.2.2 The Glorious Seven

• The seven summary statistics—mean, median, best, worst, first and third quartile, and standard deviation—describe central tendency and variability but are sensitive to data quality and sample limitations.The median is more robust than the mean with sufficient data, while best and worst values rely on single observations; quantiles can be meaningless for small samples.Source: §6.2.2 · p. 24

6.2.3 Graphical Tools

• Histograms, density plots, and boxplots summarize final-result distributions, expose outliers, and reveal distribution shape, with histograms best combined with density plots.Boxplots compactly visualize the summary statistics, whereas histogram shape depends strongly on bin size.Source: §6.2.3 · p. 24
• Convergence plots evaluate algorithm performance against function evaluations, enabling comparison of multiple algorithms’ runtime behavior and dynamics.This requires performance information at successive iterations.Source: §6.2.3 · p. 24
• Performance profiles compare algorithms using cumulative distributions of performance ratios to the best observed metric, but require a known or estimated optimum.When the optimum is unknown, using the best known solution or an experience-based guess is possible, although the latter is error-prone.Source: §6.2.3 · p. 24
• Data profiles compare derivative-free optimization algorithms by the best solutions achieved within a fixed function-evaluation budget.They provide the budget-based capability that performance profiles lack.Source: §6.2.3 · p. 24

6.3.1 Motivation

• Confirmatory analysis tests statistical hypotheses with probability models, using hypothesis tests and confidence intervals to provide precise answers for a specific experimental design.It can be misleadingly precise when the statistical context is unsuitable or assumptions are violated.Source: §6.3.1 · p. 25
• For minimization, one-sided testing formulates “a outperforms b” as H1: p(b) − p(a) > 0 against H0: p(b) − p(a) ≤ 0.This framework is motivated by cases where exploratory analysis cannot clearly resolve small performance differences; related procedures are discussed in [Amini and Barr, 1993, Barr et al., 1995, Carrano et al., 2011, Chiarandini et al., 2007, Eftimov et al., 2017, Garc´ıa et al., 2009, Golden et al., 1986, McGeoch, 1996].Source: §6.3.1 · p. 25

6.3.2 Assumptions for the Safe Use of the Parametric Tests

• Parametric tests require independence, normality, and homoscedasticity; when these assumptions hold they offer higher power, otherwise a non-parametric test should be selected.Independent random seeds satisfy independence, while normality and equal variances can be checked with statistical or graphical tests; transformations require care because they change the decision space.Source: §6.3.2 · p. 25
• Paired versus unpaired data depends on experimental design, and Common Random Numbers can create paired samples that reduce variance and improve reliability [Kleijnen, 1988, Nazzal et al., 2012].Paired data contains uniquely matched values across samples, whereas unpaired data does not.Source: §6.3.2 · pp. 25–26

6.3.3 A Pipeline for Selecting an Appropriate Statistical Test

• In single-problem analysis, t tests or Mann-Whitney U tests compare pairs, while one-way ANOVA or Kruskal-Wallis tests compare multiple algorithms before post-hoc identification of significant pairs.The appropriate choice depends on parametric assumptions and whether samples are paired or unpaired.Source: §6.3.2 · p. 25, §6.3.3 · p. 26

Multiple-problem analysis.

• For multiple-problem analysis, mean or median summaries can be used, but Deep Statistical Comparison ranks whole distributions to avoid sensitivity to outliers and small ε-neighborhood differences.Appropriate tests include t or Wilcoxon signed-rank tests for pairs, repeated-measures ANOVA or Friedman-family tests for multiple algorithms, followed by post-hoc testing after rejection.Source: Multiple-problem analysis · p. 27
• After rejecting a null hypothesis for multiple algorithms, post-hoc procedures identify contributing pairs and correct p-values, while uncontrolled pairwise comparisons can lose Family-Wise Error Rate control.For k algorithms, all-pairs testing requires k(k −1)/2 comparisons, versus k −1 comparisons against a control algorithm.Source: Multiple-problem analysis · pp. 27–28

6.4.1 Motivation

• Statistical significance can be practically meaningless when observed differences are too small to measure or are artifacts of inadequate experimental designs.For example, δ = 10−14 was statistically significant but below an assembly-line timer’s precision.Source: §6.4.1 · p. 28
• Practical significance depends on the problem and can be distorted by computer accuracy, variable types, and stopping criteria, even when statistical significance exists.These factors may produce values that do not represent algorithms’ actual performance.Source: §6.4.1 · p. 28

6.4.2 Severity: Relevance of Parametric Test Results

• Severity is a post-data analysis that evaluates how well data support hypothesis-testing decisions and addresses conclusions’ dependence on large sample sizes [Bartz-Beielstein et al., 2010, Mayo and Spanos, 2006].It represents the actual attained power separately for rejecting or not rejecting the null hypothesis.Source: §6.4.2 · p. 28

6.4.3 Multiple-Problem Analysis

• CRS4EA ranks evolutionary algorithms through a chess-style tournament, using user-defined draw limits and confidence intervals based on tournament ratings.Each game compares two algorithms’ performance measures, while the draw limit is problem-specific.Source: §6.4.3 · pp. 28–29
• pDSC preprocesses performance data using user-specified practical levels before DSC, with sequential and Monte-Carlo options for identifying relevant differences.The Monte-Carlo option avoids dependence on the order of independent runs, and pDSC rankings support both multiple- and single-problem analyses.Source: §6.4.3 · p. 29

• Benchmark-problem analysis should extract and interpret structural characteristics to support suitable algorithm design, selection, and configuration.The document does not yet address this analysis, although multiple approaches exist to improve understanding of the problem itself.Source: §6.5 · p. 29
• Problem-landscape visualizations can reveal challenges such as multimodality and help study algorithm search behavior, but most works treat visualization poorly.The continuation of the document will address this issue, including visualizing continuous problems and approximate tours for TSP instances.Source: §6.5 · p. 29

7.1 Design of Experiments (DoE)

• Design of experiments makes benchmarking more transparent and objective by determining which and how many algorithm runs are needed, while reporting tuning time prevents underestimated runtimes.DOE covers planning, conducting, analyzing, and interpreting controlled tests; adjustment time should be included in all reported running times.Source: §7.1 · p. 29

7.2 Design Decisions

• Factorial or space-filling designs are recommended over OFAT because they reduce inefficiency and can identify factor interactions, although optimal design characteristics remain an open question.Taguchi and Plackett–Burman designs support robust-cost or screening objectives, while modern space-filling designs can require fewer evaluations for nonlinear problems.Source: §7.2 · p. 30

7.3 Designs for Benchmark Studies

• A benchmark design combines problem-specific factors, algorithm-specific factors, and performance measures, with algorithm designs defining parameterized algorithm instances and problem designs specifying problem information and resources.Algorithm-specific factors include parameters such as ES population size, while problem designs include available function evaluations and problem dimension.Source: §7.3 · pp. 30–31

7.4 How to Select a Design for Benchmarking

• Benchmark design selection should address goals, test problems, algorithms, problem classes, tuning, validation, analysis, presentation, randomization, and replicability.These questions structure the experimental plan across the benchmark’s objectives, methods, evaluation, reporting, and reproducibility requirements.Source: §7.4 · p. 31

7.5 Tuning Before Benchmarking

• Fair comparisons require tuning algorithms before benchmarking when possible; otherwise, limited space-filling tuning or common defaults provide progressively weaker alternatives with explicit limitations.Full per-problem tuning can compare methods at peak performance, whereas sparse tuning avoids misconfiguration but may miss peak performance; default-only comparisons omit problem-specific parameter optimization.Source: §7.5 · p. 31

7.6 Open Issues

• Open issues include when to prefer uniform, Latin hypercube, low-discrepancy, or other space-filling designs and how to assess design quality for unknown, misspecified, or multi-objective functions.Design-quality assessment becomes difficult when objective-function properties are unavailable, assumptions such as linearity are wrong, or no single objective exists in MOO.Source: §7.6 · p. 32

8.1 General Recommendations

• Reports should present suitable statistical test results, plan experiments without rushing, report negative results, and follow eight guidelines addressing reproducibility, influential factors, measures, parameters, design, comparisons, variability, and comprehensiveness.Source: §8.1 · p. 32

8.2 Reporting Methodologies

• The proposed methodology structures reports from objectives and planning through hypotheses, reproducible experimental design, results, observations, and subjective interpretation.Separating results, analysis, and conclusions allows others to draw different conclusions from the same observations; labels make this structure explicit.Source: §8.2 · p. 33
• Applying labels to otherwise mixed report components and maintaining experiment journals improves structural clarity, later reference, overview, and avoidance of repeated tests.Preuss [2015] refined the methodology by emphasizing separate results, analysis, and conclusions.Source: §8.2 · p. 33

8.3 Open Issues

• Negative results document failed approaches, reveal limitations, and prevent duplicated effort, but papers presenting them are regularly less accepted than papers reporting improvements or outperforming algorithms.This limited acceptance is identified as an open issue, with Gent and Walsh [1994] cited in connection with the problem.Source: §8.3 · p. 34

Reproducibility concepts

• Replicability uses different teams and experimental setups to obtain the same result, making it the most scientifically useful but hardest level to achieve.Repeatability keeps the same team and setup, while reproducibility changes the team but retains the setup and author artifacts.Source: §9 · p. 34

Practical guidelines and tools

• Code versioning, data repositories, reproducible documents, and software environments provide practical support for repeatability and reproducibility.Examples include Subversion, Git, Zenodo, Rmarkdown, Jupyter notebooks, OSF, CodeOcean, and Docker [Gent et al., 1997, Johnson, 2002a].Source: §9 · p. 34

Challenges of replicability

• Replicability cannot generally reproduce exact results; it instead requires field-accepted statistical guidelines showing that conclusions hold under different but similar experimental conditions.For algorithm benchmarks, what counts as similar conditions has no simple answer.Source: §9 · p. 34
• Preregistration fixes hypotheses and experimental designs and reduces spurious results from adaptive data analysis, but adaptive computational experiments remain difficult to control before registration.Computational experiments are easier to run and rerun than randomized controlled trials, increasing opportunities for adaptation before registration.Source: §9 · pp. 34–35

• The survey organizes benchmarking best practice around eight essential topics: goals, problems, algorithms, performance, analysis, design, presentation, and reproducibility.These topics define the article’s structure and are intended for consideration in every benchmark study.Source: §10 · p. 35
• It is intended as a starting guide, not a textbook, combining recommendations, best-practice examples, open issues, and extensive references.The guide covers classical and recent work and supports the setup of benchmark studies.Source: §10 · p. 35
• Proposed follow-up activities include tutorials, workshops, explanatory videos, software tools, beginner checklists, and discussion sections on controversial topics.The videos would explain experiment setup, result analysis, and reporting of important findings.Source: §10 · p. 35
• The checklist asks whether studies clearly state goals, justify problem instances, compare relevant competitors, use adequate performance measures, and apply statistical standards.These questions are intended to guide authors and reviewers.Source: §10 · p. 35
• Transparent standards should improve review quality and objectivity, but authors should justify their chosen designs, tools, measures, and study goals rather than follow mandated specifics.The checklist also covers efficient and fair design, avoiding cherry-picking, clear presentation, and data and code availability.Source: §10 · pp. 35–36
• The survey frames benchmarking as an ongoing public discussion, alongside initiatives such as the Benchmarking Network [Weinand et al., 2020], and accepts that it may raise more questions than answers.Its final outlook emphasizes continued questioning and discussion.Source: §10 · p. 36

• Organizations and conferences include AAAI, ACM, CEC, IEEE, and GECCO.AAAI is the Association for the Advancement of Artificial Intelligence; ACM is the Association for Computing Machinery; CEC is the Congress on Evolutionary Computation; IEEE is the Institute of Electrical and Electronics Engineers; GECCO is the Genetic and Evolutionary Computation Conference.Source: Glossary · p. 37
• Benchmarking resources and frameworks include BBOB, COCO, ASlib, ELA, and NFLT.BBOB means Black-Box-Optimization-Benchmarking; COCO means Comparing Continuous Optimizers; ASlib means Algorithm Selection Library; ELA means Exploratory Landscape Analysis; NFLT means no free lunch theorem.Source: Glossary · pp. 37–38
• Optimization algorithms and configuration methods include BFGS, CMA-ES, EDAlgo, EGO, ES, irace, ParamILS, PSO, SANN, SMAC, and SPOT.These abbreviations expand to named optimization algorithms, algorithm-selection or configuration procedures, and a parameter-optimization toolbox.Source: Glossary · p. 37
• Benchmarking, experimentation, and analysis terms include CRN, CRS4EA, DACE, EDA, ERT, FE, OFAT, and pDSC.They refer to Common Random Numbers, Chess Rating Systems for Evolutionary Algorithms, Design and Analysis of Computer Experiments, Exploratory Data Analysis, Expected Running Time, Function Evaluation, One-factor-at-a-time, and practical Deep Statistical Comparison.Source: Glossary · p. 37
• Optimization algorithms and configuration methods also include irace, ParamILS, PSO, SANN, SMAC, and SPOT.irace means iterated racing; ParamILS means Iterated Local Search in Parameter Configuration Space; PSO means Particle Swarm Optimization; SANN means Simulated Annealing; SMAC means Sequential Model-based Algorithm Configuration; SPOT means Sequential Parameter Optimization Toolbox.Source: Glossary · pp. 37–38
• Optimization problems and decision frameworks include LABS, MACODA, MAX-SAT, MOO, PBO, SAT, and TSP.These abbreviations denote Low Auto-correlation Binary Sequence, Many Criteria Optimization and Decision Analysis, Maximum Satisfiability, Multi-Objective Optimization, Pseudo-Boolean Optimization, Boolean Satisfiability, and Traveling Salesperson Problem.Source: Glossary · pp. 37–38