Участник:Sergey Ivanov/Генетические алгоритмы: различия между версиями
| Строка 3: | Строка 3: | ||
Генетический алгоритм - универсальный<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>. | Генетический алгоритм - универсальный<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>. Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref>. | + | От функции <math>F</math> требуется только возможность вычислять её значение в произвольной точке. От пространства аргументов требуется наличие т.н. функции кроссинговера, т.е. функции <math> Crossover\colon \mathbb{X}\times \mathbb{X}\to \mathbb{X} </math>. Обычно для этого объекты пространства представляются в виде набора генов, т.е. по сути вещественных или бинарных векторов фиксированной (или даже меняющийся по ходу оптимизации<ref>http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf</ref>) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов <math>g_1, g_2</math> результатом обычно полагается <math>\alpha g_1 + (1 - \alpha) g_2</math>, где <math>\alpha \sim Unifrom(0, 1)</math> |
| + | |||
| + | Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<ref>http://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1174&context=cs_techreports</ref> и задачи обучения с подкреплением<ref>https://www.jair.org/media/613/live-613-1809-jair.pdf</ref>. | ||
== Математическое описание алгоритма == | == Математическое описание алгоритма == | ||
| Строка 22: | Строка 24: | ||
Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math> | Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math> | ||
| + | |||
| + | == Возможные вариации == | ||
| + | |||
| + | Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций: | ||
| + | |||
| + | * битвы на выживание: на этапе отбора брать две случайные особи и устроить между ними "сражение", в котором один из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>. | ||
| + | * острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними. | ||
| + | * старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог. | ||
= Литература = | = Литература = | ||
<references /> | <references /> | ||
Версия 19:12, 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]) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов g_1, g_2 результатом обычно полагается \alpha g_1 + (1 - \alpha) g_2, где \alpha \sim Unifrom(0, 1)
Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения[3] и задачи обучения с подкреплением[4].
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)
3 Возможные вариации
Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:
- битвы на выживание: на этапе отбора брать две случайные особи и устроить между ними "сражение", в котором один из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции F.
- острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
- старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.
