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

Jun He; Colin Reeves; Carsten Witt; Xin Yao

doi:10.1162/evco.2007.15.4.435

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

Jun He, Colin Reeves, Carsten Witt, Xin Yao

Adran Cyfrifiadureg

Allbwn ymchwil: Cyfraniad at gyfnodolyn › Erthygl › adolygiad gan gymheiriaid

54 Dyfyniadau (Scopus)

Crynodeb

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.

Iaith wreiddiol	Saesneg
Tudalennau (o-i)	435-443
Cyfnodolyn	Evolutionary Computation
Cyfrol	15
Rhif cyhoeddi	4
Dyddiad ar-lein cynnar	19 Tach 2007
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1162/evco.2007.15.4.435
Statws	Cyhoeddwyd - 01 Rhag 2007

Mynediad at Ddogfen

10.1162/evco.2007.15.4.435

Cysylltiad parhaol

Dolen barhaus

Ffeiliau eraill a chysylltiadau

http://hdl.handle.net/2160/13241

Dyfynnu hyn

@article{101f992cae5549ee9c54fb8889d88521,

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 = "black-box optimiazation, evolutionary algorithm, problem difficulty measure, running time, satisfiability problem",

author = "Jun He and Colin Reeves and Carsten Witt and Xin Yao",

note = "He, J., Reeves, C., Witt, C., Yao, X. (2007). A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Realizations and Predictability. Evolutionary Computation, 15 (4), 435-443",

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 = "MIT Press",

number = "4",

}

TY - JOUR

T1 - A Note on Problem Difficulty Measures in Black-Box Optimization

T2 - Classification, Realizations and Predictability

AU - He, Jun

AU - Reeves, Colin

AU - Witt, Carsten

AU - Yao, Xin

N1 - He, J., Reeves, C., Witt, C., Yao, X. (2007). A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Realizations and Predictability. Evolutionary Computation, 15 (4), 435-443

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 - black-box optimiazation

KW - evolutionary algorithm

KW - problem difficulty measure

KW - running time

KW - satisfiability problem

UR - http://hdl.handle.net/2160/13241

U2 - 10.1162/evco.2007.15.4.435

DO - 10.1162/evco.2007.15.4.435

M3 - Article

SN - 1063-6560

VL - 15

SP - 435

EP - 443

JO - Evolutionary Computation

JF - Evolutionary Computation

IS - 4

ER -

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

Crynodeb

Mynediad at Ddogfen

Cysylltiad parhaol

Ffeiliau eraill a chysylltiadau

Ôl bys

Dyfynnu hyn