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

Материал из MachineLearning.

Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol) и проверена участником Aleksei Kovalenko 21:00, 14 июля 2026 (MSD)

Содержание

1 Постановка задачи
- 1.1 Связь со случайным поиском и машинным обучением
2 Представление и функция приспособленности
- 2.1 Кодирование решения
- 2.2 Приспособленность и ограничения
3 Операторы генетического алгоритма
4 Общий алгоритм
5 Теоретические свойства
6 Динамика популяции и настройка
7 Варианты и обобщения
8 Применения в машинном обучении
9 Сравнение с методами оптимизации
10 Ограничения и типичные ошибки
11 Практический протокол эксперимента
12 См. также
13 Примечания
14 Литература

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

Термин следует употреблять узко. Классический ГА Холланда работает с популяцией строк фиксированной длины, пропорциональным отбором, одноточечным скрещиванием и редкой побитовой мутацией.^[1] Современные ГА сохраняют популяцию, наследуемое представление и операторы отбора, рекомбинации и мутации, но допускают вещественные, перестановочные, графовые и иные геномы. Генетическое программирование эволюционирует программы или деревья выражений; Эволюционные стратегии исторически ориентированы на вещественную оптимизацию и самоадаптацию параметров мутации; Дифференциальная эволюция порождает вещественные векторы из масштабированных разностей; Нейроэволюция обозначает применение эволюционных методов к весам, топологии или правилам обучения нейронных сетей. Эти семейства родственны, но не являются синонимами ГА.

Постановка задачи

Пусть задано пространство допустимых фенотипов $\mathcal X$ и задача минимизации

$x^*\in\operatorname*{arg\,min}_{x\in\mathcal X} f(x),$

где вычисление $f:\mathcal X\to\mathbb R\cup\{+\infty\}$ может включать обучение и валидацию модели. Для задачи максимизации знак меняют или определяют приспособленность как монотонное преобразование критерия. Генотипы принадлежат пространству $\mathcal G$ , а декодер $d:\mathcal G\to\mathcal X$ переводит генотип в решение. В поколении $t$ состояние алгоритма — мультимножество

$P_t=(g_{t,1},\ldots,g_{t,\mu})\in\mathcal G^\mu,$

где $\mu$ — размер популяции. Оценка особи определяется функцией

$F(g;\xi)=\Phi\bigl(f(d(g);\xi),d(g)\bigr),$

где $\xi$ обозначает случайность данных, обучения или симуляции, а $\Phi$ включает изменение направления оптимизации, штрафы и масштабирование. Один шаг ГА задаёт переходное ядро

$\Pr(P_{t+1}\in A\mid P_t)=K_t(P_t,A),$

образованное отбором родителей, рекомбинацией, мутацией, оцениванием и замещением. При неизменных операторах и параметрах популяционный процесс является однородной конечной цепью Маркова, если $\mathcal G$ конечно.

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

Связь со случайным поиском и машинным обучением

ГА — адаптивный случайный поиск: распределение новых запросов зависит от истории оценок. При нулевом давлении отбора и полной повторной случайной инициализации он вырождается в независимый случайный поиск; при популяции из одной особи, мутации и элитарном принятии — в простой эволюционный локальный поиск. Универсального превосходства над другими оптимизаторами нет: теоремы «нет бесплатного обеда» усредняют по всем целевым функциям на конечном пространстве и при замкнутости класса функций относительно перестановок; они не утверждают равенства методов на структурированных практических задачах.^[1]

В машинном обучении различаются параметры модели $w$ , гиперпараметры или структура $\lambda$ и состояние оптимизатора. Типичная внешняя задача имеет вид

$\min_{\lambda\in\Lambda}\; \widehat L_{\mathrm{val}}\bigl(w^*(\lambda),\lambda\bigr),\qquad w^*(\lambda)\in\operatorname*{arg\,min}_{w}\widehat L_{\mathrm{train}}(w,\lambda).$

ГА обычно решает внешнюю, часто смешанную и недифференцируемую задачу по $\lambda$ , тогда как веса $w$ обучаются градиентным методом. Прямая эволюция миллионов весов возможна, но является уже нейроэволюцией и обычно требует очень большого числа оценок.

