## 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.

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 wreiddiol | Saesneg |
---|---|

Teitl | GECCO '20 |

Is-deitl | Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion |

Cyhoeddwr | Association for Computing Machinery |

Tudalennau | 1669-1677 |

Nifer y tudalennau | 9 |

ISBN (Argraffiad) | 978-1-4503-7127-8 |

Dynodwyr Gwrthrych Digidol (DOIs) | |

Statws | Cyhoeddwyd - 08 Gorff 2020 |

Cyhoeddwyd yn allanol | Ie |

Digwyddiad | GECCO 2020 - Genetic and Evolutionary Computation Conference - Cancun, Mecsico Hyd: 08 Gorff 2020 → 12 Gorff 2020 |

### Cynhadledd

Cynhadledd | GECCO 2020 - Genetic and Evolutionary Computation Conference |
---|---|

Gwlad/Tiriogaeth | Mecsico |

Dinas | Cancun |

Cyfnod | 08 Gorff 2020 → 12 Gorff 2020 |