Изменения
Нет описания правки
{{В разработке}}
== Введение в 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> — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box'' сложность алгоритма — количество вычислений ''fitness''-функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки ''black-box'' сложности, например, полиномиальную сложность для [[Классы_NP_и_Σ₁|<tex>\mathrm{NP}</tex>-полной ]] задачи поиска максимальной клики<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'' сложности.
|id=remark2
|statement=Предположим, что для задачи <tex>P</tex> существует ''black-box'' алгоритм <tex>A</tex>, который с константной вероятностью успеха решает <tex>P</tex> за <tex>s</tex> итераций. Тогда ''black-box'' сложность <tex>P</tex> не больше <tex>O(s)</tex>.
|proof=Доказательство приведено в работе <ref name="bbox"/>.
}}
*<tex>O(n / \log(m))</tex> для <tex>m</tex>-арных вариативных операторов при <tex>2 \leq m \leq n</tex>;
*<tex>O(n / \log(n))</tex> для *-арных вариативных операторов.
|proof=Доказательство приведено в работе <ref name="bbox"/>.
}}
|id=lemma5
|statement=Задача <tex>Partition</tex> остается <tex>\mathrm{NP}</tex>-трудной, когда <tex>\forall v, w \in \mathcal{I}: v \neq 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> — множество элементов, которые необходимо переместить для получения оптимального решения. В итоге получается, что несмещенная ''black-box'' сложность задачи <tex>Partition_{\neq}</tex> относительно заданной ''fitness''-функции равна <tex>O(n \log(n))</tex>. Полное доказательство приведено в работе <ref name="bbox"/>.
}}
23 <tex>x^{(4,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(4,t)})</tex>;
Можно показать, что приведенный алгоритм с большой вероятностью за <tex>O(n \log(n))</tex> запросов находит оптимальное решение. Полное доказательство приведено в работе <ref name="bbox"/>.
}}
== Источники Ссылки ==# [http:<references//rain.ifmo.ru/~tsarev/teaching/ea-2012/seminars/p2043.pdf Doerr B., Kotzing T., Winzen C. Too Fast Unbiased Black-Box Algorithms]>
