Runtime analysis of the (1 + (λ, λ)) genetic algorithm on random satisfiable 3-CNF formulas

Maxim Buzdalov, Benjamin Doerr

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)

52 Dyfyniadau (Scopus)

Crynodeb

The (1 + (λ, λ)) genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on some optimization problems. The theoretical analysis so far was restricted to the OneMax test function, where this GA profited from the perfect fitness-distance correlation. In this work, we conduct a rigorous runtime analysis of this GA on random 3-SAT instances in the planted solution model having at least logarithmic average degree, which are known to have a weaker fitness distance correlation.

We prove that this GA with fixed not too large population size again obtains runtimes better than Θ(n log n), which is a lower bound for most evolutionary algorithms on pseudo-Boolean problems with unique optimum. However, the self-adjusting version of the GA risks reaching population sizes at which the intermediate selection of the GA, due to the weaker fitness-distance correlation, is not able to distinguish a profitable offspring from others. We show that this problem can be overcome by equipping the self-adjusting GA with an upper limit for the population size. Apart from sparse instances, this limit can be chosen in a way that the asymptotic performance does not worsen compared to the idealistic OneMax case. Overall, this work shows that the (1 + (λ, λ)) GA can provably have a good performance on combinatorial search and optimization problems also in the presence of a weaker fitness-distance correlation.
Iaith wreiddiolSaesneg
TeitlGECCO '17
Is-deitlProceedings of the Genetic and Evolutionary Computation Conference
CyhoeddwrAssociation for Computing Machinery
Tudalennau1343-1350
Nifer y tudalennau8
ISBN (Argraffiad)978-1-4503-4920-8
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 01 Gorff 2017
Cyhoeddwyd yn allanolIe
DigwyddiadGECCO 2017: The Genetic and Evolutionary Computation Conference -
Hyd: 15 Gorff 201719 Gorff 2017

Cynhadledd

CynhadleddGECCO 2017
Cyfnod15 Gorff 201719 Gorff 2017

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Runtime analysis of the (1 + (λ, λ)) genetic algorithm on random satisfiable 3-CNF formulas'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn