A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Realizations and Predictability

Research output: Contribution to journalArticle

Standard

A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Realizations and Predictability. / He, Jun; Reeves, C; Witt, C; Yao, Xin.

In: Evolutionary Computation, Vol. 15, No. 4, 01.12.2007, p. 435-443.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Bibtex

@article{707cb90502014f8ea227d03088e25440,
title = "A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Realizations and Predictability",
abstract = "Various methods have been defined to measure the hardness of a fitness function for evolutionary algorithms and other black-box heuristics. Examples include fitness landscape analysis, epistasis, fitness-distance correlations etc., all of which are relatively easy to describe. However, they do not always correctly specify the hardness of the function. Some measures are easy to implement, others are more intuitive and hard to formalize. This paper rigorously defines difficulty measures in black-box optimization and proposes a classification. Different types of realizations of such measures are studied, namely exact and approximate ones. For both types of realizations, it is proven that predictive versions that run in polynomial time in general do not exist unless certain complexity-theoretical assumptions are wrong.",
keywords = "satisfiability problem, problem difficulty measure, evolutionary algorithm, running time, black-box optimization",
author = "Jun He and C Reeves and C Witt and Xin Yao",
year = "2007",
month = dec,
day = "1",
doi = "10.1162/evco.2007.15.4.435",
language = "English",
volume = "15",
pages = "435--443",
journal = "Evolutionary Computation",
issn = "1063-6560",
publisher = "Massachusetts Institute of Technology Press",
number = "4",

}

RIS

TY - JOUR

T1 - A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Realizations and Predictability

AU - He, Jun

AU - Reeves, C

AU - Witt, C

AU - Yao, Xin

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Various methods have been defined to measure the hardness of a fitness function for evolutionary algorithms and other black-box heuristics. Examples include fitness landscape analysis, epistasis, fitness-distance correlations etc., all of which are relatively easy to describe. However, they do not always correctly specify the hardness of the function. Some measures are easy to implement, others are more intuitive and hard to formalize. This paper rigorously defines difficulty measures in black-box optimization and proposes a classification. Different types of realizations of such measures are studied, namely exact and approximate ones. For both types of realizations, it is proven that predictive versions that run in polynomial time in general do not exist unless certain complexity-theoretical assumptions are wrong.

AB - Various methods have been defined to measure the hardness of a fitness function for evolutionary algorithms and other black-box heuristics. Examples include fitness landscape analysis, epistasis, fitness-distance correlations etc., all of which are relatively easy to describe. However, they do not always correctly specify the hardness of the function. Some measures are easy to implement, others are more intuitive and hard to formalize. This paper rigorously defines difficulty measures in black-box optimization and proposes a classification. Different types of realizations of such measures are studied, namely exact and approximate ones. For both types of realizations, it is proven that predictive versions that run in polynomial time in general do not exist unless certain complexity-theoretical assumptions are wrong.

KW - satisfiability problem

KW - problem difficulty measure

KW - evolutionary algorithm

KW - running time

KW - black-box optimization

U2 - 10.1162/evco.2007.15.4.435

DO - 10.1162/evco.2007.15.4.435

M3 - Article

C2 - 18021014

VL - 15

SP - 435

EP - 443

JO - Evolutionary Computation

JF - Evolutionary Computation

SN - 1063-6560

IS - 4

ER -