## Abstract

We study the (1 + λ) EA with mutation probability c/n, where c > 0 is a constant, on the ONEMAX problem. Using an improved variable drift theorem, we show that upper and lower bounds on the expected runtime of the (1+λ) EA obtained from variable drift theorems are at most apart by a small lower order term if the exact drift is known. This reduces the analysis of expected optimization time to finding an exact expression for the drift.

We then give an exact closed-form expression for the drift and develop a method to approximate it very efficiently, enabling us to determine approximate optimal mutation rates for the (1+λ) EA for various parameter settings of c and λ and also for moderate sizes of n. This makes the need for potentially lengthy and costly experiments in order to optimize the parameters unnecessary.

Interestingly, even for moderate n and not too small λ it turns out that mutation rates up to 10% larger than the asymptotically optimal rate 1/n minimize the expected runtime. However, in absolute terms the expected runtime does not change by much when replacing 1/n with the optimal mutation rate.

We then give an exact closed-form expression for the drift and develop a method to approximate it very efficiently, enabling us to determine approximate optimal mutation rates for the (1+λ) EA for various parameter settings of c and λ and also for moderate sizes of n. This makes the need for potentially lengthy and costly experiments in order to optimize the parameters unnecessary.

Interestingly, even for moderate n and not too small λ it turns out that mutation rates up to 10% larger than the asymptotically optimal rate 1/n minimize the expected runtime. However, in absolute terms the expected runtime does not change by much when replacing 1/n with the optimal mutation rate.

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

Title of host publication | Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '16) |

Publisher | Association for Computing Machinery |

Publication date | 2016 |

Pages | 1147-1154 |

ISBN (Print) | 978-1-4503-4206-3 |

DOIs | |

Publication status | Published - 2016 |

Event | 2016 Genetic and Evolutionary Computation Conference - Denver, United States Duration: 20 Jul 2016 → 24 Jul 2016 http://gecco-2016.sigevo.org/index.html/HomePage#&panel1-1 |

### Conference

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

Country | United States |

City | Denver |

Period | 20/07/2016 → 24/07/2016 |

Internet address |

## Keywords

- Runtime Analysis
- Populations
- Mutation