Участник:Sergey Ivanov/Генетические алгоритмы: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 22: Строка 22:
  
 
Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>
 
Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>
 
== Ссылки ==
 
  
 
= Литература =
 
= Литература =
 
<references />
 
<references />

Версия 18:26, 22 октября 2017

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

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

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

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

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

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

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

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

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

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

3 Литература