Изменения
Введение, обозначения
{{В разработке}}
{{Boring}}
== Black-box Complexity. Примеры нереалистичных оценок Black-box Complexity ==
=== Введение в Black-box complexity ===
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''fitness'' функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.
'''Black-box Complexity''' — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box complexity'' алгоритма — количество вычислений ''fitness'' функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки ''black-box complexity'', например, полиномиальную сложность для NP-полной задачи поиска максимальной клики.
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''несмещенные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Так же введено понятие '''арности''' — <tex>k</tex>-арный несмещенный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box complexity'' позволяет получить более реалистичные оценки сложности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В данной статье показано, что даже для алгоритмов, использующих только мутационные операторы можно получить не реалистично маленькую оценку ''black-box complexity''.
=== Обозначения ===
*<tex>N</tex> — положительные целые числа
*<tex>\forall k \in N</tex>
:<tex>[k] := \{1, \ldots , k\}</tex>
*<tex>[0..k] := [k] \cup \{0\}</tex>
*Для битовой строки <tex>x = x_1 \cdots x_n \in \{0, 1\}^n</tex>
:<tex>\overline{x}</tex> — побитовое дополнение строки <tex>x</tex>
*<tex>\bigoplus</tex> — побитовое исключающее или
*Для любого множества <tex>S</tex>
:<tex>2^S</tex> — множество всех подмножеств множества <tex>S</tex>
*Для <tex>n \in N</tex>
:<tex>S_n</tex> — множество всех перестановок <tex>[n]</tex>
*Для <tex>\sigma \in S_n</tex> и <tex>x \in \{0,1\}^n</tex>
:<tex>\sigma(x) := x_{\sigma(1)} \cdots x_{\sigma(n)}</tex>
*Под <tex>log</tex> понимается натуральный логарифм
{{Boring}}
== Black-box Complexity. Примеры нереалистичных оценок Black-box Complexity ==
=== Введение в Black-box complexity ===
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''fitness'' функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.
'''Black-box Complexity''' — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box complexity'' алгоритма — количество вычислений ''fitness'' функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки ''black-box complexity'', например, полиномиальную сложность для NP-полной задачи поиска максимальной клики.
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''несмещенные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Так же введено понятие '''арности''' — <tex>k</tex>-арный несмещенный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box complexity'' позволяет получить более реалистичные оценки сложности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В данной статье показано, что даже для алгоритмов, использующих только мутационные операторы можно получить не реалистично маленькую оценку ''black-box complexity''.
=== Обозначения ===
*<tex>N</tex> — положительные целые числа
*<tex>\forall k \in N</tex>
:<tex>[k] := \{1, \ldots , k\}</tex>
*<tex>[0..k] := [k] \cup \{0\}</tex>
*Для битовой строки <tex>x = x_1 \cdots x_n \in \{0, 1\}^n</tex>
:<tex>\overline{x}</tex> — побитовое дополнение строки <tex>x</tex>
*<tex>\bigoplus</tex> — побитовое исключающее или
*Для любого множества <tex>S</tex>
:<tex>2^S</tex> — множество всех подмножеств множества <tex>S</tex>
*Для <tex>n \in N</tex>
:<tex>S_n</tex> — множество всех перестановок <tex>[n]</tex>
*Для <tex>\sigma \in S_n</tex> и <tex>x \in \{0,1\}^n</tex>
:<tex>\sigma(x) := x_{\sigma(1)} \cdots x_{\sigma(n)}</tex>
*Под <tex>log</tex> понимается натуральный логарифм
