research-article

Public Access

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

Authors:

Francisco Chicano,

Darrell Whitley,

Gabriela Ochoa,

Renato TinósAuthors Info & Claims

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 753 - 760

https://doi.org/10.1145/3071178.3071285

Published: 01 July 2017 Publication History

PDF eReader

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.

Supplementary Material

ZIP File (p753-chicano.zip)

Supplemental material.

Download
183.46 KB

References

[1]

Francisco Chicano, Darrell Whitley, and Andrew M. Sutton. 2014. Efficient identification of improving moves in a ball for pseudo-boolean problems. In Proceedings of GECCO, Vancouver, BC, Canada, July 12--16, 2014, Dirk V. Arnold (Ed.). ACM, NY, USA, 437--444.

Digital Library

Google Scholar

[2]

Brian W. Goldman and William F. Punch. 2015. Gray-Box Optimization Using the Parameter-less Population Pyramid. In Proceedings of GECCO. ACM, New York, NY, USA, 855--862.

Digital Library

Google Scholar

[3]

Robert B. Heckendorn, Soraya Rana, and Darrell Whitley. 1999. Polynomial Time Summary Statistics for a Generalization of MAXSAT. In Proceedings of GECCO - Volume 1. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 281--288. http://dl.acm.org/citation.cfm?id=2933923.2933952

Digital Library

Google Scholar

[4]

Holger H. Hoos and Thomas Stützle. 2004. Stochastic Local Search: Foundations and Applications. Morgan Kaufman.

Digital Library

Google Scholar

[5]

Stuart A. Kauffman and Edward D. Weinberger. 1989. The NK model of rugged fitness landscapes and its application to maturation of the immune response. Journal of Theoretical Biology 141, 2 (1989), 211 -- 245.

Crossref

Google Scholar

[6]

Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Leslie Pérez-Cáceres, Mauro Birattari, and Thomas Stützle. 2016. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives 3 (2016), 43 -- 58.

Crossref

Google Scholar

[7]

Gabriela Ochoa, Francisco Chicano, Renato Tinós, and Darrell Whitley. 2015. Tunnelling Crossover Networks. In Proceedings of GECCO. ACM, New York, NY, USA, 449--456.

Digital Library

Google Scholar

[8]

Renato Tinós, Darrell Whitley, and Francisco Chicano. 2015. Partition Crossover for Pseudo-Boolean Optimization. In Proceedings of FOGA. ACM, New York, NY, USA, 137--149.

Digital Library

Google Scholar

[9]

Darrell Whitley and Wenxiang Chen. 2012. Constant time steepest descent local search with lookahead for NK-landscapes and MAX-kSAT. In Proceedings of GECCO. ACM, NY, USA, 1357--1364.

Digital Library

Google Scholar

[10]

Darrell Whitley, Doug Hains, and Adele Howe. 2009. Tunneling Between Optima: Partition Crossover for the Traveling Salesman Problem. In Proceedings of GECCO. ACM, NY, USA, 915--922.

Digital Library

Google Scholar

[11]

L. Darrell Whitley, Francisco Chicano, and Brian W. Goldman. 2016. Gray Box Optimization for Mk Landscapes (NK Landscapes and MAX-kSAT). Evolutionary Computation 24 (Jan-09-2016 2016), 491 -- 519.

Digital Library

Google Scholar

[12]

Alden Wright, Richard Thompson, and Jian Zhang. 2000. The computational complexity of NK fitness functions. IEEE Transactions on Evolutionary Computation 4, 4 (2000), 373--379.

Digital Library

Google Scholar

Cited By

View all

Canonne LDerbel BTsuji MSato M(2024)Large-scale and cooperative graybox parallel optimization on the supercomputer FugakuJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104921191:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104921
Chicano FWhitley DOchoa GTinós R(2024)Generalizing and Unifying Gray-Box Combinatorial Optimization OperatorsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_4(52-67)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_4
Whitley DOchoa GChicano F(2024)Over Sampling Local Optima: Selection and Sampling Bias in Hybrid Genetic AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_24(393-408)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_24
Show More Cited By

Index Terms

Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Random search heuristics

Recommendations

Enhancing partition crossover with articulation points analysis
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Partition Crossover is a recombination operator for pseudo-Boolean optimization with the ability to explore an exponential number of solutions in linear or square time. It decomposes the objective function as a sum of subfunctions, each one depending on ...
Partition Crossover for Pseudo-Boolean Optimization
FOGA '15: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

A partition crossover operator is introduced for use with NK landscapes, MAX-kSAT and for all k-bounded pseudo-Boolean functions. By definition, these problems use a bit representation. Under partition crossover, the evaluation of offspring can be ...
Adaptation of a multiagent evolutionary algorithm to NK landscapes
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

Multiagent evolutionary algorithm (MEA) is a relatively new optimization technique, where a life cycle of a population of agents, which perform local search, is simulated. The algorithm was originally intended as a method for solving the graph coloring ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
349
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)13

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Canonne LDerbel BTsuji MSato M(2024)Large-scale and cooperative graybox parallel optimization on the supercomputer FugakuJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104921191:COnline publication date: 18-Jul-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104921
Chicano FWhitley DOchoa GTinós R(2024)Generalizing and Unifying Gray-Box Combinatorial Optimization OperatorsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_4(52-67)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-70055-2_4
Whitley DOchoa GChicano F(2024)Over Sampling Local Optima: Selection and Sampling Bias in Hybrid Genetic AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_24(393-408)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_24
Vendi VVerel SFonlupt C(2024)Sparse Surrogate Model for Optimization: Example of the Bus Stops Spacing ProblemEvolutionary Computation in Combinatorial Optimization10.1007/978-3-031-57712-3_2(16-32)Online publication date: 2024
https://doi.org/10.1007/978-3-031-57712-3_2
Buzdalov MSilva SPaquete L(2023)Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of PatchesProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596388(1873-1881)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596388
Tari SOchoa GBasseur MVerel SSilva SPaquete L(2023)On the Global Structure of PUBOi Fitness LandscapesProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3590649(247-250)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3590649
Canonne LDerbel BChicano FOchoa GSilva SPaquete L(2023)To Combine or not to Combine Graybox Crossover and Local Search?Proceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590466(257-265)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590466
Chicano FOchoa GDerbel BCanonne LSilva SPaquete L(2023)Local Optima Markov Chain: A New Tool for Landscape-aware Analysis of Algorithm DynamicsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590422(284-292)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590422
Tari SBasseur MGoëffon A(2023)Expansion-based Hill-climbingInformation Sciences10.1016/j.ins.2023.119635(119635)Online publication date: Sep-2023
https://doi.org/10.1016/j.ins.2023.119635
Lopes RFreitas A(2023)Gray-box local search with groups of step sizesSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-09129-127:24(18709-18722)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s00500-023-09129-1
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Enhancing partition crossover with articulation points analysis

Partition Crossover for Pseudo-Boolean Optimization

Adaptation of a multiagent evolutionary algorithm to NK landscapes