Изменения
Нет описания правки
Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''fitness'' функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.
'''Black-box Complexity''' — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, ''black-box complexity'' алгоритма — количество вычислений ''fitness'' функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки ''black-box complexity'', например, полиномиальную сложность для <tex>\mathrm{NP}</tex>-полной задачи поиска максимальной клики.
По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''несмещенные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Так же введено понятие '''арности''' — <tex>k</tex>-арный несмещенный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box complexity'' позволяет получить более реалистичные оценки сложности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В данной статье показано, что даже для алгоритмов, использующих только мутационные операторы можно получить не реалистично маленькую оценку ''black-box complexity''.
=== Неограниченная и несмещенная Black-box модели ======= Обозначения ====*<tex>\mathbb{N}</tex> — положительные целые числа;*<tex>\forall k \in \mathbb{N}</tex>:<tex>[k] := \{1, \ldots , k\}</tex>;*<tex>[0..k] := [k] \cup \{0\}</tex>;*Для для битовой строки <tex>x = x_1 \cdots x_n \in \{0, 1\}^n</tex>:<tex>\overline{x}</tex> — побитовое дополнение строки <tex>x</tex>;*<tex>\bigoplus</tex> — побитовое исключающее или;*Для для любого множества <tex>S</tex>
:<tex>2^S</tex> — множество всех подмножеств множества <tex>S</tex>
*Для для <tex>n \in \mathbb{N}</tex>:<tex>S_n</tex> — множество всех перестановок <tex>[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>log</tex> понимается натуральный логарифм. ==== Неограниченная Black-box модель ====Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление ''fitness'' функции возможных решений. Заданная ''fitness'' функция вычисляется ''ораклом'', или дается как ''black-box''. Алгоритм может запросить у ''оракла'' значение функции для любого решения, однако более никакой информации о решении получить не может. В качестве ''fitness'' функции берется псевдо-булевая функция <tex>F:\{0,1\}^n \rightarrow \mathbb{R}</tex>. Согласно концепции ''black-box'', алгоритм может включать следующие действия:*выбор вероятностного распределения над <tex>\{0,1\}^n</tex>;*выбор кандидата <tex>x \in \{0,1\}^n</tex> cогласно выбранному распределению;*запрос значения ''fitness'' функции выбранного кандидата у ''оракла''. Схема неограниченного ''black-box'' алгоритма: '''Инициализация:''' выбрать <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''' Исходя из <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>. В качестве времени работы ''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'' сложность равна единице — алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию. Чтобы избежать этих недостатков была введена более строгая модель. В ней алгоритмы могут генерировать новые решения используя только ''несмещенные вариативные операторы''. {{Определение|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>D(x|y^{(1)},\ldots,y^{(k)}) = D(x \bigoplus z|y^{(1)} \bigoplus z,\ldots,y^{(k)} \bigoplus z)</tex>;*<tex>\forall x \in \{0,1\}^n \forall \sigma \in S_n</tex>::<tex>D(x|y^{(1)},\ldots,y^{(k)}) = D(\sigma(x)|\sigma(y^{(1)}),\ldots,\sigma(y^{(k)}))</tex>.}} Первое условие называется <tex>\bigoplus</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>. '''Оптимизация:''' '''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>x^{(t)}</tex> согласно <tex>D(\cdot|x^{(i_1)},\ldots,x^{(i_k)})</tex> и запросить <tex>f(x^{(t)})</tex>.
