Algorithmes parallèles et basés sur méta-modèles pour la résolution de problèmes d'optimisation coûteux
Guillaume Briffoteaux · theses.fr (ABES) · 2022
Combining machine learning, parallel computing and optimization gives rise to Parallel Surrogate-Based Optimization Algorithms (P-SBOAs). These algorithms are useful to solve black-box computationally expensive simulation-based optimization problems where the function to optimize relies on a computationally costly simulator. In addition to the search landscape topography, that may exhibit features complicating the optimization, the search is limited by a computational budget due to the objective function expensiveness.This thesis focuses on the design of P-SBOAs to deal with various search landscape characteristics and computational budgets. The distinction between very and moderately expensive problems is introduced through the definition of the budget as a limited time on a restricted amount of computing resources. The three dimensions of the design space of P-SBOAs as considered in this work are the surrogate model, the definition of promisingness of new candidate solutions and the coupling between the optimizer and the surrogate. On the one hand, machine learning is triggered to build surrogate models that imitate the simulator in order to evaluate and/or locate new promising solutions in a fast way. On the other hand, parallel computing is leveraged to perform multiple simulations simultaneously in order to reduce the execution time. The overall challenge consists in adequately allocating the budget to the tasks of simulation, surrogate training and acquisition of new solutions.Surrogate models should be trained fast especially to handle moderately expensive problems where the training-set size may become significant, they should also provide adequate predictive capacity to approximate rugged landscapes and predictive uncertainty information to guide the search. The Bayesian Neural Network approximated extit{via} Monte-Carlo Dropout (BNN_MCD) is investigated as it gathers all the desired features. Firstly, it is used to build Parallel Surrogate-Assisted Evolutionary Algorithms (P-SAEAs) by evaluating and filtering candidate solutions. Secondly, it is employed along with Gaussian Processes (GPs) to design new Parallel Surrogate-Driven Algorithms (P-SDAs) where sub-surrogates are optimized in parallel to produce multiple new promising solutions. The promisingness of solutions is defined by dynamically changing the trade-off between exploration and exploitation during the search through ensembles of evolution controls.Systematic experiments are conducted on multiple benchmark problems as well as on a real-world application of Covid-19 control to compare an extensive range of algorithm designs. The results demonstrate that P-SAEAs are much more adapted to solve moderately expensive problems while P-SDAs are to be put forward on very expensive ones. In P-SAEAs, the definition of promisingness promoted by the numerical results consists in favoring exploration at the early stage and exploration at the latter stage of the search while more intensification is preferred in P-SDAs. The BNN_MCD surrogate model shows to perform well on multi-modal landscapes with weakly informative global structure and GPs are promoted otherwise. Consequently, a new hybrid algorithm retaining the best of P-SAEAs and P-SDAs is proposed to offer robustness with respect to the computational budgets. The novel method demonstrates a striking parallel scalability and produces the best solutions on the Covid-19 contact reduction problem featuring multi-modality and weak global structure.