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

Стохастический генетический алгоритм — рандомизированный эволюционный поиск для оптимизации

Автор метода
Holland, J. H.
Год
1975
Тип
Stochastic evolutionary metaheuristic
Семейство
Simulation / optimization

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

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

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

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

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

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

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

История

Джон Холланд представил теоретические основы генетических алгоритмов в Мичиганском университете в 1975 году, опираясь на более ранние работы Фрейзера (1957) по имитации генетических систем. Учебник Дэвида Голдберга 1989 года популяризировал ГА для инженерной оптимизации. Стохастическая природа отбора была формализована с помощью теоремы о схемах, и метод стал краеугольным камнем эволюционных вычислений и вычислительного интеллекта.

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

Использовать стохастический генетический алгоритм, когда: (1) пространство поиска велико, мультимодально или дискретно, и градиентные методы не работают или неприменимы; (2) целевая функция является «черным ящиком», зашумлена или дорога в оценке, но поддается выборке на уровне популяции; (3) комбинаторные задачи или задачи со смешанными целями не имеют эффективных точных решателей; (4) приемлемо найти близкое к оптимальному решение в пределах разумного числа оценок. НЕ использовать СГА, когда: задача выпуклая или градиент доступен и дешев — классическая оптимизация сходится быстрее; когда оценки функции чрезвычайно дороги (десятки или сотни), популяционные методы могут исчерпать бюджет; или когда требуется доказуемо оптимальное решение, поскольку ГА не дают гарантий оптимальности.

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

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

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

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

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

Применение

  • Планирование производственных процессов (job-shop) и сквозных процессов (flow-shop) в производстве и логистике
  • Отбор признаков и настройка гиперпараметров в конвейерах машинного обучения
  • Оптимизация структуры и топологии в машиностроении и гражданском строительстве
  • Задачи коммивояжера и маршрутизации транспортных средств в исследовании операций
  • Предсказание структуры белков и открытие лекарств в биоинформатике
  • Поиск архитектуры нейронных сетей и оптимизация весов

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

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

1

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

2

Вычислить приспособленность f(x_i) для каждого индивида в популяции, используя целевую функцию (или ее суррогат). Приспособленность количественно определяет качество решения; более высокая приспособленность означает лучшее решение. Для задач минимизации приспособленность часто определяется как обратная величина или преобразование функции затрат.

Формула
f(x_i), \quad i = 1, \ldots, N
3

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

Формула
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}
4

С вероятностью p_c (обычно 0,6–0,9) рекомбинировать пары выбранных родителей для получения потомства. Одноточечный, двухточечный или равномерный кроссовер обмениваются генетическим материалом между родительскими хромосомами, создавая потомков, которые наследуют признаки от обоих. Этот оператор способствует эксплуатации хороших строительных блоков.

5

С низкой вероятностью p_m (обычно 0,001–0,05 на ген) случайным образом изменять отдельные гены в каждой хромосоме потомка. Мутация поддерживает генетическое разнообразие, предотвращает преждевременную сходимость и гарантирует, что алгоритм может выйти из локальных оптимумов. Скорость мутации является критическим параметром, настраиваемым под задачу.

6

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

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

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

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

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

Метка «стохастический» подчеркивает, что все основные операторы — отбор, кроссовер и мутация — включают вероятностные выборки. Канонический ГА, представленный Холландом, по своей сути стохастичен. Метка используется в литературе по моделированию/оптимизации для отличия от редких детерминированных вариантов (например, детерминированного скопления) и для уточнения, что поведение алгоритма варьируется от запуска к запуску из-за случайности.

Насколько большой должна быть популяция?

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

Когда следует предпочесть оптимизацию роем частиц или имитацию отжига генетическому алгоритму?

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

Масштабируется ли стохастический генетический алгоритм для задач высокой размерности?

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

Как обрабатывать ограничения в генетическом алгоритме?

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

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

Источники

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

    ISBN: 978-0262581110
    Скопировано.
  2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

    ISBN: 978-0201157673
    Скопировано.