Skip to Main content Skip to Navigation
New interface
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 metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Geoffrey Pruvost Connect in order to contact the contributor
Submitted on : Wednesday, July 15, 2020 - 10:29:41 AM
Last modification on : Tuesday, November 22, 2022 - 2:26:16 PM
Long-term archiving on: : Tuesday, December 1, 2020 - 7:04:39 PM


Files produced by the author(s)



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⟩



Record views


Files downloads