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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Неограниченная Black-box модель)
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
== Введение в Black-box Complexity ==
 
== Введение в Black-box Complexity ==
Целью [[Теория_сложности|теории сложности]] является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае [[Эволюционные_алгоритмы|эволюционных алгоритмов]], алгоритм обладает информацией только о качестве (значении ''fitness''-функции) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы.
+
Целью [[Теория_сложности|теории сложности]] является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае [[Эволюционные_алгоритмы|эволюционных алгоритмов]], алгоритм обладает информацией только о качестве (значении функции приспособленности) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы.
  
'''Black-box Complexity''' <ref name="bbox">[http://dl.acm.org/citation.cfm?doid=2001576.2001851 Doerr B., Kötzing T., Winzen C. Too fast unbiased black-box algorithms]</ref> &mdash; попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box'' сложность алгоритма &mdash; количество вычислений ''fitness''-функции, необходимое для получения решения. Такое определение позволяет получить нереалистично низкие оценки ''black-box'' сложности, например, полиномиальную сложность для [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полной]] задачи поиска максимальной клики <ref>[http://en.wikipedia.org/wiki/Clique_problem Clique problem]</ref>.
+
'''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; положительные целые числа;
Строка 24: Строка 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'' алгоритма:
Строка 37: Строка 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>;
Строка 57: Строка 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>.
  
Строка 78: Строка 78:
 
:<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> <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> нереалистично мала.
+
Далее будет показано, что для любого константного <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> других строк из выборки приведет к нужному результату &mdash; функция вернет количество единиц в строке <tex>x</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> невыбранных позиций. Отсюда, с использованием неравенства Бернулли <ref>[http://en.wikipedia.org/wiki/Bernoulli%27s_inequality Bernoulli's inequality]</ref>, получается граница на вероятность выбора <tex>k</tex> единиц:
 
Понятно, что функция корректна при всех <tex>x</tex>, таких, что <tex>k < |x|_1 < n-k</tex>. Остальные два случая симметричны, поэтому пусть <tex>|x|_1 \geq n-k</tex>. Очевидно, что результат функции корректен тогда и только тогда, когда хотя бы в одной из <tex>c</tex> строк были заменены только единицы. Требуется вычислить вероятность <tex>p</tex> этого события. Итеративно выбираются <tex>k</tex> бит для замены, поэтому после <tex>i</tex> итераций имеется как минимум <tex>n-k-i</tex> позиций с единицей из <tex>n-i</tex> невыбранных позиций. Отсюда, с использованием неравенства Бернулли <ref>[http://en.wikipedia.org/wiki/Bernoulli%27s_inequality Bernoulli's inequality]</ref>, получается граница на вероятность выбора <tex>k</tex> единиц:
Строка 106: Строка 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> для унарных вариативных операторов;
Строка 136: Строка 136:
 
Далее <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>.
Строка 145: Строка 145:
 
Цель заключается в минимизации <tex>|f_{\mathcal{I}}^{*}|</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>. Тогда ''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>.
Строка 151: Строка 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>;
Строка 172: Строка 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'''
Строка 179: Строка 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>. Полное доказательство приведено в работе <ref name="bbox"/>.
+
За <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>;
Строка 231: Строка 232:
 
}}
 
}}
  
== Ссылки ==
+
== Источники ==
 
<references/>
 
<references/>
  
 
[[Категория:Теория сложности]]
 
[[Категория:Теория сложности]]
 
[[Категория:Эволюционные алгоритмы]]
 
[[Категория:Эволюционные алгоритмы]]

Текущая версия на 19:29, 4 сентября 2022

Введение в 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]

Источники