Skip to content
Назад к результатам поиска

Генетический алгоритм — Эволюционная оптимизация

Автор метода
John Henry Holland
Год
1975
Тип
Population-based metaheuristic

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Генетический алгоритм (ГА) — это метаэвристический метод оптимизации, основанный на популяции, введенный Джоном Генри Холландом (1975), который имитирует принципы естественного отбора.

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

Интуиция метода

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

История

Генетический алгоритм был введен Джоном Генри Холландом в его книге 1975 года «Адаптация в естественных и искусственных системах», которая формализовала понятие схемы (строительного блока) и предоставила фундаментальный теоретический анализ того, почему скрещивание и отбор направляют поиск к более приспособленным областям. Студенты Холланда — в частности, Дэвид Голдберг — популяризировали ГА через инженерные приложения в 1980-х годах. Кальяной Мой Деб позже расширил рамки для многокритериальных настроек, кульминацией чего стал широко используемый алгоритм NSGA-II (2002). Сегодня ГА остаются стандартным инструментом в эволюционных вычислениях, с активными исследованиями гибридных методов, которые сочетают эволюционный поиск с локальным уточнением.

Когда применять

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

Ограничения и замечания

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

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Работает на разрывных, недифференцируемых и мультимодальных ландшафтах целевой функции, где градиентные методы дают сбой.
  • Не накладывает предположений о распределении — единственным требуемым входом является вычислимая функция приспособленности.
  • Естественным образом обрабатывает широкий спектр типов переменных: непрерывные, бинарные, категориальные и порядковые.
  • Разнообразие популяции позволяет одновременно исследовать несколько областей пространства поиска, снижая риск преждевременного застревания в локальном оптимуме.
  • Высокая расширяемость: специфичные для предметной области операторы скрещивания и мутации, обработка ограничений и многокритериальные варианты (например, NSGA-II) хорошо зарекомендовали себя в литературе.

Применение

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

Как это работает

Как это работает

1

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

2

Каждый индивид в популяции оценивается функцией приспособленности, которая количественно определяет, насколько хорошим является данное решение по отношению к цели задачи. Функция приспособленности — это единственный специфичный для предметной области компонент, который должен предоставить пользователь; это может быть любая вычислимая мера — выход симуляции, формула стоимости или метрика ошибки модели.

3

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

4

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

5

Цикл «оценка → отбор → воспроизводство» продолжается заданное количество поколений или до тех пор, пока не будет достигнут критерий сходимости (например, отсутствие улучшения в течение окна поколений). Лучший индивид, найденный за все поколения, возвращается в качестве решения. Поскольку сходимость к глобальному оптимуму не гарантируется, для задач с высокими ставками рекомендуется проводить несколько независимых запусков.

Частые ошибки

  • Запуск слишком малого числа поколений является наиболее распространенной ошибкой: при недостаточном количестве поколений алгоритм не сходится, поэтому аналитические или градиентные методы следует предпочесть, когда доступен только небольшой бюджет итераций.
  • Преждевременная конвергенция — потеря разнообразия популяции слишком рано — приводит к локально оптимальному, но глобально субоптимальному результату; для противодействия этому поддерживайте достаточный размер популяции и частоту мутации.
  • Использование плохо определенной или неверно специфицированной функции приспособленности дает вводящие в заблуждение результаты независимо от корректности алгоритма; проверьте функцию приспособленности независимо перед запуском ГА.
  • Применение ГА к гладкой, выпуклой задаче, где достаточно градиентного спуска или линейного программирования, приводит к растрате вычислительных ресурсов и вносит ненужную стохастичность.
  • Сообщение об одном запуске как о решении без проверки воспроизводимости; для приложений с высокими ставками запускайте алгоритм несколько раз и сообщайте о распределении результатов.

Часто задаваемые вопросы

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

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

Сколько поколений и какой размер популяции мне нужен?

Универсальных правил нет; оба зависят от сложности пространства поиска. Слишком маленькая популяция или слишком короткий запуск рискуют преждевременной конвергенцией. В качестве практической отправной точки размеры популяции 50–200 и количество поколений 100–1000 являются распространенными в литературе, но сложные задачи обычно требуют большего. Всегда проверяйте кривые сходимости, а не фиксируйте произвольные критерии остановки.

Гарантирован ли генетический алгоритм нахождение глобального оптимума?

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

Когда мне следует выбрать ГА вместо имитации отжига или оптимизации роем частиц?

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

Похожие методы

Источники

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Открыть ссылку на публикацию
    Скопировано.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Скопировано.