Jove
Visualize
Contact Us

Related Experiment Videos

Embedded landscapes.

Robert B Heckendorn1

  • 1Department of Computer Science, University of Idaho, Moscow, ID 83844-1010, USA. heckendo@cs.uidaho.edu

Evolutionary Computation
|November 27, 2002
PubMed
Summary
This summary is machine-generated.

We introduce embedded landscapes, extending NK landscapes and MAXSAT problems. These landscapes reveal that while epistasis statistics are computable, the true problem difficulty lies in epistatic interactions, not epistasis alone.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

The Influence of Higher-Order Epistasis on Biological Fitness Landscape Topography.

Journal of statistical physics·2018
Same author

Should evolutionary geneticists worry about higher-order epistasis?

Current opinion in genetics & development·2013
Same author

Cellular automaton simulation examining progenitor hierarchy structure effects on mammary ductal carcinoma in situ.

Journal of theoretical biology·2007
Same author

Gene knockout experiments to quantify a G2/M genetic network simulation for mammary cancer susceptibility.

In silico biology·2006
Same journal

Computing Optimal Populations for Binary Problems using Logic Minimization.

Evolutionary computation·2026
Same journal

Enhancing Generalization and Scalability for Multi-Objective Optimization with Population Pre-Training.

Evolutionary computation·2026
Same journal

XCS for Sequential Perceptual Aliasing in Multi-Step Decision Making.

Evolutionary computation·2026
Same journal

A dynamic multi-objective evolutionary algorithm using dual-space prediction and surrogate-based sampling.

Evolutionary computation·2026
Same journal

Adapting MOEA/D to CMA-ES for Dealing with Ill-conditioned Multiobjective Problems.

Evolutionary computation·2026
Same journal

Editorial of the Special Issue: Parallel Problem Solving from Nature PPSN 2024 Extended Versions of Best Paper Candidates.

Evolutionary computation·2026
See all related articles
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Area of Science:

  • Computational complexity
  • Statistical mechanics
  • Constraint satisfaction problems

Background:

  • NK landscapes and MAXSAT problems are foundational models in computational complexity and optimization.
  • Many real-world problems involve additive constraints or interactions between subcomponents.
  • Understanding the structure of these problems is crucial for developing efficient algorithms.

Purpose of the Study:

  • To introduce embedded landscapes as a novel extension of NK landscapes and MAXSAT problems.
  • To analyze the computational complexity and statistical properties of these new landscapes.
  • To identify the sources of computational difficulty in complex problems.

Main Methods:

  • Defining embedded landscapes for problems representable as sums of subfunctions.

Related Experiment Videos

  • Analyzing the sparsity of embedded landscapes in epistatic space.
  • Developing polynomial-time algorithms for computing statistical features like epistasis and hyperplane statistics.
  • Investigating the NP-completeness of embedded landscapes with fixed epistasis K.

    • Main Results:

    • Embedded landscapes with fixed maximum epistasis K are exponentially sparse.
    • Key statistical features, including all epistatic interactions and hyperplane statistics, can be computed in polynomial time.
    • Embedded landscapes with small fixed K can be NP-complete, indicating inherent computational difficulty.
    • The difficulty of these problems stems from the interaction of epistatic parts, not epistasis itself.

    Conclusions:

    • Embedded landscapes provide a powerful framework for analyzing a broad class of complex problems.
    • Polynomial-time computation of epistasis and hyperplane statistics does not fully resolve the computational complexity of these problems.
    • The interaction between epistatic components is the primary source of computational hardness in these general problems.