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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 10: Строка 10:
  
 
Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<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>.
 
Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения<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>.
 +
 +
Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что ''генотипом'' является некоторая точка <math>x</math>, а ''фенотипом'' - значение в данной точке функции <math>F</math>. Основная идея алгоритма заключается в том, чтобы в рамках некоторой ''популяции'', т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется ''эпохой''. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Строка 27: Строка 29:
 
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>
 
* при наличии мутаций к каждой особи с вероятностью <math>\epsilon</math> применить функцию <math>Mutation</math>
  
Одна итерация алгоритма называется ''эпохой''. На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>
+
На выход алгоритм подаётся <math>\mathop{argmax}_{x \in Population_{last}} F(x)</math>
  
 
=== Возможные вариации ===
 
=== Возможные вариации ===
Строка 33: Строка 35:
 
Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:
 
Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:
  
* битвы на выживание: на этапе отбора брать две случайные особи и устроить между ними "сражение", в котором один из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
+
* битвы на выживание: на этапе отбора выбирать две случайные особи и устроить между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции <math>F</math>.
 
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
 
* острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
 
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.
 
* старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

Версия 23:47, 3 ноября 2017

Автор текущей версии статьи: Иванов Сергей, гр. 417, 2017-ый год

1 Структура алгоритма

1.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]) размерности. Функция кроссинговера обычно полагается независимой для каждого гена (то есть для каждого элемента последовательности): для бинарных генов с вероятностью 1/2 берётся ген первого аргумента, иначе второго; для вещественных генов [math]g_1, g_2[/math] результатом обычно полагается [math]\alpha g_1 + (1 - \alpha) g_2[/math], где [math]\alpha \sim Unifrom(0, 1)[/math]

Такие слабые требования позволяют алгоритму работать в случаях, где традиционные методы непрерывной оптимизации неприменимы, таких как отбор признаков в задачах машинного обучения[3] и задачи обучения с подкреплением[4].

Канонически использующаяся для описания алгоритма терминология взята из теории эволюции. Под "особью" в биологии понимают совокупность фенотипа и генотипа живого организма; с математической точки зрения, в рамках задачи оптимизации, можно положить, что генотипом является некоторая точка [math]x[/math], а фенотипом - значение в данной точке функции [math]F[/math]. Основная идея алгоритма заключается в том, чтобы в рамках некоторой популяции, т.е. набора особей, отобрать лучшие по фенотипу особи, а затем построить новую популяцию на основе только лучших генотипов. Одна такая итерация называется эпохой. Соответственно, два основных параметра алгоритма - размер популяции, и число отбираемых ("выживающих") особей на каждой итерации.

1.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]

1.3 Возможные вариации

Стоит отдельно отметить, что алгоритм допускает бесчисленное количество вариаций, и редко применяется в исходной форме. Модификациям можно подвергнуть практически любой этап алгоритма без существенного изменения идеи процесса. Большинство модификаций призвано бороться с главным недостатком алгоритма - отсутствием вариативности, вызванной похожестью результата операции кроссинговера на свои операнды. Ниже перечислены некоторые из возможных модификаций:

  • битвы на выживание: на этапе отбора выбирать две случайные особи и устроить между ними "сражение", в котором одна из них "погибает" (удаляется из популяции). Сражение может проходить по принципу "побеждает сильнейший", или стохастически, с вероятностью победы пропорциональной силе особи, где сила - значение функции [math]F[/math].
  • острова: запускать генетический поиск для нескольких независимо сэмплированных популяций и допускать редкие обмены генотипами между ними. Нестрого говоря, это позволяет найти несколько локальных максимумов, и проверить, нет ли лучших вариантов между ними.
  • старение: оставлять топ-k особей популяции неизменными для следующего поколения; удалять их, если их "возраст" превысил определённый порог.

2 Литература