Black-box Complexity. Примеры нереалистичных оценок Black-box Complexity — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 30 промежуточных версий 3 участников)
Строка 1: Строка 1:
{{В разработке}}
+
== Введение в Black-box Complexity ==
== Введение в Black-box complexity ==
+
Целью [[Теория_сложности|теории сложности]] является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае [[Эволюционные_алгоритмы|эволюционных алгоритмов]], алгоритм обладает информацией только о качестве (значении функции приспособленности) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы.
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''fitness'' функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.
 
  
'''Black-box Complexity''' &mdash; попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box complexity'' алгоритма &mdash; количество вычислений ''fitness'' функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки ''black-box complexity'', например, полиномиальную сложность для <tex>\mathrm{NP}</tex>-полной задачи поиска максимальной клики.
+
'''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; количество вычислений функции приспособленности, необходимое для получения решения. Такое определение позволяет получить нереалистично низкие оценки ''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 complexity'' позволяет получить более реалистичные оценки сложности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В данной статье показано, что даже для алгоритмов, использующих только мутационные операторы можно получить не реалистично маленькую оценку ''black-box complexity''.
+
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''беспристрастные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Также было введено понятие '''арности''' &mdash; <tex>k</tex>-арный беспристрастный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box'' сложности позволяет получить более реалистичные оценки вычислительной трудности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В настоящей статье показано, что даже для алгоритмов, использующих только мутационные операторы, можно получить нереалистично маленькую оценку ''black-box'' сложности.
  
== Неограниченная и несмещенная Black-box модели ==
+
== Неограниченная и беспристрастная Black-box модели ==
 
=== Обозначения ===
 
=== Обозначения ===
 
*<tex>\mathbb{N}</tex> &mdash; положительные целые числа;
 
*<tex>\mathbb{N}</tex> &mdash; положительные целые числа;
*<tex>\forall k \in \mathbb{N}</tex>
+
*<tex>\forall k \in \mathbb{N}</tex>:
 
:<tex>[k] := \{1, \ldots , k\}</tex>;
 
:<tex>[k] := \{1, \ldots , k\}</tex>;
 
*<tex>[0..k] := [k] \cup \{0\}</tex>;
 
*<tex>[0..k] := [k] \cup \{0\}</tex>;
*для битовой строки <tex>x = x_1 \cdots x_n \in \{0, 1\}^n</tex>
+
*для битовой строки <tex>x = x_1 \cdots x_n \in \{0, 1\}^n</tex>:
 
:<tex>\overline{x}</tex> &mdash; побитовое дополнение строки <tex>x</tex>;
 
:<tex>\overline{x}</tex> &mdash; побитовое дополнение строки <tex>x</tex>;
 
*<tex>\bigoplus</tex> &mdash; побитовое исключающее или;
 
*<tex>\bigoplus</tex> &mdash; побитовое исключающее или;
*для любого множества <tex>S</tex>
+
*для любого множества <tex>S</tex>:
 
:<tex>2^S</tex> &mdash; множество всех подмножеств множества <tex>S</tex>
 
:<tex>2^S</tex> &mdash; множество всех подмножеств множества <tex>S</tex>
*для <tex>n \in \mathbb{N}</tex>
+
*для <tex>n \in \mathbb{N}</tex>:
 
:<tex>S_n</tex> &mdash; множество всех перестановок <tex>[n]</tex>;
 
:<tex>S_n</tex> &mdash; множество всех перестановок <tex>[n]</tex>;
*для <tex>\sigma \in S_n</tex> и <tex>x \in \{0,1\}^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>\sigma(x) := x_{\sigma(1)} \cdots x_{\sigma(n)}</tex>;
 
*под <tex>log</tex> понимается натуральный логарифм.
 
*под <tex>log</tex> понимается натуральный логарифм.
  
 
=== Неограниченная Black-box модель ===
 
=== Неограниченная Black-box модель ===
Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление ''fitness'' функции возможных решений. Заданная ''fitness'' функция вычисляется ''ораклом'', или дается как ''black-box''. Алгоритм может запросить у ''оракла'' значение функции для любого решения, однако более никакой информации о решении получить не может.
+
Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление функции приспособленности возможных решений. Заданная функция приспособленности вычисляется '''оракулом''', или дается как ''black-box''. Алгоритм может запросить у ''оракула'' значение функции для любого решения, однако больше никакой информации о решении получить не может.
  
В качестве ''fitness'' функции берется псевдо-булевая функция <tex>F:\{0,1\}^n \rightarrow \mathbb{R}</tex>.
+
В качестве функции приспособленности берется псевдо-булевая функция <tex>F:\{0,1\}^n \rightarrow \mathbb{R}</tex>.
  
 
Согласно концепции ''black-box'', алгоритм может включать следующие действия:
 
Согласно концепции ''black-box'', алгоритм может включать следующие действия:
 
*выбор вероятностного распределения над <tex>\{0,1\}^n</tex>;
 
*выбор вероятностного распределения над <tex>\{0,1\}^n</tex>;
 
*выбор кандидата <tex>x \in \{0,1\}^n</tex> cогласно выбранному распределению;
 
*выбор кандидата <tex>x \in \{0,1\}^n</tex> cогласно выбранному распределению;
*запрос значения ''fitness'' функции выбранного кандидата у ''оракла''.
+
*запрос значения функции приспособленности выбранного кандидата у ''оракула''.
  
 
Схема неограниченного ''black-box'' алгоритма:
 
Схема неограниченного ''black-box'' алгоритма:
Строка 38: Строка 37:
 
  '''Инициализация:''' выбрать <tex>x^{(0)}</tex> согласно некоторому вероятностному распределению <tex>p^{(0)}</tex> над <tex>\{0,1\}^n</tex>. Запросить <tex>f(x^{(0)})</tex>.
 
  '''Инициализация:''' выбрать <tex>x^{(0)}</tex> согласно некоторому вероятностному распределению <tex>p^{(0)}</tex> над <tex>\{0,1\}^n</tex>. Запросить <tex>f(x^{(0)})</tex>.
 
  '''Оптимизация:''' '''for''' <tex>t = 1, 2, 3, \ldots </tex> '''until''' ''условие остановки'' '''do'''
 
  '''Оптимизация:''' '''for''' <tex>t = 1, 2, 3, \ldots </tex> '''until''' ''условие остановки'' '''do'''
   Исходя из <tex>((x^{(0)}, f(x^{(0)}), \ldots, (x^{(t-1)}, f(x^{(t-1)}))</tex>, выбрать вероятностное распределение <tex>p^{(t)}</tex> над <tex>\{0,1\}^n</tex>.
+
   Исходя из <tex>((x^{(0)}, f(x^{(0)})), \ldots, (x^{(t-1)}, f(x^{(t-1)})))</tex>, выбрать вероятностное распределение <tex>p^{(t)}</tex> над <tex>\{0,1\}^n</tex>.
 
   Выбрать <tex>x^{(t)}</tex> согласно <tex>p^{(t)}</tex> и запросить <tex>f(x^{(t)})</tex>.
 
   Выбрать <tex>x^{(t)}</tex> согласно <tex>p^{(t)}</tex> и запросить <tex>f(x^{(t)})</tex>.
  
В качестве времени работы ''black-box'' алгоритма берется количество запросов к ''ораклу'' сделанное до первого запроса с оптимальным решением.
+
В качестве времени работы ''black-box'' алгоритма берется количество запросов к ''оракулу'', сделанное до первого запроса с оптимальным решением.
  
 
Пусть <tex>\mathcal{F}</tex> &mdash; класс псевдо-булевых функций. Сложностью алгоритма <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>\mathcal{F}</tex> &mdash; класс псевдо-булевых функций. Сложностью алгоритма <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 модель ===
 
Класс неограниченных ''black-box'' алгоритмов слишком мощный. Например для любого функционального класса <tex>\mathcal{F} = \{f\}</tex> неограниченная ''black-box'' сложность равна единице &mdash; алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию.
 
Класс неограниченных ''black-box'' алгоритмов слишком мощный. Например для любого функционального класса <tex>\mathcal{F} = \{f\}</tex> неограниченная ''black-box'' сложность равна единице &mdash; алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию.
  
Чтобы избежать этих недостатков была введена более строгая модель. В ней алгоритмы могут генерировать новые решения используя только ''несмещенные вариативные операторы''.
+
Чтобы избежать этих недостатков была введена более строгая модель. В ней алгоритмы могут генерировать новые решения используя только ''беспристрастные вариативные операторы''.
  
 
{{Определение
 
{{Определение
|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> выполняются следующие условия:
+
|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>\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>D(x|y^{(1)},\ldots,y^{(k)}) = D(x \bigoplus z|y^{(1)} \bigoplus z,\ldots,y^{(k)} \bigoplus z)</tex>;
Строка 58: Строка 57:
 
}}
 
}}
  
Первое условие называется <tex>\bigoplus</tex>-инвариантностью, второе &mdash; перестановочной инвариантностью. Оператор, выбранный из <tex>k</tex>-арного несмещенного распределения называется '''<tex>k</tex>-арным несмещенным вариативным оператором'''.
+
Первое условие называется <tex>\bigoplus</tex>-инвариантностью, второе &mdash; перестановочной инвариантностью. Оператор, выбранный из <tex>k</tex>-арного беспристрастного распределения, называется '''<tex>k</tex>-арным беспристрастным вариативным оператором'''.
  
Схема <tex>k</tex>-арного несмещенного ''black-box'' алгоритма:
+
Схема <tex>k</tex>-арного беспристрастного ''black-box'' алгоритма:
  
 
  '''Инициализация:''' выбрать <tex>x^{(0)}</tex> равновероятно из <tex>\{0,1\}^n</tex>. Запросить <tex>f(x^{(0)})</tex>.
 
  '''Инициализация:''' выбрать <tex>x^{(0)}</tex> равновероятно из <tex>\{0,1\}^n</tex>. Запросить <tex>f(x^{(0)})</tex>.
 
  '''Оптимизация:''' '''for''' <tex>t = 1, 2, 3, \ldots </tex> '''until''' ''условие остановки'' '''do'''
 
  '''Оптимизация:''' '''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>(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>x^{(t)}</tex> согласно <tex>D(\cdot|x^{(i_1)},\ldots,x^{(i_k)})</tex> и запросить <tex>f(x^{(t)})</tex>.
  
 
{{Лемма
 
{{Лемма
 
|id=remark2
 
|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>.
+
|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=
+
|proof=Доказательство приведено в работе <ref name="bbox"/>.
 
}}
 
}}
  
== Jump функции ==
+
== Jump функция ==
 
{{Определение
 
{{Определение
|definition=<tex>\forall k < n/2</tex> функция <tex>Jump_k</tex> определяется как
+
|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>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>\forall x \in \{0,1\}^n</tex>, где <tex>|\cdot|_1</tex> &mdash; количество единиц в битовой строке.
 
}}
 
}}
  
Будет показано, что для любого константного <tex>k</tex> можно с высокой вероятностью решить проблему <tex>OneMax</tex> за малое количество ''black-box'' обращений к <tex>Jump_k</tex>. С помощью этого можно показать, что для любого константного <tex>k</tex> несмещенная ''black-box'' сложность для функции <tex>Jump_k</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
 
|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>.
+
|statement=Для любых <tex>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|_1 \leq k</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> позиций, которые можно выбирать. Это приводит к границе на вероятность выбора единиц:
+
Понятно, что функция корректна при всех <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>(\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>p \geq 1 - (\frac{k^2}{n-k})^c</tex>.
  
Процедура <tex>s</tex>:
+
Функция <tex>s</tex>:
  
 
  '''if''' <tex>Jump_k(x) \neq 0</tex> '''then output''' <tex>Jump_k(x)</tex>;
 
  '''if''' <tex>Jump_k(x) \neq 0</tex> '''then output''' <tex>Jump_k(x)</tex>;
Строка 107: Строка 106:
 
}}
 
}}
  
