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

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

Версия от 18:28, 19 июля 2026; Danial Zhumabekov (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Статья написана с использованием LLM Claude Sonnet 5 и проверена участником Д. Жумабеков 21:28, 19 июля 2026 (MSD)

Содержание

1 Введение
2 Историческая справка
3 Постановка задачи отбора признаков по внешнему критерию
4 Поиск в ширину (beam search) как переходный метод
5 Терминология эволюционного алгоритма
6 Генетические операторы
- 6.1 Скрещивание
- 6.2 Мутация
7 Эволюционный (генетический) алгоритм
8 Эвристики управления процессом эволюции
9 Смежные задачи, решаемые эволюционными алгоритмами
10 Сравнение с альтернативными методами дискретной оптимизации
11 Литература

Введение

Выбор структуры модели — числа и состава входящих в неё признаков, конфигурации базисных функций, топологии композиции — принципиально отличается от настройки числовых параметров уже фиксированной модели. Пространство поиска в задаче настройки параметров непрерывно, и минимум функционала качества может отыскиваться градиентными методами, использующими локальную информацию о производной. Пространство поиска в задаче выбора структуры, напротив, дискретно и комбинаторно: например, для задачи отбора признаков из общего набора $F$ , $|F|=n$ , каждое подмножество $J \subseteq F$ — отдельная точка пространства поиска, а таких точек $2^n$ . Понятие производной функционала качества по «направлению» в этом пространстве не определено, что делает градиентные методы неприменимыми в принципе, а не только вычислительно невыгодными.

Единственный точный способ решения такой задачи — полный перебор всех $2^n$ подмножеств — становится практически неосуществим уже при умеренных $n$ (десятки признаков дают число вариантов, на много порядков превышающее любые доступные вычислительные ресурсы). Эволюционный (генетический) алгоритм — представитель широкого класса методов случайного поиска с адаптацией, предлагающих альтернативу полному перебору^[1]: вместо исчерпывающего просмотра пространства поиска поддерживается конечная популяция кандидатных решений, которая на каждой итерации преобразуется операциями, стохастически смещающими её в сторону более качественных решений, при сохранении управляемого уровня случайного разнообразия, предотвращающего преждевременную сходимость к локальному, но не глобальному оптимуму.

Историческая справка

Задача отбора признаков и, шире, задача построения оптимальной по сложности модели по ограниченной выборке — центральная тема научной школы А. Г. Ивахненко, предложившего метод группового учёта аргументов (МГУА)^[1]. Ключевая идея МГУА — принцип самоорганизации моделей по внешнему критерию: вместо единственной модели, обучаемой по всей выборке и оцениваемой по той же выборке (что систематически завышает оценку качества сложных моделей), строится множество кандидатных моделей возрастающей сложности, и отбор среди них производится по внешнему критерию — вычисленному на данных, не участвовавших непосредственно в настройке параметров конкретной модели. Такая процедура выявляет оптимальную сложность модели как точку, в которой внешний критерий достигает минимума, тогда как внутренний критерий (ошибка на обучающих данных) продолжал бы монотонно улучшаться при неограниченном росте сложности.

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

Постановка задачи отбора признаков по внешнему критерию

Пусть $F$ — полный набор доступных признаков, $|F| = n$ , и для любого подмножества $J \subseteq F$ определена процедура обучения модели $a_J$ исключительно по признакам из $J$ . Внешний критерий $Q(J)$ — функционал качества модели $a_J$ , вычисленный на данных, не использованных при её обучении (например, по скользящему контролю или на отложенной контрольной выборке). Задача отбора признаков формулируется как задача дискретной оптимизации:

$Q(J) \to \min_{J \subseteq F}$

Принципиальная сложность этой задачи — не только комбинаторный рост числа вариантов с $n$ , но и немонотонность зависимости $Q(J)$ от числа отобранных признаков $|J|$ . При малом $|J|$ модель недообучена — доступной информации недостаточно для восстановления зависимости, и $Q(J)$ велико. По мере добавления информативных признаков $Q(J)$ , как правило, убывает. Однако после достижения некоторого оптимального объёма признакового описания дальнейшее добавление признаков — в первую очередь малоинформативных, шумовых или дублирующих уже включённые, — увеличивает эффективную сложность модели без пропорционального увеличения полезной информации, что приводит к переобучению и последующему росту внешнего критерия $Q(J)$ . Такая немонотонная, U-образная в типичном случае зависимость исключает применение методов, опирающихся на предположение о монотонности (например, последовательное наращивание признаков до первого ухудшения критерия не гарантирует нахождения глобального минимума), и мотивирует полноценный комбинаторный поиск по всему пространству подмножеств.

Поиск в ширину (beam search) как переходный метод

Промежуточным по вычислительной сложности между полным перебором и жадным пошаговым наращиванием служит усечённый поиск в ширину (beam search): на каждом шаге сохраняется не единственный текущий вариант, а $B$ лучших по критерию $Q$ кандидатов (луч ширины $B$ ); от каждого из них порождаются все допустимые расширения (добавление одного нового признака к уже отобранному подмножеству), из объединённого множества расширений вновь отбирается $B$ лучших, и процедура повторяется до заданной глубины или до отсутствия улучшения критерия. При $B=1$ метод вырождается в жадный пошаговый отбор признаков, при $B \to \infty$ приближается к полному перебору.

Этот метод — прямая формализация принципа неокончательных решений Габора применительно к многорядным алгоритмам МГУА: на каждом «ряду» селекции сохраняется ограниченное число $B$ частных моделей возрастающей сложности (частных подмножеств признаков или промежуточных полиномиальных членов), которые передаются на следующий ряд для дальнейшего комбинирования, вместо немедленного окончательного выбора единственной модели. Поиск в ширину, однако, остаётся в существенной мере локальным: набор кандидатов на очередном ряду порождается исключительно расширением кандидатов предыдущего ряда, что ограничивает исследуемую часть пространства подмножеств и мотивирует переход к эволюционному алгоритму, оперирующему популяцией решений произвольной, не обязательно монотонно растущей структуры.

Терминология эволюционного алгоритма

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

Индивидом называется одно кандидатное решение задачи — в задаче отбора признаков это конкретное подмножество $J \subseteq F$ . Хромосомой называется кодировка индивида в виде, пригодном для применения генетических операторов, — бинарный вектор $\beta = (\beta_1, \dots, \beta_n)$ , $\beta_j \in \{0,1\}$ , находящийся во взаимно однозначном соответствии с подмножеством:

$J(\beta) = \{ f_j \in F:\, \beta_j = 1 \}$

то есть ген $\beta_j$ хромосомы кодирует включение ( $\beta_j=1$ ) или исключение ( $\beta_j=0$ ) признака $f_j$ из отбираемого подмножества. Поколением (популяцией) называется конечный набор из $N$ хромосом $\beta^{(1)}, \dots, \beta^{(N)}$ , одновременно рассматриваемых на данной итерации алгоритма; смена поколений — переход от текущей популяции к новой посредством отбора и генетических операторов, рассматриваемых в следующем разделе.

Генетические операторы

Скрещивание

Скрещивание (кроссовер) порождает потомка на основе двух родительских хромосом $\beta'$ и $\beta''$ . Рассмотрим два способа его реализации.

Усредняющее скрещивание. Разыгрывается единственный случайный вес $\rho \sim \mathrm{Uniform}(0,1)$ , общий для всех генов хромосомы, и ген потомка получается взвешенным усреднением значений генов родителей с последующим округлением до ближайшего целого (бинаризацией):

$\beta_j = [\, \rho\, \beta'_j + (1-\rho)\, \beta''_j \geq 0{,}5 \,], \qquad j = 1, \dots, n$

При $\rho$ , близком к $0$ или $1$ , потомок практически совпадает с одним из родителей; при $\rho \approx 0{,}5$ потомок наследует ген от каждого родителя с сопоставимым вкладом (для различающихся генов $\beta'_j \neq \beta''_j$ результат бинаризации при $\rho=0{,}5$ требует отдельного правила разрешения неопределённости, например случайного выбора одного из родительских значений).

Одноточечное скрещивание. Разыгрывается точка разрыва $s$ , равномерно распределённая на множестве $\{1, \dots, n-1\}$ ; потомок наследует гены до точки разрыва от первого родителя, а после неё — от второго:

$\beta_j = \begin{cases} \beta'_j, & j \leq s \\ \beta''_j, & j > s \end{cases}$

В отличие от усредняющего варианта, одноточечное скрещивание не требует бинаризации: результат по построению остаётся корректной бинарной хромосомой. Частный случай этой схемы при $n$ точках разрыва, разыгрываемых независимо для каждого гена (ген наследуется от первого или второго родителя с вероятностью $0{,}5$ независимо от прочих генов), называется однородным скрещиванием и лучше подходит для задач без содержательного порядка признаков в хромосоме, тогда как одноточечное скрещивание предпочтительно, если соседние по индексу признаки содержательно связаны (например, получены из одного источника данных или являются последовательными во времени измерениями).

Мутация

Мутация вносит в хромосому потомка независимый от родителей случайный элемент, предотвращающий вырождение популяции в набор идентичных или близких друг к другу решений. Для каждого гена $\beta'_j$ хромосомы, полученной скрещиванием, независимо разыгрывается индикатор мутации $\rho_j \sim \mathrm{Bin}(p_m)$ — бернуллиевская случайная величина, принимающая значение $1$ с вероятностью $p_m$ (вероятность мутации одного гена) и значение $0$ с вероятностью $1-p_m$ . Итоговое значение гена после мутации:

$\beta_j = \rho_j (1 - \beta'_j) + (1 - \rho_j)\, \beta'_j$

При $\rho_j = 1$ (мутация произошла) формула даёт $\beta_j = 1-\beta'_j$ — инверсию гена: включённый признак исключается, исключённый — включается. При $\rho_j = 0$ (мутации не произошло) формула даёт $\beta_j = \beta'_j$ — ген сохраняется без изменений. Таким образом, приведённая формула — компактная запись стандартного побитового инвертирования с вероятностью $p_m$ на каждый ген, применительно к отбору признаков интерпретируемая как случайное включение ранее не рассматривавшегося признака или исключение уже отобранного, независимо от того, что определило исходный состав подмножества $J(\beta')$ .

Эволюционный (генетический) алгоритм

Вход: набор признаков $F$ , $|F|=n$ ; внешний критерий $Q(J)$ ; размер популяции $N$ ; вероятность мутации $p_m$ ; предельное число поколений без улучшения $d$ .

Выход: наилучшее найденное подмножество признаков $J^{*}$ .

Инициализировать популяцию $\beta^{(1)}, \dots, \beta^{(N)}$ случайными бинарными хромосомами (например, каждый ген независимо равен $1$ с фиксированной начальной вероятностью).
Вычислить $Q(J(\beta^{(k)}))$ для каждого индивида популяции; положить $J^{*}$ равным $J(\beta^{(k)})$ с наименьшим значением $Q$ ; счётчик поколений без улучшения $t \leftarrow 0$ .
Повторять:
1. Ранжировать текущую популяцию по возрастанию $Q$ .
2. Сформировать новое поколение размера :
  1. сохранить в новом поколении без изменений $e$ лучших индивидов текущей популяции (элитизм);
  2. для оставшихся $N-e$ позиций — выбрать пару родителей из текущей популяции (например, пропорционально рангу или турнирным отбором среди лучших индивидов), применить к ним операцию скрещивания и затем операцию мутации, поместить полученного потомка в новое поколение.
3. Вычислить $Q$ для всех новых индивидов поколения.
4. Если наименьшее значение $Q$ в новом поколении меньше значения $Q(J^{*})$ , обновить $J^{*}$ и обнулить $t \leftarrow 0$ ; иначе $t \leftarrow t+1$ .
5. Если $t \geq d$ , завершить цикл.
Вернуть $J^{*}$ .

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

Эвристики управления процессом эволюции

Адаптивная вероятность мутации. Вероятность $p_m$ не обязана оставаться постоянной на протяжении всего поиска: типичная стратегия — увеличивать $p_m$ по мере роста числа поколений без улучшения (сигнал приближающейся стагнации популяции) и уменьшать её после успешного улучшения $Q(J^{*})$ , возвращаясь к более консервативному, преимущественно эксплуатационному режиму поиска в окрестности уже найденного хорошего решения.
Накопление оценок информативности признаков. В процессе работы алгоритма для каждого признака $f_j$ может накапливаться статистика — например, среднее значение критерия $Q$ среди индивидов, включающих данный признак, по сравнению со средним значением среди индивидов, его не включающих. Такая статистика используется для смещения вероятностей инициализации и мутации в сторону более информативных признаков, ускоряя сходимость по сравнению с полностью равновероятными операторами.
Элитизм. Гарантированный перенос нескольких лучших индивидов текущего поколения в следующее без применения к ним генетических операторов (шаг 3.2.1 псевдокода) предотвращает случайную потерю уже найденного хорошего решения в результате неудачного скрещивания или мутации — без элитизма значение критерия для лучшего индивида популяции не гарантированно монотонно не возрастает от поколения к поколению.
Увеличение разнообразия при стагнации. При достижении порогового числа поколений без улучшения (до срабатывания основного критерия остановки $d$ ) применяется частичный или полный рестарт — замена существенной доли популяции новыми случайными индивидами либо резкое временное увеличение $p_m$ , — что позволяет алгоритму покинуть окрестность локального оптимума, в которой популяция преждевременно сконцентрировалась.
Островная модель эволюции. Вместо единственной популяции поддерживается несколько независимо эволюционирующих субпопуляций («островов»), между которыми с некоторой периодичностью происходит миграция — перенос нескольких лучших индивидов одного острова в другой. Такая схема поддерживает более высокое суммарное разнообразие генетического материала, чем единственная популяция того же общего размера, и допускает естественную параллелизацию вычислений по островам.

Смежные задачи, решаемые эволюционными алгоритмами

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

Более общее обобщение — генетическое программирование^[1], в котором индивидом служит не вектор фиксированной длины, а произвольное синтаксическое дерево, кодирующее программу или математическое выражение; операции скрещивания и мутации в этом случае определяются как обмен и случайная замена поддеревьев соответственно. Частный, но практически значимый случай генетического программирования — Символьная регрессия: поиск не параметров фиксированной функциональной формы, а самой этой формы (выражения из элементарных функций и арифметических операций), наилучшим образом приближающей зависимость по данным, с тем же внешним критерием качества, что и в задаче отбора признаков, но определённым на пространстве синтаксических выражений, а не на пространстве бинарных масок. Оба направления рассматриваются как обобщение единого эволюционного подхода, кодировка индивида в котором подбирается под структуру конкретного пространства поиска.

Сравнение с альтернативными методами дискретной оптимизации

Сопоставление методов дискретной оптимизации для отбора признаков
Критерий	Точный полный перебор	Поиск в глубину (жадный)	Стохастический локальный поиск	Эволюционный алгоритм
Вычислительная сложность	$O(2^n)$ — экспоненциальная, неприменима при больших $n$	$O(n^2)$ (для последовательного наращивания/удаления по одному признаку) — низкая	управляется числом итераций, независимо от $n$ в явном виде, но эффективность падает с ростом $n$	управляется размером популяции и числом поколений, масштабируется на большие $n$ лучше жадных методов за счёт более широкого охвата пространства
Гарантия глобального оптимума	даёт точный глобальный оптимум по построению	не даёт: чувствителен к немонотонности $Q(J)$ , легко застревает в первом локальном оптимуме	не даёт формальной гарантии, но допускает выход из локального оптимума за счёт случайных шагов и приёма ухудшающих решений с некоторой вероятностью	не даёт формальной гарантии; практическая близость к оптимуму определяется размером популяции, числом поколений и балансом операторов
Использование структуры популяции решений	отсутствует (перебираются одиночные решения)	отсутствует	как правило, отсутствует (одна текущая точка поиска) либо ограниченная память недавних решений	центральный механизм: одновременное параллельное исследование множества решений с обменом информацией через скрещивание
Типичная область применения	малое число признаков (единицы — первые десятки)	умеренное число признаков при доверии к приблизительной монотонности $Q(J)$	широкий класс комбинаторных задач без выраженной структуры пространства поиска	большое число признаков, немонотонная зависимость $Q(J)$ , наличие вычислительного бюджета на десятки-сотни поколений

Литература

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%AD%D0%B2%D0%BE%D0%BB%D1%8E%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC»

Категории: Методы оптимизации | Энциклопедия анализа данных | Эволюционные вычисления | Отбор признаков