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

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

История

Первые идеи, связывающие эволюцию и оптимизацию, появились в 1950-х годах. В 1960-х годах были заложены основы трёх основных направлений эволюционных алгоритмов:

• Генетические алгоритмы (ГА) — разработаны Джоном Холландом (США) в 1960–1970-х годах. Холланд предложил использовать бинарное кодирование решений и операции кроссинговера и мутации для поиска в пространстве возможных вариантов.
• Эволюционные стратегии (ЭС) — созданы в 1960-х годах Инго Рехенбергом и Хансом-Паулем Швефелем (Германия). Первоначально применялись для численной оптимизации в инженерных задачах (например, для оптимизации формы сопла). В ЭС акцент делается на мутации с адаптивным шагом.
• Эволюционное программирование (ЭП) — предложено Лоуренсом Фогелем (США) в 1960-х годах. Изначально разрабатывалось для создания искусственного интеллекта путём эволюции конечных автоматов. В отличие от ГА, в ЭП нет операции кроссинговера, а мутация является основным оператором.

В 1990-х годах эти направления были объединены под общим термином «эволюционные вычисления». В 1992 году появился метод генетического программирования (Джон Коза), который позволяет эволюционировать программы (деревья выражений). В 1993 году был предложен дифференциальный алгоритм эволюции (Райнер Шторн и Кеннет Прайс), эффективный для непрерывной оптимизации. В 2000-х годах развитие получили гибридные методы, сочетающие эволюционные алгоритмы с другими метаэвристиками (например, с методом имитации отжига или роевым интеллектом), а также параллельные и распределённые реализации для работы с большими данными.

Основные принципы

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

1. Инициализация. Создаётся начальная популяция решений. Обычно она формируется случайным образом, но может включать и известные хорошие решения.
2. Оценка приспособленности. Для каждого решения (особи) вычисляется значение целевой функции (функции приспособленности). Чем лучше решение, тем выше его приспособленность.
3. Селекция. Выбираются родительские особи для создания следующего поколения. Вероятность выбора пропорциональна приспособленности (например, метод рулетки или турнирный отбор). Более приспособленные особи имеют больше шансов передать свои «гены» потомству.
4. Рекомбинация (кроссинговер). Из двух или более родительских решений создаются новые решения (потомки). Оператор кроссинговера комбинирует части решений родителей.
5. Мутация. В потомки вносятся случайные изменения с определённой вероятностью. Это позволяет алгоритму не застревать в локальных оптимумах и исследовать новые области пространства решений.
6. Формирование нового поколения. Из потомков и, возможно, части лучших родителей (элитизм) формируется новая популяция.
7. Повторение. Цикл возвращается к шагу 2, пока не будет выполнен критерий остановки.

Классификация и разновидности

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

Генетические алгоритмы (ГА)

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

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

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

Эволюционное программирование (ЭП)

Решения — это конечные автоматы или программы. Мутация изменяет структуру автомата или программы (например, добавляет или удаляет состояние). Кроссинговер отсутствует. ЭП используется для задач прогнозирования временных рядов и создания адаптивных систем.

Генетическое программирование (ГП)

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

Дифференциальная эволюция (ДЭ)

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

Применение

Эволюционные алгоритмы нашли широкое применение в различных областях науки и техники:

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

Преимущества и недостатки

Преимущества

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

Недостатки

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

Критика и ограничения

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

Источники

• Холланд Дж. «Адаптация в естественных и искусственных системах» (1975).
• Рехенберг И. «Эволюционные стратегии: оптимизация технических систем по принципам биологической эволюции» (1973).
• Фогель Л. «Искусственный интеллект через эволюционное моделирование» (1966).
• Коза Дж. «Генетическое программирование: программирование компьютеров с помощью естественного отбора» (1992).
• Шторн Р., Прайс К. «Дифференциальная эволюция — простой и эффективный адаптивный метод глобальной оптимизации над непрерывными пространствами» (1997).
• Эйбен А. Э., Смит Дж. Э. «Введение в эволюционные вычисления» (2003).