Представление и функция приспособленности

Кодирование решения

Представление определяет соседство и наследуемость. Хороший генотип удовлетворяет четырём условиям: декодирование однозначно или контролируемо; допустимые решения не редки; небольшая мутация обычно даёт осмысленное изменение; рекомбинация сохраняет полезные зависимости.

Двоичная строка. Подходит для отбора признаков, логических решений и ограниченных целых параметров. Для $p$ признаков бит $g_j=1$ означает включение признака. Обычное двоичное кодирование целого создаёт «обрывы Хэмминга»; код Грея уменьшает это явление для соседних чисел, но не устраняет эпистаз.
Целочисленный или категориальный вектор. Каждая позиция выбирает категорию, оператор или число слоёв. Мутация должна учитывать различные мощности доменов.
Вещественный вектор. Применяются арифметическое, BLX- $\alpha$ или моделирующее двоичное скрещивание (SBX) и гауссова либо полиномиальная мутация. Побитовое кодирование вещественных чисел обычно создаёт искусственную точность и плохую локальность.
Перестановка. Используется в задачах комбинаторной оптимизации, где существенен порядок. Обычное одноточечное скрещивание создаёт повторы и пропуски; нужны PMX, OX, cycle crossover или операторы обмена и инверсии.
Дерево, граф, переменная длина. Пригодно для конвейеров и архитектур, но требует типобезопасных операторов, устранения изоморфных дубликатов и контроля разрастания. Деревья программ относятся к генетическому программированию, а не к классическому ГА.

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

Приспособленность и ограничения

Для максимизации можно использовать $F=-f$ , ранговое преобразование или положительное масштабирование. Рулеточный отбор требует неотрицательных значений и чувствителен к сдвигу шкалы; турнирный и ранговый отбор сохраняют порядок и обычно устойчивее.

В ML оценка должна отражать обобщающую способность. Один и тот же валидационный набор, многократно используемый в тысячах поколений, превращается в объект переобучения. Корректный протокол отделяет финальный тест, использует вложенную кросс-валидацию либо независимую переоценку финалистов и фиксирует бюджет обучения. Для стохастической оценки полезны общие случайные числа, повторные запуски и адаптивное увеличение числа повторов у перспективных кандидатов.

Ограничения $c_k(x)\leq 0$ обрабатывают несколькими способами:

декодером, который всегда строит допустимый фенотип;
восстанавливающим оператором после вариации;
правилом допустимости: допустимое решение лучше недопустимого, среди недопустимых лучше меньшее нарушение;
штрафом

$F(x)=-f(x)-\sum_k\rho_k\max\{0,c_k(x)\}^{q_k};$

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

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

Операторы генетического алгоритма

Инициализация

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

Отбор

Отбор родителей создаёт давление отбора — скорость, с которой более приспособленные особи увеличивают ожидаемое число потомков.

При пропорциональном отборе вероятность выбрать $i$ -ю особь равна

$p_i=\frac{F_i}{\sum_{j=1}^{\mu}F_j},$

что корректно при положительных приспособленностях и зависит от масштаба.

При турнире размера $k$ выбирается лучшая из $k$ случайно взятых особей; увеличение $k$ усиливает давление.
Ранговый отбор назначает вероятности по рангу и отделяет давление от числовой шкалы.
Усечение допускает к размножению только верхнюю долю популяции; оно просто, но при сильном усечении ускоряет потерю разнообразия.

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

Скрещивание

Скрещивание с вероятностью $p_c$ строит потомка из двух или более родителей. Для двоичных строк одноточечное скрещивание выбирает границу и меняет суффиксы; равномерное независимо выбирает родителя для каждого локуса. Эффективность зависит от того, расположены ли взаимодействующие гены рядом и сохраняет ли оператор строительные блоки. Утверждение, что скрещивание всегда полезно, неверно: при сильном эпистазе или несогласованном представлении оно систематически разрушает хорошие комбинации. Методы обучения связям (linkage learning) и алгоритмы оценки распределения пытаются оценивать зависимости явно, но это уже обобщения классического ГА.

