The (1 + (λ, λ)) genetic algorithm for permutations

A. O. Bassin, Maxim Buzdalov

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

Abstract

The (1 + (λ, λ)) genetic algorithm is a bright example of an evolutionary algorithm which was developed based on the insights from theoretical findings. This algorithm uses crossover, and it was shown to asymptotically outperform all mutation-based evolutionary algorithms even on simple problems like OneMax. Subsequently it was studied on a number of other problems, but all of these were pseudo-Boolean.

We aim at improving this situation by proposing an adaptation of the (1 + (λ, λ)) genetic algorithm to permutation-based problems. Such an adaptation is required, because permutations are noticeably different from bit strings in some key aspects, such as the number of possible mutations and their mutual dependence. We also present the first runtime analysis of this algorithm on a permutation-based problem called Ham whose properties resemble those of OneMax. On this problem, where the simple mutation-based algorithms have the running time of Θ(n2 log n) for problem size n, the (1 + (λ, λ)) genetic algorithm finds the optimum in O(n2) fitness queries. We augment this analysis with experiments, which show that this algorithm is also fast in practice.
Original languageEnglish
Title of host publicationGECCO '20
Subtitle of host publicationProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery
Pages1669-1677
Number of pages9
ISBN (Print)978-1-4503-7127-8
DOIs
Publication statusPublished - 08 Jul 2020
Externally publishedYes
EventGECCO 2020 - Genetic and Evolutionary Computation Conference - Cancun, Mexico
Duration: 08 Jul 202012 Jul 2020

Conference

ConferenceGECCO 2020 - Genetic and Evolutionary Computation Conference
Country/TerritoryMexico
CityCancun
Period08 Jul 202012 Jul 2020

Keywords

  • (1 + (λ λ)) GA
  • permutations
  • runtime analysis

Fingerprint

Dive into the research topics of 'The (1 + (λ, λ)) genetic algorithm for permutations'. Together they form a unique fingerprint.

Cite this