Black-box Complexity. Примеры нереалистичных оценок Black-box Complexity — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Введение, обозначения)
(нет различий)

Версия 17:51, 17 июня 2012

Эта статья находится в разработке!
nothumb
Эта статья сделана из уныния и отчаяния.
Сделайте с ней что-нибудь.
Пожалуйста.

Black-box Complexity. Примеры нереалистичных оценок Black-box Complexity

Введение в Black-box complexity

Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении fitness функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.

Black-box Complexity — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, black-box complexity алгоритма — количество вычислений fitness функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки black-box complexity, например, полиномиальную сложность для NP-полной задачи поиска максимальной клики.

По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только несмещенные (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) вариативные операторы. Так же введено понятие арности[math]k[/math]-арный несмещенный black-box алгоритм использует только те операторы, которые принимают не более чем [math]k[/math] аргументов. Для некоторых классов задач такой подход к опеределению black-box complexity позволяет получить более реалистичные оценки сложности. Операторы с арностью [math]1[/math] называют мутационными. В данной статье показано, что даже для алгоритмов, использующих только мутационные операторы можно получить не реалистично маленькую оценку black-box complexity.

Обозначения

  • [math]N[/math] — положительные целые числа
  • [math]\forall k \in N[/math]
[math][k] := \{1, \ldots , k\}[/math]
  • [math][0..k] := [k] \cup \{0\}[/math]
  • Для битовой строки [math]x = x_1 \cdots x_n \in \{0, 1\}^n[/math]
[math]\overline{x}[/math] — побитовое дополнение строки [math]x[/math]
  • [math]\bigoplus[/math] — побитовое исключающее или
  • Для любого множества [math]S[/math]
[math]2^S[/math] — множество всех подмножеств множества [math]S[/math]
  • Для [math]n \in N[/math]
[math]S_n[/math] — множество всех перестановок [math][n][/math]
  • Для [math]\sigma \in S_n[/math] и [math]x \in \{0,1\}^n[/math]
[math]\sigma(x) := x_{\sigma(1)} \cdots x_{\sigma(n)}[/math]
  • Под [math]log[/math] понимается натуральный логарифм