Изменения
Нет описания правки
{{В разработке}}
== Введение в Black-box complexity ==
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''fitness'' функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.
Исходя из <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>.
{{Лемма
|id=remark2
|statement=Предположим, что для задачи <tex>P</tex> существует ''black-box'' алгоритм <tex>A</tex>, который с константной вероятностью успеха решает <tex>P</tex> за <tex>s</tex> итераций. Тогда ''black-box'' сложность <tex>P</tex> не больше <tex>O(s)</tex>.
|proof=
}}
== Jump функции ==
{{Определение
|definition=<tex>\forall k < n/2</tex> функция <tex>Jump_k</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>k</tex> можно с высокой вероятностью решить проблему <tex>OneMax</tex> за малое количество ''black-box'' обращений к <tex>Jump_k</tex>. С помощью этого можно показать, что для любого константного <tex>k</tex> несмещенная ''black-box'' сложность для функции <tex>Jump_k</tex> удивительно мала.
{{Лемма
|id=lemma3
|statement=<tex>\forall k,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|_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> позиций, которые можно выбирать. Это приводит к границе на вероятность выбора единиц:
:<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>p \geq 1 - (\frac{k^2}{n-k})^c</tex>.
Процедура <tex>s</tex>:
'''if''' <tex>Jump_k(x) \neq 0</tex> '''then output''' <tex>Jump_k(x)</tex>;
<tex>M \leftarrow \{Jump_k(flip_k(x)) | i \in [c]\}</tex>;
'''if''' <tex>max(M) < n/2</tex> '''then''' <tex>m \leftarrow max(M) - k</tex>;
'''else''' <tex>m \leftarrow min(M \backslash \{0\}) + k</tex>;
'''output''' <tex>m</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>O(n / \log(m))</tex> для <tex>m</tex>-арных вариативных операторов при <tex>2 \leq m \leq n</tex>;
*<tex>O(n / \log(n))</tex> для *-арных вариативных операторов.
|proof=
}}
Процедуре из [[#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>.
== Задача о разбиении ==
