Изменения
Нет описания правки
{{В разработке}}
== Введение в Black-box complexity ==
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''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 модель ===
Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление ''fitness'' -функции возможных решений. Заданная ''fitness'' -функция вычисляется ''ораклом'', или дается как ''black-box''. Алгоритм может запросить у ''оракла'' значение функции для любого решения, однако более никакой информации о решении получить не может.
В качестве ''fitness'' -функции берется псевдо-булевая функция <tex>F:\{0,1\}^n \rightarrow \mathbb{R}</tex>.
Согласно концепции ''black-box'', алгоритм может включать следующие действия:
*выбор вероятностного распределения над <tex>\{0,1\}^n</tex>;
*выбор кандидата <tex>x \in \{0,1\}^n</tex> cогласно выбранному распределению;
*запрос значения ''fitness'' -функции выбранного кандидата у ''оракла''.
Схема неограниченного ''black-box'' алгоритма:
== Задача о разбиении ==
{{Задача
|definition=Задача о разбиении (<tex>Partition</tex> problem) ставится следующим образом. Дано мультимножество <tex>\mathcal{I}</tex> положительных целых чисел (весов). Возможно ли разбить его на два непересекающихся множества <tex>\mathcal{I}=\mathcal{I}_0 \cup \mathcal{I}_1</tex> таким образом, что <tex>\Sigma_{w \in \mathcal{I}_0} w = \Sigma_{w \in \mathcal{I}_1} w</tex>?
}}
Оптимизационная версия задачи ставит вопрос о минимизации функции <tex>|\Sigma_{w \in \mathcal{I}_0} w - \Sigma_{w \in \mathcal{I}_1} w|</tex>.
Задача <tex>Partition</tex> является <tex>\mathrm{NP}</tex>-трудной. Предположительно <tex>\mathrm{P} \neq \mathrm{NP}</tex> и не существует полиномиального алгоритма решения этой задачи.
{{Лемма
|id=lemma5
|statement=Задача <tex>Partition</tex> остается <tex>\mathrm{NP}</tex>-трудной, когда <tex>\forall v, w \in \mathcal{I}: v \neq w</tex>.
|proof=
}}
Далее <tex>Partition_{\neq}</tex> — подкласс задачи <tex>Partition</tex> с взятыми различными весами.
Предлагаются две различные ''fitness''-функции и показывается, что в обоих случаях может быть достигнута полиномиальная несмещенная ''black-box'' сложность. Показывается, что унарная несмещенная ''black-box'' сложность для задачи <tex>Partition_{\neq}</tex> равна <tex>O(n \log(n))</tex>.
=== Знаковая ''fitness''-функция ===
Полагаем <tex>\mathcal{F}_{\mathcal{I}} := \{(\mathcal{I}_0, \mathcal{I}_1) \in 2^{\mathcal{I}} \times 2^{\mathcal{I}} | \mathcal{I}_0 \dot{\cup} \mathcal{I}_1 = \mathcal{I}\}</tex> — множество всех возможных решений для <tex>\mathcal{I}</tex>. Определим знаковую ''fitness''-функцию как:
:<tex>f_{\mathcal{I}}^{*}: \mathcal{F} \rightarrow \mathbb{Z}, (\mathcal{I}_0, \mathcal{I}_1) \mapsto \Sigma_{w \in \mathcal{I}_0} w - \Sigma_{w \in \mathcal{I}_1} w</tex>.
Цель заключается в минимизации <tex>|f_{\mathcal{I}}^{*}|</tex>.
Зафиксируем нумерацию элементов <tex>\mathcal{I}</tex>: <tex>\sigma: \mathcal{I} \rightarrow [n]</tex>. Для любой битовой строки <tex>x \in \{0,1\}^n</tex> определим <tex>\mathcal{I}_0(x) := \{w \in \mathcal{I} | x_{\sigma{w}} = 0\}</tex> и <tex>\mathcal{I}_1(x) := \{w \in \mathcal{I} | x_{\sigma{w}} = 1\}</tex>. Тогда ''fitness''-функция выглядит так:
:<tex>f_{\mathcal{I}}: \{0,1\}^n \rightarrow \mathbb{Z}, x \mapsto \Sigma_{i \in [n], x_i=0} \sigma^{-1}(i) - \Sigma_{i \in [n], x_i=1} \sigma^{-1}(i)</tex>.
{{Теорема
|id=th6
|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>uniform()</tex> — выбирает случайную битовую строку <tex>x \in \{0,1\}^n</tex>;
:*<tex>RLS(\cdot)</tex> — случайно меняет элемент в одной из позиций входной строки.
Для краткости положим <tex>f := f_{\mathcal{I}}</tex>.
Следующий алгоритм служит доказательством теоремы:
1 '''Инициализация'''
2 <tex>x^{(0)} \leftarrow uniform()</tex>. Запрос <tex>f(x^{(0)})</tex>;
3 <tex>t \leftarrow 0, \mathcal{I}_0', \mathcal{I}_1', \mathcal{W}_0 = \varnothing</tex>;
4 '''Определение весов'''
5 '''while''' <tex>|\mathcal{W}_t| < n</tex> '''do'''
6 <tex>t \leftarrow t + 1</tex>;
7 <tex>x^{(t)} \leftarrow RLS(x^{(0)})</tex>. Запрос <tex>f(x^{(t)})</tex>;
8 <tex>\mathcal{W}_t \leftarrow \mathcal{W}_{t-1} \cup \{|f(x^{(0)}) - f(x^{(t)})|/2\}</tex>;
9 '''if''' <tex>f(x^{(0)}) > f(x^{(t)})</tex> '''then'''
10 <tex>\mathcal{I}_0' \leftarrow \mathcal{I}_0' \cup {|f(x^{(0)}) - f(x^{(t)})|/2}</tex>;
11 '''else''' <tex>\mathcal{I}_1' \leftarrow \mathcal{I}_1' \cup {|f(x^{(0)}) - f(x^{(t)})|/2}</tex>;
12 '''Оптимизация'''
13 В оффлайне вычисляем оптимальное решение <tex>(\mathcal{O}_0, \mathcal{O}_1)</tex> и множество <tex>\mathcal{M} \leftarrow \{w \in \mathcal{O}_0 | w \notin \mathcal{I}_0'\} \cup \{w \in \mathcal{O}_1 | w \notin \mathcal{I}_1'\}</tex> — множество элементов, которые надо переместить.
14 <tex>z \leftarrow x^{(0)}</tex>;
15 '''while''' <tex>|\mathcal{M}| > 0</tex> '''do'''
16 <tex>y \leftarrow RLS(z)</tex>. Запрос <tex>f(y)</tex>;
17 '''if''' <tex>w := |f(y)-f(z)|/2 \in \mathcal{M}</tex> '''then'''
18 <tex>z \leftarrow y</tex>, <tex>\mathcal{M} \leftarrow \mathcal{M} \backslash \{w\}</tex>;
За <tex>(1+o(1))n \log(n)</tex> итераций будут определены веса всех элементов <tex>\mathcal{I}</tex>. Зная веса, можно в оффлайне перебором найти оптимальное решение задачи, после чего надо это решение восстановить с помощью вариативного <tex>1</tex>-арного оператора. Для этого было найдено множество <tex>\mathcal{M}</tex> — множество элементов, которые необходимо переместить для получения оптимального решения. В итоге получается, что несмещенная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно заданной ''fitness''-функции равна <tex>O(n \log(n))</tex>.
}}
=== Беззнаковая ''fitness''-функция ===
