TL;DR
This paper investigates how the initial design phase of surrogate-assisted optimization algorithms affects their performance. By comparing different initial design strategies (Latin Hypercube vs. random sampling) and sizes on the BBOB-2015 benchmark, they found that smaller initial designs generally lead to better performance, and the choice between LHS and random sampling has a minimal impact.
What Problem Does This Paper Address?
Many real-world optimization problems involve objective functions that are extremely expensive to evaluate, such as complex simulations in engineering or biological modeling. For these scenarios, surrogate-assisted optimization algorithms are crucial. These algorithms work by building a cheaper, approximate model (a surrogate) of the expensive objective function. A typical workflow involves an initial "design phase" where a few points are evaluated on the true function to seed the surrogate model. Then, an iterative process refines the surrogate model and suggests new points to evaluate.
However, the choices made during the design of these algorithms, particularly the initial design phase, can significantly impact their overall performance. This paper focuses on understanding how two key aspects of the initial design – the sampling strategy (Latin Hypercube Sampling vs. uniform random sampling) and the size of the initial design – affect the performance of the MATLAB Surrogate Model Toolbox (MATSuMoTo) on a standard benchmark suite.
Methods
The authors used the freely available MATLAB Surrogate Model Toolbox (MATSuMoTo) and configured it to run four different experimental setups, varying only the initial design phase:
- LHD-Default: Uses Latin Hypercube Sampling (LHS) with the default initial design size of 2*(DIM+1) function evaluations.
- LHD-2xDefault: Uses LHS but doubles the default initial design size.
- RAND-2xDefault: Uses uniform random sampling for the initial design, with the same doubled size as LHD-2xDefault.
- LHD-10xDefault: Uses LHS with ten times the default initial design size.
All variants were run on the 24 noiseless benchmark functions from the BBOB-2015 test suite. The performance was evaluated using the Expected Running Time (ERT) metric, which measures the average number of function evaluations needed to reach a certain target objective value. Statistical significance was assessed using rank-sum tests.
Datasets
The study evaluated the algorithms on the BBOB-2015 test suite, which consists of 24 noiseless, real-parameter optimization benchmark functions. These functions are designed to represent a range of challenges, including separable, ill-conditioned, and multi-modal landscapes. The experiments were conducted across various dimensions, specifically 5-D and 20-D.
Key Insights and Ideas
- Bigger isn't always better for initial designs: The most striking finding is that increasing the size of the initial design beyond the default often leads to worse performance, particularly for "any-time" scenarios (where performance is measured at any point during the optimization). This suggests that spending too many initial evaluations might not be the most efficient use of resources.
- LHS vs. Random Sampling: A Tie? For the tested configurations, there was no significant difference in performance between using Latin Hypercube Sampling (LHS) and simple uniform random sampling for the initial design, especially when the initial design size was doubled. This implies that the complexity of the sampling method might be less critical than other factors.
- The "default" might be optimal (within tested parameters): The LHD-Default configuration, with its smaller initial design and LHS, generally performed best among the tested variants. This highlights the importance of carefully tuning the initial design phase.
- Multi-modal functions are an exception: For certain multi-modal functions, the larger initial designs (specifically LHD-10xDefault) showed a slight advantage, though the results were not statistically significant. This hints that more complex landscapes might benefit from more extensive initial exploration.
Key Results
- Performance Degradation with Larger Designs: Increasing the initial design size from the default to 2x or 10x the default generally resulted in a performance loss, with a maximum loss of about a factor of 3 in 5-D and 6 in 20-D for the 10x default size.
- Minimal Impact of Sampling Type: When comparing LHD-2xDefault and RAND-2xDefault, their empirical cumulative distribution functions were nearly superimposed, indicating no significant performance difference between LHS and random sampling for the initial design in this context.
- CPU Time is Negligible: The study found that the CPU time per function evaluation was very small (less than two seconds even in 20-D), making it negligible in the context of expensive optimization problems.
Limitations and Future Work
The authors acknowledge that their study is preliminary and does not cover all possible initial design choices. They specifically mention that MATSuMoTo also offers symmetric LHS and two-level factorial designs, which were not investigated. Future work could explore these additional design options and conduct a more exhaustive parameter sweep to further refine the understanding of optimal initial design strategies. The authors also suggest that even smaller initial designs than the default might further improve performance.
Summary updated