Performance of evolutionary algorithms on NK landscapes with nearest neighbor interactions and tunable overlap

This paper presents a class of NK landscapes with nearest-neighbor interactions and tunable overlap. The considered class of NK landscapes is solvable in polynomial time using dynamic programming; this allows us to generate a large number of random problem instances with known optima. Several genetic and evolutionary algorithms are then applied to the generated problem instances. The results are analyzed and related to scalability theory for genetic algorithms and estimation of distribution algorithms.

• Publication year

  2009

• Venue

  Annual Conference on Genetic and Evolutionary Computation

• Publication date

  2009-07-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1569901.1570018
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Analysis of estimation of distribution algorithms and genetic algorithms on NK landscapes

  2008cited by this paper
• Convergence of Estimation of Distribution Algorithms for Finite Samples

  2007cited by this paper
• Why is parity hard for estimation of distribution algorithms?

  2007cited by this paper
• Empirical analysis of ideal recombination on random decomposable problems

  2007cited by this paper
• Population sizing for entropy-based model building in discrete estimation of distribution algorithms

  2007influential reference
• Performance of Evolutionary Algorithms on Random Decomposable Problems

  2006cited by this paper
• Phase transition in a random NK landscape model

  2005cited by this paper
• Hierarchical Bayesian Optimization Algorithm - Toward a new Generation of Evolutionary Algorithms

  2005influential reference
• Evaluation-Relaxation Schemes for Genetic and Evolutionary Algorithms

  2004cited by this paper
• Optimization of a Constrained Feed Network for an Antenna Array Using Simple and Competent Genetic Algorithm Techniques

  2004cited by this paper
• Genetic Algorithms on NK-Landscapes: Effects of Selection, Drift, Mutation, and Recombination

  2003cited by this paper
• Hierarchical BOA Solves Ising Spin Glasses and MAXSAT

  2003cited by this paper
• The theory of elementary landscapes

  2003cited by this paper
• Representations for genetic and evolutionary algorithms

  2002cited by this paper
• The Design of Innovation: Lessons from and for Competent Genetic Algorithms

  2002influential reference
• An Analysis of Phase Transition in NK Landscapes

  2002influential reference
• Scalability of the Bayesian optimization algorithm

  2002cited by this paper
• Escaping hierarchical traps with competent genetic algorithms

  2001cited by this paper
• The computational complexity of N-K fitness functions

  2000influential reference
• Scalability Problems of Simple Genetic Algorithms

  1999cited by this paper
• Domino convergence, drift, and the temporal-salience structure of problems

  1998cited by this paper
• A Bayesian Approach to Learning Bayesian Networks with Local Structure

  1997cited by this paper
• The Gambler's Ruin Problem, Genetic Algorithms, and the Sizing of Populations

  1997cited by this paper
• Handbook of evolutionary computation

  1997cited by this paper
• Learning Linkage

  1996cited by this paper
• Learning Bayesian Networks with Local Structure

  1996cited by this paper
• From Recombination of Genes to the Estimation of Distributions I. Binary Parameters

  1996cited by this paper
• Finding Multimodal Solutions Using Restricted Tournament Selection

  1995cited by this paper
• Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning

  1994cited by this paper
• Learning Bayesian networks: The combination of knowledge and statistical data

  1994cited by this paper
• Convergence Models of Genetic Algorithm Selection Schemes

  1994cited by this paper
• The origins of order

  1993influential reference
• Mixing in Genetic Algorithms

  1993cited by this paper
• Genetic Algorithms, Noise, and the Sizing of Populations

  1992cited by this paper
• Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence

  1992cited by this paper
• Analyzing Deception in Trap Functions

  1992cited by this paper
• Genetic Algorithms and the Variance of Fitness

  1991influential reference
• Where the Really Hard Problems Are

  1991cited by this paper
• Genetic Algorithms in Search Optimization and Machine Learning

  1988cited by this paper
• An empirical study of bit vector function optimization

  1987cited by this paper

• The Pitfalls and Potentials of Adding Gene-invariance to Optimal Mixing

  2025cites this paper
• Exploring SLUG: Feature Selection Using Genetic Algorithms and Genetic Programming

  2023cites this paper