Мутация

Мутация двоичной строки длины $n$ независимо инвертирует каждый бит с вероятностью $p_m$ ; выбор $p_m=1/n$ даёт в среднем одно изменение. Вероятность не изменить строку при этом стремится к $e^{-1}$ , поэтому реализация должна явно решить, разрешены ли клоны. Для вещественных генов масштаб мутации согласуют с диапазоном или адаптируют. Мутация обеспечивает новые аллели и, при положительной вероятности любого необходимого изменения, делает пространство достижимым.

Замещение и элитизм

В поколенческой схеме вся популяция заменяется потомками; в стационарной (steady-state) схеме заменяется несколько особей. Элитизм копирует лучшие $e$ решений или выбирает лучшие из объединения родителей и потомков. Он гарантирует невозрастание лучшего найденного значения в детерминированной задаче, но не гарантирует быстрого нахождения глобального оптимума. При шуме элитизм может навсегда закрепить случайно переоценённого кандидата; нужны переоценка, статистическое сравнение или ограниченный возраст.

Общий алгоритм

Вход: декодер $d$ , функция оценки $F$ , размер $\mu$ , число потомков $\lambda$ , бюджет $B$ , операторы отбора $S$ , скрещивания $C$ , мутации $M$ и замещения $R$ .

P := Initialize(mu)
Evaluate(P)
archive := Best(P)
while budget remains and stopping criterion is false:
    Q := empty multiset
    while |Q| < lambda:
        parents := Select(P)
        children := Crossover(parents)
        children := Mutate(children)
        children := DecodeOrRepair(children)
        EvaluateUnevaluated(children)
        Q := Q union children
    P := Replace(P, Q, archive)
    archive := UpdateArchive(archive, P)
return archive

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

Теоретические свойства

Схемы и пределы классической теории

Схема $H\in\{0,1,*\}^n$ задаёт подмножество строк; $o(H)$ — число фиксированных позиций, $\delta(H)$ — расстояние между крайними фиксированными позициями. Для классического пропорционального отбора, одноточечного скрещивания с вероятностью $p_c$ и побитовой мутации $p_m$ ожидаемое число представителей схемы удовлетворяет нижней оценке Холланда

$\mathbb E[m(H,t+1)]\geq m(H,t)\frac{\bar F_H(t)}{\bar F(t)}\left(1-p_c\frac{\delta(H)}{n-1}\right)(1-p_m)^{o(H)}.$

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

Сходимость

Следует различать сходимость лучшего значения и распределения популяции. Пусть $\mathcal G$ конечно, декодер содержит глобально оптимальный фенотип, используется архив или элитизм, а из любого состояния существует вероятность не меньше $\varepsilon>0$ за конечное число шагов породить каждый генотип (например, побитовая мутация имеет $0<p_m<1$ и кандидат может попасть в популяцию). Тогда вероятность хотя бы раз посетить глобальный оптимум стремится к единице при неограниченном числе поколений:

$\Pr\{\exists t\leq T:\;x^*\in d(P_t)\}\longrightarrow 1,\qquad T\to\infty.$

Без элитизма оптимум может быть потерян, поэтому сама популяция не обязана сходиться к множеству оптимумов. Более того, канонический ГА с положительной мутацией в общем случае имеет стационарное распределение, а не поглощение в оптимальной популяции. Если мутация не обеспечивает достижимость или замещение может всегда отвергать путь, утверждение об архиве неприменимо. Для непрерывного пространства положительная плотность мутации не даёт положительной вероятности попасть ровно в единственную точку; формулируют сходимость в окрестность или по значению при дополнительных условиях регулярности. Марковские доказательства асимптотичны и не дают практически приемлемого времени.^[1]^[1]

Время работы и вычислительная сложность

Стоимость одного поколения без оценки обычно составляет $O(\mu+\lambda n)$ для строк длины $n$ ; доминирует $\lambda C_F$ , где $C_F$ — стоимость оценки. Память равна $O(\mu n)$ плюс модели, кэш и архив. Для NSGA-II недоминирующая сортировка исходного алгоритма имеет сложность $O(M\mu^2)$ при $M$ целях.^[1]

