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 language||English (US)|
|Title of host publication||Parallel Problem Solving from Nature – PPSN XVI - 16th International Conference, PPSN 2020, Proceedings|
|Editors||Thomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann|
|Publisher||Springer Science and Business Media Deutschland GmbH|
|Number of pages||13|
|State||Published - 2020|
|Event||16th International Conference on Parallel Problem Solving from Nature, PPSN 2020 - Leiden, Netherlands|
Duration: Sep 5 2020 → Sep 9 2020
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||16th International Conference on Parallel Problem Solving from Nature, PPSN 2020|
|Period||9/5/20 → 9/9/20|
Bibliographical notePublisher Copyright:
© Springer Nature Switzerland AG 2020.