Black-box Complexity. Примеры нереалистичных оценок Black-box Complexity — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 32 промежуточные версии 4 участников) | |||
Строка 1: | Строка 1: | ||
− | + | == Введение в Black-box Complexity == | |
− | == Введение в Black-box | + | Целью [[Теория_сложности|теории сложности]] является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае [[Эволюционные_алгоритмы|эволюционных алгоритмов]], алгоритм обладает информацией только о качестве (значении функции приспособленности) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы. |
− | Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении | ||
− | '''Black-box Complexity''' — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box | + | '''Black-box Complexity''' <ref name="bbox">[http://dl.acm.org/citation.cfm?doid=2001576.2001851 Doerr B., Kötzing T., Winzen C. Too fast unbiased black-box algorithms]</ref> — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box'' сложность алгоритма — количество вычислений функции приспособленности, необходимое для получения решения. Такое определение позволяет получить нереалистично низкие оценки ''black-box'' сложности, например, полиномиальную сложность для [[Примеры_NP-полных_языков._Теорема_Кука|<tex>\mathrm{NP}</tex>-полной]] задачи поиска максимальной клики <ref name="bbox"/><ref>[http://en.wikipedia.org/wiki/Clique_problem Clique problem]</ref>. |
− | По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только ''' | + | По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''беспристрастные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Также было введено понятие '''арности''' — <tex>k</tex>-арный беспристрастный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box'' сложности позволяет получить более реалистичные оценки вычислительной трудности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В настоящей статье показано, что даже для алгоритмов, использующих только мутационные операторы, можно получить нереалистично маленькую оценку ''black-box'' сложности. |
− | == Неограниченная и | + | == Неограниченная и беспристрастная Black-box модели == |
=== Обозначения === | === Обозначения === | ||
*<tex>\mathbb{N}</tex> — положительные целые числа; | *<tex>\mathbb{N}</tex> — положительные целые числа; | ||
− | *<tex>\forall k \in \mathbb{N}</tex> | + | *<tex>\forall k \in \mathbb{N}</tex>: |
:<tex>[k] := \{1, \ldots , k\}</tex>; | :<tex>[k] := \{1, \ldots , k\}</tex>; | ||
*<tex>[0..k] := [k] \cup \{0\}</tex>; | *<tex>[0..k] := [k] \cup \{0\}</tex>; | ||
− | *для битовой строки <tex>x = x_1 \cdots x_n \in \{0, 1\}^n</tex> | + | *для битовой строки <tex>x = x_1 \cdots x_n \in \{0, 1\}^n</tex>: |
:<tex>\overline{x}</tex> — побитовое дополнение строки <tex>x</tex>; | :<tex>\overline{x}</tex> — побитовое дополнение строки <tex>x</tex>; | ||
*<tex>\bigoplus</tex> — побитовое исключающее или; | *<tex>\bigoplus</tex> — побитовое исключающее или; | ||
− | *для любого множества <tex>S</tex> | + | *для любого множества <tex>S</tex>: |
:<tex>2^S</tex> — множество всех подмножеств множества <tex>S</tex> | :<tex>2^S</tex> — множество всех подмножеств множества <tex>S</tex> | ||
− | *для <tex>n \in \mathbb{N}</tex> | + | *для <tex>n \in \mathbb{N}</tex>: |
:<tex>S_n</tex> — множество всех перестановок <tex>[n]</tex>; | :<tex>S_n</tex> — множество всех перестановок <tex>[n]</tex>; | ||
− | *для <tex>\sigma \in S_n</tex> и <tex>x \in \{0,1\}^n</tex> | + | *для <tex>\sigma \in S_n</tex> и <tex>x \in \{0,1\}^n</tex>: |
:<tex>\sigma(x) := x_{\sigma(1)} \cdots x_{\sigma(n)}</tex>; | :<tex>\sigma(x) := x_{\sigma(1)} \cdots x_{\sigma(n)}</tex>; | ||
*под <tex>log</tex> понимается натуральный логарифм. | *под <tex>log</tex> понимается натуральный логарифм. | ||
=== Неограниченная Black-box модель === | === Неограниченная Black-box модель === | ||
− | Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление | + | Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление функции приспособленности возможных решений. Заданная функция приспособленности вычисляется '''оракулом''', или дается как ''black-box''. Алгоритм может запросить у ''оракула'' значение функции для любого решения, однако больше никакой информации о решении получить не может. |
− | В качестве | + | В качестве функции приспособленности берется псевдо-булевая функция <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огласно выбранному распределению; | ||
− | *запрос значения | + | *запрос значения функции приспособленности выбранного кандидата у ''оракула''. |
Схема неограниченного ''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> — класс псевдо-булевых функций. Сложностью алгоритма <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> — класс псевдо-булевых функций. Сложностью алгоритма <tex>A</tex> над <tex>\mathcal{F}</tex> называется максимальное предположительное время работы <tex>A</tex> на функции <tex>f \in \mathcal{F}</tex> (в худшем случае). Сложностью <tex>\mathcal{F}</tex> относительно класса алгоритмов <tex>\mathcal{A}</tex> называется минимальная сложность среди всех <tex>A \in \mathcal{A}</tex> над <tex>\mathcal{F}</tex>. Неограниченной ''black-box'' сложностью <tex>\mathcal{F}</tex> называется сложность <tex>\mathcal{F}</tex> относительно класса неограниченных ''black-box'' алгоритмов. | ||
− | === | + | === Беспристрастная Black-box модель === |
Класс неограниченных ''black-box'' алгоритмов слишком мощный. Например для любого функционального класса <tex>\mathcal{F} = \{f\}</tex> неограниченная ''black-box'' сложность равна единице — алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию. | Класс неограниченных ''black-box'' алгоритмов слишком мощный. Например для любого функционального класса <tex>\mathcal{F} = \{f\}</tex> неограниченная ''black-box'' сложность равна единице — алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию. | ||
− | Чтобы избежать этих недостатков была введена более строгая модель. В ней алгоритмы могут генерировать новые решения используя только '' | + | Чтобы избежать этих недостатков была введена более строгая модель. В ней алгоритмы могут генерировать новые решения используя только ''беспристрастные вариативные операторы''. |
{{Определение | {{Определение | ||
− | |definition=<tex>\forall k \in \mathbb{N}, k</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>-инвариантностью, второе — перестановочной инвариантностью. Оператор, выбранный из <tex>k</tex>-арного | + | Первое условие называется <tex>\bigoplus</tex>-инвариантностью, второе — перестановочной инвариантностью. Оператор, выбранный из <tex>k</tex>-арного беспристрастного распределения, называется '''<tex>k</tex>-арным беспристрастным вариативным оператором'''. |
− | Схема <tex>k</tex>-арного | + | Схема <tex>k</tex>-арного беспристрастного ''black-box'' алгоритма: |
'''Инициализация:''' выбрать <tex>x^{(0)}</tex> равновероятно из <tex>\{0,1\}^n</tex>. Запросить <tex>f(x^{(0)})</tex>. | '''Инициализация:''' выбрать <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>(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= | + | |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>\forall x \in \{0,1\}^n</tex>, где <tex>|\cdot|_1</tex> — количество единиц в битовой строке. |
}} | }} | ||
− | + | Далее будет показано, что для любого константного <tex>k</tex> можно с высокой вероятностью решить задачу <tex>OneMax</tex> <ref>[http://tracer.lcc.uma.es/problems/onemax/onemax.html OneMax problem]</ref> за малое количество ''black-box'' обращений к <tex>Jump_k</tex>. С помощью этого утверждения можно показать, что для любой константы <tex>k</tex> беспристрастная ''black-box'' сложность для функции <tex>Jump_k</tex> нереалистично мала. | |
{{Лемма | {{Лемма | ||
|id=lemma3 | |id=lemma3 | ||
− | |statement=<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=Используется унарный | + | |proof=Используется унарный беспристрастный вариативный оператор <tex>flip_k</tex>, который равновероятно выбирает строку из <tex>k</tex>-окрестности для аргумента (битовую строку, которая отличается в <tex>k</tex> позициях). Ниже предлагается функция <tex>s</tex>, которая использует <tex>Jump_k</tex> для аппроксимации <tex>OneMax</tex>. Функция выбирает <tex>c</tex> битовых строк в <tex>k</tex>-окрестности <tex>x</tex>. Если <tex>|x|_1 \geq n-k</tex>, то есть вероятность того, что хотя бы раз в <tex>x</tex> будут заменены только единицы, что приведет к тому, что <tex>Jump_k = |x|_1 - k</tex>. Так как больше никакая строка из выборки не будет иметь меньшее <tex>Jump_k</tex> значение, то добавление <tex>k</tex> к минимальному ненулевому значению <tex>Jump_k</tex> других строк из выборки приведет к нужному результату — функция вернет количество единиц в строке <tex>x</tex>. Случай, когда <tex>|x|_1 \leq k</tex>, аналогичен. |
− | Понятно, что | + | Понятно, что функция корректна при всех <tex>x</tex>, таких, что <tex>k < |x|_1 < n-k</tex>. Остальные два случая симметричны, поэтому пусть <tex>|x|_1 \geq n-k</tex>. Очевидно, что результат функции корректен тогда и только тогда, когда хотя бы в одной из <tex>c</tex> строк были заменены только единицы. Требуется вычислить вероятность <tex>p</tex> этого события. Итеративно выбираются <tex>k</tex> бит для замены, поэтому после <tex>i</tex> итераций имеется как минимум <tex>n-k-i</tex> позиций с единицей из <tex>n-i</tex> невыбранных позиций. Отсюда, с использованием неравенства Бернулли <ref>[http://en.wikipedia.org/wiki/Bernoulli%27s_inequality Bernoulli's inequality]</ref>, получается граница на вероятность выбора <tex>k</tex> единиц: |
− | :<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>(\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>: | |
'''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|предыдущую лемму]], можно найти | + | Теперь, используя [[#lemma3|предыдущую лемму]], можно найти беспристрастную ''black-box'' сложность для функции <tex>Jump_k</tex> при константном <tex>k</tex>. |
{{Теорема | {{Теорема | ||
|id=th4 | |id=th4 | ||
− | |statement=Для константы <tex>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>. | |
== Задача о разбиении == | == Задача о разбиении == | ||
+ | {{Задача | ||
+ | |definition=Задача о разбиении <ref>[http://en.wikipedia.org/wiki/Partition_problem Partition problem]</ref> (<tex>Partition</tex> problem) ставится следующим образом. Дано мультимножество <tex>\mathcal{I}</tex> положительных целых чисел (весов). Возможно ли разбить его на два непересекающихся множества <tex>\mathcal{I}=\mathcal{I}_0 \cup \mathcal{I}_1</tex> таким образом, что <tex>\Sigma_{w \in \mathcal{I}_0} w = \Sigma_{w \in \mathcal{I}_1} w</tex>? | ||
+ | }} | ||
+ | |||
+ | Оптимизационная версия задачи ставит вопрос о минимизации функции <tex>|\Sigma_{w \in \mathcal{I}_0} w - \Sigma_{w \in \mathcal{I}_1} w|</tex>. | ||
+ | |||
+ | Задача <tex>Partition</tex> является <tex>\mathrm{NP}</tex>-трудной. Предположительно <tex>\mathrm{P} \neq \mathrm{NP}</tex> и не существует полиномиального алгоритма решения этой задачи. | ||
+ | |||
+ | {{Лемма | ||
+ | |id=lemma5 | ||
+ | |statement=Задача <tex>Partition</tex> остается <tex>\mathrm{NP}</tex>-трудной, когда <tex>\forall v, w \in \mathcal{I}: v \neq w</tex>. | ||
+ | }} | ||
+ | |||
+ | Далее <tex>Partition_{\neq}</tex> — подкласс задачи <tex>Partition</tex> с заданными различными весами. | ||
+ | |||
+ | Далее предлагаются две различные функции приспособленности и показывается, что в обоих случаях может быть достигнута полиномиальная беспристрастная ''black-box'' сложность. Показывается, что унарная беспристрастная ''black-box'' сложность для задачи <tex>Partition_{\neq}</tex> равна <tex>O(n \log(n))</tex>. | ||
+ | |||
+ | === Знаковая функция приспособленности === | ||
+ | Пусть <tex>\mathcal{F}_{\mathcal{I}} := \{(\mathcal{I}_0, \mathcal{I}_1) \in 2^{\mathcal{I}} \times 2^{\mathcal{I}} | \mathcal{I}_0 \dot{\cup} \mathcal{I}_1 = \mathcal{I}\}</tex> — множество всех возможных решений для <tex>\mathcal{I}</tex>. Знаковая функция приспособленности определяется следующим образом: | ||
+ | |||
+ | :<tex>f_{\mathcal{I}}^{*}: \mathcal{F} \rightarrow \mathbb{Z}, (\mathcal{I}_0, \mathcal{I}_1) \mapsto \Sigma_{w \in \mathcal{I}_0} w - \Sigma_{w \in \mathcal{I}_1} w</tex>. | ||
+ | |||
+ | Цель заключается в минимизации <tex>|f_{\mathcal{I}}^{*}|</tex>. | ||
+ | |||
+ | Необходимо ввести нумерацию элементов <tex>\mathcal{I}</tex> — <tex>\sigma: \mathcal{I} \rightarrow [n]</tex>. Для любой битовой строки <tex>x \in \{0,1\}^n</tex> определены <tex>\mathcal{I}_0(x) := \{w \in \mathcal{I} | x_{\sigma(w)} = 0\}</tex> и <tex>\mathcal{I}_1(x) := \{w \in \mathcal{I} | x_{\sigma(w)} = 1\}</tex>. Тогда функция приспособленности преобразуется к следующему виду: | ||
+ | |||
+ | :<tex>f_{\mathcal{I}}: \{0,1\}^n \rightarrow \mathbb{Z}, x \mapsto \Sigma_{i \in [n], x_i=0} \sigma^{-1}(i) - \Sigma_{i \in [n], x_i=1} \sigma^{-1}(i)</tex>. | ||
+ | |||
+ | {{Теорема | ||
+ | |id=th6 | ||
+ | |statement=Унарная беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно функции приспособленности <tex>f_{\mathcal{I}}</tex> равна <tex>O(n \log(n))</tex>, где <tex>n := |\mathcal{I}|</tex>. | ||
+ | |proof=Для доказательства теоретмы строится алгоритм с применением двух вариативных операторов: | ||
+ | :*<tex>uniform()</tex> — выбирает случайную битовую строку <tex>x \in \{0,1\}^n</tex>; | ||
+ | :*<tex>RLS(\cdot)</tex> — случайно меняет элемент в одной из позиций входной строки. | ||
+ | |||
+ | Для краткости полагается <tex>f := f_{\mathcal{I}}</tex>. | ||
+ | |||
+ | Следующий алгоритм служит доказательством теоремы: | ||
+ | |||
+ | 1 '''Инициализация''' | ||
+ | 2 <tex>x^{(0)} \leftarrow uniform()</tex>. Запрос <tex>f(x^{(0)})</tex>; | ||
+ | 3 <tex>t \leftarrow 0, \mathcal{I}_0', \mathcal{I}_1', \mathcal{W}_0 = \varnothing</tex>; | ||
+ | 4 '''Определение весов''' | ||
+ | 5 '''while''' <tex>|\mathcal{W}_t| < n</tex> '''do''' | ||
+ | 6 <tex>t \leftarrow t + 1</tex>; | ||
+ | 7 <tex>x^{(t)} \leftarrow RLS(x^{(0)})</tex>. Запрос <tex>f(x^{(t)})</tex>; | ||
+ | 8 <tex>\mathcal{W}_t \leftarrow \mathcal{W}_{t-1} \cup \{|f(x^{(0)}) - f(x^{(t)})|/2\}</tex>; | ||
+ | 9 '''if''' <tex>f(x^{(0)}) > f(x^{(t)})</tex> '''then''' | ||
+ | 10 <tex>\mathcal{I}_0' \leftarrow \mathcal{I}_0' \cup {|f(x^{(0)}) - f(x^{(t)})|/2}</tex>; | ||
+ | 11 '''else''' <tex>\mathcal{I}_1' \leftarrow \mathcal{I}_1' \cup {|f(x^{(0)}) - f(x^{(t)})|/2}</tex>; | ||
+ | 12 '''Оптимизация''' | ||
+ | 13 В оффлайне перебором вычисляется оптимальное решение <tex>(\mathcal{O}_0, \mathcal{O}_1)</tex> | ||
+ | и множество <tex>\mathcal{M} \leftarrow \{w \in \mathcal{O}_0 | w \notin \mathcal{I}_0'\} \cup \{w \in \mathcal{O}_1 | w \notin \mathcal{I}_1'\}</tex> — множество элементов, которые необходимо переместить. | ||
+ | 14 <tex>z \leftarrow x^{(0)}</tex>; | ||
+ | 15 '''while''' <tex>|\mathcal{M}| > 0</tex> '''do''' | ||
+ | 16 <tex>y \leftarrow RLS(z)</tex>. Запрос <tex>f(y)</tex>; | ||
+ | 17 '''if''' <tex>w := |f(y)-f(z)|/2 \in \mathcal{M}</tex> '''then''' | ||
+ | 18 <tex>z \leftarrow y</tex>, <tex>\mathcal{M} \leftarrow \mathcal{M} \backslash \{w\}</tex>; | ||
+ | |||
+ | За <tex>(1+o(1))n \log(n)</tex> итераций определяются веса всех элементов <tex>\mathcal{I}</tex>. Зная веса элементов, в оффлайне перебором находится оптимальное решение задачи, после чего это решение необходимо восстановить с помощью вариативного <tex>1</tex>-арного оператора. Для этого построено множество <tex>\mathcal{M}</tex> — множество элементов, которые необходимо переместить для получения оптимального решения. В итоге, беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно заданной функции приспособленности равна <tex>O(n \log(n))</tex>. Полное доказательство приведено в работе <ref name="bbox"/>. | ||
+ | |||
+ | }} | ||
+ | |||
+ | === Беззнаковая функция приспособленности === | ||
+ | Можно заметить, что при доказательстве [[#th6|предыдущей теоремы]] происходила минимизация не самой функции <tex>f_{\mathcal{I}}</tex>, а только ее абсолютной величины. Однако та же асимптотика достигается и для беззнаковой функции приспособленности. Сложность заключается в том, что в этом случае нельзя просто определить вес перемещенного элемента. Этот факт выражается в более сложной процедуре для определения весов элементов. | ||
+ | |||
+ | {{Теорема | ||
+ | |id=th8 | ||
+ | |statement=Унарная беспристрастная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно функции приспособленности <tex>|f_{\mathcal{I}}|</tex> равна <tex>O(n \log(n))</tex>. Где <tex>n := |\mathcal{I}|</tex>. | ||
+ | |proof=Для краткости полагается: | ||
+ | :*<tex>f := |f_{\mathcal{I}}|</tex>; | ||
+ | :*<tex>S_0(x) = \Sigma_{w \in \mathcal{I}_0(x)} w</tex>; | ||
+ | :*<tex>S_1(x) = \Sigma_{w \in \mathcal{I}_1(x)} w</tex>; | ||
+ | :*<tex>\mathcal{I}_{max(x)}</tex> — множество элементов, принадлежащих корзине с большим весом. Например, <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> — элемент с максимальным весом. | ||
+ | |||
+ | Общая идея алгоритма состоит в следующем: | ||
+ | :*генерируется строка, такая, что все ее элементы находятся в одной корзине (с большой вероятностью это можно сделать за <tex>4n \log(n)</tex> запросов); | ||
+ | :*за <tex>2n \log(n)</tex> шагов с помощью <tex>RLS(\cdot)</tex> опеределяются веса всех элементов (с большой вероятностью); | ||
+ | :*за <tex>3n \log(n)</tex> шагов восстанавливаетчся решение (с большой вероятностью). | ||
+ | |||
+ | Следующий алгоритм является доказательством теоремы: | ||
+ | |||
+ | 1 '''Инициализация''' | ||
+ | 2 <tex>x^{(1,0)} \leftarrow uniform()</tex>. Запрос <tex>f(x^{(1,0)})</tex>; | ||
+ | 3 '''Перемещение всех элементов в одну корзину''' | ||
+ | 4 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do''' | ||
+ | 5 <tex>x^{(1,t)} \leftarrow RLS(x^{(1,0)})</tex>. Запрос <tex>f(x^{(1,t)})</tex>; | ||
+ | 6 Пусть <tex>l \in \arg \max_{0 \leq t \leq 2n \log(n)} f(x^{(1,t)})</tex>; | ||
+ | 7 <tex>x \leftarrow x^{(1,l)}</tex>; | ||
+ | 8 '''for''' <tex>t = 2n \log(n) + 1</tex> '''to''' <tex>4n \log(n)</tex> '''do''' | ||
+ | 9 <tex>y \leftarrow RLS(x)</tex>. Запрос <tex>f(y)</tex>; | ||
+ | 10 '''if''' <tex>f(y) > f(x)</tex> '''then''' <tex>x \leftarrow y</tex>; | ||
+ | 11 '''Определение весов всех элементов''' | ||
+ | 12 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do''' | ||
+ | 13 <tex>x^{(2,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(2,t)})</tex>; | ||
+ | 14 '''Оптимизация''' | ||
+ | 15 В оффлайне перебором вычисляется оптимальное решение <tex>(\mathcal{O}_0, \mathcal{O}_1)</tex>, такое что <tex>w_{max} \in \mathcal{O}_1</tex>. <tex>\mathcal{M} \leftarrow \mathcal{O}_1</tex>; | ||
+ | 16 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do''' | ||
+ | 17 <tex>x^{(3,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(3,t)})</tex>; | ||
+ | 18 '''if''' <tex>f(x) > 2w_{max}</tex> '''and''' <tex>f(x^{(3,t)}) < f(x)</tex> '''then''' | ||
+ | 19 вычислить <tex>w := (f(x) - f(x^{(3,t)})) / 2</tex>; | ||
+ | 20 '''if''' <tex>w \neq w_{max}</tex> '''and''' <tex>w \in \mathcal{M}</tex> '''then''' | ||
+ | 21 <tex>x \leftarrow x^{(3,t)}; \mathcal{M} \leftarrow \mathcal{M} \backslash w</tex>; | ||
+ | 22 '''for''' <tex>t = 1</tex> '''to''' <tex>n \log(n)</tex> '''do''' | ||
+ | 23 <tex>x^{(4,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(4,t)})</tex>; | ||
+ | |||
+ | Можно показать, что приведенный алгоритм с большой вероятностью за <tex>O(n \log(n))</tex> запросов находит оптимальное решение. Полное доказательство приведено в работе <ref name="bbox"/>. | ||
+ | |||
+ | }} | ||
+ | |||
+ | == Источники == | ||
+ | <references/> | ||
+ | |||
+ | [[Категория:Теория сложности]] | ||
+ | [[Категория:Эволюционные алгоритмы]] |
Текущая версия на 19:29, 4 сентября 2022
Введение в Black-box Complexity
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении функции приспособленности) получаемого им решения, по этой причине утверждения классической теории сложности здесь мало применимы.
Black-box Complexity [1] — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, black-box сложность алгоритма — количество вычислений функции приспособленности, необходимое для получения решения. Такое определение позволяет получить нереалистично низкие оценки black-box сложности, например, полиномиальную сложность для задачи поиска максимальной клики -полной[1][2].
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только беспристрастные (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) вариативные операторы. Также было введено понятие арности —
-арный беспристрастный black-box алгоритм использует только те операторы, которые принимают не более чем аргументов. Для некоторых классов задач такой подход к опеределению black-box сложности позволяет получить более реалистичные оценки вычислительной трудности. Операторы с арностью называют мутационными. В настоящей статье показано, что даже для алгоритмов, использующих только мутационные операторы, можно получить нереалистично маленькую оценку black-box сложности.Неограниченная и беспристрастная Black-box модели
Обозначения
- — положительные целые числа;
- :
- ;
- ;
- для битовой строки :
- — побитовое дополнение строки ;
- — побитовое исключающее или;
- для любого множества :
- — множество всех подмножеств множества
- для :
- — множество всех перестановок ;
- для и :
- ;
- под понимается натуральный логарифм.
Неограниченная Black-box модель
Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление функции приспособленности возможных решений. Заданная функция приспособленности вычисляется оракулом, или дается как black-box. Алгоритм может запросить у оракула значение функции для любого решения, однако больше никакой информации о решении получить не может.
В качестве функции приспособленности берется псевдо-булевая функция
.Согласно концепции black-box, алгоритм может включать следующие действия:
- выбор вероятностного распределения над ;
- выбор кандидата cогласно выбранному распределению;
- запрос значения функции приспособленности выбранного кандидата у оракула.
Схема неограниченного black-box алгоритма:
Инициализация: выбратьсогласно некоторому вероятностному распределению над . Запросить . Оптимизация: for until условие остановки do Исходя из , выбрать вероятностное распределение над . Выбрать согласно и запросить .
В качестве времени работы black-box алгоритма берется количество запросов к оракулу, сделанное до первого запроса с оптимальным решением.
Пусть
— класс псевдо-булевых функций. Сложностью алгоритма над называется максимальное предположительное время работы на функции (в худшем случае). Сложностью относительно класса алгоритмов называется минимальная сложность среди всех над . Неограниченной black-box сложностью называется сложность относительно класса неограниченных black-box алгоритмов.Беспристрастная Black-box модель
Класс неограниченных black-box алгоритмов слишком мощный. Например для любого функционального класса
неограниченная black-box сложность равна единице — алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию.Чтобы избежать этих недостатков была введена более строгая модель. В ней алгоритмы могут генерировать новые решения используя только беспристрастные вариативные операторы.
Определение: |
| -арным беспристрастным распределением называется семейство вероятностных распределений над таких, что для любых выполняются следующие условия:
Первое условие называется -инвариантностью, второе — перестановочной инвариантностью. Оператор, выбранный из -арного беспристрастного распределения, называется -арным беспристрастным вариативным оператором.
Схема
-арного беспристрастного black-box алгоритма:Инициализация: выбратьравновероятно из . Запросить . Оптимизация: for until условие остановки do Исходя из , выбрать индексов и -арное беспристрастное распределение . Выбрать согласно и запросить .
Лемма: |
Пусть для задачи существует black-box алгоритм , который с константной вероятностью успеха решает за итераций. Тогда black-box сложность не больше . |
Доказательство: |
Доказательство приведено в работе [1]. |
Jump функция
Определение: |
| функция определяется следующим образом:
Далее будет показано, что для любого константного можно с высокой вероятностью решить задачу [3] за малое количество black-box обращений к . С помощью этого утверждения можно показать, что для любой константы беспристрастная black-box сложность для функции нереалистично мала.
Лемма: |
Для любых и существует унарная беспристрастная функция , использующая запросов к такая, что для всех битовых строк , с вероятностью . |
Доказательство: |
Используется унарный беспристрастный вариативный оператор , который равновероятно выбирает строку из -окрестности для аргумента (битовую строку, которая отличается в позициях). Ниже предлагается функция , которая использует для аппроксимации . Функция выбирает битовых строк в -окрестности . Если , то есть вероятность того, что хотя бы раз в будут заменены только единицы, что приведет к тому, что . Так как больше никакая строка из выборки не будет иметь меньшее значение, то добавление к минимальному ненулевому значению других строк из выборки приведет к нужному результату — функция вернет количество единиц в строке . Случай, когда , аналогичен.Понятно, что функция корректна при всех [4], получается граница на вероятность выбора единиц: , таких, что . Остальные два случая симметричны, поэтому пусть . Очевидно, что результат функции корректен тогда и только тогда, когда хотя бы в одной из строк были заменены только единицы. Требуется вычислить вероятность этого события. Итеративно выбираются бит для замены, поэтому после итераций имеется как минимум позиций с единицей из невыбранных позиций. Отсюда, с использованием неравенства Бернулли
Таким образом:
Функция :ifthen output ; ; if then ; else ; output ; |
Теперь, используя предыдущую лемму, можно найти беспристрастную black-box сложность для функции при константном .
Теорема: |
Для константы беспристрастная black-box сложность :
|
Доказательство: |
Доказательство приведено в работе [1]. |
Функции из предыдущей леммы для работы необходимо знать параметр , но ее можно модифицировать таким образом, что она будет работать без этого знания. Как только функция впервые выберет случайную битовую строку с она определит , затем продолжит работу как было описано выше. Параметр определяется с помощью выбора достаточно большого количества случайных строк в -окрестности от строки с , начиная с и продолжая до тех пор, пока не станет отличным от нуля. Найденная строка будет иметь максимальное значение . Из этого значения и функция может вычислить .
Задача о разбиении
Задача: |
Задача о разбиении [5] ( problem) ставится следующим образом. Дано мультимножество положительных целых чисел (весов). Возможно ли разбить его на два непересекающихся множества таким образом, что ? |
Оптимизационная версия задачи ставит вопрос о минимизации функции .
Задача
является -трудной. Предположительно и не существует полиномиального алгоритма решения этой задачи.Лемма: |
Задача остается -трудной, когда . |
Далее
— подкласс задачи с заданными различными весами.Далее предлагаются две различные функции приспособленности и показывается, что в обоих случаях может быть достигнута полиномиальная беспристрастная black-box сложность. Показывается, что унарная беспристрастная black-box сложность для задачи
равна .Знаковая функция приспособленности
Пусть
— множество всех возможных решений для . Знаковая функция приспособленности определяется следующим образом:- .
Цель заключается в минимизации
.Необходимо ввести нумерацию элементов
— . Для любой битовой строки определены и . Тогда функция приспособленности преобразуется к следующему виду:- .
Теорема: |
Унарная беспристрастная black-box сложность задачи относительно функции приспособленности равна , где . |
Доказательство: |
Для доказательства теоретмы строится алгоритм с применением двух вариативных операторов:
Для краткости полагается .Следующий алгоритм служит доказательством теоремы: 1 Инициализация 2За . Запрос ; 3 ; 4 Определение весов 5 while do 6 ; 7 . Запрос ; 8 ; 9 if then 10 ; 11 else ; 12 Оптимизация 13 В оффлайне перебором вычисляется оптимальное решение и множество — множество элементов, которые необходимо переместить. 14 ; 15 while do 16 . Запрос ; 17 if then 18 , ; итераций определяются веса всех элементов . Зная веса элементов, в оффлайне перебором находится оптимальное решение задачи, после чего это решение необходимо восстановить с помощью вариативного -арного оператора. Для этого построено множество — множество элементов, которые необходимо переместить для получения оптимального решения. В итоге, беспристрастная black-box сложность задачи относительно заданной функции приспособленности равна . Полное доказательство приведено в работе [1]. |
Беззнаковая функция приспособленности
Можно заметить, что при доказательстве предыдущей теоремы происходила минимизация не самой функции , а только ее абсолютной величины. Однако та же асимптотика достигается и для беззнаковой функции приспособленности. Сложность заключается в том, что в этом случае нельзя просто определить вес перемещенного элемента. Этот факт выражается в более сложной процедуре для определения весов элементов.
Теорема: |
Унарная беспристрастная black-box сложность задачи относительно функции приспособленности равна . Где . |
Доказательство: |
Для краткости полагается:
Общая идея алгоритма состоит в следующем:
Следующий алгоритм является доказательством теоремы: 1 Инициализация 2Можно показать, что приведенный алгоритм с большой вероятностью за . Запрос ; 3 Перемещение всех элементов в одну корзину 4 for to do 5 . Запрос ; 6 Пусть ; 7 ; 8 for to do 9 . Запрос ; 10 if then ; 11 Определение весов всех элементов 12 for to do 13 . Запрос ; 14 Оптимизация 15 В оффлайне перебором вычисляется оптимальное решение , такое что . ; 16 for to do 17 . Запрос ; 18 if and then 19 вычислить ; 20 if and then 21 ; 22 for to do 23 . Запрос ; запросов находит оптимальное решение. Полное доказательство приведено в работе [1]. |