26.10.2016 - Francesco Quinzan
EAs in Real-World Optimization: Noise, Performance, Applications
When dealing with optimization of real-world numerical models, it is often unfeasible to perform correlation via direct methods. This is the case of the thermal analysis of bespoke electro-mechanical systems for extreme harsh environments, such as actuators and wireless sensors. Evolutionary Algorithms (EAs) are generic population-based optimization algorithms, useful to approach such problems.
Even though in the last decade theoretical results have been presented regarding the running time of EAs, there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques, such as statistical resampling. We report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions.
We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-off between noise reduction and the computational cost of resampling. We perform experiments to find the optimal parameters at a given noise intensity for a mutation-only evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We observe how the optimal parameter depends on the noise intensity for the different algorithms. We locate the point where statistical resampling costs more than it is worth in terms of run time.
We find that the EA requires the highest number of resamples to obtain the best speed-up, whereas crossover reduces both the run time and the number of resamples required. We find that EDA-like algorithms require no resampling, and can handle noise implicitly. Interestingly, we observe that all tested algorithms exhibit high variance for increasing noise. We plan to combine the latter observation with rigorous analysis to define the optimal re-start strategy, with the hope of further improving performance.