Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search
The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Large language models (LLMs; [9,13]) are behind many of the approaches achieving state-of-the-art results in natural language processing domains, such as question-answering [19,33,70], code-generation [17,66], and few-shot classification [13,99].”
From Language Model Crossover: Variation through Few-Shot Prompting (2024) · cites this paper as [19]
Citations
Cites
The irace package: Iterated racing for automatic algorithm configuration
López-Ibáñez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Birattari, M., & Stützle, T. (2016) · Operations Research Perspectives · doi:10.1016/j.orp.2016.09.002 · Cited by 1,761
Stochastic Local Search: Foundations & Applications
Hoos, H. H., & St�tzle, T. (2004) · Medical Entomology and Zoology · Cited by 1,227
The NK model of rugged fitness landscapes and its application to maturation of the immune response
Kauffman, S. A., & Weinberger, E. D. (1989) · Journal of Theoretical Biology · doi:10.1016/s0022-5193(89)80019-0 · Cited by 669
Partition Crossover for Pseudo-Boolean Optimization
Tinós, R., Whitley, D., & Chicano, F. (2015) · doi:10.1145/2725494.2725497 · Cited by 82
Self-citationThe computational complexity of N-K fitness functions
Zhang, J. Q., Thompson, R. K., & Wright, A. H. (2000) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.887236 · Cited by 80
Tunneling between optima: partition crossover for the traveling salesman problem
Whitley, D., Hains, D., & Howe, A. E. (2009) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/1569901.1570026 · Cited by 78
Self-citationGray Box Optimization for Mk Landscapes (NK Landscapes and MAX-kSAT)
Whitley, L. D., Chicano, F., & Goldman, B. W. (2016) · Evolutionary Computation · doi:10.1162/evco_a_00184 · Cited by 77
Self-citationConstant time steepest descent local search with lookahead for NK-landscapes and MAX-kSAT
Whitley, D., & Chen, W.-X. (2012) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/2330163.2330351 · Cited by 54
Self-citationEfficient identification of improving moves in a ball for pseudo-boolean problems
Chicano, F., Whitley, D., & Sutton, A. M. (2014) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/2576768.2598304 · Cited by 49
Self-citationPolynomial time summary statistics for a generalization of MAXSAT
Heckendorn, R. B., Rana, S., & Whitley, D. (1999) · Genetic and Evolutionary Computation Conference (GECCO) · Cited by 22
Self-citation
Cited by
NSGA-Net: neural architecture search using multi-objective genetic algorithm
Lu, Z., Whalen, I., Boddeti, V., Dhebar, Y., Deb, K., Goodman, E., & Banzhaf, W. (2019) · Proceedings of the Genetic and Evolutionary Computation Conference · doi:10.1145/3321707.3321729 · Cited by 496
Language Model Crossover: Variation through Few-Shot Prompting
Meyerson, E., Nelson, M. J., Bradley, H., Gaier, A., Moradi, A., Hoover, A. K., & Lehman, J. (2024) · ACM Transactions on Evolutionary Learning and Optimization · doi:10.1145/3694791 · Cited by 75
“Figure 4 shows the heritability of LMX in the binary strings domain, and Figure 5 shows how fitness evolves in OneMax using LMX.”
Language model crossover: Variation through few-shot prompting
Meyerson, E., Nelson, M. J., Bradley, H., Gaier, A., Moradi, A., Hoover, A. K., & Lehman, J. (2023) · arXiv · doi:10.48550/arxiv.2302.12170 · Cited by 75
Search Trajectory Networks of Population-Based Algorithms in Continuous Spaces
Ochoa, G., Malan, K. M., & Blum, C. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-43722-0_5 · Cited by 52
Self-citationRecent advances in fitness landscape analysis
Ochoa, G., & Malan, K. M. (2019) · Genetic and Evolutionary Computation Conference Companion (GECCO Companion) · doi:10.1145/3319619.3323383 · Cited by 44
Self-citation
Metadata
- Authors
- Chicano, F., Whitley, D., Ochoa, G., & Tinós, R.
- Affiliations
- Universidad de Málaga (ES)
- Colorado State University (US)
- University of Stirling (GB)
- Universidade de São Paulo (BR)
- Venue
- Proceedings of the Genetic and Evolutionary Computation Conference
- Publisher
- ACM
- Published
- 2017-07
- Pages
- 753-760
- OpenAlex
- W2725770446
- Cited by
- 52
- References
- 12
- Citations by year
- 2026: 7 · 2025: 1 · 2024: 6 · 2023: 8 · 2022: 2 · 2021: 8 · 2020: 7 · 2019: 7 · 2018: 6
- FWCI
- 2.49
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Genetic and Evolutionary Computation Conference (GECCO) (publishedVersion)
- Stirling Online Research Repository (University of Stirling) (submittedVersion, public-domain)
- Repositorio Institucional de la Universidad de Málaga (University of Málaga) (submittedVersion)
- Funders
- Ministerio de Economía y Competitividad (TIN2014-57341-R)
- Air Force Office of Scientific Research (FA9550-11-1-0088)
- Fundação de Amparo à Pesquisa do Estado de São Paulo (2015/06462-1)
- Conselho Nacional de Desenvolvimento Científico e Tecnológico (304400/2014-9)
- Ministerio de Educación, Cultura y Deporte (CAS12/00274)
- Leverhulme Trust (RPG-2015-395)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Constraint Satisfaction and Optimization
- Keywords
- NK landscapes, local search, pseudo-Boolean optimization, global optimization, hybrid metaheuristic
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search. https://app.cochat.ai/papers/10.1145/3071178.3071285
- The paper
- Chicano, F., Whitley, D., Ochoa, G., & Tinós, R. (2017). Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search. Proceedings of the Genetic and Evolutionary Computation Conference. https://doi.org/10.1145/3071178.3071285
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.