Jove
Visualize
Contact Us
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

Related Experiment Videos

A note on problem difficulty measures in black-box optimization: classification, realizations and predictability.

Jun He1, Colin Reeves, Carsten Witt

  • 1School of Computer Science, University of Birmingham Edgbaston, Birmingham B15 2TT, UK. j.he@cs.bham.ac.uk

Evolutionary Computation
|November 21, 2007
PubMed
Summary
This summary is machine-generated.

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

Fast Pareto Optimization Using Sliding Window Selection for Problems with Determinstic and Stochastic Constraints.

Evolutionary computation·2025
Same author

Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables.

Evolutionary computation·2024
Same author

Stagnation Detection with Randomized Local Search.

Evolutionary computation·2022
Same author

A Runtime Analysis of Parallel Evolutionary Algorithms in Dynamic Optimization.

Algorithmica·2020
Same author

The Impact of a Sparse Migration Topology on the Runtime of Island Models in Dynamic Optimization.

Algorithmica·2019
Same author

MuRF2 regulates PPARγ1 activity to protect against diabetic cardiomyopathy and enhance weight gain induced by a high fat diet.

Cardiovascular diabetology·2015
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

Measuring fitness function hardness for evolutionary algorithms is complex. This study defines difficulty measures and proves that polynomial-time predictive versions are unlikely, impacting black-box optimization research.

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Optimization

Background:

  • Existing methods for measuring fitness function hardness in evolutionary algorithms and black-box heuristics are often easy to describe but may not accurately reflect function difficulty.
  • Techniques like fitness landscape analysis, epistasis, and fitness-distance correlations have limitations in formalization and predictive power.

Purpose of the Study:

  • To rigorously define and classify difficulty measures for black-box optimization problems.
  • To analyze exact and approximate realizations of these difficulty measures.
  • To investigate the computational complexity of predicting function hardness.

Main Methods:

  • Formal definition and classification of difficulty measures in black-box optimization.

Related Experiment Videos

  • Analysis of exact and approximate realizations of these measures.
  • Complexity-theoretical analysis to determine the existence of polynomial-time predictive measures.

    • Main Results:

    • A rigorous framework for defining and classifying difficulty measures in black-box optimization is proposed.
    • Both exact and approximate realizations of difficulty measures were studied.
    • It was proven that polynomial-time predictive versions of these measures generally do not exist, unless P=NP or similar complexity-theoretic assumptions are violated.

    Conclusions:

    • The proposed classification provides a structured approach to understanding fitness function hardness.
    • The computational hardness results imply limitations on the efficiency of predicting optimization problem difficulty.
    • Further research may explore alternative approaches or heuristics for estimating fitness function hardness within practical time constraints.