Source-linked AI summary
Empirical review of standard benchmark functions using evolutionary global optimization
Johannes M. Dieterich, Bernd Hartke
TL;DR
The paper examines whether standard optimization benchmarks meaningfully distinguish genetic-algorithm variants or reflect real-world scaling. It tests standard functions alongside Lunacek’s function and tunable landscapes generated from random Gaussians. Standard benchmarks show sub-quadratic scaling, while the Gaussian class offers greater difficulty and tunability.
Problem
Method
The authors use a genetic algorithm to test standard benchmark functions and compare them with Lunacek’s deceptive function and landscapes generated by randomly distributed Gaussians.
Source: §1 · p. 3, §4 · p. 16, §5 · p. 18Results
Standard benchmarks showed sub-quadratic scaling and often did not support statistically significant comparisons of crossover operators or local optimization; real-world applications can scale cubically at best and often worse.
Source: §6 · p. 20Takeaways & Limitations
The authors advocate using deceptive and tunable, more complex benchmark functions alongside standard benchmarks for algorithm development and benchmarking.
Source: §5 · p. 18, §6 · p. 20Ten successive runs provide only a rough estimate of the maximum, while capturing the full range of deviations would require infinitely many runs.
Source: §3.6 · p. 14
Abstract
from arXiv · showhide
We have employed a recent implementation of genetic algorithms to study a range of standard benchmark functions for global optimization. It turns out that some of them are not very useful as challenging test functions, since they neither allow for a discrimination between different variants of genetic operators nor exhibit a dimensionality scaling resembling that of real-world problems, for example that of global structure optimization of atomic and molecular clusters. The latter properties seem to be simulated better by two other types of benchmark functions. One type is designed to be deceptive, exemplified here by Lunacek's function. The other type offers additional advantages of markedly increased complexity and of broad tunability in search space characteristics. For the latter type, we use an implementation based on randomly distributed Gaussians. We advocate the use of the latter types of test functions for algorithm development and benchmarking.
1 Introduction
The authors argue that conventional benchmark functions may be too simple to distinguish algorithm variants or reflect real-world dimensionality scaling. They extend testing to higher dimensions and alternative benchmarks, aiming to establish an empirical baseline for scaling comparisons.
1 Introduction
- Traditional benchmark functions may be too simple to compare algorithm variants meaningfully or to support conclusions about real-world optimization performance.The authors note that some functions can even become easier as dimensionality increases.Source: §1 · p. 2
- The authors exclude benchmark modifications such as rotations, translations, and randomized noise because added parameters can reduce comparability across results.Source: §1 · p. 2
- The study measures global optimization steps across dimensions up to 500, and up to 10000 for one function, to examine crossover and local-optimization effects.It compares standard benchmarks with function types considered more challenging and closer to real-world problems in some respects.Source: §1 · p. 3
2 Methods and Techniques
The methods use a pool-based genetic algorithm in ogolem to benchmark crossover variants, mutation, mating, and optional local optimization. Results are measured in global optimization steps under a fixed benchmark setup.
2 Methods and Techniques
- Benchmarks used ogolem’s Java genetic algorithm with pool-based updates and 24 concurrent threads.Pool updates eliminate serial bottlenecks and reduce the number of tunable parameters; benchmark tunables were kept constant.Source: §2 · p. 3
- Crossover variants differ in the number and placement of genome cuts, randomized with linear or sharpened Gaussian distributions.The random-number generator is the standard JVM PRNG.Source: §2 · p. 4, Table 2 · p. 4
- All tests use 5% one-point genotype mutation and the same mating procedure; optional local optimization uses L-BFGS with analytical gradients.Mating selects one parent randomly and the other by a fitness-based rank procedure.Source: §2 · p. 4
- Each global optimization step comprises mating, crossover, mutation, and optional local optimization; only the fitter child is considered for pool entry.A fitness-diversity criterion rejects duplicates or near-duplicates, and five independent runs were used for local-optimization tests.Source: §2 · p. 5
3 Standard benchmark functions
Popular analytic benchmark functions have known minima and often extend to arbitrary dimensions, but most neither distinguish algorithm variants nor reflect real-world problem difficulty.
3.1 Ackley’s Function
- Ackley scaled linearly without local optimization; a modified gradient decoupled dimensions, enabling constant-effort solutions up to 10,000 dimensions through local optimization.The modified problem could be solved by locally optimizing a few randomized individuals.Source: §3.1 · pp. 6, 8
3.2 Rastrigin’s Function
- Rastrigin scaled excellently without local optimization; with it, mutation-only Holland had by far the best prefactor and scaling.The authors suggest repeated rediscovery of nonoptimal minima may account for the high number of global steps.Source: §3.2 · pp. 9–10
3.3 Schwefel’s Function
- Schwefel achieved sub-quadratic scaling with and without local optimization, which the authors considered too easy for a realistic test case.Local optimization could increase scaling from 1.15 to 1.75.Source: §3.3 · p. 11
3.4 Schaffer’s F7 function
- Schaffer’s F7 discriminated implementations (Germany quartic; others linear), but 40D likely makes multi-cut performance misleading; mutation-only still matched crossover.The authors caution that the sublinear scaling seen at 40D should increase toward linear at higher dimensions.Source: §3.4 · pp. 11–12
3.5 Schaffer’s F6 Function
- Schaffer’s F6 difficulty comes from potential maxima growing near the global minimum; local optimization erased the Germany–Portugal crossover difference seen without it.The authors nevertheless judged this two-dimensional function readily solvable with or without local optimization.Source: §3.5 · pp. 13–14
3.6 Scatter of the benchmarking results
- Ten runs gave a rough, not exhaustive, view of scatter; enhanced statistics preserved operator trends, while explanations for spread patterns remained speculative.The authors note that stochastic deviations cannot be fully captured without infinitely many runs.Source: §3.6 · pp. 14–15, Table 4 · p. 14
4 Gaussian benchmark class
The authors introduce randomly distributed Gaussian landscapes as a tunable alternative to conventional benchmarks, intended to better reflect the difficulty of global optimization problems. Their GRUNGE tests show similar-scale outcomes across algorithms, while also exposing the effects of initialization and local optimization.
4 Gaussian benchmark class
- The authors seek benchmarks that are difficult to solve, extend to higher dimensions, support analytical gradients, and have multiple minima but one known global minimum.They explain that real-world chemical optimization can be considerably more challenging than the conventional benchmarks considered earlier.Source: §4 · p. 15
- GRUNGE combines randomized Gaussians whose count, dimensionality, and density tune landscapes from overlapping “mountain ranges” to isolated “golf courses.”The Gaussian representation also provides an analytical gradient, and the authors describe the functions as readily extendable to higher dimensions.Source: §4 · pp. 15–16
- GRUNGE does not deliberately create deceptive landscapes, but its uncorrelated random features make it harder than traditional benchmarks in the authors’ experience.The authors caution that realistic problems may lie between traditional benchmarks and GRUNGE in both landscape characteristics and difficulty.Source: §4 · p. 16
- All algorithms’ three-run averages on GRUNGE[10,2000] fall within the same order of magnitude; without local optimization, this benchmark is extremely difficult to solve.The authors note that two locally optimized initial parameter sets already contained the global optimum, motivating tests at higher dimensionality.Source: Table 5 · p. 17, §4 · p. 17
5 Lunacek’s function
Lunacek’s function combines Rastrigin and double-sphere components to create a deceptive landscape. The authors question how well its double-funnel design represents real-world cluster optimization, while noting that diversity-preserving search can solve a 30-dimensional case.
5 Lunacek’s function
- Lunacek’s function is a Rastrigin–double-sphere hybrid designed to model double-funnel landscapes, with the double-sphere term creating a fake minimum in each dimension.For the stated settings s = 0.7 and d = 1.0, the optimum is located at x_i = 2.5.Source: §5 · p. 18
- The authors dispute that Lunacek’s double-funnel design establishes a general model of real-world cluster difficulty, noting that LJ38’s proposed funnel separation is not established.Even if two funnels exist in the 108-dimensional search space, the authors argue that this is not necessarily an overwhelming challenge and differs from the function’s construction.Source: §5 · p. 18
- The authors support the function’s difficulty in tests on 30-dimensional cases, while noting that more sophisticated global search can reduce it.They describe maintaining population diversity as a way to prevent premature collapse into a non-global solution.Source: §5 · p. 19
- Static niching makes the previously unsolvable Lunacek function solvable in 30 dimensions, but its grid-cell count impedes higher-dimensional scaling and it slows cases solvable without niches.The authors expect more advanced strategies, such as dynamic grids, to help at higher dimensionalities.Source: §5 · p. 19, Table 6 · p. 19
6 Summary and Outlook
The paper finds that conventional benchmarks can show sub-quadratic scaling and may not distinguish algorithm variants, unlike the behavior observed in real-world applications. It presents deceptive functions and tunable Gaussian landscapes as alternatives, while cautioning that further work is needed to establish how real-world problems compare.
6 Summary and Outlook
- Conventional benchmarks showed sub-quadratic scaling, unlike real-world applications, where scaling was cubic at best and often worse; they also often failed to distinguish crossover operators or local optimization.The authors conclude that such benchmarks alone are not relevant test beds for practical global cluster structure optimization or similar applications.Source: §6 · p. 20
- Random-Gaussian landscape generators allow search-space features to be tuned from “mountain ranges” to “golf courses,” and their uncorrelated minima make them harder than traditional benchmarks in the reported tests.The Gaussian count, depth, width, density, and dimensionality can be varied.Source: §6 · p. 20
- Deceptive benchmarks are designed to mislead global optimization, and their difficulty can be reduced by ensuring sufficient population diversity.The authors describe this deceptive class as a subclass of landscape generators when the setup is sufficiently flexible.Source: §6 · p. 20
- Further work is needed to test the authors’ suspicion that real-world problems fall between traditional simple benchmarks and less-correlated, more-deceptive functions.Their claim that traditional functions should not be used alone is framed around algorithm development and performance assessment.Source: §6 · p. 20