Conference Paper (in Formal Publication) ()
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.
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.
|Authors||Chicano Francisco, Whitley Darrell, Ochoa Gabriela, Tinós Renato|
|Date of public distribution||07/2017|
|Date accepted by journal||05/04/2017|
|Place of publication||New York|