Walsh functions as surrogate model for pseudo-boolean optimization problems

Abstract : Surrogate-modeling is about formulating quick-to-evaluate mathematical models, to approximate black-box and time-consuming computations or simulation tasks. Although such models are well-established to solve continuous optimization problems, very few investigations regard the optimization of combinatorial structures. These structures deal for instance with binary variables, allowing each compound in the representation of a solution to be activated or not. Still, this field of research is experiencing a sudden renewed interest, bringing to the community fresh algorithmic ideas for growing these particular surrogate models. This article proposes the first surrogate-assisted optimization algorithm (WSaO) based on the mathematical foundations of discrete Walsh functions, combined with the powerful grey-box optimization techniques in order to solve pseudo-boolean optimization problems. We conduct our experiments on a benchmark of combinatorial structures and demonstrate the accuracy, and the optimization efficiency of the proposed model. We finally highlight how Walsh surrogates may outperform the state-of-the-art surrogate models for pseudo-boolean functions.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

Contributeur : Florian Leprêtre <>
Soumis le : lundi 22 juillet 2019 - 10:04:01
Dernière modification le : mardi 23 juillet 2019 - 01:21:10


Fichiers produits par l'(les) auteur(s)




Florian Leprêtre, Sébastien Verel, Cyril Fonlupt, Virginie Marion. Walsh functions as surrogate model for pseudo-boolean optimization problems. The Genetic and Evolutionary Computation Conference (GECCO 2019), Jul 2019, Prague, Czech Republic. pp.303-311, ⟨10.1145/3321707.3321800⟩. ⟨hal-02190141⟩



Consultations de la notice


Téléchargements de fichiers