When do evolutionary algorithms optimize separable functions in parallel?

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 O(log k) overhead. More generally, for sums of weighted subfunctions that each attain non-negative integer values less than r = o(log1/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. Copyright © 2013 ACM.