Введение

Подмножество эволюционных вычислений

В области вычислительного интеллекта (CI) эволюционный алгоритм (EA) является подмножеством эволюционных вычислений – обобщенным алгоритмом метаэвристической оптимизации, основанным на популяциях. EA использует механизмы, вдохновленные биологической эволюцией, такие как воспроизводство, мутация, рекомбинация и отбор. Кандидатные решения оптимизационной задачи выступают в роли индивидуумов в популяции, а функция пригодности (фитнес-функция) определяет качество этих решений (см. также функцию потерь). Эволюция популяции происходит в результате многократного применения указанных операторов. Эволюционные алгоритмы часто эффективно находят приближенные решения для задач различного типа, поскольку, в идеале, не делают никаких предположений об underlying ландшафте пригодности. Методы эволюционных алгоритмов, применяемые к моделированию биологической эволюции, как правило, ограничиваются изучением микроэволюционных процессов и разработкой моделей, основанных на клеточных процессах. В большинстве практических применений EA вычислительная сложность является существенным ограничением. Эта сложность, как правило, связана с вычислением значения функции пригодности. Приближение функции пригодности – одно из решений для преодоления этой трудности. Однако, даже относительно простые EA могут решать сложные задачи, поэтому не всегда существует прямая связь между сложностью алгоритма и сложностью решаемой проблемы. Эволюционные алгоритмы можно рассматривать как разновидность метода Монте-Карло.

Типы

Подобные методы отличаются генетическим представлением и другими деталями реализации, а также характером конкретной прикладной задачи. Генетический алгоритм – Это самый популярный тип эволюционных алгоритмов. Решение проблемы ищется в виде строк чисел (традиционно двоичных, хотя лучшие представления обычно отражают особенности решаемой задачи). Дифференциальная эволюция – Основана на векторных разностях и поэтому в первую очередь подходит для задач численной оптимизации. Коэволюционный алгоритм – Похож на генетические алгоритмы и стратегии эволюции, но созданные решения сравниваются на основе результатов их взаимодействия с другими решениями. Решения могут конкурировать или сотрудничать в процессе поиска. Коэволюционные алгоритмы часто используются в сценариях, где ландшафт пригодности динамичен, сложен или включает конкурентные взаимодействия. Нейроэволюция – Похожа на генетическое программирование, но геномы представляют собой искусственные нейронные сети, описывая структуру и веса соединений. Кодирование генома может быть прямым или косвенным. Система классификаторов обучения – Здесь решением является набор классификаторов (правил или условий). Мичиганская LCS эволюционирует на уровне отдельных классификаторов, в то время как питтсбургская LCS использует популяции наборов классификаторов. Изначально классификаторы были только двоичными, но теперь включают вещественные, нейронные сети или S-выражения. Пригодность обычно определяется с помощью обучения с подкреплением, основанного на силе или точности, либо подхода контролируемого обучения. Алгоритмы качества-разнообразия – Алгоритмы QD одновременно стремятся к высокому качеству и разнообразию решений. В отличие от традиционных алгоритмов оптимизации, которые сосредоточены исключительно на поиске наилучшего решения задачи, алгоритмы QD исследуют широкий спектр решений в пространстве задачи и сохраняют те, которые не только высокоэффективны, но и разнообразны и уникальны.

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

Следующие теоретические принципы применимы ко всем или почти всем советникам.

Нет теоремы бесплатного обеда

Теорема оптимизации "нет бесплатного обеда" утверждает, что все стратегии оптимизации одинаково эффективны, если рассматривать множество всех задач оптимизации. При том же условии, ни один эволюционный алгоритм не превосходит другой по своей сути. Это возможно лишь при ограничении множества всех задач. Именно это и происходит неизбежно на практике. Следовательно, для улучшения ЭА необходимо использовать знания о решаемой задаче в той или иной форме (например, путем выбора определенной интенсивности мутации или кодирования, адаптированного к задаче). Таким образом, при сравнении двух ЭА это ограничение подразумевается. Более того, ЭА может использовать специфические знания о задаче, например, не генерируя начальную популяцию случайным образом, а создавая часть особей с помощью эвристик или других процедур. Другой способ адаптации ЭА к конкретной области задач – включение подходящих эвристических методов, процедур локального поиска или других процедур, связанных с задачей, в процесс генерации потомства. Эта форма расширения ЭА также известна как меметический алгоритм. Оба этих подхода играют важную роль в практических приложениях, поскольку они могут ускорить процесс поиска и повысить его устойчивость.

Сближение

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

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

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

Виртуальные алфавиты

С помощью теории виртуальных алфавитов Дэвид Э. Голдберг показал в 1990 году, что при использовании представления с вещественными числами, эволюционный алгоритм (ЭА), использующий классические операторы рекомбинации (например, равномерный или n-точечный кроссовер), не может достичь определенных областей пространства поиска, в отличие от кодирования двоичными числами. Это приводит к рекомендации использовать для ЭА с вещественным представлением арифметические операторы для рекомбинации (например, арифметическое среднее или промежуточную рекомбинацию). При использовании подходящих операторов, вещественное представление оказывается более эффективным, чем двоичное, вопреки прежним представлениям.

Сравнение с биологическими процессами

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

Приложения

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

Примеры

В 2020 году Google заявил, что их AutoML Zero способен успешно заново открывать классические алгоритмы, такие как концепция нейронных сетей. Компьютерные симуляции Tierra и Avida пытаются моделировать динамику макроэволюции.