Точный анализ числа оценок возможен лишь для конкретного алгоритма и класса функций. Например, для элитарного алгоритма $(1+1)$ EA с побитовой мутацией $1/n$ ожидаемое время на OneMax имеет порядок $\Theta(n\log n)$ , а на LeadingOnes — $\Theta(n^2)$ . Эти результаты не переносятся автоматически на популяционный ГА с кроссовером и задачу обучения модели.^[1] Для некоторых функций кроссовер с подходящей популяцией доказуемо ускоряет поиск, для других добавляет стоимость без пользы. В худшем случае время экспоненциально; нахождение точного решения NP-трудной задачи общим ГА не отменяет предположений теории сложности.

Динамика популяции и настройка

Размер популяции

Большая $\mu$ уменьшает выборочный дрейф, сохраняет больше аллелей и позволяет параллельные оценки, но при фиксированном бюджете уменьшает число поколений. Маленькая популяция быстро обновляется, однако легко фиксирует случайные варианты. Универсального оптимального размера нет: он зависит от размерности, эпистаза, шума, оператора, числа ниш и параллельного оборудования. Теоретические модели выбора размера популяции предполагают, например, аддитивную декомпозицию на конкурирующие строительные блоки и заданную вероятность правильного решения; вне этих предпосылок они не являются общим рецептом.^[1]

Практический протокол — назначить бюджет оценок, выбрать $\mu$ , достаточную для представления разных областей, и проверять устойчивость по нескольким независимым запускам. При массовом параллелизме $\lambda$ можно сделать больше $\mu$ , не увеличивая архив родителей.

Давление отбора и разнообразие

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

Потеря разнообразия до обнаружения нужных комбинаций называется преждевременной сходимостью. Её ограничивают умеренным турниром, разделением приспособленности (fitness sharing), вытеснением (crowding), нишированием, отрицательным ассортативным скрещиванием, перезапусками, островами и адаптацией мутации. Простое повышение $p_m$ может разрушить накопленную структуру. Элитный архив следует отделять от числа элит, непосредственно копируемых в популяцию.

Исследование и эксплуатация

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

Варианты и обобщения

Вещественно-кодированный ГА

Вещественный ГА хранит $x\in\mathbb R^n$ непосредственно. BLX- $\alpha$ для каждой координаты родителей $x_i,y_i$ выбирает значение равномерно из расширенного интервала; SBX имитирует распределение потомков двоичного скрещивания, а полиномиальная мутация контролирует локальность индексом распределения. Это ГА, если основой остаются отбор и рекомбинация геномов. Самоадаптация ковариации, как в CMA-ES, относится к эволюционным стратегиям.

Многоцелевая оптимизация

При целях $f(x)=(f_1(x),\ldots,f_M(x))$ решение $x$ доминирует $y$ , если оно не хуже по всем целям и строго лучше хотя бы по одной. Искомое множество Парето состоит из недоминируемых решений. NSGA-II ранжирует по фронтам, сохраняет элиту из объединения родителей и потомков и использует расстояние скученности (crowding distance) для поддержания разнообразия.^[1] В ML целями служат ошибка, задержка, память, энергия, справедливость и сложность. Полученный фронт — приближение, зависящее от бюджета и масштаба целей; алгоритм не доказывает полноту истинного фронта.

Меметические алгоритмы

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

Параллельные модели

Master–worker параллелизует только оценивание общей популяции.
Островная модель развивает несколько субпопуляций и периодически мигрирует особей; топология, интервал и политика миграции меняют давление и разнообразие.
Клеточная модель ограничивает взаимодействия локальным соседством.
Асинхронная модель принимает завершившиеся оценки без барьера поколения; она лучше использует неодинаковые по скорости работники, но быстрые кандидаты получают систематическое репродуктивное преимущество, если время оценки связано с генотипом.^[1]

Применения в машинном обучении

Отбор признаков

Двоичный геном задаёт подмножество признаков. В обёрточной схеме (wrapper) приспособленность — оценка обученного предиктора, например

$F(g)=\widehat L_{\mathrm{CV}}(g)+\lambda\left\|g\right\|_0.$

