Изменения
Нет описания правки
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''fitness''-функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.
'''Black-box Complexity''' — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box complexity'' сложность алгоритма — количество вычислений ''fitness''-функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки ''black-box complexity''сложности, например, полиномиальную сложность для <tex>\mathrm{NP}</tex>-полной задачи поиска максимальной клики.
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''несмещенные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Так же введено понятие '''арности''' — <tex>k</tex>-арный несмещенный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box complexity'' сложности позволяет получить более реалистичные оценки сложности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В данной статье показано, что даже для алгоритмов, использующих только мутационные операторы можно получить не реалистично маленькую оценку ''black-box complexity''сложности.
== Неограниченная и несмещенная Black-box модели ==
=== Обозначения ===
*<tex>\mathbb{N}</tex> — положительные целые числа;
*<tex>\forall k \in \mathbb{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 \mathbb{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> понимается натуральный логарифм.
=== Беззнаковая ''fitness''-функция ===
Кому-то может не понравиться, что при доказательстве [[#th6|предыдущей теоремы]] происходила минимизация не самой функции <tex>f_{\mathcal{I}}</tex>, а только ее абсолютной величины. Однако можно достичь той же асимптотики и для беззнаковой ''fitness''-функции. Сложность заключается в том, что теперь нельзя просто определить вес перемещенного элемента. Этот факт выражается в более сложной процедуре для определения весов элементов.
{{Теорема
|id=th8
|statement=Унарная несмещенная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно ''fitness''-функции <tex>|f_{\mathcal{I}}|</tex> равна <tex>O(n \log(n))</tex>. Где <tex>n := |\mathcal{I}|</tex>.
|proof=Для краткости положим:
:*<tex>f := |f_{\mathcal{I}}|</tex>;
:*<tex>S_0(x) = \Sigma_{w \in \mathcal{I}_0(x)} w</tex>;
:*<tex>S_1(x) = \Sigma_{w \in \mathcal{I}_1(x)} w</tex>;
:*<tex>\mathcal{I}_{max(x)}</tex> — множество элементов, принадлежащих корзине с большим весом. Например <tex>\mathcal{I}_{max(x)} = \mathcal{I}_0</tex> если <tex>S_0(x) \geq S_1(x)</tex>;
:*<tex>w_{max} = \max \mathcal{I}</tex> — элемент с максимальным весом.
Общая идея алгоритма состоит в следующем:
:*сгенерировать строку, такую, что все элементы находятся в одной корзине (с большой вероятностью это можно сделать за <tex>4n \log(n)</tex> запросов);
:*за <tex>2n \log(n)</tex> шагов с помощью <tex>RLS(\cdot)</tex> опеределить веса всех элементов (с большой вероятностью);
:*за <tex>3n \log(n)</tex> шагов восстановить решение (с большой вероятностью).
Следующий алгоритм является доказательством теоремы:
1 '''Инициализация'''
2 <tex>x^{(1,0)} \leftarrow uniform()</tex>. Запрос <tex>f(x^{(1,0)})</tex>;
3 '''Перемещение всех элементов в одну корзину'''
4 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do'''
5 <tex>x^{(1,t)} \leftarrow RLS(x^{(1,0)})</tex>. Запрос <tex>f(x^{(1,t)})</tex>;
6 Пусть <tex>l \in \arg \max_{0 \leq t \leq 2n \log(n)} f(x^{(1,t)})</tex>;
7 <tex>x \leftarrow x^{(1,l)}</tex>;
8 '''for''' <tex>t = 2n \log(n) + 1</tex> '''to''' <tex>4n \log(n)</tex> '''do'''
9 <tex>y \leftarrow RLS(x)</tex>. Запрос <tex>f(y)</tex>;
10 '''if''' <tex>f(y) > f(x)</tex> '''then''' <tex>x \leftarrow y</tex>;
11 '''Определение весов всех элементов'''
12 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do'''
13 <tex>x^{(2,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(2,t)})</tex>;
14 '''Оптимизация'''
15 Вычислить в оффлайне перебором оптимальное решение <tex>(\mathcal{O}_0, \mathcal{O}_1)</tex>, такое что <tex>w_{max} \in \mathcal{O}_1</tex>. <tex>\mathcal{M} \leftarrow \mathcal{O}_1</tex>;
16 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do'''
17 <tex>x^{(3,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(3,t)})</tex>;
18 '''if''' <tex>f(x) > 2w_{max}</tex> '''and''' <tex>f(x^{(3,t)}) < f(x)</tex> '''then'''
19 вычислить <tex>w := (f(x) - f(x^{(3,t)})) / 2</tex>;
20 '''if''' <tex>w \neq w_{max}</tex> '''and''' <tex>w \in \mathcal{M}</tex> '''then'''
21 <tex>x \leftarrow x^{(3,t)}; \mathcal{M} \leftarrow \mathcal{M} \backslash w</tex>;
22 '''for''' <tex>t = 1</tex> '''to''' <tex>n \log(n)</tex> '''do'''
23 <tex>x^{(4,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(4,t)})</tex>;
Можно показать, что приведенный алгоритм с большой вероятностью за <tex>O(n \log(n))</tex> запросов находит оптимальное решение.
}}
== Источники ==
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/p2043.pdf Doerr B., Kotzing T., Winzen C. Too Fast Unbiased Black-Box Algorithms]
