Участник:Sergey Ivanov/Генетические алгоритмы: различия между версиями
(→Ссылки) |
|||
| Строка 1: | Строка 1: | ||
== Описание алгоритма == | == Описание алгоритма == | ||
| − | Генетический алгоритм - универсальный субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>. | + | Генетический алгоритм - универсальный<ref>http://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf</ref> субоптимальный метод оптимизации <math>F(x) \rightarrow \mathop{max}_x</math>. Универсальность проявляется в его пригодности к задачам с произвольными функциями <math>F\colon \mathbb{X} \to \mathbb{R} </math> и нетривиальной природой пространства аргументов <math>\mathbb{X}</math>. |
| − | От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы. | + | От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref>. |
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
Версия 18:24, 22 октября 2017
1 Описание алгоритма
Генетический алгоритм - универсальный[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].
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)