ГА естественно моделирует взаимодействия признаков и ограничения групп, но требует многих обучений. Фильтрующие критерии дешевле, однако могут не соответствовать итоговой модели; встроенные методы, например регуляризация, часто предпочтительнее при линейной структуре и больших $p$ . Нельзя выбирать признаки на полном наборе до кросс-валидации: отбор должен выполняться внутри каждого обучающего фолда. Ранние работы показали применимость ГА как обёрточного поиска, но не устанавливают его универсального превосходства.^[1]

Оптимизация гиперпараметров и конвейеров

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

Сравнение должно включать случайный поиск: если важны лишь немногие координаты, он эффективнее сетки и предоставляет сильную бюджетную базовую линию.^[1] Для дорогих низкоразмерных задач Байесовская оптимизация обычно использует оценки экономнее.^[1] При сравнении запрещено давать ГА больше полных обучений или использовать тестовую выборку в функции приспособленности.

Поиск архитектур нейронных сетей

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

Алгоритм регуляризованной эволюции (Regularized Evolution) использует турнирный отбор и удаляет старейшую особь, что вводит возрастную регуляризацию; это современный эволюционный NAS, а не канонический ГА.^[1] Многоцелевой NSGA-Net одновременно учитывает ошибку и вычислительную сложность, сочетая ГА с моделью зависимостей; это гибридное расширение.^[1] Первые строгие оценки времени эволюционного NAS получены для искусственной задачи бинарной классификации UNIFORM и алгоритма $(1+1)$ без скрещивания; авторы прямо указывают, что анализ реального NAS пока недоступен из-за неявной и шумной связи обучения с функцией приспособленности. Поэтому эти результаты нельзя считать гарантией для практических глубоких сетей.^[1]

Нейроэволюция

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

Преимущество возникает при разреженной, запаздывающей или недифференцируемой награде и при необходимости искать структуру. Цена — высокая дисперсия оценки и число взаимодействий со средой. Поиск новизны (novelty search) и методы качества и разнообразия (quality-diversity) оптимизируют поведенческую новизну или репертуар решений; это обобщения эволюционного поиска, а не стандартный ГА.

Ансамбли

Геном может кодировать выбор базовых моделей, их веса, гиперпараметры и признаки. Функция приспособленности должна одновременно учитывать качество и разнообразие ошибок; иначе ГА выбирает множество коррелированных сильных моделей и не улучшает ансамбль. GASEN использует эволюционное взвешивание и отбор сетей как один из ранних примеров.^[1] На практике сравнивают с усреднением, стекингом, бэггингом и жадным отбором ансамбля, поскольку они дешевле и часто достаточны.

Недифференцируемые модели и метрики

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

Сравнение с методами оптимизации

Метод	Подходящее пространство и цель	Стоимость и параллелизация	Предпосылки и гарантии
Независимый случайный поиск	Любое пространство с сэмплером; сильная базовая линия для условных гиперпараметров	Минимальные накладные расходы; полностью параллелен	Асимптотическое попадание требует положительной меры хорошей области; не использует историю
Генетический алгоритм	Дискретные, смешанные, структурные геномы; чёрный ящик; несколько целей	Обычно много оценок; популяция естественно параллельна	Вероятностная асимптотическая сходимость лишь при достижимости и сохранении; общих скоростных гарантий нет
Градиентные методы	Непрерывные дифференцируемые параметры, особенно высокая размерность	Одна траектория, но эффективные батчи и ускорители; обычно существенно меньше вычислений функции потерь	Для выпуклых гладких задач — строгие скорости; в невыпуклом случае обычно стационарная точка при предпосылках
Байесовская оптимизация	Дорогая функция, малая или средняя эффективная размерность; возможны смешанные переменные	Экономна по оценкам, но обновление суррогата и оптимизация функции приобретения дорожают; пакетный режим менее естественен	Гарантии зависят от модели, ядра, шума и функции приобретения; эффективность ухудшается в очень высокой размерности
Эволюционная стратегия, в частности CMA-ES	Вещественные векторы, нелинейные и плохо обусловленные ландшафты	Популяционно параллельна; оценок много, обновление ковариации может стоить $O(n^2)$	Инвариантности и адаптация геометрии; это не ГА и нет общей гарантии быстрого глобального поиска^[1]
Дифференциальная эволюция	Ограниченная вещественная оптимизация	Простая, популяционная, параллельная; разностная мутация использует масштаб популяции	Требует вещественных векторов; чувствительна к параметрам и размерности; не является ГА^[1]

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

