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

Эта статья находится в разработке!

Эта статья сделана из уныния и отчаяния. Сделайте с ней что-нибудь. Пожалуйста.

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

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

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

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

Неограниченная и несмещенная Black-box модели

Обозначения

• [math]\mathbb{N}[/math] — положительные целые числа;
• [math]\forall k \in \mathbb{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 \mathbb{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] понимается натуральный логарифм.

Неограниченная Black-box модель

Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление fitness функции возможных решений. Заданная fitness функция вычисляется ораклом, или дается как black-box. Алгоритм может запросить у оракла значение функции для любого решения, однако более никакой информации о решении получить не может.

В качестве fitness функции берется псевдо-булевая функция [math]F:\{0,1\}^n \rightarrow \mathbb{R}[/math].

Согласно концепции black-box, алгоритм может включать следующие действия:

• выбор вероятностного распределения над [math]\{0,1\}^n[/math];
• выбор кандидата [math]x \in \{0,1\}^n[/math] cогласно выбранному распределению;
• запрос значения fitness функции выбранного кандидата у оракла.

Схема неограниченного black-box алгоритма:

Инициализация: выбрать [math]x^{(0)}[/math] согласно некоторому вероятностному распределению [math]p^{(0)}[/math] над [math]\{0,1\}^n[/math]. Запросить [math]f(x^{(0)})[/math].
Оптимизация: for [math]t = 1, 2, 3, \ldots [/math] until условие остановки do
  Исходя из [math]((x^{(0)}, f(x^{(0)}), \ldots, (x^{(t-1)}, f(x^{(t-1)}))[/math], выбрать вероятностное распределение [math]p^{(t)}[/math] над [math]\{0,1\}^n[/math].
  Выбрать [math]x^{(t)}[/math] согласно [math]p^{(t)}[/math] и запросить [math]f(x^{(t)})[/math].

В качестве времени работы black-box алгоритма берется количество запросов к ораклу сделанное до первого запроса с оптимальным решением.

Пусть [math]\mathcal{F}[/math] — класс псевдо-булевых функций. Сложностью алгоритма [math]A[/math] над [math]\mathcal{F}[/math] называется максимальное предположительное время работы [math]A[/math] на функции [math]f \in \mathcal{F}[/math] (в худшем случае). Сложностью [math]\mathcal{F}[/math] относительно класса алгоритмов [math]\mathcal{A}[/math] называется минимальная сложность среди всех [math]A \in \mathcal{A}[/math] над [math]\mathcal{F}[/math]. Неограниченной black-box сложностью [math]\mathcal{F}[/math] называется сложность [math]\mathcal{F}[/math] относительно класса неограниченных black-box алгоритмов.

Несмещенная Black-box модель

Класс неограниченных black-box алгоритмов слишком мощный. Например для любого функционального класса [math]\mathcal{F} = \{f\}[/math] неограниченная black-box сложность равна единице — алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию.

Чтобы избежать этих недостатков была введена более строгая модель. В ней алгоритмы могут генерировать новые решения используя только несмещенные вариативные операторы.

Определение:

[math]\forall k \in \mathbb{N}, k[/math]-арным несмещенным распределением [math](D(\cdot|y^{(1)},\ldots,y^{(k)}))_{y^{(1)},\ldots,y^{(k)} \in \{0,1\}^n}[/math] называется семейство вероятностных распределений над [math]\{0,1\}^n[/math] таких, что для любых [math]y^{(1)},\ldots,y^{(k)} \in \{0,1\}^n[/math] выполняются следующие условия: [math]\forall x, z \in \{0,1\}^n[/math]: [math]D(x|y^{(1)},\ldots,y^{(k)}) = D(x \bigoplus z|y^{(1)} \bigoplus z,\ldots,y^{(k)} \bigoplus z)[/math]; [math]\forall x \in \{0,1\}^n \forall \sigma \in S_n[/math]: [math]D(x|y^{(1)},\ldots,y^{(k)}) = D(\sigma(x)|\sigma(y^{(1)}),\ldots,\sigma(y^{(k)}))[/math].

Первое условие называется [math]\bigoplus[/math]-инвариантностью, второе — перестановочной инвариантностью. Оператор, выбранный из [math]k[/math]-арного несмещенного распределения называется [math]k[/math]-арным несмещенным вариативным оператором.

Схема [math]k[/math]-арного несмещенного black-box алгоритма:

Инициализация: выбрать [math]x^{(0)}[/math] равновероятно из [math]\{0,1\}^n[/math]. Запросить [math]f(x^{(0)})[/math].
Оптимизация: for [math]t = 1, 2, 3, \ldots [/math] until условие остановки do
  Исходя из [math](f(x^{(0)}), \ldots, f(x^{(t-1)}))[/math], выбрать [math]k[/math] индексов [math]i_1, \ldots, i_k \in [0..t-1][/math] и [math]k[/math]-арное несмещенное распределение [math]D(\cdot|x^{(i_1)},\ldots,x^{(i_k)})[/math].
  Выбрать [math]x^{(t)}[/math] согласно [math]D(\cdot|x^{(i_1)},\ldots,x^{(i_k)})[/math] и запросить [math]f(x^{(t)})[/math].