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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 28 промежуточных версий 3 участников)
Строка 1: Строка 1:
{{В разработке}}
+
== Введение в Black-box Complexity ==
== Введение в Black-box complexity ==
+
Целью [[Теория_сложности|теории сложности]] является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае [[Эволюционные_алгоритмы|эволюционных алгоритмов]], алгоритм обладает информацией только о качестве (значении функции приспособленности) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы.
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''fitness''-функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.
 
  
'''Black-box Complexity''' &mdash; попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box'' сложность алгоритма &mdash; количество вычислений ''fitness''-функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки ''black-box'' сложности, например, полиномиальную сложность для <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'' сложности позволяет получить более реалистичные оценки сложности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В данной статье показано, что даже для алгоритмов, использующих только мутационные операторы можно получить не реалистично маленькую оценку ''black-box'' сложности.
+
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''беспристрастные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Также было введено понятие '''арности''' &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; положительные целые числа;
Строка 25: Строка 24:
  
 
=== Неограниченная 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=Задача о разбиении (<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>?
+
|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>?
 
}}
 
}}
  
Строка 133: Строка 132:
 
|id=lemma5
 
|id=lemma5
 
|statement=Задача <tex>Partition</tex> остается <tex>\mathrm{NP}</tex>-трудной, когда <tex>\forall v, w \in \mathcal{I}: v \neq w</tex>.
 
|statement=Задача <tex>Partition</tex> остается <tex>\mathrm{NP}</tex>-трудной, когда <tex>\forall v, w \in \mathcal{I}: v \neq w</tex>.
|proof=
 
 
}}
 
}}
  
Далее <tex>Partition_{\neq}</tex> &mdash; подкласс задачи <tex>Partition</tex> с взятыми различными весами.
+
Далее <tex>Partition_{\neq}</tex> &mdash; подкласс задачи <tex>Partition</tex> с заданными различными весами.
  
Предлагаются две различные ''fitness''-функции и показывается, что в обоих случаях может быть достигнута полиномиальная несмещенная ''black-box'' сложность. Показывается, что унарная несмещенная ''black-box'' сложность для задачи <tex>Partition_{\neq}</tex> равна <tex>O(n \log(n))</tex>.
+
Далее предлагаются две различные функции приспособленности и показывается, что в обоих случаях может быть достигнута полиномиальная беспристрастная ''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{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}}^{*}: \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>.
Строка 147: Строка 145:
 
Цель заключается в минимизации <tex>|f_{\mathcal{I}}^{*}|</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>\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>.
 
:<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>.
Строка 153: Строка 151:
 
{{Теорема
 
{{Теорема
 
|id=th6
 
|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>.
+
|statement=Унарная беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно функции приспособленности <tex>f_{\mathcal{I}}</tex> равна <tex>O(n \log(n))</tex>, где <tex>n := |\mathcal{I}|</tex>.
|proof=Для доказательства будет построен алгоритм с применением двух вариативных операторов:
+
|proof=Для доказательства теоретмы строится алгоритм с применением двух вариативных операторов:
 
:*<tex>uniform()</tex> &mdash; выбирает случайную битовую строку <tex>x \in \{0,1\}^n</tex>;
 
:*<tex>uniform()</tex> &mdash; выбирает случайную битовую строку <tex>x \in \{0,1\}^n</tex>;
 
:*<tex>RLS(\cdot)</tex> &mdash; случайно меняет элемент в одной из позиций входной строки.
 
:*<tex>RLS(\cdot)</tex> &mdash; случайно меняет элемент в одной из позиций входной строки.
  
Для краткости положим <tex>f := f_{\mathcal{I}}</tex>.
+
Для краткости полагается <tex>f := f_{\mathcal{I}}</tex>.
  
 
Следующий алгоритм служит доказательством теоремы:
 
Следующий алгоритм служит доказательством теоремы:
Строка 174: Строка 172:
 
  11  '''else''' <tex>\mathcal{I}_1' \leftarrow \mathcal{I}_1' \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 '''Оптимизация'''
 
  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; множество элементов, которые надо переместить.
+
  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>;
 
  14 <tex>z \leftarrow x^{(0)}</tex>;
 
  15 '''while''' <tex>|\mathcal{M}| > 0</tex> '''do'''
 
  15 '''while''' <tex>|\mathcal{M}| > 0</tex> '''do'''
Строка 181: Строка 180:
 
  18    <tex>z \leftarrow y</tex>, <tex>\mathcal{M} \leftarrow \mathcal{M} \backslash \{w\}</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> &mdash; множество элементов, которые необходимо переместить для получения оптимального решения. В итоге получается, что несмещенная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно заданной ''fitness''-функции равна <tex>O(n \log(n))</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"/>.
  
 
}}
 
}}
  