Ограничения и типичные ошибки

Ограничения

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

Ошибки проектирования

Кодировать вещественные параметры битами без анализа точности и локальности.
Применять одноточечное скрещивание к перестановкам или графам без восстановления допустимости.
Скрещивать условные конвейеры так, что большинство потомков недопустимо.
Подменять целевой критерий удобной прокси-метрикой, не проверив корреляцию рангов.
Суммировать несопоставимые цели с произвольными весами вместо нормировки или многоцелевой оптимизации.
Использовать долю правильных ответов (accuracy) на несбалансированных данных либо тестовый набор в функции приспособленности.
Не учитывать случайность обучения и выбирать «счастливый» шумовой выброс.
Сохранять слишком много элит, клонировать единственного победителя или выбирать чрезмерный турнир.
Считать одинаковые фенотипы повторно и не кэшировать детерминированные оценки.
Сравнивать методы по поколениям, а не по оценкам, времени и ресурсам.
Делать вывод по одному запуску без сопоставимой настройки конкурентов.

Когда ГА практически предпочтителен

ГА является обоснованным выбором, если одновременно выполняется несколько условий:

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

Если эти условия отсутствуют, сначала проверяют случайный поиск и предметную эвристику; для гладких весов — градиентный метод, для дорогой маломерной функции — байесовскую оптимизацию, для вещественного чёрного ящика — CMA-ES или дифференциальную эволюцию. Выбор следует подтверждать бюджетно-равным экспериментом, а не названием метода.

Практический протокол эксперимента

Сформулировать фенотип, ограничения, метрику и независимый тест до запуска поиска.
Выбрать генотип так, чтобы генетическое соседство соответствовало предметному.
Построить случайный поиск с тем же сэмплером как обязательную базовую линию.
Назначить общий бюджет оценок и вычислений; определить правила кэширования и ранней остановки.
Настроить $\mu$ , турнир, $p_c$ , $p_m$ и элитизм на отдельных задачах или внутри внешнего протокола, не на тесте.
Следить за лучшей и медианной приспособленностью, числом уникальных фенотипов, разнообразием, долей недопустимых потомков и временем оценки.
Выполнить независимые запуски с разными семенами; сообщить все заранее выбранные метрики и неопределённость.
Переобучить и переоценить финалистов на одинаковом бюджете; для NAS учитывать стоимость всего поиска, а не только финальной модели.

См. также

Примечания

Литература

Holland J. H. Adaptation in Natural and Artificial Systems. — Ann Arbor: University of Michigan Press, 1975. — ISBN 978-0-262-58111-0
Goldberg D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. — Reading, MA: Addison-Wesley, 1989. — ISBN 978-0-201-15767-3
Eiben A. E., Smith J. E. Introduction to Evolutionary Computing. — 2nd ed.. — Berlin: Springer, 2015.
Vose M. D. The Simple Genetic Algorithm: Foundations and Theory. — Cambridge, MA: MIT Press, 1999.
Deb K., Pratap A., Agarwal S., Meyarivan T. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation. — 2002. — Т. 6. — № 2. — С. 182—197.
Bäck T. H. W., Kononova A. V., van Stein B., Wang H., Antonov K. A., Kalkreuth R. T., de Nobel J., Vermetten D., de Winter R., Ye F. Evolutionary Algorithms for Parameter Optimization—Thirty Years Later // Evolutionary Computation. — 2023. — Т. 31. — № 2. — С. 81—122.
Lv Z., Qian C., Sun Y. A First Step Towards Runtime Analysis of Evolutionary Neural Architecture Search2024-04-08.

Источник — «http://recognition.su/wiki/index.php?title=%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B»