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

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 language | English |
---|---|

Title of host publication | GECCO '20 |

Subtitle of host publication | Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion |

Publisher | Association for Computing Machinery |

Pages | 1669-1677 |

Number of pages | 9 |

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

DOIs | |

Publication status | Published - 08 Jul 2020 |

Externally published | Yes |

Event | GECCO 2020 - Genetic and Evolutionary Computation Conference - Cancun, Mexico Duration: 08 Jul 2020 → 12 Jul 2020 |

### Conference

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

Country/Territory | Mexico |

City | Cancun |

Period | 08 Jul 2020 → 12 Jul 2020 |

## Keywords

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