Resumo

by Matheus Bernardelli de Moraes, Guilherme Palermo Coelho, presented at 2022 IEEE Congress on Evolutionary Computation (CEC), September 2022.

Abstract

Abstract—Many real-world optimization problems involve time-consuming fitness evaluation. To reduce the computational cost of expensive evaluations, researchers have been developing surrogate models to approximate the objective function values of unevaluated candidate solutions. However, most of the research has been developed for continuous optimization problems, while only a few of them address surrogate modeling for expensive multi-objective Combinatorial Optimization Problems (COPs). COPs have inherently different challenges than continuous opti- mization. For example, (i) many COPs have categorical and nom- inal decision variables; (ii) they often require the combination of both global and local search mechanisms; and (iii) some of them have constraints that make them NP-hard problems, which makes them even more difficult to solve with a reasonable number of fitness evaluations. To address these issues, this paper proposes a surrogate-assisted evolutionary algorithm that combines the decomposition-based algorithm MOEA/D, Tabu Local Search, and Random Forest as a surrogate model to approximate the objective function of unevaluated individuals on multi-objective COPs. Experiments were conducted on constrained and uncon- strained well-known multi-objective combinatorial optimization benchmark problems. The experimental results demonstrate that the proposed design outperforms state-of the-art algorithms without violating the restrictions in the number of objective function evaluations, which indicates that it may be suitable for real-world expensive multi-objective COPs.

DOI: https://doi.org/10.1109/CEC55065.2022.9870412

Access the full paper.