Руководство для начинающих по генетическим алгоритмам, а также немного больше…

«…Он также будет выпускать песни ваших любимых исполнителей, речи, которые вы произносили, когда учились в школе, и даже эту самую статью».

Когда я впервые прочитал о генетических алгоритмах, я был ошеломлен не меньше этой обезьяны. Генетические алгоритмы являются одними из самых интуитивно понятных методов оптимизации, поскольку они вдохновлены «Теорией эволюции» Чарльза Дарвина. Подобно тому, как самолет эволюционировал из птицы, а наш мозг вдохновил на создание популярной нейронной сети, я всегда поражаюсь, когда мы смотрим на природу и процессы, происходящие вокруг нас, как на основу для методов оптимизации. Благодаря биомимикрии многие из самых передовых и простых технологий, существующих сегодня, берут свое скромное начало в природе.

Теорема о бесконечных обезьянах

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

Пространства решений — и почему богосортировка работает

Алгоритм Bogosort — это (крайне неэффективный) алгоритм сортировки. Он использует метод проб и испытаний. Пошаговая процедура этого алгоритма выглядит следующим образом:

  1. Отсортированы ли элементы массива? Если да, верните массив.
  2. Случайным образом перемешайте массив. Вернитесь к шагу 1.

Вот программа python этого алгоритма:

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

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

«Выживает сильнейший» — естественный отбор и эволюция

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

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

Генетический алгоритм

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

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

  1. Кодирование проблемы
  2. Инициализировать родительское поколение
  3. Выберите членов из этого поколения, которые с большей вероятностью перейдут в следующее поколение.
  4. Скрестите родителей, чтобы получить детей
  5. Измените детей, чтобы улучшить разнообразие
  6. Выберите родителей и детей, которые выживут
  7. Переходите к шагу 3, пока не будет найдено оптимальное решение.

Попробуем изучить этот алгоритм на примере.

Оптимизируйте функцию f(x) = x³ + 9, где x находится в пределах [0, 63] и x принадлежит множеству целых чисел.

Кодирование проблемы

Для нашего алгоритма требуется пакет решений и метрика, чтобы определить, насколько хорош ответ. В качестве этой метрики будет выступать функция, которую нам нужно оптимизировать f(x). Начальная партия растворов всегда выбирается случайным образом.

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

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

Первое поколение инициализируется путем выбора случайных чисел в пространстве решений. Чтобы продемонстрировать алгоритм и дать равные шансы начальной популяции, значения выбираются из значительно меньшего подмножества. Если бы мы этого не сделали, мы могли бы получить инопланетянина (скажем, 52) в овечьей популяции ([1, 5, 12, 16…]), и алгоритм сходился бы очень быстро. После выбора чисел значения преобразуются в битовые строки.

Выбор

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

… где fᵢ — значение пригодности для значения iᵗʰ.

Выбор колеса рулетки прост. Представьте, что каждая секция колеса рулетки связана с членом населения. Чтобы дать выигрышному участнику больше шансов на выживание, каждый сектор колеса увеличивается или уменьшается пропорционально pᵢ. Программно нам не пришлось бы беспокоиться о моделировании колеса рулетки; NumPy имеет возможность установить вероятность выбора значения из заданного массива.

Самые зоркие среди вас уже заметили ограничение выбора колеса рулетки. Этот процесс выбора не будет хорошо сочетаться с отрицательными значениями пригодности. Мы бы пока умалчивали об этом, ограничив область определения x таким образом, что f(x) ≥ 0. Чтобы решить эту проблему, используйте другой выбор алгоритм, известный как турнирный отбор, при котором для турнира отбираются K случайных кандидатов, и кандидат с наибольшим значением проходит в следующий раунд. Этот процесс повторяется до тех пор, пока не останется только один член.

кроссовер

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

  1. Кроссовер по одной точке.В качестве точки кроссовера выбирается случайный индекс из массива. Все биты от точки кроссовера до конца переставляются между двумя родителями.
  2. Равномерное пересечение: каждый индекс из массива рассматривается для замены.

Мутация

Каждый ребенок из нового поколения модифицируется (мутируется) для обеспечения большего разнообразия. Эту мутацию можно применить ко всем битам или к нескольким случайным битам.

Эволюция

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

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

Твоя очередь узнать!

Сколько поколений требуется, чтобы найти оптимальное решение?

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

Что произойдет, если мутаций будет слишком мало? Слишком часто? И пока мы в этом, нужна ли вообще мутация? А кроссовер? Будет ли достаточно одной из этих генетических операций?

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

Дополнительный

  1. Если вы все еще считаете шекспировскую Обезьяну нереальной, вы можете заглянуть в Вавилонскую библиотеку и на эту страницу с веб-сайта. Держите глаза открытыми👀.
  2. В Интернете есть отличное руководство, в котором гораздо более подробно рассматриваются другие типы методов селекции, скрещивания и мутации. Я настоятельно рекомендую пройти его, если вам интересно узнать больше.
  3. Программу на Python для создания графика для расчета времени, затрачиваемого алгоритмом Bogosort на количество элементов в массиве, можно найти здесь.

Присоединяйтесь к FAUN: Сайт💻|Подкаст🎙️|Twitter🐦|Facebook👥 |Instagram📷|Группа Facebook🗣️|Группа Linkedin💬| Slack 📱|Cloud Native Новости📰|Дополнительно.

Если этот пост был полезен, пожалуйста, несколько раз нажмите кнопку аплодисментов 👏 ниже, чтобы выразить свою поддержку автору 👇