Алговики - Вклад [ru]

Участник:Sergey Ivanov/Генетические алгоритмы

2017-12-03T18:13:48Z

Sergey Ivanov: /* Масштабируемость алгоритма и его реализации */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

== Вычислительное ядро алгоритма ==
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

== Макроструктура алгоритма ==
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

== Схема реализации последовательного алгоритма ==
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

== Последовательная сложность алгоритма ==
Предположим, что сложность одного вычисления фитнес-функции имеет сложность <math>F</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

== Информационный граф ==
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|500px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

== Ресурс параллелизма алгоритма ==
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

== Входные и выходные данные алгоритма ==

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>;
<math>\mathbb{X}</math> должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x \in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.01. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GeneticOptimizationStrongScalability.png|thumb|center|600px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-12-03T18:07:43Z

Sergey Ivanov: /* Последовательная сложность алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

== Вычислительное ядро алгоритма ==
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

== Макроструктура алгоритма ==
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

== Схема реализации последовательного алгоритма ==
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

== Последовательная сложность алгоритма ==
Предположим, что сложность одного вычисления фитнес-функции имеет сложность <math>F</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

== Информационный граф ==
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|500px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

== Ресурс параллелизма алгоритма ==
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

== Входные и выходные данные алгоритма ==

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>;
<math>\mathbb{X}</math> должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x \in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GeneticOptimizationStrongScalability.png|thumb|center|600px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-30T15:48:57Z

Sergey Ivanov: /* Входные и выходные данные алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

== Вычислительное ядро алгоритма ==
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

== Макроструктура алгоритма ==
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

== Схема реализации последовательного алгоритма ==
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

== Последовательная сложность алгоритма ==
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

== Информационный граф ==
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|500px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

== Ресурс параллелизма алгоритма ==
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

== Входные и выходные данные алгоритма ==

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>;
<math>\mathbb{X}</math> должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x \in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GeneticOptimizationStrongScalability.png|thumb|center|600px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-30T15:48:42Z

Sergey Ivanov: /* Входные и выходные данные алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

== Вычислительное ядро алгоритма ==
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

== Макроструктура алгоритма ==
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

== Схема реализации последовательного алгоритма ==
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

== Последовательная сложность алгоритма ==
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

== Информационный граф ==
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|500px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

== Ресурс параллелизма алгоритма ==
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

== Входные и выходные данные алгоритма ==

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
<math>\mathbb{X}</math> должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x \in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GeneticOptimizationStrongScalability.png|thumb|center|600px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-30T15:48:12Z

Sergey Ivanov: /* Входные и выходные данные алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

== Вычислительное ядро алгоритма ==
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

== Макроструктура алгоритма ==
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

== Схема реализации последовательного алгоритма ==
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

== Последовательная сложность алгоритма ==
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

== Информационный граф ==
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|500px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

== Ресурс параллелизма алгоритма ==
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

== Входные и выходные данные алгоритма ==

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x \in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GeneticOptimizationStrongScalability.png|thumb|center|600px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-30T15:47:52Z

Sergey Ivanov: /* Структура алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

== Вычислительное ядро алгоритма ==
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

== Макроструктура алгоритма ==
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

== Схема реализации последовательного алгоритма ==
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

== Последовательная сложность алгоритма ==
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

== Информационный граф ==
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|500px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

== Ресурс параллелизма алгоритма ==
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

== Входные и выходные данные алгоритма ==

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GeneticOptimizationStrongScalability.png|thumb|center|600px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-30T15:22:15Z

Sergey Ivanov:

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

== Возможные вариации ==

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

== Макроструктура алгоритма ==
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

== Схема реализации последовательного алгоритма ==
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

== Последовательная сложность алгоритма ==
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

== Информационный граф ==
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|500px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

== Ресурс параллелизма алгоритма ==
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

== Входные и выходные данные алгоритма ==

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GeneticOptimizationStrongScalability.png|thumb|center|600px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
<references />

Файл:GeneticOptimizationStrongScalability.png

2017-11-30T15:20:49Z

Sergey Ivanov:

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-30T15:20:13Z

Sergey Ivanov:

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

== Возможные вариации ==

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

== Макроструктура алгоритма ==
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

== Схема реализации последовательного алгоритма ==
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

== Последовательная сложность алгоритма ==
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

== Информационный граф ==
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

== Ресурс параллелизма алгоритма ==
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

== Входные и выходные данные алгоритма ==

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

= Программная реализация алгоритма =

== Особенности реализации последовательного алгоритма ==

== Локальность данных и вычислений ==

== Возможные способы и особенности параллельной реализации алгоритма ==

== Масштабируемость алгоритма и его реализации ==

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GA_Graph.png|thumb|center|300px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

== Динамические характеристики и эффективность реализации алгоритма ==

== Выводы для классов архитектур ==

== Существующие реализации алгоритма ==

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-30T15:18:46Z

Sergey Ivanov:

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
* операция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
* вероятность мутации одного гена; обычно 0,01 или меньше.
* критерий останова: например, достижение определённого результата или ограничение на количество эпох.

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона <math>[0, 1]</math>) с вероятностью 0.1. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2

[[file:GA_Graph.png|thumb|center|300px|Рис.2. Сильная масштабируемость генетической оптимизации]]

Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины <math>D=100</math> от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-30T15:03:03Z

Sergey Ivanov: /* Входные и выходные данные алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===

'''Входные данные''': функция <math>f: \mathbb{X} \to \mathbb{R} </math>
\mathbb{X} должно иметь некоторое программное представление, например, определена некоторая инъекция <math>\mathbb{R}^d \to \mathbb{X}</math>.

'''Выходные данные''': субоптимальный <math>x in \mathbb{X}</math>

'''Параметры''':
* размер популяции (100-1000)
* количество особей для отбора (например, относительно объёма размера популяции; обычно 10-50%)
* операция кроссинговера <math>Crossover: \mathbb{X} \to \mathbb{R} </math>

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-29T15:38:27Z

Sergey Ivanov: /* Схема реализации последовательного алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-29T14:41:40Z

Sergey Ivanov: /* Ресурс параллелизма алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} ~ \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-29T14:21:56Z

Sergey Ivanov: /* Последовательная сложность алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} ~ \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>.

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>.

Этап 7 также имеет сложность <math>PD</math>.

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступно для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-29T14:21:38Z

Sergey Ivanov: /* Последовательная сложность алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} ~ \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>

Этап 7 также имеет сложность <math>PD</math>

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между <math>F</math> и <math>D</math> таково, что сложность по факту становится <math>O(PF)</math>

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступно для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-29T14:20:45Z

Sergey Ivanov: /* Информационный граф */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} ~ \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>

