Участник:Sergey Ivanov/Генетические алгоритмы: различия между версиями
| (не показано 11 промежуточных версий этого же участника) | |||
| Строка 3: | Строка 3: | ||
= Структура алгоритма = | = Структура алгоритма = | ||
== Описание алгоритма == | |||
Генетический алгоритм - универсальный<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>. | Генетический алгоритм - универсальный<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>. | ||
| Строка 13: | Строка 13: | ||
Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации. | Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации. | ||
== Математическое описание алгоритма == | |||
'''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math> | '''Входные данные:''' функция <math> F\colon \mathbb{X} \to \mathbb{R}</math> | ||
| Строка 39: | Строка 39: | ||
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог. | * старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог. | ||
== Вычислительное ядро алгоритма == | |||
В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие: | В типичной ситуации [[глоссарий#Вычислительное ядро|''вычислительным ядром'']] алгоритма является вычисление <math>PopulationSize</math> значений оптимизируемой функции <math>F</math>. Основными причинами такого положения являются следующие: | ||
* генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой. | * генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой. | ||
* все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000 | * все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или <math>O(PopulationSize \log PopulationSize)</math>, где <math>PopulationSize</math> редко превосходит 1000 | ||
== Макроструктура алгоритма == | |||
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций: | Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций: | ||
* вычисление значений <math>F</math> для каждой особи | * вычисление значений <math>F</math> для каждой особи | ||
| Строка 51: | Строка 51: | ||
* проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами) | * проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами) | ||
== Схема реализации последовательного алгоритма == | |||
1. Провести инициализацию первой популяции <math>{x}</math> | 1. Провести инициализацию первой популяции <math>{x}</math> | ||
| Строка 60: | Строка 60: | ||
4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math> | 4. Проверить критерий останова. Если он выполнен, ответом алгоритма является <math>x_0</math> | ||
5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} | 5. Для каждой особи засэмплировать <math>p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\}</math> | ||
6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math> | 6. Составить <math>{y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})}</math> | ||
| Строка 68: | Строка 68: | ||
8. Перейти к пункту 2 | 8. Перейти к пункту 2 | ||
== Последовательная сложность алгоритма == | |||
Предположим, что сложность одного вычисления функции | Предположим, что сложность одного вычисления фитнес-функции имеет сложность <math>F</math>, процедура кроссинговера --- <math>D</math>; размер популяции для сокращения выкладок обозначим <math>P</math>. Рассчитаем сложность одной эпохи алгоритма: | ||
Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>; | Этап 2 является наиболее вычислительно трудоёмким и имеет сложность <math>PF</math>; | ||
| Строка 85: | Строка 85: | ||
При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел. | При этом в памяти необходимо хранить два массива из <math>P</math> объектов из пространства <math>\mathbb{X}</math>. В предположении, что его размерность совпадает со сложностью кроссинговера, это <math>2PD</math> вещественных чисел. | ||
== Информационный граф == | |||
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма. | На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов <math>{x}</math>; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми <math>x</math>, получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма. | ||
[[file:GA_Graph.png|thumb|center| | [[file:GA_Graph.png|thumb|center|500px|Рис.1. Информационный граф генетического поиска]] | ||
Формально граф на рис.1 состоит из следующих элементов: | Формально граф на рис.1 состоит из следующих элементов: | ||
| Строка 97: | Строка 97: | ||
* полученные значения становятся новыми особями популяции | * полученные значения становятся новыми особями популяции | ||
== Ресурс параллелизма алгоритма == | |||
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма. | На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с <math>O(PN)</math> до <math>O(N)</math>, и при больших <math>N</math> эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции <math>F</math>, что фундаментально является существенным преимуществом алгоритма. | ||
Информационный граф показывает, что также | Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера <math>P</math> раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание. | ||
Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания: | Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания: | ||
* индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-<math>SelectionSize</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 /> | <references /> | ||
Текущая версия от 18:13, 3 декабря 2017
Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год
Структура алгоритма
Описание алгоритма
Генетический алгоритм - универсальный[1] субоптимальный метод оптимизации [math]\displaystyle{ F(x) \rightarrow \mathop{max}_x }[/math]. Универсальность проявляется в его пригодности к задачам с произвольными функциями [math]\displaystyle{ F\colon \mathbb{X} \to \mathbb{R} }[/math] и нетривиальной природой пространства аргументов [math]\displaystyle{ \mathbb{X} }[/math].
От функции [math]\displaystyle{ F }[/math] требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции [math]\displaystyle{ Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} }[/math]. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации[2]) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов [math]\displaystyle{ g_1, g_2 }[/math] результатом обычно полагается [math]\displaystyle{ \alpha g_1 + (1 - \alpha) g_2 }[/math], где [math]\displaystyle{ \alpha \sim Unifrom(0, 1) }[/math]
Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения[3] и задачи обучения с подкреплением[4].
Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что генотипом является некоторая точка [math]\displaystyle{ x }[/math], а фенотипом - значение в данной точке функции [math]\displaystyle{ F }[/math]. Основная идея алгоритма заключается в том, чтобы в рамках некоторой популяции, т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется эпохой. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.
Математическое описание алгоритма
Входные данные: функция [math]\displaystyle{ F\colon \mathbb{X} \to \mathbb{R} }[/math]
Параметры алгоритма: размер популяции [math]\displaystyle{ PopulationSize }[/math], число выживающих особей на каждом этапе [math]\displaystyle{ SurvivalSize }[/math], функция кроссинговера [math]\displaystyle{ Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} }[/math], критерий останова. Опционально: функция мутации [math]\displaystyle{ Mutation\colon \mathbb{X}\to \mathbb{X} }[/math], вероятность мутации [math]\displaystyle{ \epsilon }[/math].
Выходные данные: субоптимальный экстремум [math]\displaystyle{ x* }[/math]
Инициализация: [math]\displaystyle{ Population_0 := PopulationSize }[/math] случайных объектов из [math]\displaystyle{ \mathbb{X} }[/math]
До выполнения критерия останова:
- вычислить [math]\displaystyle{ F(x) }[/math] для всех [math]\displaystyle{ x }[/math] из [math]\displaystyle{ Population_i }[/math]
- оставить топ-[math]\displaystyle{ SurvivalSize }[/math] особей из [math]\displaystyle{ Population_i }[/math]
- составить [math]\displaystyle{ Population_{i+1} }[/math]: каждая новая особь есть результат применения [math]\displaystyle{ Crossover }[/math] к двум случайным выжившим особям
- при наличии мутаций к каждой особи с вероятностью [math]\displaystyle{ \epsilon }[/math] применить функцию [math]\displaystyle{ Mutation }[/math]
На выход алгоритм подаётся [math]\displaystyle{ \mathop{argmax}_{x \in Population_{last}} F(x) }[/math]
Возможные вариации
Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:
- битвы на выживание: на этапе отбора выбирать две случайные особи и устраивать между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции [math]\displaystyle{ F }[/math].
- острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
- старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.
Вычислительное ядро алгоритма
В типичной ситуации вычислительным ядром алгоритма является вычисление [math]\displaystyle{ PopulationSize }[/math] значений оптимизируемой функции [math]\displaystyle{ F }[/math]. Основными причинами такого положения являются следующие:
- генетические алгоритмы "специализированы" для оптимизации функций, для которых вычисление значения в точке является нетривиальной или достаточно вычислительно трудоёмкой процедурой.
- все остальные макрооперации алгоритма обычно имеют сложность или линейную от размерности пространства аргументов, или [math]\displaystyle{ O(PopulationSize \log PopulationSize) }[/math], где [math]\displaystyle{ PopulationSize }[/math] редко превосходит 1000
Макроструктура алгоритма
Алгоритм, как видно из математического описания алгоритма, состоит в проведении следующих макроопераций:
- вычисление значений [math]\displaystyle{ F }[/math] для каждой особи
- сортировка полученных значений
- сэмплирование индексов родителей для каждой особи из дискретного равномерного распределения
- проведение кроссинговера для генерации новых особей (типично представляет собой поэлементную процедуру над двумя векторами)
Схема реализации последовательного алгоритма
1. Провести инициализацию первой популяции [math]\displaystyle{ {x} }[/math]
2. Для каждой особи вычислить значение [math]\displaystyle{ f_i = F(x_i) }[/math]
3. Отсортировать особи по массиву значений [math]\displaystyle{ f_i }[/math]
4. Проверить критерий останова. Если он выполнен, ответом алгоритма является [math]\displaystyle{ x_0 }[/math]
5. Для каждой особи засэмплировать [math]\displaystyle{ p_{i1}, p_{i2} \sim \mathcal{U}\{0, SelectionSize\} }[/math]
6. Составить [math]\displaystyle{ {y_i = Crossover(x_{p_{i1}}, x_{p_{i2}})} }[/math]
7. Положить [math]\displaystyle{ {x} = {y} }[/math]
8. Перейти к пункту 2
Последовательная сложность алгоритма
Предположим, что сложность одного вычисления фитнес-функции имеет сложность [math]\displaystyle{ F }[/math], процедура кроссинговера --- [math]\displaystyle{ D }[/math]; размер популяции для сокращения выкладок обозначим [math]\displaystyle{ P }[/math]. Рассчитаем сложность одной эпохи алгоритма:
Этап 2 является наиболее вычислительно трудоёмким и имеет сложность [math]\displaystyle{ PF }[/math];
Этап 3 имеет сложность [math]\displaystyle{ P \log P }[/math].
Этапы 4-5 имеют константную сложность.
Этап 6 имеет сложность [math]\displaystyle{ PD }[/math].
Этап 7 также имеет сложность [math]\displaystyle{ PD }[/math].
Для произвольной [math]\displaystyle{ F }[/math] в общем случае сложность алгоритма составляет [math]\displaystyle{ O(PF + P \log P + PD) }[/math], обычно выбор параметров таков, что вторым слагаемым можно пренебречь. Зачастую соотношение между [math]\displaystyle{ F }[/math] и [math]\displaystyle{ D }[/math] таково, что сложность по факту становится [math]\displaystyle{ O(PF) }[/math].
При этом в памяти необходимо хранить два массива из [math]\displaystyle{ P }[/math] объектов из пространства [math]\displaystyle{ \mathbb{X} }[/math]. В предположении, что его размерность совпадает со сложностью кроссинговера, это [math]\displaystyle{ 2PD }[/math] вещественных чисел.
Информационный граф
На рис.1 показана информационная структура типичного генетического поиска. Стоит отметить, что на рисунке p1 и p2 формально являются не индексами родителей, а их генотипами, т.е. с точки зрения данного графа процедура сортировки возвращает отсортированный список именно что объектов [math]\displaystyle{ {x} }[/math]; более частой реализацией является применение кроссинговера к особям с сэмплированными индексами, в таком случае формально требовалось бы соединить каждую из операций кроссинговера со всеми [math]\displaystyle{ x }[/math], получая таким образом на графе полносвязную структуру, являющуюся основным препятствием к распараллеливанию алгоритма.
Формально граф на рис.1 состоит из следующих элементов:
- для очередной популяции высчитываются значения фитнес-функции. Это происходит независимо для каждой особи, и может быть сделано параллельно.
- полученный набор значений подаётся на вход алгоритму сортировки [math]\displaystyle{ {x} }[/math] в качестве критерия сортировки.
- вычисляются генотипы p1, p2 среди случайных особей, оказавшихся в топ-[math]\displaystyle{ SelectionSize }[/math] по результатам сортировки
- после предыдущей операции к генотипам p1, p2 независимо для каждой особи применяется [math]\displaystyle{ Crossover }[/math]
- полученные значения становятся новыми особями популяции
Ресурс параллелизма алгоритма
На информационном графе на рис. 1 видно, что все вычисления фитнес-функции, самой трудоёмкой операции алгоритма, на одной эпохе можно распараллелить. Это позволяет в общем случае снизить стоимость одной эпохи с [math]\displaystyle{ O(PN) }[/math] до [math]\displaystyle{ O(N) }[/math], и при больших [math]\displaystyle{ N }[/math] эта сложность принципиально неулучшаема (на каждом шаге оптимизации функции, для которой мы умеем только считать значение в некоторой точке, не может быть ничего оптимальнее, чем сделать это один раз). При возможности неограниченно распараллеливать вычисление, одна эпоха генетического алгоритма начинает стоить всего один вызов функции [math]\displaystyle{ F }[/math], что фундаментально является существенным преимуществом алгоритма.
Информационный граф показывает, что также доступна для распараллеливания и операция кроссинговера. Однако, для этого требуется каждому процессу получить доступ к двум требуемым генотипам, находящимся у двух других процессов. В возникающей схеме взаимных обменов информации потенциальные затраты на организацию доступа и передачу данных могут оказаться выше проведения кроссинговера [math]\displaystyle{ P }[/math] раз на одном процессоре, однако такая альтернатива существует, и, особенно при нелинейной сложности кроссинговера, её стоит принимать во внимание.
Поскольку алгоритм эвристический, в оптимизационных целях был придуман ряд эвристик, направленных на увеличение потенциала распараллеливания:
- индексы родителей могут сэмплироваться так, чтобы заранее упростить процесс обмена сообщениями; в предельной идее, например, индексы родителей из топа-[math]\displaystyle{ SelectionSize }[/math] для каждой новой особи можно зафиксировать, чтобы точно указать на информационном графе, какие именно генотипы для какой операции кроссинговера используются.
- отчасти упрощает распараллеливание такое ответвление генетического поиска, как естественный генетический поиск, в целом являющимся Монте-Карло методом оценки невычислимого градиента.
Входные и выходные данные алгоритма
Входные данные: функция [math]\displaystyle{ f: \mathbb{X} \to \mathbb{R} }[/math]; [math]\displaystyle{ \mathbb{X} }[/math] должно иметь некоторое программное представление, например, определена некоторая инъекция [math]\displaystyle{ \mathbb{R}^d \to \mathbb{X} }[/math].
Выходные данные: субоптимальный [math]\displaystyle{ x \in \mathbb{X} }[/math]
Параметры:
- размер популяции (100-1000)
- количество особей для отбора (например, относительно объёма размера популяции; обычно 5-50%)
- операция кроссинговера [math]\displaystyle{ Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} }[/math]. Обычно это одна из типично используемых процедур: поэлементное среднее, какая-либо её стохастическая модификация, случайный выбор для каждого гена, от какого родителя взять значение.
- вероятность мутации одного гена; обычно 0,01 или меньше.
- критерий останова: например, достижение определённого результата или ограничение на количество эпох.
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
На суперкомпьютере "Ломоносов" была проведена экспериментальная оценка сильной масштабируемости для задачи квадратичной сложности от размерности данных (100) с объёмом популяции 1000 и количеством отбираемых особей 100. В качестве операции кроссинговера было взято поэлементное среднее, один ген мутировал (сэмплировался случайно из диапазона [math]\displaystyle{ [0, 1] }[/math]) с вероятностью 0.01. Для количества процессоров 1, 2 ... 128 было проведено по три замера времени; для 256 и 512 два замера. Результаты приведены на рис.2
Узким горлом алгоритма для распараллеливания является процедура сортировки и последующего сэмплирования индексов родителей на основе результатов этого процесса, а точнее, сопряжённая с этим передача данных. В версии, для которой был проведён эксперимент, один процесс отвечал за сортировку и последующий кроссинговер, после чего передавал генотипы другим процессам для вычисления значения функции в этих точках. Видно, что начиная с некоторого количества процессоров, где-то 64-128, затраты на передачу массивов длины [math]\displaystyle{ D=100 }[/math] от одного процесса остальным начали перекрывать выигрыш от увеличения числа процессоров. Поэтому потенциально такая реализация не является оптимальной.