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

A. O. Bassin, Maxim Buzdalov

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)

Crynodeb

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.
Iaith wreiddiolSaesneg
TeitlGECCO '20
Is-deitlProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
CyhoeddwrAssociation for Computing Machinery
Tudalennau1669-1677
Nifer y tudalennau9
ISBN (Argraffiad)978-1-4503-7127-8
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 08 Gorff 2020
Cyhoeddwyd yn allanolIe
DigwyddiadGECCO 2020 - Genetic and Evolutionary Computation Conference - Cancun, Mecsico
Hyd: 08 Gorff 202012 Gorff 2020

Cynhadledd

CynhadleddGECCO 2020 - Genetic and Evolutionary Computation Conference
Gwlad/TiriogaethMecsico
DinasCancun
Cyfnod08 Gorff 202012 Gorff 2020

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'The (1 + (λ, λ)) genetic algorithm for permutations'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn