Зачем нам нужен генетический алгоритм?

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

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

В таких случаях пригодятся эволюционные алгоритмы (EAs).

Введение в генетический алгоритм

Генетический алгоритм (ГА), предложенный Джоном Холландом в 1970 году, является одним из самых популярных советников. Он основан на теории Дарвина о «выживании сильнейшего». Он в основном используется для оптимизации наших проблем. В GA мы вносим случайные изменения в текущие решения с помощью Selection, Crossover и Mutation, чтобы создавать новые решения, пока не достигнем наилучшего решения.

Как это работает?

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

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

Теперь мы выбираем лучших людей из этой недавно созданной популяции в качестве родителей для нового поколения. Чем выше значение пригодности решения, тем больше шансов, что оно будет выбрано в качестве родительского, и плохие решения будут исключены. Эти отобранные особи проходят кроссовер, чтобы создать новое потомство. Спаривая высококлассных особей, мы можем рассчитывать на получение потомства лучше, чем их родители. Кстати, а вы знаете какой-нибудь другой алгоритм, который так элегантно использует секс ??? Прокомментируйте и дайте нам знать.

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

На диаграмме ниже представлен весь рабочий процесс GA.

Кодирование хромосомы

Хромосомы кодируются в основном 3 способами:

  • Двоичное кодирование: каждая хромосома представлена ​​набором двоичных цифр.
  • Кодирование перестановки: каждая хромосома представляет собой строку чисел, которая представляет число в последовательности. Он в основном используется для задач заказа, таких как задача коммивояжера.
  • Кодировка значения: здесь фактическое значение кодируется как есть.

Еще немного о…

Выбор

Мы отбираем лучших особей из предыдущей популяции для кроссовера. Это делается разными способами. Самые распространенные из них:

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

Кроссовер

Мы комбинируем генетический материал выбранной родительской хромосомы, чтобы произвести потомство. Необязательно, чтобы выбранная пара хромосом подверглась кроссоверу. Мы определяем вероятностный фактор, называемый скоростью кроссовера, который действует как порог. Этот фактор определяет, подвергнется ли пара хромосом кроссоверу или нет. Есть разные способы, которыми мы можем выполнить кроссовер. Например :

Единый кроссовер - в этом случае две особи создают одно потомство. Мы случайным образом выбираем индивидуума из двух для каждого гена потомства, чтобы внести свой вклад в одно и то же.

Кроссовер в одну точку - в этом случае две особи создают двух потомков. Мы определяем общую точку как для особей, так и для их потомков, по которой для первого потомства мы берем все левые гены первого родителя и все правые гены второго родителя, и наоборот, для второго потомства. Рисунок ниже дает представление о кроссовере в одной точке.

Мутация

Здесь решается проблема, о которой мы говорили вначале. Из-за мутации мы не зацикливаемся на локальном оптимуме, поскольку он вносит генетическое разнообразие в популяцию. При мутации у нас есть скорость мутации, аналогичная скорости кроссовера, которая определяет, подвергнется ли человек мутации или нет. Если человек выбран для мутации, мы случайным образом / равномерно меняем один / несколько (по мере необходимости) генов. Например, если наша хромосома закодирована в двоичном формате, мы меняем значение гена (если оно равно 0, мы меняем его на 1 или наоборот).

Спасибо за чтение этого. Следите за новостями о машинном обучении :)