Что такое генетические алгоритмы

Генетический алгоритм — это класс эволюционных алгоритмов поиска. Идея генетических алгоритмов основана на эволюционной теории Чарльза Дарвина. Этот алгоритм симулирует процесс естественного отбора, когда более сильные особи из популяции переживают более слабых и производят следующее поколение особей. В глубоком обучении генетические алгоритмы применяются для задачи оптимизации параметров нейросети.

Естественный отбор

Процесс естественного отбора начинается с выбора сильных особей из популяции. Их потомство наследует характеристики родителей и является частью следующего поколения особей. Если оба родителя сильные, то их потомство будет сильнее родителей.

Это итеративный процесс и завершается, когда найдены наиболее сильные особи. Эта идея применяется для задачи поиска. Рассматривается набор решений для проблемы и отбирается набор лучших из них.

5 шагов генетического алгоритма

Процесс обучения генетического алгоритма делится на 5 этапов:

1. Начальная популяция
2. Функция силы особи
3. Отбор наиболее сильных решений
4. Обмен характеристиками между двумя особями
5. Мутация
6. Новая итерация с созданием начальной популяции

Процесс начинается с набора особей, который называется популяцией. Каждая особь — это решение проблемы, которая была поставлена. Особь характеризуется набором параметров (переменных), которые называют генами. Гены объединены в одну строку и формируют хромосому — решение задачи.

В генетическом алгоритме набор генов особи представлен в виде бинарной строки. Закодированная комбинация генов называется хромосомой.

Популяция, хромосомы и гены

Функция силы

Функция силы определяет, насколько сильна отдельная особь. Сила определяется как способность особи конкурировать с остальными особями по заданной метрике. Функция присваивает каждой особи уровень силы. Вероятность того, что особь будет выбрана для произведения следующей популяции, основывается на уровне силы особи.

Отбор

Идея отбора заключается в том, чтобы отобрать наиболее сильных особей и передать их гены следующему поколению особей. N пар особей (родители) отбирается на основании их силы.

Скрещивание

Скрещивание — это основная часть генетического алгоритма. Для каждой пары родителей. Рандомно выбирается точка в бинарной строке хромосомы, до которой особи обмениваются генами. После этого модифицированные особи называются потомством.

Точка скрещивания

Потомство создается через процесс обмена генами родителей до случайно заданной позиции в строке. Ниже можно увидеть, как родители обмениваются генами, когда точка скрещивания = 3.

После обмена генами между родителями потомство добавляется в новую популяцию.

Мутация

Какая-то часть генов будет маловероятной. Чтобы поддерживать разнообразие популяции, отдельно прописывается процесс мутации новых особей.

Завершение алгоритма

Алгоритм завершает работу, когда популяция сошлась, то есть не производит потомство, которое значительно отличается от предыдущего поколения. Когда алгоритм сошелся, на выходе получается набор оптимальных решений заданной проблемы.

Псевдокод процесса обучения генетического алгоритма:

START  Generate the initial population  Compute fitness  REPEAT      Selection      Crossover      Mutation      Compute fitness  UNTIL population has converged  STOP

Генетические алгоритмы в глубоком обучении

В глубоком обучении с помощью генетических алгоритмов оптимизируются параметры нейросети. В качестве особей популяции выступают сами параметры. Введение в state-of-the-art использование генетических алгоритмов для задач глубокого обучения находится по ссылке.