Neidio i’r brif dudalen lywio Neidio i chwilio Neidio i’r prif gynnwys

Fast Mutation in Crossover-Based Algorithms

  • Denis Antipov*
  • , Maxim Buzdalov
  • , Benjamin Doerr
  • *Awdur cyfatebol y gwaith hwn
  • ITMO University
  • École Polytechnique

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

32 Dyfyniadau (Scopus)
29 Wedi eu Llwytho i Lawr (Pure)

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 wreiddiolSaesneg
Tudalennau (o-i)1724-1761
Nifer y tudalennau38
CyfnodolynAlgorithmica
Cyfrol84
Rhif cyhoeddi6
Dyddiad ar-lein cynnar25 Maw 2022
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 30 Meh 2022
Cyhoeddwyd yn allanolIe

Ô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