Изменения

{{В разработке}}

{{Boring}}

Целью теории сложности является определение вычислительной трудности алгоритмов. Классическая теория сложности предполагает, что алгоритму полностью известна структура решаемой задачи. В случае эволюционных алгоритмов, алгоритм обладает информацией только о качестве (значении ''fitness'' функции) получаемого им решения. По этой причине утверждения классической теории сложности мало применимы для эволюционных алгоритмов.

По этой причине были введены ограничения на исследуемые алгоритмы. Требуется, чтобы для получения новых кандидатов на решение использовались только '''несмещенные''' (позиция элемента в битовой строке и его значение не влияют на выбор битов для изменения) '''вариативные операторы'''. Так же введено понятие '''арности''' &mdash; <tex>k</tex>-арный несмещенный ''black-box'' алгоритм использует только те операторы, которые принимают не более чем <tex>k</tex> аргументов. Для некоторых классов задач такой подход к опеределению ''black-box complexity'' позволяет получить более реалистичные оценки сложности. Операторы с арностью <tex>1</tex> называют '''мутационными'''. В данной статье показано, что даже для алгоритмов, использующих только мутационные операторы можно получить не реалистично маленькую оценку ''black-box complexity''.

*<tex>\mathbb{N}</tex> &mdash; положительные целые числа;

*<tex>\forall k \in \mathbb{N}</tex>

*под <tex>log</tex> понимается натуральный логарифм.

Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление ''fitness'' функции возможных решений. Заданная ''fitness'' функция вычисляется ''ораклом'', или дается как ''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'' алгоритмов слишком мощный. Например для любого функционального класса <tex>\mathcal{F} = \{f\}</tex> неограниченная ''black-box'' сложность равна единице &mdash; алгоритм, который просто запрашивает оптимальное решение первым же шагом, удовлетворяет этому условию.