When do evolutionary algorithms optimize separable functions in parallel?
When do evolutionary algorithms optimize separable functions in parallel?
复制标题
进化算法何时并行优化可分离函数？
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
C. Witt
中科院分区：
文献类型：
--
作者：
Benjamin Doerr;Dirk Sudholt;C. Witt
可分离函数由依赖于相互不相交的位集的子函数组成。这些子函数可以独立优化，但在黑盒优化中，这种直接方法是不可行的，因为子函数的组成可能是未知的。人们普遍认为，进化算法在所有子函数上并行进行，因此优化可分离函数所需的时间不会比优化最难的子函数花费的时间长-子函数是“并行”优化的。
我们表明，这只是部分正确的，已经对简单的(1+1)进化算法((1+1)EA)。实际上，对于由k个布尔函数组成的可分函数，优化时间等于这些函数的最大优化时间乘以较小的(Logk)开销。更一般地，对于每个加权子函数的和都达到小于r=o(log1/2n)的非负整数值，我们得到O(Rlogn)的开销。然而，所希望的并行优化行为并不总是能够实现。给出了一个具有k个≤√n个子函数的可分函数，使得(1+1)进化算法有可能连续优化多个子函数。原因是标准突变会导致不同子功能上的搜索过程之间的干扰。在较温和的假设下，我们证明了这样的顺序优化行为是最差的。
Separable functions are composed of subfunctions that depend on mutually disjoint sets of bits. These subfunctions can be optimized independently, however in black-box optimization this direct approach is infeasible as the composition of subfunctions may be unknown. Common belief is that evolutionary algorithms make progress on all subfunctions in parallel, so that optimizing a separable function does not take not much longer than optimizing the hardest subfunction---subfunctions are optimized "in parallel."
We show that this is only partially true, already for the simple (1+1) evolutionary algorithm ((1+1)EA). For separable functions composed of k Boolean functions indeed the optimization time is the maximum optimization time of these functions times a small(log k) overhead. More generally, for sums of weighted subfunctions that each attain non negative integer values less than r = o(log 1/2 n), we get an overhead of O(r log n). However, the hoped for parallel optimization behavior does not always come true. We present a separable function with k ≤ √ n subfunctions such that the (1+1)EA is likely to optimize many subfunctions sequentially. The reason is that standard mutation leads to interferences between search processes on different subfunctions. Under mild assumptions, we show that such a sequential optimization behavior is worst possible.
影响因子：
1.1
作者：
Benjamin Doerr;L. A. Goldberg
通讯作者：
Benjamin Doerr;L. A. Goldberg