• SLUG: Feature Selection Using Genetic Algorithms and Genetic Programming

  2022cites this paper
• A Novel Approach to Designing Surrogate-assisted Genetic Algorithms by Combining Efficient Learning of Walsh Coefficients and Dependencies

  2021cites this paper
• Parameterless Gene-Pool Optimal Mixing Evolutionary Algorithms

  2021cites this paper
• Benchmark generator for TD Mk landscapes

  2021influential citation
• On the investigation of population sizing of genetic algorithms using optimal mixing

  2019cites this paper
• Bayesian partition crossover for pseudo-Boolean optimization

  2019cites this paper
• Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem

  2019cites this paper
• Convolutional neural network surrogate-assisted GOMEA

  2019cites this paper
• Investigation of the exponential population scheme for genetic algorithms

  2018influential citation
• Exploring the probabilistic graphic model of a hybrid multi-objective Bayesian estimation of distribution algorithm

  2018influential citation
• On the Performance of Multi-Objective Estimation of Distribution Algorithms for Combinatorial Problems

  2018cites this paper
• A diversity preservation scheme for DSMGA-II to conquer the hierarchical difficulty

  2017cites this paper
• Two-edge graphical linkage model for DSMGA-II

  2017cites this paper
• Automatic generation of domain-specific genetic algorithm operators using the hierarchical bayesian optimization algorithm

  2017cites this paper
• Fighting the Symmetries: The Structure of Cryptographic Boolean Function Spaces

  2015cites this paper
• Parallelizing the Linkage Tree Genetic Algorithm and Searching for the Optimal Replacement for the Linkage Tree

  2015cites this paper
• Partition Crossover for Pseudo-Boolean Optimization

  2015cites this paper
• Optimization by Pairwise Linkage Detection, Incremental Linkage Set, and Restricted / Back Mixing: DSMGA-II

  2015cites this paper
• Handling Overlap by Pairwise Linkage Detection, Incremental Linkage Set, and Restricted / Back Mixing: DSMGA-II

  2015cites this paper
• Inferring and Exploiting Problem Structure with Schema Grammar

  2014cites this paper
• A step toward constant time local search for optimizing pseudo Boolean functions

  2013cites this paper
• A new algorithm for reducing metaheuristic design effort

  2013cites this paper
• Using prior knowledge and learning from experience in estimation of distribution algorithms

  2013cites this paper
• Design of test problems for discrete estimation of distribution algorithms

  2013cites this paper
• Second order partial derivatives for NK-landscapes

  2013cites this paper
• More concise and robust linkage learning by filtering and combining linkage hierarchies

  2013cites this paper
• Effects of discrete hill climbing on model building forestimation of distribution algorithms

  2013cites this paper
• On Measures to Build Linkage Trees in LTGA

  2012cites this paper
• Predetermined versus learned linkage models

  2012cites this paper
• Linkage neighbors, optimal mixing and forced improvements in genetic algorithms

  2012cites this paper
• A test problem with adjustable degrees of overlap and conflict among subproblems

  2012cites this paper
• Learning the Neighborhood with the Linkage Tree Genetic Algorithm

  2012cites this paper
• Evolvability Analysis of the Linkage Tree Genetic Algorithm

  2012cites this paper
• Using network mesures to test evolved NK-landscapes

  2012cites this paper
• The roles of local search, model building and optimal mixing in evolutionary algorithms from a bbo perspective

  2011cites this paper
• Advanced neighborhoods and problem difficulty measures

  2011cites this paper
• Optimal mixing evolutionary algorithms

  2011influential citation
• Analysis of epistasis correlation on NK landscapes with nearest-neighbor interactions

  2011cites this paper
• The Linkage Tree Genetic Algorithm

  2010cites this paper
• Performance of Network Crossover on NK Landscapes and Spin Glasses

  2010cites this paper
• Estimation of Bayesian networks algorithms in a class of complex networks

  2010cites this paper
• NK landscapes, problem difficulty, and hybrid evolutionary algorithms

  2010cites this paper
• Network crossover performance on NK landscapes and deceptive problems

  2010cites this paper