Этап 7 также имеет сложность <math>PD</math>

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступно для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-29T14:20:25Z

Sergey Ivanov: /* Последовательная сложность алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} ~ \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \log P </math>

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>

Этап 7 также имеет сложность <math>PD</math>

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \log P + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке <math>p1</math> и <math>p2</math> формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступно для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-29T14:19:50Z

Sergey Ivanov: /* Структура алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} ~ \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \logP </math>

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>

Этап 7 также имеет сложность <math>PD</math>

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \logP + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке <math>p1</math> и <math>p2</math> формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:GA_Graph.png|thumb|center|300px|Рис.1. Информационный граф генетического поиска]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступно для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

= Литература =
<references />

Файл:GA Graph.png

2017-11-29T14:18:56Z

Sergey Ivanov:

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-29T14:18:08Z

Sergey Ivanov: /* Структура алгоритма */

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

=== Вычислительное ядро алгоритма ===
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие:
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000

=== Макроструктура алгоритма ===
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
* вычисление значений <math>F</math> для каждой особи
* сортировка полученных значений
* сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)

=== Схема реализации последовательного алгоритма ===
1. Провести инициализацию первой популяции <math>{x}</math>

2. Для каждой особи вычислить значение <math>f_i = F(x_i)</math>

3. Отсортировать особи по массиву значений <math>f_i</math>

4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math>

5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} ~ \mathcal{U}\{0, SelectionSize\}</math>

6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math>

7. Положить <math>{x} = {y}</math>

8. Перейти к пункту 2

=== Последовательная сложность алгоритма ===
Предположим, что сложность одного вычисления функции <math>F</math> имеет сложность <math>N</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма:

Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>;

