Изменения
Нет описания правки
'''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'' сложность алгоритма — количество вычислений функции приспособленности, необходимое для получения решения. Такое определение позволяет получить нереалистично низкие оценки ''black-box'' сложности, например, полиномиальную сложность для [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полной]] задачи поиска максимальной клики <ref name="bbox"/><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 модели ==
=== Обозначения ===
*<tex>\mathbb{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> понимается натуральный логарифм.
Выбрать <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'' алгоритмов.
=== Несмещенная Беспристрастная Black-box модель ===
Класс неограниченных ''black-box'' алгоритмов слишком мощный. Например для любого функционального класса <tex>\mathcal{F} = \{f\}</tex> неограниченная ''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>\forall x, z \in \{0,1\}^n</tex>:
:<tex>D(x|y^{(1)},\ldots,y^{(k)}) = D(x \bigoplus z|y^{(1)} \bigoplus z,\ldots,y^{(k)} \bigoplus z)</tex>;
}}
Первое условие называется <tex>\bigoplus</tex>-инвариантностью, второе — перестановочной инвариантностью. Оператор, выбранный из <tex>k</tex>-арного несмещенного беспристрастного распределения , называется '''<tex>k</tex>-арным несмещенным беспристрастным вариативным оператором'''.
Схема <tex>k</tex>-арного несмещенного беспристрастного ''black-box'' алгоритма:
'''Инициализация:''' выбрать <tex>x^{(0)}</tex> равновероятно из <tex>\{0,1\}^n</tex>. Запросить <tex>f(x^{(0)})</tex>.
'''Оптимизация:''' '''for''' <tex>t = 1, 2, 3, \ldots </tex> '''until''' ''условие остановки'' '''do'''
Исходя из <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>.
Выбрать <tex>x^{(t)}</tex> согласно <tex>D(\cdot|x^{(i_1)},\ldots,x^{(i_k)})</tex> и запросить <tex>f(x^{(t)})</tex>.
:<tex>Jump_k(x) = \left\{ \begin{array}{ccc} n, & if & |x|_1=n; \\ |x|_1, & if & k < |x|_1 < n-k; \\ 0, & & otherwise, \end{array}\right.</tex>
:<tex>\forall x \in \{0,1\}^n.</tex>, где <tex>|\cdot|_1</tex> — количество единиц в битовой строке.
}}
Далее будет показано, что для любого константного <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> нереалистично мала.
{{Лемма
|id=lemma3
|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> других строк из выборки приведет к нужному результату — функция вернет количество единиц в строке <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> единиц:
}}
Теперь, используя [[#lemma3|предыдущую лемму]], можно найти несмещенную беспристрастную ''black-box'' сложность для функции <tex>Jump_k</tex> при константном <tex>k</tex>.
{{Теорема
|id=th4
|statement=Для константы <tex>k</tex> несмещенная беспристрастная ''black-box'' сложность <tex>Jump_k</tex>:
*<tex>O(n \log(n))</tex> для унарных вариативных операторов;
Далее <tex>Partition_{\neq}</tex> — подкласс задачи <tex>Partition</tex> с заданными различными весами.
Далее предлагаются две различные функции приспособленности и показывается, что в обоих случаях может быть достигнута полиномиальная несмещенная беспристрастная ''black-box'' сложность. Показывается, что унарная несмещенная беспристрастная ''black-box'' сложность для задачи <tex>Partition_{\neq}</tex> равна <tex>O(n \log(n))</tex>.
=== Знаковая функция приспособленности ===
{{Теорема
|id=th6
|statement=Унарная несмещенная беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно функции приспособленности <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> относительно заданной функции приспособленности равна <tex>O(n \log(n))</tex>. Полное доказательство приведено в работе <ref name="bbox"/>.
}}
{{Теорема
|id=th8
|statement=Унарная несмещенная беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно функции приспособленности <tex>|f_{\mathcal{I}}|</tex> равна <tex>O(n \log(n))</tex>. Где <tex>n := |\mathcal{I}|</tex>.
|proof=Для краткости полагается:
:*<tex>f := |f_{\mathcal{I}}|</tex>;
}}
== Ссылки Источники ==
<references/>
[[Категория:Теория сложности]]
[[Категория:Эволюционные алгоритмы]]
