View in EDS

Self-adjusting population sizes for the (1,λ)-EA on monotone functions.

Saved in:
Bibliographic Details
Title: Self-adjusting population sizes for the (1,λ)-EA on monotone functions.
Authors: Kaufmann, Marc1 (AUTHOR) marc.kaufmann@inf.ethz.ch, Larcher, Maxime1 (AUTHOR) larcherm@inf.ethz.ch, Lengler, Johannes1 (AUTHOR) johannes.lengler@inf.ethz.ch, Zou, Xun1 (AUTHOR) xun.zou@inf.ethz.ch
Source: Theoretical Computer Science. Nov2023, Vol. 979, pN.PAG-N.PAG. 1p.
Subjects: Evolutionary algorithms
Abstract: We study the (1 , λ) -EA with mutation rate c / n for c ≤ 1 , where the population size is adaptively controlled with the (1 : s + 1) -success rule. Recently, Hevia Fajardo and Sudholt have shown that this setup with c = 1 is efficient on OneMax for s < 1 , but inefficient if s ≥ 18. Surprisingly, the hardest part is not close to the optimum, but rather at linear distance. We show that this behaviour is not specific to OneMax. If s is small, then the algorithm is efficient on all monotone functions, and if s is large, then it needs super-polynomial time on all monotone functions. In the former case, for c < 1 we show a O (n) upper bound for the number of generations and O (n log ⁡ n) for the number of function evaluations, and for c = 1 we show O (n log ⁡ n) generations and O (n 2 log ⁡ log ⁡ n) evaluations. We also show formally that optimization is always fast, regardless of s , if the algorithm starts in proximity of the optimum. All results also hold in a dynamic environment where the fitness function changes in each generation. An extended abstract, containing only the results without proofs, has been published at the PPSN conference [1]. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 173118864
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Self-adjusting population sizes for the (1,λ)-EA on monotone functions.
– Name: Author
  Label: Authors
  Group: Au
  Data: &lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Kaufmann%2C+Marc%22&quot;&gt;Kaufmann, Marc&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; marc.kaufmann@inf.ethz.ch&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Larcher%2C+Maxime%22&quot;&gt;Larcher, Maxime&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; larcherm@inf.ethz.ch&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Lengler%2C+Johannes%22&quot;&gt;Lengler, Johannes&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; johannes.lengler@inf.ethz.ch&lt;/i&gt;&lt;br /&gt;&lt;searchLink fieldCode=&quot;AR&quot; term=&quot;%22Zou%2C+Xun%22&quot;&gt;Zou, Xun&lt;/searchLink&gt;&lt;relatesTo&gt;1&lt;/relatesTo&gt; (AUTHOR)&lt;i&gt; xun.zou@inf.ethz.ch&lt;/i&gt;
– Name: TitleSource
  Label: Source
  Group: Src
  Data: &lt;searchLink fieldCode=&quot;JN&quot; term=&quot;%22Theoretical+Computer+Science%22&quot;&gt;Theoretical Computer Science&lt;/searchLink&gt;. Nov2023, Vol. 979, pN.PAG-N.PAG. 1p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: &lt;searchLink fieldCode=&quot;DE&quot; term=&quot;%22Evolutionary+algorithms%22&quot;&gt;Evolutionary algorithms&lt;/searchLink&gt;
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We study the (1 , λ) -EA with mutation rate c / n for c ≤ 1 , where the population size is adaptively controlled with the (1 : s + 1) -success rule. Recently, Hevia Fajardo and Sudholt have shown that this setup with c = 1 is efficient on OneMax for s &lt; 1 , but inefficient if s ≥ 18. Surprisingly, the hardest part is not close to the optimum, but rather at linear distance. We show that this behaviour is not specific to OneMax. If s is small, then the algorithm is efficient on all monotone functions, and if s is large, then it needs super-polynomial time on all monotone functions. In the former case, for c &lt; 1 we show a O (n) upper bound for the number of generations and O (n log ⁡ n) for the number of function evaluations, and for c = 1 we show O (n log ⁡ n) generations and O (n 2 log ⁡ log ⁡ n) evaluations. We also show formally that optimization is always fast, regardless of s , if the algorithm starts in proximity of the optimum. All results also hold in a dynamic environment where the fitness function changes in each generation. An extended abstract, containing only the results without proofs, has been published at the PPSN conference [1]. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: &lt;i&gt;Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder&#39;s express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.&lt;/i&gt; (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=173118864
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.tcs.2023.114181
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 1
        StartPage: N.PAG
    Subjects:
      – SubjectFull: Evolutionary algorithms
        Type: general
    Titles:
      – TitleFull: Self-adjusting population sizes for the (1,λ)-EA on monotone functions.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Kaufmann, Marc
      – PersonEntity:
          Name:
            NameFull: Larcher, Maxime
      – PersonEntity:
          Name:
            NameFull: Lengler, Johannes
      – PersonEntity:
          Name:
            NameFull: Zou, Xun
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 10
              M: 11
              Text: Nov2023
              Type: published
              Y: 2023
          Identifiers:
            – Type: issn-print
              Value: 03043975
          Numbering:
            – Type: volume
              Value: 979
          Titles:
            – TitleFull: Theoretical Computer Science
              Type: main
ResultId 1