The Interplay of Population Size and Mutation Probability in the (1+λ) EA on OneMax

Publication: Research - peer-reviewJournal article – Annual report year: 2016

Documents

DOI

View graph of relations

The ((Formula presented.)) EA with mutation probability c / n, where (Formula presented.) is an arbitrary constant, is studied for the classical OneMax function. Its expected optimization time is analyzed exactly (up to lower order terms) as a function of c and (Formula presented.). It turns out that 1 / n is the only optimal mutation probability if (Formula presented.), which is the cut-off point for linear speed-up. However, if (Formula presented.) is above this cut-off point then the standard mutation probability 1 / n is no longer the only optimal choice. Instead, the expected number of generations is (up to lower order terms) independent of c, irrespectively of it being less than 1 or greater. The theoretical results are obtained by a careful study of order statistics of the binomial distribution and variable drift theorems for upper and lower bounds. Experimental supplements shed light on the optimal mutation probability for small problem sizes.
Original languageEnglish
JournalAlgorithmica
Volume78
Issue number2
Pages (from-to)587–609
ISSN0178-4617
DOIs
StatePublished - 2017
CitationsWeb of Science® Times Cited: 0

    Keywords

  • Runtime analysis, Populations, Mutation
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 126469690