Изменения
Нет описания правки
== Введение в Black-box Complexity ==
Целью [[Теория_сложности|теории сложности]] является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае [[Эволюционные_алгоритмы|эволюционных алгоритмов]], алгоритм обладает информацией только о качестве (значении ''fitness''-функцииприспособленности) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы.
'''Black-box Complexity''' <ref name="bbox">[http://dl.acm.org/citation.cfm?doid=2001576.2001851 Doerr B., Kötzing T., Winzen C. Too fast unbiased black-box algorithms]</ref> — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box'' сложность алгоритма — количество вычислений ''fitness''-функцииприспособленности, необходимое для получения решения. Такое определение позволяет получить нереалистично низкие оценки ''black-box'' сложности, например, полиномиальную сложность для [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полной]] задачи поиска максимальной клики <ref>[http://en.wikipedia.org/wiki/Clique_problem Clique problem]</ref>.
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''несмещенные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Также было введено понятие '''арности''' — <tex>k</tex>-арный несмещенный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box'' сложности позволяет получить более реалистичные оценки вычислительной трудности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В настоящей статье показано, что даже для алгоритмов, использующих только мутационные операторы, можно получить нереалистично маленькую оценку ''black-box'' сложности.
=== Неограниченная 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'' алгоритма:
Выбрать <tex>x^{(t)}</tex> согласно <tex>p^{(t)}</tex> и запросить <tex>f(x^{(t)})</tex>.
В качестве времени работы ''black-box'' алгоритма берется количество запросов к ''ораклуоракулу'' сделанное до первого запроса с оптимальным решением.
Пусть <tex>\mathcal{F}</tex> — класс псевдо-булевых функций. Сложностью алгоритма <tex>A</tex> над <tex>\mathcal{F}</tex> называется максимальное предположительное время работы <tex>A</tex> на функции <tex>f \in \mathcal{F}</tex> (в худшем случае). Сложностью <tex>\mathcal{F}</tex> относительно класса алгоритмов <tex>\mathcal{A}</tex> называется минимальная сложность среди всех <tex>A \in \mathcal{A}</tex> над <tex>\mathcal{F}</tex>. Неограниченной ''black-box'' сложностью <tex>\mathcal{F}</tex> называется сложность <tex>\mathcal{F}</tex> относительно класса неограниченных ''black-box'' алгоритмов.
Далее <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>;
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>. Полное доказательство приведено в работе <ref name="bbox"/>.
}}
=== Беззнаковая ''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>;
