Walsh functions as surrogate model for pseudo-boolean optimization problems
| Autor: | Cyril Fonlupt, Sébastien Verel, Florian Leprêtre, Virginie Marion |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique Signal et Image de la Côte d'Opale (LISIC), Université du Littoral Côte d'Opale (ULCO) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Continuous optimization
Mathematical optimization Optimization problem Combinatorial optimization Mathematical model Computer science business.industry Local search 0102 computer and information sciences 02 engineering and technology [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] 01 natural sciences Empirical study [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Surrogate model 010201 computation theory & mathematics Walsh function 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Local search (optimization) Surrogate model/fitness approximation Representation (mathematics) business |
| Zdroj: | The Genetic and Evolutionary Computation Conference (GECCO 2019) The Genetic and Evolutionary Computation Conference (GECCO 2019), Jul 2019, Prague, Czech Republic. pp.303-311, ⟨10.1145/3321707.3321800⟩ GECCO |
| DOI: | 10.1145/3321707.3321800⟩ |
| Popis: | International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|