English
Estimation-of-distribution algorithms (EDAs) are general-purpose optimization heuristics that iteratively evolve a probabilistic model of the search domain. Shortly after their inception more than 20~years ago, EDAs employed in practice captured complex (multivariate) dependencies among the problem variables via Bayesian networks, allowing them to solve hard optimization problems and to provide insights into the problem space. In contrast, to this date, all theoretical guarantees for such EDAs assume independence (i.e., univariate dependencies) among all problem variables. With this project, we will reduce this massive gap between theory and practice and prove the first theoretical results for such multivariate EDAs. To this end, we naturally extend the known results for univariate EDAs by incorporating increasing degrees of dependence. This constitutes a milestone for the theory of EDAs and for the theoretical domain of randomized optimization heuristics as a whole.