Этап 3 имеет сложность <math>P \logP </math>

Этапы 4-5 имеют константную сложность.

Этап 6 имеет сложность <math>PD</math>

Этап 7 также имеет сложность <math>PD</math>

Для произвольной <math>F</math> в общем случае сложность алгоритма составляет <math>O(PF + P \logP + PD)</math>, обычно выбор параметров таков, что вторым слагаемым можно пренебречь.

При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел.

=== Информационный граф ===
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке <math>p1</math> и <math>p2</math> формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.

[[file:Fig1.svg|thumb|center|300px|Рис.1. Информационная структура алгоритма умножения матриц]]

Формально граф на рис.1 состоит из следующих элементов:
* для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
* полученный набор значений подаётся на вход алгоритму сортировки <math>{x}</math> в качестве критерия сортировки.
* вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-<math>SelectionSize</math> по результатам сортировки
* после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется <math>Crossover</math>
* полученные значения становятся новыми особями популяции

=== Ресурс параллелизма алгоритма ===
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма.

Информационный граф показывает, что также доступно для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.

Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</math> для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
* отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.

=== Входные и выходные данные алгоритма ===
В данном разделе необходимо описать объем, структуру, особенности и свойства входных и выходных данных алгоритма: векторы, матрицы, скаляры, множества, плотные или разреженные структуры данных, их объем. Полезны предположения относительно диапазона значений или структуры, например, диагональное преобладание в структуре входных матриц, соотношение между размером матриц по отдельным размерностям, большое число матриц очень малой размерности, близость каких-то значений к машинному нулю, характер разреженности матриц и другие.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-04T11:55:32Z

Sergey Ivanov: /* Возможные вариации */

Участник:Sergey Ivanov/Генетические алгоритмы

2017-11-03T20:47:28Z

Sergey Ivanov: /* Структура алгоритма */

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T17:04:53Z

Sergey Ivanov:

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T16:21:09Z

Sergey Ivanov:

= Структура алгоритма =

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора брать две случайные особи и устроить между ними "сражение", в котором один из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T16:20:31Z

Sergey Ivanov:

= Структура алгоритма =

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

== Возможные вариации ==

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора брать две случайные особи и устроить между ними "сражение", в котором один из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T16:20:08Z

Sergey Ivanov:

=== Описание алгоритма ===

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

=== Математическое описание алгоритма ===

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

=== Возможные вариации ===

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора брать две случайные особи и устроить между ними "сражение", в котором один из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T16:12:24Z

Sergey Ivanov:

== Описание алгоритма ==

Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math>

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

== Возможные вариации ==

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

* битвы на выживание: на этапе отбора брать две случайные особи и устроить между ними "сражение", в котором один из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T15:26:31Z

Sergey Ivanov:

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T15:24:27Z

Sergey Ivanov: /* Описание алгоритма */

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T15:22:40Z

Sergey Ivanov: /* Ссылки */

== Описание алгоритма ==

Генетический алгоритм - универсальный субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>.

От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы.

== Математическое описание алгоритма ==

'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math>

'''Параметры алгоритма:''' размер популяции <math>PopulationSize</math>, число выживающих особей на каждом этапе <math>SurvivalSize</math>, функция кроссинговера <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>, критерий останова. Опционально: функция мутации <math> Mutation\colon \mathbb{X}\to \mathbb{X} </math>, вероятность мутации <math>\epsilon</math>.

'''Выходные данные:''' субоптимальный экстремум <math>x*</math>

'''Инициализация: ''' <math>Population_0 := PopulationSize</math> случайных объектов из <math>\mathbb{X}</math>

До выполнения критерия останова:
* вычислить <math>F(x)</math> для всех <math>x</math> из <math>Population_i</math>
* оставить топ-<math>SurvivalSize</math> особей из <math>Population_i</math>
* составить <math>Population_{i+1}</math>: каждая новая особь есть результат применения <math>Crossover</math> к двум случайным выжившим особям
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>

Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>

== Ссылки ==

= Литература =
<references />

Участник:Sergey Ivanov/Генетические алгоритмы

2017-10-22T15:20:08Z

Sergey Ivanov: Новая страница: «== Описание алгоритма == Генетический алгоритм - универсальный субоптимальный метод опти…»