New EDA Method Optimizes Sparse Black-Box Problems

Estimation-of-Distribution Algorithms (EDAs) are a robust class of evolutionary methods particularly effective for black-box optimization problems where the objective function's structure is largely unknown. Unlike traditional evolutionary algorithms that rely on predefined mutation and crossover operators, EDAs generate new solutions by fitting a probability distribution to the best-performing individuals and then sampling from it. A significant limitation of existing EDAs has been their inability to effectively handle sparse parameter spaces, where most coefficients in an optimal solution are exactly zero. Current solutions for sparse black-box optimization often reintroduce the very problem EDAs aim to avoid: the need for hand-crafted sparsity operators or complex multi-level schemes. This research introduces a generalization of EDAs to sparse parameter spaces by employing multivariate zero-inflated Gaussian (ZIG) distributions as the sampling law. This allows for the joint optimization of both sparsity patterns and the values of active parameters, bypassing the need for manual operator design. The proposed ZIG-EDA demonstrates faster convergence and higher returns on benchmarks like Lunar Lander, while also finding more parsimonious solutions.