Эволюционные алгоритмы

Эволюционные алгоритмы преимущественно применяются для оптимизации и поиска. К конкретным задачам, решаемым посредством ЭА, относятся: проектирование сенсорных сетей, анализ фондовых рынков, предсказание структуры РНК^[8], задачи планирования расписаний^[9], оптимизация конструирования^[10] (например, как в случае оптимизации спутниковой антенны на фото выше), или планирование траектории робота^[11]. ЭА могут найти приемлемые решения даже для задач с неполным знанием о свойствах предметной области, благодаря их сходству с естественными эволюционными процессами.

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

Аналогично биологической эволюции, в ЭА индивиды представлены геномом, хранящим признаки потенциальных решений. Созданные с помощью генетических операторов особи называются потомками или детьми, повторение шага называется поколением. Более точные определения можно найти в стандарте VDI/VDE 3550^[12].

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

Введённые для упрощения различия между природой и эволюционными алгоритмами ограничивают возможности применения ЭА к биологическим вопросам: результаты не всегда переносятся на реальную природу.

Хотя фундаментальные принципы ЭА остаются неизменными, с середины 2010-х годов область получила значительное развитие за счёт глубокой интеграции с машинным обучением. Это привело к активному развитию нейроэволюции — подхода, в котором ЭА используются для оптимизации архитектуры, гиперпараметров и правил обучения нейронных сетей. Появилось и новое мета-направление «Обучение для эволюционных вычислений» (англ. Learning for Evolutionary Computation, L4EC), где методы машинного обучения применяются для автоматического проектирования и улучшения самих эволюционных алгоритмов^[13].

Базовый процесс эволюционных алгоритмов состоит, как правило, из инициализации и генерационного цикла, выполняющегося до наступления критерия завершения^[14].^[15][16] Пример псевдокода (аналогично Krasnogor^[17]):