Теперь, используя [[#lemma3|предыдущую лемму]], можно найти несмещенную ''black-box'' сложность для функции <tex>Jump_k</tex> при константном <tex>k</tex>.
+
Теперь, используя [[#lemma3|предыдущую лемму]], можно найти беспристрастную ''black-box'' сложность для функции <tex>Jump_k</tex> при константном <tex>k</tex>.
  
 
{{Теорема
 
{{Теорема
 
|id=th4
 
|id=th4
|statement=Для константы <tex>k</tex> несмещенная ''black-box'' сложность <tex>Jump_k</tex>:
+
|statement=Для константы <tex>k</tex> беспристрастная ''black-box'' сложность <tex>Jump_k</tex>:
  
 
*<tex>O(n \log(n))</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(m))</tex> для <tex>m</tex>-арных вариативных операторов при <tex>2 \leq m \leq n</tex>;
 
*<tex>O(n / \log(n))</tex> для *-арных вариативных операторов.
 
*<tex>O(n / \log(n))</tex> для *-арных вариативных операторов.
|proof=
+
|proof=Доказательство приведено в работе <ref name="bbox"/>.
 
}}
 
}}
  
Процедуре из [[#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>.
+
Функции из [[#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>|\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>.
 +
}}
 +
 +
Далее <tex>Partition_{\neq}</tex> &mdash; подкласс задачи <tex>Partition</tex> с заданными различными весами.
 +
 +
Далее предлагаются две различные функции приспособленности и показывается, что в обоих случаях может быть достигнута полиномиальная беспристрастная ''black-box'' сложность. Показывается, что унарная беспристрастная ''black-box'' сложность для задачи <tex>Partition_{\neq}</tex> равна <tex>O(n \log(n))</tex>.
 +
 +
=== Знаковая функция приспособленности ===
 +
Пусть <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>. Знаковая функция приспособленности определяется следующим образом:
 +
 +
:<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> &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>. Тогда функция приспособленности преобразуется к следующему виду:
 +
 +
:<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> относительно функции приспособленности <tex>f_{\mathcal{I}}</tex> равна <tex>O(n \log(n))</tex>, где <tex>n := |\mathcal{I}|</tex>.
 +
|proof=Для доказательства теоретмы строится алгоритм с применением двух вариативных операторов:
 +
:*<tex>uniform()</tex> &mdash; выбирает случайную битовую строку <tex>x \in \{0,1\}^n</tex>;
 +
:*<tex>RLS(\cdot)</tex> &mdash; случайно меняет элемент в одной из позиций входной строки.
 +
 +
Для краткости полагается <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> &mdash; множество элементов, которые необходимо переместить.
 +
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> &mdash; множество элементов, которые необходимо переместить для получения оптимального решения. В итоге, беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно заданной функции приспособленности равна <tex>O(n \log(n))</tex>. Полное доказательство приведено в работе <ref name="bbox"/>.
 +
 +
}}
 +
 +
=== Беззнаковая функция приспособленности ===
 +
Можно заметить, что при доказательстве [[#th6|предыдущей теоремы]] происходила минимизация не самой функции <tex>f_{\mathcal{I}}</tex>, а только ее абсолютной величины. Однако та же асимптотика достигается и для беззнаковой функции приспособленности. Сложность заключается в том, что в этом случае нельзя просто определить вес перемещенного элемента. Этот факт выражается в более сложной процедуре для определения весов элементов.
 +
 +
{{Теорема
 +
|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>;
 +
:*<tex>S_0(x) = \Sigma_{w \in \mathcal{I}_0(x)} w</tex>;
 +
:*<tex>S_1(x) = \Sigma_{w \in \mathcal{I}_1(x)} w</tex>;
 +
:*<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>w_{max} = \max \mathcal{I}</tex> &mdash; элемент с максимальным весом.
 +
 +
Общая идея алгоритма состоит в следующем:
 +
:*генерируется строка, такая, что все ее элементы находятся в одной корзине (с большой вероятностью это можно сделать за <tex>4n \log(n)</tex> запросов);
 +
:*за <tex>2n \log(n)</tex> шагов с помощью <tex>RLS(\cdot)</tex> опеределяются веса всех элементов (с большой вероятностью);
 +
:*за <tex>3n \log(n)</tex> шагов восстанавливаетчся решение (с большой вероятностью).
 +
 +
Следующий алгоритм является доказательством теоремы:
 +
 +
  1 '''Инициализация'''
 +
  2 <tex>x^{(1,0)} \leftarrow uniform()</tex>. Запрос <tex>f(x^{(1,0)})</tex>;
 +
  3 '''Перемещение всех элементов в одну корзину'''
 +
  4 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do'''
 +
  5  <tex>x^{(1,t)} \leftarrow RLS(x^{(1,0)})</tex>. Запрос <tex>f(x^{(1,t)})</tex>;
 +
  6 Пусть <tex>l \in \arg \max_{0 \leq t \leq 2n \log(n)} f(x^{(1,t)})</tex>;
 +
  7 <tex>x \leftarrow x^{(1,l)}</tex>;
 +
  8 '''for''' <tex>t = 2n \log(n) + 1</tex> '''to''' <tex>4n \log(n)</tex> '''do'''
 +
  9  <tex>y \leftarrow RLS(x)</tex>. Запрос <tex>f(y)</tex>;
 +
10  '''if''' <tex>f(y) > f(x)</tex> '''then''' <tex>x \leftarrow y</tex>;
 +
11 '''Определение весов всех элементов'''
 +
12 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do'''
 +
13  <tex>x^{(2,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(2,t)})</tex>;
 +
14 '''Оптимизация'''
 +
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>;
 +
16 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do'''
 +
17  <tex>x^{(3,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(3,t)})</tex>;
 +
18  '''if''' <tex>f(x) > 2w_{max}</tex> '''and''' <tex>f(x^{(3,t)}) < f(x)</tex> '''then'''
 +
19    вычислить <tex>w := (f(x) - f(x^{(3,t)})) / 2</tex>;
 +
20    '''if''' <tex>w \neq w_{max}</tex> '''and''' <tex>w \in \mathcal{M}</tex> '''then'''
 +
21      <tex>x \leftarrow x^{(3,t)}; \mathcal{M} \leftarrow \mathcal{M} \backslash w</tex>;
 +
22 '''for''' <tex>t = 1</tex> '''to''' <tex>n \log(n)</tex> '''do'''
 +
23  <tex>x^{(4,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(4,t)})</tex>;
 +
 +
Можно показать, что приведенный алгоритм с большой вероятностью за <tex>O(n \log(n))</tex> запросов находит оптимальное решение. Полное доказательство приведено в работе <ref name="bbox"/>.
 +
 +
}}
 +
 +
== Источники ==
 +
<references/>
 +
 +
[[Категория:Теория сложности]]
 +
[[Категория:Эволюционные алгоритмы]]

Версия 13:04, 20 июня 2012

Введение в Black-box Complexity

Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении функции приспособленности) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы.

Black-box Complexity [1] — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, black-box сложность алгоритма — количество вычислений функции приспособленности, необходимое для получения решения. Такое определение позволяет получить нереалистично низкие оценки black-box сложности, например, полиномиальную сложность для [math]\mathrm{NP}[/math]-полной задачи поиска максимальной клики [1][2].

По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только беспристрастные (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) вариативные операторы. Также было введено понятие арности[math]k[/math]-арный беспристрастный black-box алгоритм использует только те операторы, которые принимают не более чем [math]k[/math] аргументов. Для некоторых классов задач такой подход к опеределению black-box сложности позволяет получить более реалистичные оценки вычислительной трудности. Операторы с арностью [math]1[/math] называют мутационными. В настоящей статье показано, что даже для алгоритмов, использующих только мутационные операторы, можно получить нереалистично маленькую оценку black-box сложности.

Неограниченная и беспристрастная Black-box модели

Обозначения

  • [math]\mathbb{N}[/math] — положительные целые числа;
  • [math]\forall k \in \mathbb{N}[/math]:
[math][k] := \{1, \ldots , k\}[/math];
  • [math][0..k] := [k] \cup \{0\}[/math];
  • для битовой строки [math]x = x_1 \cdots x_n \in \{0, 1\}^n[/math]:
[math]\overline{x}[/math] — побитовое дополнение строки [math]x[/math];
  • [math]\bigoplus[/math] — побитовое исключающее или;
  • для любого множества [math]S[/math]:
[math]2^S[/math] — множество всех подмножеств множества [math]S[/math]
  • для [math]n \in \mathbb{N}[/math]:
[math]S_n[/math] — множество всех перестановок [math][n][/math];
  • для [math]\sigma \in S_n[/math] и [math]x \in \{0,1\}^n[/math]:
[math]\sigma(x) := x_{\sigma(1)} \cdots x_{\sigma(n)}[/math];
  • под [math]log[/math] понимается натуральный логарифм.

Неограниченная Black-box модель

Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление функции приспособленности возможных решений. Заданная функция приспособленности вычисляется оракулом, или дается как black-box. Алгоритм может запросить у оракула значение функции для любого решения, однако больше никакой информации о решении получить не может.

В качестве функции приспособленности берется псевдо-булевая функция [math]F:\{0,1\}^n \rightarrow \mathbb{R}[/math].

Согласно концепции black-box, алгоритм может включать следующие действия:

  • выбор вероятностного распределения над [math]\{0,1\}^n[/math];
  • выбор кандидата [math]x \in \{0,1\}^n[/math] cогласно выбранному распределению;
  • запрос значения функции приспособленности выбранного кандидата у оракула.

Схема неограниченного black-box алгоритма:

Инициализация: выбрать [math]x^{(0)}[/math] согласно некоторому вероятностному распределению [math]p^{(0)}[/math] над [math]\{0,1\}^n[/math]. Запросить [math]f(x^{(0)})[/math].
Оптимизация: for [math]t = 1, 2, 3, \ldots [/math] until условие остановки do
  Исходя из [math]((x^{(0)}, f(x^{(0)})), \ldots, (x^{(t-1)}, f(x^{(t-1)})))[/math], выбрать вероятностное распределение [math]p^{(t)}[/math] над [math]\{0,1\}^n[/math].
  Выбрать [math]x^{(t)}[/math] согласно [math]p^{(t)}[/math] и запросить [math]f(x^{(t)})[/math].

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

Пусть [math]\mathcal{F}[/math] — класс псевдо-булевых функций. Сложностью алгоритма [math]A[/math] над [math]\mathcal{F}[/math] называется максимальное предположительное время работы [math]A[/math] на функции [math]f \in \mathcal{F}[/math] (в худшем случае). Сложностью [math]\mathcal{F}[/math] относительно класса алгоритмов [math]\mathcal{A}[/math] называется минимальная сложность среди всех [math]A \in \mathcal{A}[/math] над [math]\mathcal{F}[/math]. Неограниченной black-box сложностью [math]\mathcal{F}[/math] называется сложность [math]\mathcal{F}[/math] относительно класса неограниченных black-box алгоритмов.

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

Класс неограниченных black-box алгоритмов слишком мощный. Например для любого функционального класса [math]\mathcal{F} = \{f\}[/math] неограниченная black-box сложность равна единице — алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию.

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


Определение:
[math]\forall k \in \mathbb{N}, k[/math]-арным беспристрастным распределением [math](D(\cdot|y^{(1)},\ldots,y^{(k)}))_{y^{(1)},\ldots,y^{(k)} \in \{0,1\}^n}[/math] называется семейство вероятностных распределений над [math]\{0,1\}^n[/math] таких, что для любых [math]y^{(1)},\ldots,y^{(k)} \in \{0,1\}^n[/math] выполняются следующие условия:
  • [math]\forall x, z \in \{0,1\}^n[/math]:
[math]D(x|y^{(1)},\ldots,y^{(k)}) = D(x \bigoplus z|y^{(1)} \bigoplus z,\ldots,y^{(k)} \bigoplus z)[/math];
  • [math]\forall x \in \{0,1\}^n \forall \sigma \in S_n[/math]:
[math]D(x|y^{(1)},\ldots,y^{(k)}) = D(\sigma(x)|\sigma(y^{(1)}),\ldots,\sigma(y^{(k)}))[/math].


Первое условие называется [math]\bigoplus[/math]-инвариантностью, второе — перестановочной инвариантностью. Оператор, выбранный из [math]k[/math]-арного беспристрастного распределения, называется [math]k[/math]-арным беспристрастным вариативным оператором.

Схема [math]k[/math]-арного беспристрастного black-box алгоритма:

Инициализация: выбрать [math]x^{(0)}[/math] равновероятно из [math]\{0,1\}^n[/math]. Запросить [math]f(x^{(0)})[/math].
Оптимизация: for [math]t = 1, 2, 3, \ldots [/math] until условие остановки do
  Исходя из [math](f(x^{(0)}), \ldots, f(x^{(t-1)}))[/math], выбрать [math]k[/math] индексов [math]i_1, \ldots, i_k \in [0..t-1][/math] и [math]k[/math]-арное беспристрастное распределение [math]D(\cdot|x^{(i_1)},\ldots,x^{(i_k)})[/math].
  Выбрать [math]x^{(t)}[/math] согласно [math]D(\cdot|x^{(i_1)},\ldots,x^{(i_k)})[/math] и запросить [math]f(x^{(t)})[/math].
Лемма:
Пусть для задачи [math]P[/math] существует black-box алгоритм [math]A[/math], который с константной вероятностью успеха решает [math]P[/math] за [math]s[/math] итераций. Тогда black-box сложность [math]P[/math] не больше [math]O(s)[/math].
Доказательство:
[math]\triangleright[/math]
Доказательство приведено в работе [1].
[math]\triangleleft[/math]

Jump функция

Определение:
[math]\forall k \lt n/2[/math] функция [math]Jump_k[/math] определяется следующим образом:
[math]Jump_k(x) = \left\{ \begin{array}{ccc} n, & if & |x|_1=n; \\ |x|_1, & if & k \lt |x|_1 \lt n-k; \\ 0, & & otherwise, \end{array}\right.[/math]
[math]\forall x \in \{0,1\}^n[/math], где [math]|\cdot|_1[/math] — количество единиц в битовой строке.


Далее будет показано, что для любого константного [math]k[/math] можно с высокой вероятностью решить задачу [math]OneMax[/math] [3] за малое количество black-box обращений к [math]Jump_k[/math]. С помощью этого утверждения можно показать, что для любой константы [math]k[/math] беспристрастная black-box сложность для функции [math]Jump_k[/math] нереалистично мала.

Лемма:
Для любых [math]k[/math] и [math]c[/math] существует унарная беспристрастная функция [math]s[/math], использующая [math]c+1[/math] запросов к [math]Jump_k[/math] такая, что для всех битовых строк [math]x[/math], [math]s(x) = OneMax(x)[/math] с вероятностью [math]1 - O(n^{-c})[/math].
Доказательство:
[math]\triangleright[/math]

Используется унарный беспристрастный вариативный оператор [math]flip_k[/math], который равновероятно выбирает строку из [math]k[/math]-окрестности для аргумента (битовую строку, которая отличается в [math]k[/math] позициях). Ниже предлагается функция [math]s[/math], которая использует [math]Jump_k[/math] для аппроксимации [math]OneMax[/math]. Функция выбирает [math]c[/math] битовых строк в [math]k[/math]-окрестности [math]x[/math]. Если [math]|x|_1 \geq n-k[/math], то есть вероятность того, что хотя бы раз в [math]x[/math] будут заменены только единицы, что приведет к тому, что [math]Jump_k = |x|_1 - k[/math]. Так как больше никакая строка из выборки не будет иметь меньшее [math]Jump_k[/math] значение, то добавление [math]k[/math] к минимальному ненулевому значению [math]Jump_k[/math] других строк из выборки приведет к нужному результату — функция вернет количество единиц в строке [math]x[/math]. Случай, когда [math]|x|_1 \leq k[/math], аналогичен.

Понятно, что функция корректна при всех [math]x[/math], таких, что [math]k \lt |x|_1 \lt n-k[/math]. Остальные два случая симметричны, поэтому пусть [math]|x|_1 \geq n-k[/math]. Очевидно, что результат функции корректен тогда и только тогда, когда хотя бы в одной из [math]c[/math] строк были заменены только единицы. Требуется вычислить вероятность [math]p[/math] этого события. Итеративно выбираются [math]k[/math] бит для замены, поэтому после [math]i[/math] итераций имеется как минимум [math]n-k-i[/math] позиций с единицей из [math]n-i[/math] невыбранных позиций. Отсюда, с использованием неравенства Бернулли [4], получается граница на вероятность выбора [math]k[/math] единиц:

[math](\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})[/math].

Таким образом:

[math]p \geq 1 - (\frac{k^2}{n-k})^c[/math].

Функция [math]s[/math]:

if [math]Jump_k(x) \neq 0[/math] then output [math]Jump_k(x)[/math];
[math]M \leftarrow \{Jump_k(flip_k(x)) | i \in [c]\}[/math];
if [math]max(M) \lt  n/2[/math] then [math]m \leftarrow max(M) - k[/math];
else [math]m \leftarrow min(M \backslash \{0\}) + k[/math];
output [math]m[/math];
[math]\triangleleft[/math]

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

Теорема:
Для константы [math]k[/math] беспристрастная black-box сложность [math]Jump_k[/math]:
  • [math]O(n \log(n))[/math] для унарных вариативных операторов;
  • [math]O(n / \log(m))[/math] для [math]m[/math]-арных вариативных операторов при [math]2 \leq m \leq n[/math];
  • [math]O(n / \log(n))[/math] для *-арных вариативных операторов.
Доказательство:
[math]\triangleright[/math]
Доказательство приведено в работе [1].
[math]\triangleleft[/math]

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

Задача о разбиении

Задача:
Задача о разбиении [5] ([math]Partition[/math] problem) ставится следующим образом. Дано мультимножество [math]\mathcal{I}[/math] положительных целых чисел (весов). Возможно ли разбить его на два непересекающихся множества [math]\mathcal{I}=\mathcal{I}_0 \cup \mathcal{I}_1[/math] таким образом, что [math]\Sigma_{w \in \mathcal{I}_0} w = \Sigma_{w \in \mathcal{I}_1} w[/math]?


Оптимизационная версия задачи ставит вопрос о минимизации функции [math]|\Sigma_{w \in \mathcal{I}_0} w - \Sigma_{w \in \mathcal{I}_1} w|[/math].

Задача [math]Partition[/math] является [math]\mathrm{NP}[/math]-трудной. Предположительно [math]\mathrm{P} \neq \mathrm{NP}[/math] и не существует полиномиального алгоритма решения этой задачи.

Лемма:
Задача [math]Partition[/math] остается [math]\mathrm{NP}[/math]-трудной, когда [math]\forall v, w \in \mathcal{I}: v \neq w[/math].

Далее [math]Partition_{\neq}[/math] — подкласс задачи [math]Partition[/math] с заданными различными весами.

Далее предлагаются две различные функции приспособленности и показывается, что в обоих случаях может быть достигнута полиномиальная беспристрастная black-box сложность. Показывается, что унарная беспристрастная black-box сложность для задачи [math]Partition_{\neq}[/math] равна [math]O(n \log(n))[/math].

Знаковая функция приспособленности

Пусть [math]\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}\}[/math] — множество всех возможных решений для [math]\mathcal{I}[/math]. Знаковая функция приспособленности определяется следующим образом:

[math]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[/math].

Цель заключается в минимизации [math]|f_{\mathcal{I}}^{*}|[/math].

Необходимо ввести нумерацию элементов [math]\mathcal{I}[/math][math]\sigma: \mathcal{I} \rightarrow [n][/math]. Для любой битовой строки [math]x \in \{0,1\}^n[/math] определены [math]\mathcal{I}_0(x) := \{w \in \mathcal{I} | x_{\sigma(w)} = 0\}[/math] и [math]\mathcal{I}_1(x) := \{w \in \mathcal{I} | x_{\sigma(w)} = 1\}[/math]. Тогда функция приспособленности преобразуется к следующему виду:

[math]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)[/math].
Теорема:
Унарная беспристрастная black-box сложность задачи [math]Partition_{\neq}[/math] относительно функции приспособленности [math]f_{\mathcal{I}}[/math] равна [math]O(n \log(n))[/math], где [math]n := |\mathcal{I}|[/math].
Доказательство:
[math]\triangleright[/math]

Для доказательства теоретмы строится алгоритм с применением двух вариативных операторов:

  • [math]uniform()[/math] — выбирает случайную битовую строку [math]x \in \{0,1\}^n[/math];
  • [math]RLS(\cdot)[/math] — случайно меняет элемент в одной из позиций входной строки.

Для краткости полагается [math]f := f_{\mathcal{I}}[/math].

Следующий алгоритм служит доказательством теоремы:

 1 Инициализация
 2 [math]x^{(0)} \leftarrow uniform()[/math]. Запрос [math]f(x^{(0)})[/math];
 3 [math]t \leftarrow 0, \mathcal{I}_0', \mathcal{I}_1', \mathcal{W}_0 = \varnothing[/math];
 4 Определение весов
 5 while [math]|\mathcal{W}_t| \lt  n[/math] do
 6   [math]t \leftarrow t + 1[/math];
 7   [math]x^{(t)} \leftarrow RLS(x^{(0)})[/math]. Запрос [math]f(x^{(t)})[/math];
 8   [math]\mathcal{W}_t \leftarrow \mathcal{W}_{t-1} \cup \{|f(x^{(0)}) - f(x^{(t)})|/2\}[/math];
 9   if [math]f(x^{(0)}) \gt  f(x^{(t)})[/math] then
10     [math]\mathcal{I}_0' \leftarrow \mathcal{I}_0' \cup {|f(x^{(0)}) - f(x^{(t)})|/2}[/math];
11   else [math]\mathcal{I}_1' \leftarrow \mathcal{I}_1' \cup {|f(x^{(0)}) - f(x^{(t)})|/2}[/math];
12 Оптимизация
13 В оффлайне перебором вычисляется оптимальное решение [math](\mathcal{O}_0, \mathcal{O}_1)[/math]
   и множество [math]\mathcal{M} \leftarrow \{w \in \mathcal{O}_0 | w \notin \mathcal{I}_0'\} \cup \{w \in \mathcal{O}_1 | w \notin \mathcal{I}_1'\}[/math] — множество элементов, которые необходимо переместить.
14 [math]z \leftarrow x^{(0)}[/math];
15 while [math]|\mathcal{M}| \gt  0[/math] do
16   [math]y \leftarrow RLS(z)[/math]. Запрос [math]f(y)[/math];
17   if [math]w := |f(y)-f(z)|/2 \in \mathcal{M}[/math] then
18     [math]z \leftarrow y[/math], [math]\mathcal{M} \leftarrow \mathcal{M} \backslash \{w\}[/math];
За [math](1+o(1))n \log(n)[/math] итераций определяются веса всех элементов [math]\mathcal{I}[/math]. Зная веса элементов, в оффлайне перебором находится оптимальное решение задачи, после чего это решение необходимо восстановить с помощью вариативного [math]1[/math]-арного оператора. Для этого построено множество [math]\mathcal{M}[/math] — множество элементов, которые необходимо переместить для получения оптимального решения. В итоге, беспристрастная black-box сложность задачи [math]Partition_{\neq}[/math] относительно заданной функции приспособленности равна [math]O(n \log(n))[/math]. Полное доказательство приведено в работе [1].
[math]\triangleleft[/math]

Беззнаковая функция приспособленности

Можно заметить, что при доказательстве предыдущей теоремы происходила минимизация не самой функции [math]f_{\mathcal{I}}[/math], а только ее абсолютной величины. Однако та же асимптотика достигается и для беззнаковой функции приспособленности. Сложность заключается в том, что в этом случае нельзя просто определить вес перемещенного элемента. Этот факт выражается в более сложной процедуре для определения весов элементов.

Теорема:
Унарная беспристрастная black-box сложность задачи [math]Partition_{\neq}[/math] относительно функции приспособленности [math]|f_{\mathcal{I}}|[/math] равна [math]O(n \log(n))[/math]. Где [math]n := |\mathcal{I}|[/math].
Доказательство:
[math]\triangleright[/math]

Для краткости полагается:

  • [math]f := |f_{\mathcal{I}}|[/math];
  • [math]S_0(x) = \Sigma_{w \in \mathcal{I}_0(x)} w[/math];
  • [math]S_1(x) = \Sigma_{w \in \mathcal{I}_1(x)} w[/math];
  • [math]\mathcal{I}_{max(x)}[/math] — множество элементов, принадлежащих корзине с большим весом. Например, [math]\mathcal{I}_{max(x)} = \mathcal{I}_0[/math] если [math]S_0(x) \geq S_1(x)[/math];
  • [math]w_{max} = \max \mathcal{I}[/math] — элемент с максимальным весом.

Общая идея алгоритма состоит в следующем:

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

Следующий алгоритм является доказательством теоремы:

 1 Инициализация
 2 [math]x^{(1,0)} \leftarrow uniform()[/math]. Запрос [math]f(x^{(1,0)})[/math];
 3 Перемещение всех элементов в одну корзину
 4 for [math]t = 1[/math] to [math]2n \log(n)[/math] do
 5   [math]x^{(1,t)} \leftarrow RLS(x^{(1,0)})[/math]. Запрос [math]f(x^{(1,t)})[/math];
 6 Пусть [math]l \in \arg \max_{0 \leq t \leq 2n \log(n)} f(x^{(1,t)})[/math];
 7 [math]x \leftarrow x^{(1,l)}[/math];
 8 for [math]t = 2n \log(n) + 1[/math] to [math]4n \log(n)[/math] do
 9   [math]y \leftarrow RLS(x)[/math]. Запрос [math]f(y)[/math];
10   if [math]f(y) \gt  f(x)[/math] then [math]x \leftarrow y[/math];
11 Определение весов всех элементов
12 for [math]t = 1[/math] to [math]2n \log(n)[/math] do
13   [math]x^{(2,t)} \leftarrow RLS(x)[/math]. Запрос [math]f(x^{(2,t)})[/math];
14 Оптимизация
15 В оффлайне перебором вычисляется оптимальное решение [math](\mathcal{O}_0, \mathcal{O}_1)[/math], такое что [math]w_{max} \in \mathcal{O}_1[/math]. [math]\mathcal{M} \leftarrow \mathcal{O}_1[/math];
16 for [math]t = 1[/math] to [math]2n \log(n)[/math] do
17   [math]x^{(3,t)} \leftarrow RLS(x)[/math]. Запрос [math]f(x^{(3,t)})[/math];
18   if [math]f(x) \gt  2w_{max}[/math] and [math]f(x^{(3,t)}) \lt  f(x)[/math] then
19     вычислить [math]w := (f(x) - f(x^{(3,t)})) / 2[/math];
20     if [math]w \neq w_{max}[/math] and [math]w \in \mathcal{M}[/math] then
21       [math]x \leftarrow x^{(3,t)}; \mathcal{M} \leftarrow \mathcal{M} \backslash w[/math];
22 for [math]t = 1[/math] to [math]n \log(n)[/math] do
23   [math]x^{(4,t)} \leftarrow RLS(x)[/math]. Запрос [math]f(x^{(4,t)})[/math];
Можно показать, что приведенный алгоритм с большой вероятностью за [math]O(n \log(n))[/math] запросов находит оптимальное решение. Полное доказательство приведено в работе [1].
[math]\triangleleft[/math]

Источники