Theory of Estimation-of-Distribution Algorithms (TEDA)

分布算法估计理论（TEDA）

• 批准号: 440936840
• 负责人: Professor Dr. Tobias Friedrich, Ph.D.
• 金额: --
• 依托单位: Hasso-Plattner-Institut für Digital Engineering
• 依托单位国家: 德国
• 项目类别: Research Grants
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/440936840?language=en
• 关键词: Theory; Estimation; Distribution; Algorithms; TEDA

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.

大型优化问题通常不能通过标准优化技术有效地解决，因为目标函数只能间接访问。在这种黑盒优化设置中，启发式通常被应用。流行的方法是受自然启发的通用优化器，例如进化计算。进化搜索状态有两种主要表现形式：通过突变、交叉和选择进化出的多组解决方案；以及从样本中学习的概率模型。这分别对应于进化算法（EAs）和分布估计算法（EDAs）的框架。虽然对电子辐射的理论研究已经有三十多年了，但对电子辐射的理论分析最近才有了发展势头。我们的目标是促进对eda的严格理解。特别是，我们希望减少ea和eda的理论结果之间的差距，提供一个更完整的进化计算能力的总体图景。虽然ea和eda在结构上不同，但它们的优化效率却惊人地相关。尽管如此，这两种方法都有各自的优势，这是我们想要揭示的。这一科学努力的第一步将是开发新的更适合分析eda的随机工具，因为目前大多数工具都是在考虑到eda的情况下开发的。特别是，我们计划为eda常见但在ea中很少发生的情况提供新的漂移定理。新开发的工具将有助于解决以前没有进行理论分析的eda类问题。我们进一步计划在可能比ea更适合的环境中分析eda。这种情况的一个例子是嘈杂的环境，这是经验观察到的，但没有数学上的理解。除此之外，eda几乎只在具有多个局部最优的设置中被考虑过。考虑到eda对搜索空间的全局视角，我们相信eda可以比ea更有效地绕过局部最优。最后，该项目应该对eda提供足够的见解，以便我们可以创建结合ea和eda优势的新的混合算法。