## Abstract

Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jump_{k}. All previous results in this context only hold for unrealistically low crossover probability p_{c} = O(k/n), while we give analyses for the setting of constant p_{c} < 1 in all but one case. Our bounds show a dependence on the problem size n, the jump length k, the population size μ, and the crossover probability p_{c}. For the typical case of constant k > 2 and constant p_{c}, we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of μ: • O (n^{k-1}) J for duplicate elimination/minimisation, • O (n^{2} log n) for maximising the convex hull, • O(n log n) for det. crowding (assuming p_{c} = k/n), • O(n log n) for maximising the Hamming distance, • O(n log n) for fitness sharing, • O(n log n) for the single-receiver island model. This proves a sizeable advantage of all variants of the (μ+1) GA compared to the (1+1) EA, which requires Θ(n). In a short empirical study we confirm that the asymptotic differences can also be observed experimentally.

Original language | English |
---|---|

Title of host publication | GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference |

Publisher | Association for Computing Machinery |

Pages | 645-652 |

Number of pages | 8 |

ISBN (Electronic) | 9781450342063 |

DOIs | |

Publication status | Published - 20 Jul 2016 |

Event | 2016 Genetic and Evolutionary Computation Conference, GECCO 2016 - Denver, United States Duration: 20 Jul 2016 → 24 Jul 2016 |

### Conference

Conference | 2016 Genetic and Evolutionary Computation Conference, GECCO 2016 |
---|---|

Country/Territory | United States |

City | Denver |

Period | 20/07/16 → 24/07/16 |

## Keywords

- Crossover
- Diversity
- Genetic algorithms
- Recombination
- Run time analysis
- Theory

## ASJC Scopus subject areas

- Computer Science Applications
- Computational Theory and Mathematics
- Software