Изменения

{{В разработке}}== Введение в Black-box complexity 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> &mdash; попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box'' сложность алгоритма &mdash; количество вычислений ''fitness''-функцииприспособленности, необходимое для получения решения. Такое определение позволяет получить не реалистично нереалистично низкие оценки ''black-box'' сложности, например, полиномиальную сложность для [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полной]] задачи поиска максимальной клики <ref name="bbox"/><ref>[http://en.wikipedia.org/wiki/Clique_problem Clique problem]</ref>.

По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''несмещенныебеспристрастные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Также было введено понятие '''арности''' &mdash; <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>.

*запрос значения ''fitness''-функции приспособленности выбранного кандидата у ''ораклаоракула''.

Исходя из <tex>((x^{(0)}, f(x^{(0)})), \ldots, (x^{(t-1)}, f(x^{(t-1)})))</tex>, выбрать вероятностное распределение <tex>p^{(t)}</tex> над <tex>\{0,1\}^n</tex>.

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

=== Несмещенная Беспристрастная Black-box модель ===

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

|definition=<tex>\forall k \in \mathbb{N}, k</tex>-арным несмещенным беспристрастным распределением <tex>(D(\cdot|y^{(1)},\ldots,y^{(k)}))_{y^{(1)},\ldots,y^{(k)} \in \{0,1\}^n}</tex> называется семейство вероятностных распределений над <tex>\{0,1\}^n</tex> таких, что для любых <tex>y^{(1)},\ldots,y^{(k)} \in \{0,1\}^n</tex> выполняются следующие условия:

Первое условие называется <tex>\bigoplus</tex>-инвариантностью, второе &mdash; перестановочной инвариантностью. Оператор, выбранный из <tex>k</tex>-арного несмещенного беспристрастного распределения , называется '''<tex>k</tex>-арным несмещенным беспристрастным вариативным оператором'''.

Схема <tex>k</tex>-арного несмещенного беспристрастного ''black-box'' алгоритма:

Исходя из <tex>(f(x^{(0)}), \ldots, f(x^{(t-1)}))</tex>, выбрать <tex>k</tex> индексов <tex>i_1, \ldots, i_k \in [0..t-1]</tex> и <tex>k</tex>-арное несмещенное беспристрастное распределение <tex>D(\cdot|x^{(i_1)},\ldots,x^{(i_k)})</tex>.

|statement=Предположим, что Пусть для задачи <tex>P</tex> существует ''black-box'' алгоритм <tex>A</tex>, который с константной вероятностью успеха решает <tex>P</tex> за <tex>s</tex> итераций. Тогда ''black-box'' сложность <tex>P</tex> не больше <tex>O(s)</tex>.

== Jump функции функция ==

|definition=<tex>\forall k < n/2</tex> функция <tex>Jump_k</tex> определяется какследующим образом:

:<tex>\forall x \in \{0,1\}^n.</tex>, где <tex>|\cdot|_1</tex> &mdash; количество единиц в битовой строке.

Будет Далее будет показано, что для любого константного <tex>k</tex> можно с высокой вероятностью решить проблему задачу <tex>OneMax</tex> <ref>[http://tracer.lcc.uma.es/problems/onemax/onemax.html OneMax problem]</ref> за малое количество ''black-box'' обращений к <tex>Jump_k</tex>. С помощью этого утверждения можно показать, что для любого константного любой константы <tex>k</tex> несмещенная беспристрастная ''black-box'' сложность для функции <tex>Jump_k</tex> удивительно нереалистично мала.

|statement=Для любых <tex>\forall k,</tex> и <tex>c</tex> существует унарная несмещенная процедура беспристрастная функция <tex>s</tex>, использующая <tex>c+1</tex> запросов к <tex>Jump_k</tex> такая, что для всех битовых строк <tex>x</tex>, <tex>s(x) = OneMax(x)</tex> с вероятностью <tex>1 - O(n^{-c})</tex>.|proof=Используется унарный несмещенный беспристрастный вариативный оператор <tex>flip_k</tex>, который равновероятно выбирает строку из <tex>k</tex>-окрестности для аргумента (битовую строку, которая отличается в <tex>k</tex> позициях). Затем будет использована процедура Ниже предлагается функция <tex>s</tex>, которая использует <tex>Jump_k</tex> для аппроксимации <tex>OneMax</tex> как показано ниже. Процедура Функция выбирает <tex>c</tex> битовых строк в <tex>k</tex>-окрестности <tex>x</tex>. Если <tex>|x|_1 \geq n-k</tex>, то правдоподобноесть вероятность того, что хотя бы раз только единицы из в <tex>x</tex> будут замененытолько единицы, что приведет к тому, что <tex>Jump_k = |x|_1 - k</tex>. Так как больше никакая строка из выборки не будет иметь более низкое меньшее <tex>Jump_k</tex> значение, то добавление <tex>k</tex> к минимальному ненулевому значению <tex>Jump_k</tex> других строк из выборки приведет к нужному результату&mdash; функция вернет количество единиц в строке <tex>x</tex>. Случай, когда <tex>|x|_1 \leq k</tex>, аналогичен.

Понятно, что процедура верна функция корректна при всех <tex>x</tex>, таких, что <tex>k < |x|_1 < n-k</tex>. Остальные два случая симметричны, поэтому пусть <tex>|x|_1 \geq n-k</tex>. Очевидно, что результат процедуры функции корректен тогда и только тогда, когда хотя бы в одной из <tex>c</tex> строк были заменены только единицы. Вычислим Требуется вычислить вероятность <tex>p</tex> этого события. Мы выбираем Итеративно выбираются <tex>k</tex> бит для замены итеративно, поэтому после <tex>i</tex> итераций имеется как минимум <tex>n-k-i</tex> позиций с единицей из <tex>n-i</tex> невыбранных позиций. Отсюда, которые можно выбиратьс использованием неравенства Бернулли <ref>[http://en. Это приводит к границе wikipedia.org/wiki/Bernoulli%27s_inequality Bernoulli's inequality]</ref>, получается граница на вероятность выбора <tex>k</tex> единиц:

:<tex>(\frac{n-k}{n})\cdot(\frac{n-k-1}{n-1})\cdots(\frac{n-k-(k-1)}{n-(k-1)}) = \Pi_{i=0}^{k-1}(1 - \frac{k}{n-i}) \geq (1 - \frac{k}{n-k})^k \geq (1 - \frac{k^2}{n-k}),</tex>.

используя неравенство Бернулли. Таким образом имеем:

Процедура Функция <tex>s</tex>:

Теперь, используя [[#lemma3|предыдущую лемму]], можно найти несмещенную беспристрастную ''black-box'' сложность для функции <tex>Jump_k</tex> при константном <tex>k</tex>.

|statement=Для константы <tex>k</tex> несмещенная беспристрастная ''black-box'' сложность <tex>Jump_k</tex>:

Процедуре Функции из [[#lemma3|предыдущей леммы]] для работы необходимо знание параметра знать параметр <tex>k</tex>. Процедуру , но ее можно модифицировать таким образом, что она будет работать без этого знания. Как только процедура функция впервые выберет случайную битовую строку с <tex>Jump_k=0</tex> она определит <tex>k</tex>, затем продолжит работу как было описано раньшевыше. Параметр <tex>k</tex> определяется с помощью выбора достаточно большого количества случайных строк в <tex>i</tex>-окрестности от строки с <tex>Jump_k=0</tex>, начиная с <tex>i=1</tex> и продолжая до тех пор, пока <tex>Jump_k</tex> не станет отличным от нуля. Эта Найденная строка будет иметь максимальное значение <tex>Jump_k=n-k-1</tex>. Из этого значения и <tex>n</tex> процедура функция может вычислить <tex>k</tex>.

|definition=Задача о разбиении<ref>[http://en.wikipedia.org/wiki/Partition_problem Partition problem]</ref> (<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>Partition_{\neq}</tex> &mdash; подкласс задачи <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> &mdash; множество всех возможных решений для <tex>\mathcal{I}</tex>. Определим знаковую ''fitness''-функцию какЗнаковая функция приспособленности определяется следующим образом:

Зафиксируем Необходимо ввести нумерацию элементов <tex>\mathcal{I}</tex>: &mdash; <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''-функция выглядит такприспособленности преобразуется к следующему виду:

|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>.

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> &mdash; множество элементов, которые надо необходимо переместить.

За <tex>(1+o(1))n \log(n)</tex> итераций будут определены определяются веса всех элементов <tex>\mathcal{I}</tex>. Зная весаэлементов, можно в оффлайне перебором найти находится оптимальное решение задачи, после чего надо это решение необходимо восстановить с помощью вариативного <tex>1</tex>-арного оператора. Для этого было найдено построено множество <tex>\mathcal{M}</tex> &mdash; множество элементов, которые необходимо переместить для получения оптимального решения. В итоге получается, что несмещенная беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно заданной ''fitness''-функции приспособленности равна <tex>O(n \log(n))</tex>. Полное доказательство приведено в работе <ref name="bbox"/>.

=== Беззнаковая ''fitness''-функция приспособленности ===Кому-то может не понравитьсяМожно заметить, что при доказательстве [[#th6|предыдущей теоремы]] происходила минимизация не самой функции <tex>f_{\mathcal{I}}</tex>, а только ее абсолютной величины. Однако можно достичь той та же асимптотики асимптотика достигается и для беззнаковой ''fitness''-функцииприспособленности. Сложность заключается в том, что теперь в этом случае нельзя просто определить вес перемещенного элемента. Этот факт выражается в более сложной процедуре для определения весов элементов.

|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>\mathcal{I}_{max(x)}</tex> &mdash; множество элементов, принадлежащих корзине с большим весом. Например , <tex>\mathcal{I}_{max(x)} = \mathcal{I}_0</tex> если <tex>S_0(x) \geq S_1(x)</tex>;

:*сгенерировать строкугенерируется строка, такуютакая, что все ее элементы находятся в одной корзине (с большой вероятностью это можно сделать за <tex>4n \log(n)</tex> запросов);:*за <tex>2n \log(n)</tex> шагов с помощью <tex>RLS(\cdot)</tex> опеределить опеределяются веса всех элементов (с большой вероятностью);:*за <tex>3n \log(n)</tex> шагов восстановить восстанавливаетчся решение (с большой вероятностью).

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>;

== Ссылки Источники ==