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

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

Версия 20:06, 17 июня 2012

Эта статья находится в разработке!
nothumb
Эта статья сделана из уныния и отчаяния.
Сделайте с ней что-нибудь.
Пожалуйста.

Black-box Complexity. Примеры нереалистичных оценок Black-box Complexity

Введение в Black-box complexity

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

Black-box Complexity — попытка построить теорию сложности для эволюционных алгоритмов. Вкратце, black-box complexity алгоритма — количество вычислений fitness функции, необходимое для получения решения. Такое определение позволяет получить не реалистично низкие оценки black-box complexity, например, полиномиальную сложность для [math]\mathrm{NP}[/math]-полной задачи поиска максимальной клики.

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

Неограниченная и несмещенная 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 модель

Рассматривается класс алгоритмов оптимизации, которые получают информацию о решаемой задаче через вычисление fitness функции возможных решений. Заданная fitness функция вычисляется ораклом, или дается как black-box. Алгоритм может запросить у оракла значение функции для любого решения, однако более никакой информации о решении получить не может.

В качестве fitness функции берется псевдо-булевая функция [math]F:\{0,1\}^n \rightarrow \mathbb{R}[/math].

Согласно концепции black-box, алгоритм может включать следующие действия:

  • выбор вероятностного распределения над [math]\{0,1\}^n[/math];
  • выбор кандидата [math]x \in \{0,1\}^n[/math] cогласно выбранному распределению;
  • запрос значения fitness функции выбранного кандидата у оракла.

Схема неограниченного 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].