When do evolutionary algorithms optimize separable functions in parallel?
Benjamin Doerr, Dirk Sudholt, Carsten Witt · 2013
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."