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

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

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

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

Входные данные: функция [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]

Ссылки

http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf