Complexity of model learning in EDAs: multi-structure problems

Many of the real-world problems can be decomposed into a number of sub-problems for which the solutions can be found easier. However, proper decomposition of large problems remains a challenging issue, especially in optimization, where we need to find the optimal solutions more efficiently. Estimation of distribution algorithms (EDAs) are a class of evolutionary optimization algorithms that try to capture the interactions between problem variables when learning a probabilistic model from the population of candidate solutions. In this paper, we propose a type of synthesized problems, specially designed to challenge this specific ability of EDAs. They are based on the principal idea that each candidate solution to a problem may be simultaneously interpreted by two or more different structures where only one is true, resulting in the best solution to that problem. Of course, some of these structures may be more likely according to the statistics collected from the population of candidate solutions, but may not necessarily lead to the best solution. The experimental results show that the proposed benchmarks are indeed difficult for EDAs even when they use expressive models such as Bayesian networks to capture the interactions in the problem.