Research output

Conference Paper (in Formal Publication) ()

Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search

Citation
Chicano F, Whitley D, Ochoa G & Tinós R (2017) Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search In: GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference, New York: ACM. GECCO 2017: The Genetic and Evolutionary Computation Conference, 15.7.2017 - 19.7.2017, Berlin, Germany, pp. 753-760.

Abstract
In gray-box optimization, the search algorithms have access to the variable interaction graph (VIG) of the optimization problem. For Mk Landscapes (and NK Landscapes) we can use the VIG to identify an improving solution in the Hamming neighborhood in constant time. In addition, using the VIG, deterministic Partition Crossover is able to explore an exponential number of solutions in a time that is linear in the size of the problem. Both methods have been used in isolation in previous search algorithms. We present two new gray-box algorithms that combine Partition Crossover with highly efficient local search. The best algorithms are able to locate the global optimum on Adjacent NK Landscape instances with one million variables. The algorithms are compared with a state-of-the-art algorithm for pseudo-Boolean optimization: Gray-Box Parameterless Population Pyramid. The results show that the best algorithm is always one combining Partition Crossover and highly efficient local search. But the results also illustrate that the best optimizer differs on Adjacent and Random NK Landscapes.

StatusPublished
AuthorsChicano Francisco, Whitley Darrell, Ochoa Gabriela, Tinós Renato
Publication date2017
Date of public distribution07/2017
Date accepted by journal05/04/2017
PublisherACM
Place of publicationNew York
ISBN 978-1-4503-4920-8
LanguageEnglish
© University of Stirling FK9 4LA Scotland UK • Telephone +44 1786 473171 • Scottish Charity No SC011159
My Portal