Crynodeb
The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017), called fast mutation to agree with the previously used language, so far was proven to be advantageous only in mutation-based algorithms. There, it can relieve the algorithm designer from finding the optimal mutation rate and nevertheless obtain a performance close to the one that the optimal mutation rate gives. In this first runtime analysis of a crossover-based algorithm using a heavy-tailed choice of the mutation rate, we show an even stronger impact. For the (1 + (λ, λ)) genetic algorithm optimizing the OneMax benchmark function, we show that with a heavy-tailed mutation rate a linear runtime can be achieved. This is asymptotically faster than what can be obtained with any static mutation rate, and is asymptotically equivalent to the runtime of the self-adjusting version of the parameters choice of the (1 + (λ, λ)) genetic algorithm. This result is complemented by an empirical study which shows the effectiveness of the fast mutation also on random satisfiable MAX-3SAT instances.
| Iaith wreiddiol | Saesneg |
|---|---|
| Tudalennau (o-i) | 1724-1761 |
| Nifer y tudalennau | 38 |
| Cyfnodolyn | Algorithmica |
| Cyfrol | 84 |
| Rhif cyhoeddi | 6 |
| Dyddiad ar-lein cynnar | 25 Maw 2022 |
| Dynodwyr Gwrthrych Digidol (DOIs) | |
| Statws | Cyhoeddwyd - 30 Meh 2022 |
| Cyhoeddwyd yn allanol | Ie |
Ôl bys
Gweld gwybodaeth am bynciau ymchwil 'Fast Mutation in Crossover-Based Algorithms'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.Dyfynnu hyn
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver