Изменения
→Введение в Black-box Complexity
Целью [[Теория_сложности|теории сложности]] является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае [[Эволюционные_алгоритмы|эволюционных алгоритмов]], алгоритм обладает информацией только о качестве (значении функции приспособленности) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы.
'''Black-box Complexity''' <ref name="bbox">[http://dl.acm.org/citation.cfm?doid=2001576.2001851 Doerr B., Kötzing T., Winzen C. Too fast unbiased black-box algorithms]</ref> — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box'' сложность алгоритма — количество вычислений функции приспособленности, необходимое для получения решения. Такое определение позволяет получить нереалистично низкие оценки ''black-box'' сложности, например, полиномиальную сложность для [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полной]] задачи поиска максимальной клики <ref name="bbox"/><ref>[http://en.wikipedia.org/wiki/Clique_problem Clique problem]</ref>.
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''несмещенные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Также было введено понятие '''арности''' — <tex>k</tex>-арный несмещенный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box'' сложности позволяет получить более реалистичные оценки вычислительной трудности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В настоящей статье показано, что даже для алгоритмов, использующих только мутационные операторы, можно получить нереалистично маленькую оценку ''black-box'' сложности.
