Approximation speed-up by quadratization on leadingones

Andrew M. Sutton, Darrell Whitley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We investigate the quadratization of LeadingOnes in the context of the landscape for local search. We prove that a standard quadratization (i.e., its expression as a degree-2 multilinear polynomial) of LeadingOnes transforms the search space for local search in such a way that faster progress can be made. In particular, we prove there is a $$\varOmega (n/\log n)$$ speed-up for constant-factor approximations by RLS when using the quadratized version of the function. This suggests that well-known transformations for classical pseudo-Boolean optimization might have an interesting impact on search heuristics. We derive and present numerical results that investigate the difference in correlation structure between the untransformed landscape and its quadratization. Finally, we report experiments that provide a detailed glimpse into the convergence properties on the quadratized function.

Original languageEnglish (US)
Title of host publicationParallel Problem Solving from Nature – PPSN XVI - 16th International Conference, PPSN 2020, Proceedings
EditorsThomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann
PublisherSpringer Science and Business Media Deutschland GmbH
Pages686-698
Number of pages13
ISBN (Print)9783030581145
DOIs
StatePublished - 2020
Event16th International Conference on Parallel Problem Solving from Nature, PPSN 2020 - Leiden, Netherlands
Duration: Sep 5 2020Sep 9 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12270 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Parallel Problem Solving from Nature, PPSN 2020
CountryNetherlands
CityLeiden
Period9/5/209/9/20

Fingerprint Dive into the research topics of 'Approximation speed-up by quadratization on leadingones'. Together they form a unique fingerprint.

Cite this