Olika metoder har definierats för att mäta hårdheten hos en fitnessfunktion för evolutionära algoritmer och andra svart-box heuristiker. Exempel är fitness landskapsanalys, epistasis, fitness-distans korrelationer etc., som alla är relativt lätta att beskriva. De anger dock inte alltid korrekt funktionens hårdhet. Vissa åtgärder är lätta att genomföra, andra är mer intuitiva och svåra att formalisera. Detta papper definierar noggrant svårighetsåtgärder i svart-box optimering och föreslår en klassificering. Olika typer av insikter om sådana åtgärder studeras, nämligen exakta och ungefärliga sådana. För båda typerna av insikter, är det bevisat att prediktiva versioner som körs i polynom tid i allmänhet inte existerar om inte vissa komplexitet-teoretiska antaganden är fel.
REF gav en strikt definition av svårighetsåtgärder vid optimering av svarta lådor, och visade att i allmänhet prediktiva svårigheter som löper i polynom tid inte finns om inte vissa komplexa-teoretiska antaganden är felaktiga.
A Note on Problem Difficulty Measures in Black-Box Optimization: Classification, Realizations and Predictability
{'venue': 'Evolutionary Computation', 'journal': 'Evolutionary Computation', 'mag_field_of_study': ['Computer Science', 'Medicine', 'Mathematics']}