When do evolutionary algorithms optimize separable functions in parallel?

Benjamin Doerr, Dirk Sudholt, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the 12th ACM Workshop on Foundations of Genetic Algorithms (FOGA 2013)
PublisherAssociation for Computing Machinery
Publication date2013
Pages51-64
ISBN (Print)9781450319904
DOIs
Publication statusPublished - 2013
Event12th ACM Conference on Foundations of Genetic Algorithms XII (FOGA 2013) - Adelaide, Australia
Duration: 16 Jan 201320 Jan 2013
Conference number: 12

Conference

Conference12th ACM Conference on Foundations of Genetic Algorithms XII (FOGA 2013)
Number12
CountryAustralia
CityAdelaide
Period16/01/201320/01/2013

Keywords

  • Genetic algorithms
  • Optimization
  • Boolean functions

Fingerprint Dive into the research topics of 'When do evolutionary algorithms optimize separable functions in parallel?'. Together they form a unique fingerprint.

Cite this