Theory of Estimation-of-Distribution Algorithms (TEDA)

• Applicant: Professor Dr. Tobias Friedrich, Ph.D.
• Subject Area: Theoretical Computer Science
• Term: since 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 440936840

Large optimization problems are regularly not efficiently solvable by standard optimization techniques, as the objective function is only indirectly accessible. In such black-box optimization settings, heuristics are commonly applied. Popular approaches are general-purpose optimizers inspired by nature, such as evolutionary computation. There are two cardinal representations of the evolutionary search status: multisets of solutions evolved via mutation, crossover, and selection; and probabilistic models that learn from samples. This corresponds to the frameworks of evolutionary algorithms (EAs) and estimation-of-distribution algorithms (EDAs), respectively. While EAs have been studied theoretically for more than three decades, the theoretical analysis of EDAs only gained momentum recently.Our aim is to advance the rigorous understanding of EDAs. In particular, we want to reduce the gap between the theoretical results of EAs and EDAs, providing a more complete picture of the capabilities of evolutionary computation in general. While EAs and EDAs are structurally different, their optimization efficiencies are surprisingly correlated. Nonetheless, both approaches have their individual advantages, which we want to uncover.The first step of this scientific endeavor will be the development of new stochastic tools that are more suited for the analysis of EDAs, as most of the current tools were developed with EAs in mind. In particular, we plan to provide new drift theorems for situations that are common for EDAs but rarely occur in EAs. The newly developed tools will help tackle classes of EDAs that have not been theoretically analyzed before. We further plan to analyze EDAs in settings where they may be better suited than EAs. An example for such scenarios are noisy environments, where this has been observed empirically but not understood mathematically. In addition to that, EDAs have only scarcely been considered in settings with multiple local optima. Given their more global view on the search space, we believe that EDAs can bypass local optima more efficiently than EAs. Finally, the project should give sufficient insights into EDAs such that we can create new hybrid algorithms combining the advantages of both EAs and EDAs.

• DFG Programme: Research Grants
• Co-Investigator: Dr. Timo Kötzing