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

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

Генетический алгоритм - универсальный субоптимальный метод оптимизации $F(x) \rightarrow \mathop{max}_x$. Универсальность проявляется в его пригодности к задачам с произвольными функциями $F\colon \mathbb{X} \to \mathbb{R}$ и нетривиальной природой пространства аргументов $\mathbb{X}$.

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

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

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

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

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

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

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

До выполнения критерия останова:

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

Одна итерация алгоритма называется эпохой. На выход алгоритм подаётся $\mathop{argmax}_{x \in Population_{last}} F(x)$

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

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

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