EDAs cannot be Balanced and Stable
EDAs cannot be Balanced and Stable
复制标题
DOI：
10.1145/2908812.2908895
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
T. Friedrich;Timo Kötzing;Martin S. Krejca
中科院分区：
文献类型：
--
作者：
T. Friedrich;Timo Kötzing;Martin S. Krejca
分布估计算法（EDA）通过在每次迭代的样本的帮助下迭代地更新搜索空间上的分布来工作。到目前为止，EDA的理论分析是稀缺的，目前的运行时间的结果为特定的EDA。我们提出了一个新的EDA框架，捕获了几个已知的优化器，包括PBIL，UMDA，λ -MMASIB，cGA和（1，λ）-EA的想法。我们的重点是分析EDA的两个核心特征：平衡的EDA对适应度中的信号敏感;稳定的EDA在无偏适应度函数下保持未提交。我们证明，没有EDA可以平衡和稳定。LeadingOnes函数是一个很好的例子，在优化开始时，适应度函数对许多位没有显示出偏差。由于许多著名的EDA是平衡的，因此不稳定，它们不适合优化LeadingOne。我们给出了一个稳定的EDA优化LeadingOnes的时间为O（n log n）。
Estimation of Distribution Algorithms (EDAs) work by iteratively updating a distribution over the search space with the help of samples from each iteration. Up to now, theoretical analyses of EDAs are scarce and present run time results for specific EDAs. We propose a new framework for EDAs that captures the idea of several known optimizers, including PBIL, UMDA, λ -MMASIB, cGA, and (1, λ)-EA. Our focus is on analyzing two core features of EDAs: a balanced EDA is sensitive to signals in the fitness; a stable EDA remains uncommitted under a biasless fitness function. We prove that no EDA can be both balanced and stable. The LeadingOnes function is a prime example where, at the beginning of the optimization, the fitness function shows no bias for many bits. Since many well-known EDAs are balanced and thus not stable, they are not well-suited to optimize LeadingOnes. We give a stable EDA which optimizes LeadingOnes within a time of O(n log n).