Per Instance Algorithm Configuration for Continuous Black Box Optimization

Abstract : This PhD thesis focuses on the automated algorithm configuration that aims at finding the best parameter setting for a given problem or a' class of problem. The Algorithm Configuration problem thus amounts to a metal Foptimization problem in the space of parameters, whosemetaFobjective is the performance measure of the given algorithm at hand with a given parameter configuration. However, in the continuous domain, such method can only be empirically assessed at the cost of running the algorithm on some problem instances. More recent approaches rely on a description of problems in some features space, and try to learn a mapping from this feature space onto the space of parameter configurations of the algorithm at hand. Along these lines, this PhD thesis focuses on the Per Instance Algorithm Configuration (PIAC) for solving continuous black boxoptimization problems, where only a limited budget confessionnalisations available. We first survey Evolutionary Algorithms for continuous optimization, with a focus on two algorithms that we have used as target algorithm for PIAC, DE and CMAFES. Next, we review the state of the art of Algorithm Configuration approaches, and the different features that have been proposed in the literature to describe continuous black box optimization problems. We then introduce a general methodology to empirically study PIAC for the continuous domain, so that all the components of PIAC can be explored in real Fworld conditions. To this end, we also introduce a new continuous black box test bench, distinct from the famous BBOB'benchmark, that is composed of a several multiFdimensional test functions with different problem properties, gathered from the literature. The methodology is finally applied to two EAS. First we use Differential Evolution as'target algorithm, and explore all the components of PIAC, such that we empirically assess the best. Second, based on the results on DE, we empirically investigate PIAC with Covariance Matrix Adaptation Evolution Strategy (CMAFES) as target algorithm. Both use cases empirically validate the proposed methodology on the new black box testbench for dimensions up to100.
Complete list of metadatas

Cited literature [334 references]  Display  Hide  Download

https://hal.inria.fr/tel-01669527
Contributor : Abes Star <>
Submitted on : Monday, February 19, 2018 - 1:29:07 PM
Last modification on : Tuesday, April 16, 2019 - 9:25:06 AM

File

75926_BELKHIR_2017_diffusion.p...
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01669527, version 2

Citation

Nacim Belkhir. Per Instance Algorithm Configuration for Continuous Black Box Optimization. Artificial Intelligence [cs.AI]. Université Paris-Saclay, 2017. English. ⟨NNT : 2017SACLS455⟩. ⟨tel-01669527v2⟩

Share

Metrics

Record views

416

Files downloads

614