Псевдокод элитарного ЭА с половым размножением:

   Инициализация: t = 0 // счётчик поколений
                    Сгенерировать случайную стартовую популяцию P_t;
                    Вычислить значения фитнес-функции f(p) для всех p ∈ P_t;
   пока не выполнены критерии остановки
       Отбор родителей: выбрать по f(p) подмножество из P_t, сохранить как M_t;
       Потомки: рекомбинировать и мутировать особей p ∈ M_t, сохранить результат в M'_t;
       Оценка: вычислить f(p') для всех p' ∈ M'_t;
       Следующее поколение: сформировать P_{t+1} по фитнесу из P_t и M'_t;
       t := t + 1
   конец цикла
   Результат: вернуть лучшего индивида p ∈ P_t

На стадии инициализации особи генерируются случайно для обеспечения разнообразия^[18]. Однако иногда часть стартовой популяции формируют с помощью (мета)геристик или на основе решений схожих задач.

Отбор родителей обычно происходит по значению фитнес-функции и определяет стратегию поиска — существуют разные способы «селекции»: пропорционально, «турнирно» или по рангу^[19].^[20]

Потомки получаются путём рекомбинации и последующей мутации, что соответствует половому размножению в природе^[21]. В случае бесполого размножения создаётся мутировавшая копия одной особи.

При оценке каждому ребёнку назначается значение фитнес-функции, определяющее вероятность воспроизводства — это и есть реализация «естественного отбора»^[22].

Следующее поколение формируется либо из лучших родителей и потомков (стратегия «плюс»), либо только из детей (стратегия «запятая»)^[23]. Первый подход называется элитарным^[24].

В качестве критериев остановки используют число поколений, время или достижение определённого качества решения^[25].

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

Мутация и рекомбинация — ключевые поисковые операторы ЭА, обеспечивающие исследование пространства решений. Селекция придаёт поиску направленность, способствуя достижению глобального или хотя бы локального оптимума. Мутация может открывать новые районы пространства решений, рекомбинация — совмещать удачные «строительные блоки» решений. Эффективность этих операторов зависит от свойств ландшафта фитнес-функции^[26].

Конкретный выбор компонентов определяет поведение ЭА относительно сходимости, требуемых ресурсов и эффективности освоения пространства решений^[27]. Важно, чтобы операторы были скоординированы с конкретным представлением решений^[28].

Хотя эти фундаментальные компоненты остаются основой, с середины 2010-х годов появились новые концепции, расширяющие классический подход. К ним относятся алгоритмы качественного разнообразия (англ. Quality-Diversity, QD), цель которых — найти не одно оптимальное решение, а широкий набор разнообразных и одновременно высокопроизводительных решений. Развитие параллельных вычислений на специализированном оборудовании привело к появлению матрично-дружественных генетических алгоритмов (англ. Matrix-friendly Genetic Algorithm, MGA), в которых популяция представляется в виде матрицы, а эволюционные операторы выполняются через матричные операции^[29]. Кроме того, сформировалось направление «Обучение для эволюционных вычислений» (англ. Learning for Evolutionary Computation, L4EC), где методы машинного обучения применяются для автоматического проектирования и улучшения самих компонентов ЭА, таких как генетические операторы.

Теорема «обеда не бывает» утверждает, что если рассматривать все возможные задачи оптимизации, ни одна стратегия не превосходит другую: никакой эволюционный алгоритм не может быть принципиально лучше другого для произвольной задачи. Поэтому на практике алгоритмы используют частично известную информацию о конкретной задаче (например, тип мутаций)^[30]. В частности, базовая популяция может содержать не только случайные, но и эвристически построенные особи (см. меметический алгоритм)^[31].

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

Тем не менее, теорема не определяет скорость сходимости, а элитарные схемы подвержены риску преждевременной сходимости; для её уменьшения используют специальные популяционные модели^[32].

Схематическая теорема Джона Холланда объясняет успех классических генетических алгоритмов: короткие образцы битов с высокой фитнес-функцией быстро размножаются в популяции. Практическое значение этой теоремы для ЭА с небинарным представлением решений остаётся предметом дискуссии^[33].

Дэвид Голдберг (1990) показал, что при вещественных репрезентациях и традиционных бинарных операторах определённые участки пространства решений недостижимы^[34]. Для вещественных кодировок нужны арифметические операторы рекомбинации (ср. арифметическое среднее, интермедиарная рекомбинация).

Эволюционные алгоритмы широко применяются в промышленности^[35], технике^[36][37], робототехнике, сельском хозяйстве^[38], научных исследованиях и творческой деятельности (эволюционное искусство). Начиная с середины 2010-х годов, сфера применения ЭА значительно расширилась благодаря их глубокой интеграции с машинным обучением. Ключевыми современными направлениями стали нейроэволюция (оптимизация нейронных сетей)^[39], автоматическое машинное обучение (AutoML) для подбора архитектур и гиперпараметров моделей^[40], разработка новых лекарств и молекулярный дизайн^[41], а также генерация синтетических данных для обучения других моделей искусственного интеллекта^[42]. Кроме того, ЭА используются для создания самосовершенствующихся систем, способных автоматически находить и оптимизировать новые алгоритмы^[43]. Существуют специальные публикации для новичков в этой области^[44].

Эволюционные алгоритмы применяются для верификации, оптимизации прототипов, ускорения микропроцессоров и проектирования сетей связи^[45]. В финансах ЭА используются для анализа бирж, моделирования рынков и оптимизации инвестиционных портфелей, например, при решении задачи Марковица^[46][47].

В промышленности и логистике ЭА применяются для решения сложных задач оптимизации. К ним относятся управление режимами работы электроэнергетических сетей, оптимизация цепочек поставок и производственных процессов^[48], а также решение многокритериальных транспортных задач^[49].

Одним из ключевых направлений в современной технике является применение ЭА в области искусственного интеллекта. В системах автоматического машинного обучения (AutoML) они используются для автоматического подбора архитектур моделей, выбора признаков и настройки гиперпараметров, что ускоряет внедрение ИИ-решений в финансах и здравоохранении^[50]. Прорывным направлением стало автоматизированное проектирование алгоритмов (англ. AI-Driven Research for Systems, ADRS), где эволюционные подходы в тандеме с большими языковыми моделями используются для создания и оптимизации новых, более эффективных алгоритмов. Например, системе OpenEvolve удалось в 146 раз ускорить алгоритм балансировки нагрузки для LLM, найдя решение, которое ранее не было обнаружено человеком.

В молекулярной биологии и биоинформатике ЭА применяют для анализа последовательностей ДНК, выравнивания, построения филогенетических деревьев, предсказания структуры белков и анализа данных^[51]. С 2020-х годов это направление получило значительное развитие: эволюционные методы активно используются для ускорения разработки новых лекарств и в молекулярном дизайне^[52]. Генеративный ИИ, включая ЭА, применяется для проектирования новых молекул и белков с заданными свойствами, что кардинально меняет подходы в фармацевтике.

Эволюционные алгоритмы являются ключевым компонентом в исследованиях искусственного интеллекта. Они применяются для построения и оптимизации искусственных нейронных сетей (см. NEAT), а также в рамках автоматического машинного обучения (AutoML) для подбора архитектур и гиперпараметров моделей. Новым направлением стало эволюционное самообучение (англ. Evolutionary Self-Supervised Learning), автоматизирующее проектирование нейронных сетей и снижающее зависимость от размеченных данных^[53]. Кроме того, генетическое программирование всё чаще используется для создания интерпретируемых моделей в рамках объяснимого ИИ (XAI)^[54].

Одним из прорывных направлений исследований стало создание самосовершенствующихся и самоадаптирующихся систем. Подход «AI-Driven Research for Systems» (ADRS) использует ЭА в тандеме с большими языковыми моделями для автоматического создания и оптимизации новых, более эффективных алгоритмов. Развиваются и технологии самоадаптации в реальном времени, вдохновлённые биологическими системами^[55]. Актуальность этого направления подтверждается проведением специализированных научных мероприятий, таких как воркшоп EvoSelf^[56].

К другим перспективным областям исследований относятся квантово-вдохновлённые эволюционные алгоритмы (англ. Quantum-inspired Evolutionary Algorithms, QEA), использующие принципы квантовых вычислений для решения сложных комбинаторных задач^[57], а также моделирование социальных и экономических систем.

С помощью ЭА можно создавать сложные структуры или музыкальные последовательности, оцениваемые по эстетическому критерию (часто с участием человека для выбора «красивых» решений).

Предпосылки для анализа машинного обучения с точки зрения эволюции сформулировал ещё Алан Тьюринг. Ранние работы по моделированию эволюционных процессов в информатике принадлежат Нильсу Барричелли. В 1956 году Джордж Фридман предложил аппарат для проектирования схем на основе эволюционного отбора, но его не построили. В 1960-х годах Джордж Бокс внедрил «эволюционную оптимизацию» в промышленности, а в Германии и США параллельно зародились два классических направления: эволюционные стратегии (Инго Рехенберг, Ханс-Пауль Швефель)^[58] и генетические алгоритмы (Джон Холланд).

1980-е годы стали периодом, когда эволюционные алгоритмы превратились из теоретических концепций в полноценную область исследований^[59]. Ключевым событием стала первая Международная конференция по генетическим алгоритмам (ICGA), организованная Джоном Грефенстеттом в 1985 году^[60]. В 1989 году ученик Холланда Дэвид Голдберг опубликовал книгу «Генетические алгоритмы в поиске, оптимизации и машинном обучении», ставшую настольной для тысяч исследователей^[61]. В это же десятилетие началось активное применение ГА к NP-трудным задачам, таким как задача коммивояжёра^[62], и появились первые коммерческие продукты, например, Evolver (1989)^[60]. Параллельно получили развитие и другие направления: эволюционное программирование было расширено для решения задач с вещественными числами^[63], а эволюционные стратегии были формализованы в книге Ханса-Пауля Швефеля (1981), где была представлена идея самоадаптации параметров мутации^[64].

В 1990-е годы область пережила бурный рост, были заложены основы академической инфраструктуры и появились новые парадигмы. Важнейшей вехой стало появление генетического программирования, представленного в 1992 году в книге Джона Козы «Genetic Programming: On the Programming of Computers by Means of Natural Selection»^[65]. Этот подход позволил эволюционировать не просто параметрам, а целым компьютерным программам, представленным в виде деревьев^[66]. Также в начале десятилетия зародились коэволюционные алгоритмы^[67]. Произошла институционализация области: в 1991 году был принят обобщающий термин «эволюционные вычисления» (англ. Evolutionary Computation)^[68], появились ключевые научные журналы — Evolutionary Computation (1993) и IEEE Transactions on Evolutionary Computation (1997), а в 1994 году состоялся первый конгресс IEEE по эволюционным вычислениям^[69].

2000-е годы ознаменовались зрелостью роевого интеллекта, расцветом многокритериальной оптимизации и появлением новых классов алгоритмов. Получили широкое распространение алгоритмы роя частиц (PSO) и муравьиные алгоритмы (ACO), для которых были предложены эффективные варианты, такие как MAX-MIN Ant System (2000)^[70]. Это десятилетие стало «золотым веком» для многокритериальных эволюционных алгоритмов (MOEA): знаковая работа Эккарта Цитлера и соавторов (2000) привела к созданию таких известных методов, как NSGA-II и SPEA2^[71]. Генетическое программирование продемонстрировало впечатляющие практические успехи, включая создание патентоспособных «человеко-конкурентных» решений и разработку антенны для миссии ST5 НАСА^[72]. Также оформились новые направления, такие как алгоритмы оценки распределения (EDA)^[73], меметические алгоритмы^[74] и дифференциальная эволюция, популярность которой резко возросла с 2004 года^[75].

В 2010-е годы фокус сместился на решение крупномасштабных задач оптимизации (англ. Large-Scale Global Optimization, LSGO) и глубокую интеграцию с машинным обучением^[76]. Для борьбы с «проклятием размерности» активно развивались кооперативные коэволюционные и меметические алгоритмы^[77]. Для задач с вычислительно дорогой целевой функцией получили развитие суррогатно-вспомогательные эволюционные алгоритмы (англ. Surrogate-Assisted Evolutionary Algorithms, SAEA), использующие аппроксимирующие модели для оценки приспособленности^[78]. Отдельным направлением стала многокритериальная оптимизация с большим числом критериев (4 и более, англ. Many-Objective Optimization)^[79]. Одним из главных трендов десятилетия стало слияние ЭА и машинного обучения, в частности, применение нейроэволюции для автоматического проектирования архитектур нейронных сетей (англ. Neural Architecture Search, NAS)^[80].

1980-е годы стали периодом, когда эволюционные алгоритмы превратились из теоретических концепций в полноценную область исследований^[59]. Ключевым событием стала первая Международная конференция по генетическим алгоритмам (ICGA), организованная Джоном Грефенстеттом в 1985 году^[60]. В 1989 году ученик Холланда Дэвид Голдберг опубликовал книгу «Генетические алгоритмы в поиске, оптимизации и машинном обучении», ставшую настольной для тысяч исследователей^[61]. В это же десятилетие началось активное применение ГА к NP-трудным задачам, таким как задача коммивояжёра^[62], и появились первые коммерческие продукты, например, Evolver (1989)^[60]. Параллельно получили развитие и другие направления: эволюционное программирование было расширено для решения задач с вещественными числами^[63], а эволюционные стратегии были формализованы в книге Ханса-Пауля Швефеля (1981), где была представлена идея самоадаптации параметров мутации^[64].

В 1990-е годы область пережила бурный рост, были заложены основы академической инфраструктуры и появились новые парадигмы. Важнейшей вехой стало появление генетического программирования, представленного в 1992 году в книге Джона Козы «Genetic Programming: On the Programming of Computers by Means of Natural Selection». Этот подход позволил эволюционировать не просто параметрам, а целым компьютерным программам, представленным в виде деревьев. Также в начале десятилетия зародились коэволюционные алгоритмы, в которых приспособленность особи оценивается через её взаимодействие с другими особями. В 1994 году Митчелл Поттер и Кеннет Де Йонг предложили концепцию кооперативной коэволюции, где проблема разбивается на части, и для каждой из них эволюционирует отдельная субпопуляция.

Произошла институционализация области: в 1991 году был принят обобщающий термин «эволюционные вычисления» (англ. Evolutionary Computation), появились ключевые научные журналы — Evolutionary Computation (1993) и IEEE Transactions on Evolutionary Computation (1997), а в 1994 году состоялся первый конгресс IEEE по эволюционным вычислениям.

2000-е годы ознаменовались зрелостью роевого интеллекта, расцветом многокритериальной оптимизации и появлением новых классов алгоритмов. Получили широкое распространение алгоритмы роя частиц (PSO) и муравьиные алгоритмы (ACO), для которых были предложены эффективные варианты, такие как MAX-MIN Ant System (2000)^[70]. Это десятилетие стало «золотым веком» для многокритериальных эволюционных алгоритмов (MOEA): знаковая работа Эккарта Цитлера и соавторов (2000) привела к созданию таких известных методов, как NSGA-II и SPEA2^[71]. Генетическое программирование продемонстрировало впечатляющие практические успехи, включая создание патентоспособных «человеко-конкурентных» решений и разработку антенны для миссии ST5 НАСА. Также оформились новые направления, такие как алгоритмы оценки распределения (EDA), меметические алгоритмы и дифференциальная эволюция, популярность которой резко возросла с 2004 года.

В 2010-е годы фокус сместился на решение крупномасштабных задач оптимизации (англ. Large-Scale Global Optimization, LSGO) и глубокую интеграцию с машинным обучением^[76]. Для борьбы с «проклятием размерности» активно развивались кооперативные коэволюционные и меметические алгоритмы^[77]. Для задач с вычислительно дорогой целевой функцией получили развитие суррогатно-вспомогательные эволюционные алгоритмы (англ. Surrogate-Assisted Evolutionary Algorithms, SAEA), использующие аппроксимирующие модели для оценки приспособленности^[78].

Отдельным направлением стала многокритериальная оптимизация с большим числом критериев (4 и более, англ. Many-Objective Optimization)^[79]. Одним из главных трендов десятилетия стало слияние ЭА и машинного обучения, в частности, применение нейроэволюции для автоматического проектирования архитектур нейронных сетей (англ. Neural Architecture Search, NAS)^[80].

Хотя исторически выделяют четыре основных направления (генетические алгоритмы, эволюционные стратегии, генетическое и эволюционное программирование), поле эволюционных вычислений гораздо шире и включает множество других классов алгоритмов. К значимым современным парадигмам относятся дифференциальная эволюция (DE)^[75], алгоритмы роевого интеллекта (в частности, PSO и ACO)^[70], алгоритмы оценки распределения (EDA)^[73] и гибридные меметические алгоритмы (MA)^[74].

Постановка задачи для любого эволюционного алгоритма определяется целевой функцией и «пространством решений», включающим все возможные кандидаты. Репрезентация (или представление) позволяет отличать способ внутреннего кодирования решения (генотип) от его проявления в проблемной области (фенотип). Алгоритмы различаются по следующим ключевым компонентам:

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

Исторически сложившиеся четыре типа: генетические алгоритмы (GA), эволюционные стратегии (ES), генетическое программирование (GP), эволюционное программирование (EP).

Генетические алгоритмы, популяризированные Джоном Холландом, используют бинарное представление и требуют отображения генотипа в фенотип перед оценкой. В них селекция проводится пропорционально фитнесу; кроссинговер — n-точечный^[81]. Мутация трактуется как инверсия, дублирование или удаление битов.

Эволюционные стратегии^[82] используют прямое вещественное представление; основа — самоадаптация шагов мутаций и «коэволюция». Отбор — либо только из потомков, либо из родителей и потомков, параметры подбираются по эмпирическим рекомендациям^[83].

Генетическое программирование создаёт структуры (программы, схемы, функции), представленные в виде деревьев. Классический пример — решение задачи символической регрессии^[84].

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

В 2000-е годы достигли зрелости два ведущих направления роевого интеллекта — оптимизация роем частиц (PSO) и муравьиные алгоритмы (ACO).

Оптимизация роем частиц (PSO) получила значительное развитие: были предложены ключевые модификации для улучшения производительности и скорости сходимости, такие как коэффициент сжатия (англ. Constriction Coefficient) и инерционный вес (англ. Inertia Weight)^[85]. В 2009 году была представлена адаптивная PSO (APSO), которая динамически изменяла параметры для балансировки между исследованием и эксплуатацией пространства поиска.

Муравьиные алгоритмы (ACO) также получили теоретическое обоснование: в 2000 году появилось первое доказательство сходимости для муравьиного алгоритма. Были разработаны влиятельные варианты, такие как Ant Colony System (ACS) и MAX-MIN Ant System (MMAS), предложенный в 2000 году. Эти алгоритмы продемонстрировали высокую эффективность в решении задач комбинаторной оптимизации, таких как задача коммивояжёра и маршрутизация в сетях.

Алгоритмы оценки распределения (англ. Estimation of Distribution Algorithms, EDA) оформились как отдельное направление в 2000-е годы^[73]. В отличие от классических генетических алгоритмов с операторами скрещивания и мутации, EDA строят вероятностную модель перспективных решений и генерируют новые на её основе^[86]. В 2000-х годах были предложены и исследованы различные реализации EDA, использующие байесовские сети и другие вероятностные модели^[73].

Дифференциальная эволюция (англ. Differential Evolution, DE) — метод, предложенный в середине 1990-х годов, популярность которого резко возросла в 2000-е, что подтверждается значительным ростом числа публикаций с 2004 года. В течение 2010-х годов DE оставался в центре внимания исследователей, которые предложили множество его модификаций^[87]. Основные усилия были направлены на разработку механизмов адаптации управляющих параметров (таких как F и CR) и создание новых мутационных стратегий для повышения эффективности алгоритма^[87].

Меметические алгоритмы (англ. Memetic Algorithms, MA) — это гибридные подходы, которые сочетают глобальный поиск, выполняемый эволюционным алгоритмом, с методами локального поиска для индивидуального «обучения» или «улучшения» решений. Концепция вдохновлена идеей культурной эволюции (мемов), и такие алгоритмы показали высокую эффективность для многих сложных задач оптимизации. В 2010-е годы они получили широкое распространение для решения задач крупномасштабной глобальной оптимизации (англ. Large-Scale Global Optimization, LSGO). Например, алгоритм MA-SW-Chains стал победителем на соревновании в рамках конференции IEEE CEC в 2010 году.

Оба класса используют случайность, но ключевое различие: ЭА «обучаются» — уже просмотренные варианты влияют на поиск, тогда как в Монте-Карло новые решения независимы от истории^[88].