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

PS-Автоматизированное машинное обучение не заменяет специалиста по данным (по крайней мере, пока), но оно может помочь вам быстрее находить хорошие модели. TPOT позиционирует себя как ваш помощник по науке о данных.

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

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

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

Некоторые важные термины

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

Население — это подмножество всех возможных решений данной проблемы.

Хромосомы — хромосома — это одно из таких решений данной проблемы.

Ген — ген — это положение одного элемента хромосомы.

Функция пригодности. Просто определенная функция пригодности — это функция, которая принимает решение в качестве входных данных и выдает пригодность решения в качестве выходных данных. В некоторых случаях фитнес-функция и целевая функция могут быть одинаковыми, а в других они могут различаться в зависимости от проблемы.

Генетические операторы — изменяют генетический состав потомства. К ним относятся кроссовер, мутация, отбор выживших и др.

Кроссоверы. Оператор кроссовера аналогичен репродукции и биологическому кроссоверу. При этом выбирается более одного родителя, и одно или несколько потомков производятся с использованием генетического материала родителей. Кроссовер обычно применяется в ГА с высокой вероятностью — pc .

Мутация. Проще говоря, мутацию можно определить как небольшое случайное изменение хромосомы для получения нового решения. Он используется для поддержания и внесения разнообразия в генетическую популяцию и обычно применяется с низкой вероятностью — pm. Если вероятность очень высока, ГА сводится к случайному поиску.

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

Теперь, когда мы знаем основную терминологию, давайте посмотрим, как на самом деле работает ГА.

Как работает генетический алгоритм?

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

Обобщенный псевдокод для GA объясняется в следующей программе:

GA():
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best

Условие завершения генетического алгоритма важно для определения момента окончания запуска ГА.

Обычно мы сохраняем одно из следующих условий прекращения —

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

Теперь, когда у нас есть понимание того, как работает генетический алгоритм, давайте посмотрим, как он реализован в алгоритме TPOT.

Инструмент оптимизации конвейера на основе дерева (TPOT)

Инструмент оптимизации конвейера на основе дерева (TPOT), используемый в качестве примитивов генетического программирования (GP), конвейеры на основе дерева, используемые для объединения примитивов в рабочие конвейеры машинного обучения, и алгоритм GP, используемый для развития упомянутых конвейеров на основе дерева.

Таким образом, TPOT помогает нам найти хороший алгоритм машинного обучения.

TPOT — это проект с открытым исходным кодом на GitHub, а базовый код Python можно найти по адресу https://github.com/rhiever/tpot.

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

Структуру TPOT можно пояснить на следующем рисунке.

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

Генетический алгоритм TPOT следует стандартному процессу, который мы уже видели при изучении GA. Каждый из 20 лучших выбранных конвейеров производит пять копий (т.е. потомков) в популяцию следующего поколения, 5% этих потомков скрещиваются с другим потомством, используя один- точечный кроссовер, затем 90% оставшихся незатронутых потомков случайным образом заменяются точечной, вставочной или усадочной мутацией (вероятность каждой из них составляет 1/3).

Запуск TPOT на больших наборах данных займет некоторое время, но важно понимать, почему. При настройках TPOT по умолчанию (100 поколений с размером популяции 100) перед завершением TPOT оценит 10 000 конфигураций конвейера. Чтобы представить это число в контексте, подумайте о поиске по сетке из 10 000 комбинаций гиперпараметров для алгоритма машинного обучения и о том, сколько времени займет этот поиск по сетке. Это 10 000 конфигураций моделей для оценки с 10-кратной перекрестной проверкой, что означает, что примерно 100 000 моделей подбираются и оцениваются на обучающих данных за один поиск в сетке.

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