Участник: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}$. Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы.

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)$