=== Беззнаковая ''fitness''-функция ===
+
=== Беззнаковая функция приспособленности ===
Кому-то может не понравиться, что при доказательстве [[#th6|предыдущей теоремы]] происходила минимизация не самой функции <tex>f_{\mathcal{I}}</tex>, а только ее абсолютной величины. Однако можно достичь той же асимптотики и для беззнаковой ''fitness''-функции. Сложность заключается в том, что теперь нельзя просто определить вес перемещенного элемента. Этот факт выражается в более сложной процедуре для определения весов элементов.
+
Можно заметить, что при доказательстве [[#th6|предыдущей теоремы]] происходила минимизация не самой функции <tex>f_{\mathcal{I}}</tex>, а только ее абсолютной величины. Однако та же асимптотика достигается и для беззнаковой функции приспособленности. Сложность заключается в том, что в этом случае нельзя просто определить вес перемещенного элемента. Этот факт выражается в более сложной процедуре для определения весов элементов.
  
 
{{Теорема
 
{{Теорема
 
|id=th8
 
|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>.
+
|statement=Унарная беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно функции приспособленности <tex>|f_{\mathcal{I}}|</tex> равна <tex>O(n \log(n))</tex>. Где <tex>n := |\mathcal{I}|</tex>.
|proof=Для краткости положим:
+
|proof=Для краткости полагается:
 
:*<tex>f := |f_{\mathcal{I}}|</tex>;
 
:*<tex>f := |f_{\mathcal{I}}|</tex>;
 
:*<tex>S_0(x) = \Sigma_{w \in \mathcal{I}_0(x)} w</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>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>\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>w_{max} = \max \mathcal{I}</tex> &mdash; элемент с максимальным весом.
  
 
Общая идея алгоритма состоит в следующем:
 
Общая идея алгоритма состоит в следующем:
:*сгенерировать строку, такую, что все элементы находятся в одной корзине (с большой вероятностью это можно сделать за <tex>4n \log(n)</tex> запросов);
+
:*генерируется строка, такая, что все ее элементы находятся в одной корзине (с большой вероятностью это можно сделать за <tex>4n \log(n)</tex> запросов);
:*за <tex>2n \log(n)</tex> шагов с помощью <tex>RLS(\cdot)</tex> опеределить веса всех элементов (с большой вероятностью);
+
:*за <tex>2n \log(n)</tex> шагов с помощью <tex>RLS(\cdot)</tex> опеределяются веса всех элементов (с большой вероятностью);
:*за <tex>3n \log(n)</tex> шагов восстановить решение (с большой вероятностью).
+
:*за <tex>3n \log(n)</tex> шагов восстанавливаетчся решение (с большой вероятностью).
  
 
Следующий алгоритм является доказательством теоремы:
 
Следующий алгоритм является доказательством теоремы:
Строка 219: Строка 218:
 
  13  <tex>x^{(2,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(2,t)})</tex>;
 
  13  <tex>x^{(2,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(2,t)})</tex>;
 
  14 '''Оптимизация'''
 
  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>;
+
  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'''
 
  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>;
 
  17  <tex>x^{(3,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(3,t)})</tex>;
Строка 229: Строка 228:
 
  23  <tex>x^{(4,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(4,t)})</tex>;
 
  23  <tex>x^{(4,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(4,t)})</tex>;
  
Можно показать, что приведенный алгоритм с большой вероятностью за <tex>O(n \log(n))</tex> запросов находит оптимальное решение.
+
Можно показать, что приведенный алгоритм с большой вероятностью за <tex>O(n \log(n))</tex> запросов находит оптимальное решение. Полное доказательство приведено в работе <ref name="bbox"/>.
  
 
}}
 
}}
  
 
== Источники ==
 
== Источники ==
# [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/p2043.pdf Doerr B., Kotzing T., Winzen C. Too Fast Unbiased Black-Box Algorithms]
+
<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]

Источники[править]