Вступление

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

  • Случайные мутации
  • Давление отбора

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

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

  • Схема представления (например, генотип, фенотип и т. Д.)
  • Операторы спаривания (например, кроссовер)
  • Операторы мутации (например, переворачивание битов)
  • Показатель пригодности
  • Стратегия выбора (например, выбор турнира)
  • Стратегия эволюции (например, мю, лямбда)

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

Эволюционная стратегия (ES)

Как я уже упоминал, все эволюционные алгоритмы разделяют большинство вышеупомянутых компонентов, но отличаются друг от друга деталями. Для ES схема представлений - это в основном фенотип, то есть индивидуумы (или решения) явно представлены в виде векторов чисел. У каждого человека будет сопутствующий вектор, называемый стратегией, который представляет собой просто вектор, контролирующий его мутацию. В ES используются разные операторы скрещивания, но мы будем использовать смешивание, которое в основном представляет собой форму линейной комбинации между скрещенными родителями. Оператор мутации, который мы будем использовать, является логнормальным, который, как и все операторы мутации в ES, зависит от упомянутого выше вектора стратегии для изменения различных значений в векторе представления человека. Стратегия отбора - это турнирный отбор, в котором выполняется несколько случайных выборов из подмножества индивидуумов, и каждый раз выбирается лучший индивидуум. Функция приспособленности - это единственная часть любого эволюционного алгоритма, которую необходимо делегировать пользователю для определения, то есть пользователь предоставит некоторую функцию, которая будет назначать приспособленность каждому человеку в популяции на основе подходящей меры для решения рассматриваемой проблемы. Эволюционная стратегия контролирует размер популяции, и здесь я буду использовать (mu, lambda) _pronounced 'mu comma lambda'_, где mu и lambda - положительные целые числа, а mu обозначает размер популяции родителей, а лямбда обозначает размер рожденное потомство. В этой стратегии стратегия отбора (то есть турнирный отбор в этом примере) применяется только к потомкам.

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

DEAP

DEAP - это Python-фреймворк для реализации эволюционных алгоритмов. Он обеспечивает организованный упрощенный способ координации различных компонентов, необходимых для любого эволюционного алгоритма. Для любого компонента DEAP предоставляет большинство общих вариантов в виде предопределенных компонентов, обеспечивая при этом достаточную гибкость для определения ваших собственных вариантов в случае, если обычных компонентов недостаточно для вашей проблемы.

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

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

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

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

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

Давайте импортируем основные подпакеты, которые нам понадобятся для нашей реализации,

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

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

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

Вторая строка похожа, но определяет человека. Начиная с четвертого аргумента, любые предоставленные вами аргументы будут добавлены как поля или атрибуты к определенному типу данных. Для человека мы определяем необходимое, требуемое DEAP, а именно приспособленность. DEAP будет искать его, когда захочет обновить значение пригодности или прочитать его. Вы можете видеть, что мы передаем ему наш определенный FitnessMin. Атрибут стратегии необходим для алгоритма ES, поскольку он зависит от вектора стратегии для выполнения мутаций. Мы инициализируем его как «Нет», так как позже мы сами его заполним. Вы можете передать любые другие атрибуты, которые вам нужны, в функцию create, и они будут добавлены к вашему типу данных. Третья строка определяет тип данных стратегии.

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

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

Второе использование определяет еще одну важную функцию, называемую «население», которую мы будем использовать для генерации населения. Мы передаем предопределенную функцию DEAP, то есть initRepeat. Аргументы после initRepeat, опять же, являются аргументами, которые будут переданы ему по умолчанию при вызове. Когда мы вызываем функцию «популяция» из нашего набора инструментов, вызывается initRepeat, который инициализирует набор индивидов, используя свой второй аргумент, который является просто нашей предопределенной индивидуальной функцией генерации, и помещает их в контейнер типа « list ', который является его первым аргументом, и верните его.

Теперь нам нужно зарегистрировать функцию оценки, которую DEAP будет использовать для определения пригодности для разных людей. Здесь вступает в игру наша предполагаемая полиномиальная модель:

Функция «pred» принимает индивидуума и точку данных и возвращает выходные данные модели путем вычисления полинома 4-й степени. Вы можете видеть, что индивидуальные параметры от 1 до 4 используются как коэффициенты для x с разными показателями, а пятый используется как смещение / пересечение, то есть термин без x.

Функция «приспособленность» вычисляет среднеквадратичную ошибку (MSE) между фактическим выходом и выходом нашей модели (который рассчитывается с использованием предыдущей функции «pred»). У более подходящих индивидуумов MSE будет меньше, и это причина того, что наша определенная физическая форма вначале получила отрицательный вес. Мы заинтересованы в уменьшении размера MSE.

Наконец, мы регистрируем нашу фитнес-функцию в нашем наборе инструментов с помощью специального ключевого слова «оценка», чтобы DEAP мог найти ее при вычислении фитнеса.

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

Операторы mate, mutate и select являются операторами кроссовера, мутации и отбора соответственно. Для всех из них мы используем предопределенные компоненты DEAP и передаем им необходимые аргументы.

Пока это большинство необходимых компонентов для работы ЭС. Очень удобный дополнительный инструмент, предоставляемый DEAP, - это инструмент «Статистика», который мы можем настроить для получения некоторых статистических данных об эволюционном алгоритме после каждого поколения,

Когда мы инициализируем нашу статистику, мы предоставляем в конструкторе определение функции, которая будет принимать человека при вызове DEAP, и мы должны вернуть атрибут человека, к которому мы хотим применить статистические операторы. Зарегистрированные имена функций будут использоваться в качестве метки для соответствующей статистики, например {‘avg’: ‹вывод функции np.mean›}.

Еще один удобный инструмент - «Зал славы», который мы можем настроить, и DEAP заполнит его k лучшими людьми в каждом поколении,

«1» означает, что он будет заполнен только лучшим человеком.

Теперь мы готовы запустить ES и позволить ему творить чудеса за нас,

Первая строка просто инициализирует новую популяцию, которой в качестве размера передается наше значение mu, поскольку мы собираемся использовать алгоритм (mu, lambda или MuCommaLambda), описанный ранее. Вторая строка запускает ES для одного поколения (ngen = 1) с использованием упомянутого алгоритма, передавая второй необходимый параметр lambda. Вы можете видеть, что мы также передали определенный набор инструментов, который содержит все наши настроенные функции и операторы, нашу статистику и зал славы. Ниже представлена ​​визуализация пробега 100 поколений.

использованная литература

  • Https://deap.readthedocs.io/en/master/
  • Бек Т., Фогель Д. Б. и Михалевич З. (ред.). (2018). Эволюционные вычисления 1: основные алгоритмы и операторы. CRC Press.