Участник:Sergey Ivanov/Генетические алгоритмы
Описание алгоритма
Генетический алгоритм - универсальный[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].
Математическое описание алгоритма
Входные данные: функция [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]