A benchmark generator for scenario-based discrete optimization

• Published in: Computational optimization and applications 2024-05, Vol.88 (1), p.349-378
• Main Authors: de Moraes, Matheus Bernardelli, Coelho, Guilherme Palermo
• Format: Article
• Language: English
• Subjects: Benchmarks; Black boxes; Convex and Discrete Geometry; Empirical analysis; Evolutionary algorithms; Knapsack problem; Management Science; Mathematics; Mathematics and Statistics; Multiple objective analysis; Operations Research; Operations Research/Decision Theory; Optimization; Statistics
• ISSN: 0926-6003; 1573-2894
• DOI: 10.1007/s10589-024-00551-1

Multi-objective evolutionary algorithms (MOEAs) are a practical tool to solve non-linear problems with multiple objective functions. However, when applied to expensive black-box scenario-based optimization problems, MOEA’s performance becomes constrained due to computational or time limitations. Scenario-based optimization refers to problems that are subject to uncertainty, where each solution is evaluated over an ensemble of scenarios to reduce risks. A primary reason for MOEA’s failure is that algorithm development is challenging in these cases as many of these problems are black-box, high-dimensional, discrete, and computationally expensive. For this reason, this paper proposes a benchmark generator to create fast-to-compute scenario-based discrete test problems with different degrees of complexity. Our framework uses the structure of the Multi-Objective Knapsack Problem to create test problems that simulate characteristics of expensive scenario-based discrete problems. To validate our proposition, we tested four state-of-the-art MOEAs in 30 test instances generated with our framework, and the empirical results demonstrate that the suggested benchmark generator can analyze the ability of MOEAs in tackling expensive scenario-based discrete optimization problems.