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

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

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

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

Генетический алгоритм - универсальный субоптимальный метод оптимизации [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]. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 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]

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения и задачи обучения с подкреплением.

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что генотипом является некоторая точка [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 особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.