Skip to Main content Skip to Navigation
Conference papers

Surrogate-assisted Multi-objective Combinatorial Optimization based on Decomposition and Walsh Basis

Abstract : We consider the design and analysis of surrogate-assisted algorithms for expensive multi-objective combinatorial optimization. Focusing on pseudo-boolean functions, we leverage existing techniques based on Walsh basis to operate under the decomposition framework of MOEA/D. We investigate two design components for the cheap generation of a promising pool of offspring and the actual selection of one solution for expensive evaluation. We propose different variants, ranging from a filtering approach that selects the most promising solution at each iteration by using the constructed Walsh surrogates to discriminate between a pool of offspring generated by variation, to a substitution approach that selects a solution to evaluate by optimizing the Walsh surrogates in a multi-objective manner. Considering bi-objective NK landscapes as benchmark problems offering different degree of non-linearity, we conduct a comprehensive empirical analysis including the properties of the achievable approximation sets, the anytime performance, and the impact of the order used to train the Walsh surrogates. Our empirical findings show that, although our surrogate-assisted design is effective, the optimal integration of Walsh models within a multi-objective evolutionary search process gives rise to particular questions for which different trade-off answers can be obtained.
Document type :
Conference papers
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-02898952
Contributor : Geoffrey Pruvost <>
Submitted on : Wednesday, July 15, 2020 - 10:29:41 AM
Last modification on : Wednesday, August 26, 2020 - 3:14:55 AM

File

GECCO_2020_CR.pdf
Files produced by the author(s)

Identifiers

Citation

Geoffrey Pruvost, Bilel Derbel, Arnaud Liefooghe, Sébastien Verel, Qingfu Zhang. Surrogate-assisted Multi-objective Combinatorial Optimization based on Decomposition and Walsh Basis. GECCO '20 - Genetic and Evolutionary Computation Conference, Jul 2020, Cancun, Mexico. ⟨10.1145/3377930.3390149⟩. ⟨hal-02898952⟩

Share

Metrics

Record views

53

Files downloads

205