🔴 Сложный ⏱️ 55 минут

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

📋 Содержание урока

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

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

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

Эта идея не осталась академической диковинкой. Сегодня она напрямую работает в двух важных направлениях современного машинного обучения. NeuroEvolution — это использование эволюционного поиска для подбора весов или даже целой архитектуры нейросети вместо обучения через обратное распространение ошибки: там, где среда даёт лишь итоговую награду за целый эпизод игры и невозможно продифференцировать её по параметрам политики (например, в некоторых задачах обучения с подкреплением с недифференцируемым или прерывистым сигналом), эволюционный поиск оказывается рабочей и иногда даже более устойчивой альтернативой градиентным методам. Neural Architecture Search (NAS) — это применение того же эволюционного принципа не к весам сети, а к самой её структуре: числу слоёв, типам операций, ширине каждого слоя — то есть к дискретным решениям, для которых понятие «градиент по архитектуре» попросту не определено.

В этом уроке — общем, обзорном — ты разберёшь, что объединяет всё многообразие эволюционных алгоритмов: биологическую аналогию и идею «выживания сильнейшего» применительно к оптимизации, понятия популяции и функции приспособленности, механизмы отбора родителей и полный цикл эволюционного поиска от инициализации до сходимости. Ты увидишь, почему эти методы относятся к семейству методов нулевого порядка из прошлого урока, и разберёшься в фундаментальном компромиссе между исследованием пространства решений и использованием уже найденных удачных областей. Следующий урок 296 углубится в конкретную и самую известную разновидность эволюционных алгоритмов — генетические алгоритмы с их битовыми строками, кроссовером и мутациями отдельных генов, — а этот урок закладывает общий фундамент, на котором держится вся семья: генетические алгоритмы, стратегии эволюции, эволюционное программирование, дифференциальная эволюция и десятки других вариаций одной и той же идеи.

История

Идея скрестить биологическую эволюцию с оптимизацией родилась практически одновременно и независимо в нескольких местах в 1960-х годах — редкий, но показательный случай, когда время для идеи явно назрело.

В Берлине в середине 1960-х годов студенты Технического университета Инго Рехенберг (Ingo Rechenberg) и Ханс-Пауль Швефель (Hans-Paul Schwefel) занимались вполне прикладной инженерной задачей: им нужно было подобрать форму изогнутой трубы или профиль сопла так, чтобы минимизировать сопротивление воздушному потоку в аэродинамической трубе. Аналитической формулы, связывающей форму детали с сопротивлением, не существовало — единственным источником информации был физический эксперимент: изготовить деталь, продуть её в трубе, замерить сопротивление. Рехенберг предложил не перебирать формы вручную, а генерировать их случайными вариациями вокруг текущей лучшей формы, оставлять лучший вариант и повторять процесс — по сути, ручную симуляцию «выживания сильнейшего» на одной родительской особи и одном потомке за раз. Так родились стратегии эволюции (evolution strategies, ES) — вероятно, самая ранняя формализованная разновидность эволюционных алгоритмов, изначально придуманная не для абстрактной оптимизации функций на бумаге, а для решения буквально осязаемой инженерной задачи методом проб и ошибок, организованных по эволюционному принципу.

Почти в то же самое время, но по другую сторону Атлантики, независимо развивалась другая ветвь той же идеи. В начале 1960-х годов американский инженер Лоуренс Фогель (Lawrence J. Fogel) работал над задачей прогнозирования последовательностей символов и предложил эволюционное программирование (evolutionary programming): вместо того чтобы эволюционировать числовые параметры формы, Фогель заставлял эволюционировать целые конечные автоматы — простые вычислительные машины, предсказывающие следующий символ последовательности по её истории. Популяция таких автоматов подвергалась случайным мутациям структуры (изменение переходов между состояниями), после чего лучшие по точности предсказания автоматы отбирались и мутировали дальше. Это было, по сути, одно из первых применений эволюционного подхода не просто к настройке чисел, а к эволюции самой структуры решения — идея, которая полвека спустя аукнется в том самом NAS, который упоминался во вступлении.

Третья, самая известная широкой публике ветвь эволюционных вычислений — генетические алгоритмы Джона Холланда — появится немного позже, в середине 1970-х годов, и станет темой следующего урока: именно она сегодня чаще всего всплывает в голове при словах «эволюционный алгоритм», хотя исторически она возникла позже стратегий эволюции и эволюционного программирования. Три эти линии развивались практически независимо друг от друга добрых два десятилетия, каждая со своими терминами и акцентами, пока в 1990-х годах исследовательское сообщество не осознало, что все они — вариации одной и той же общей схемы, и не объединило их под общим зонтичным названием «эволюционные вычисления» (evolutionary computation). Этот урок как раз и посвящён тому общему знаменателю, который Рехенберг, Швефель, Фогель и Холланд, каждый по-своему, открыли независимо.

Общая идея: биологическая аналогия и «выживание сильнейшего»

Интуиция

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

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

Формальное определение

Эволюционный алгоритм (evolutionary algorithm). Это класс итеративных методов стохастической оптимизации, которые поддерживают популяцию кандидатов-решений $P_t = \{x_1, x_2, \dots, x_\lambda\}$ на каждой итерации $t$ (называемой поколением), оценивают качество каждого кандидата через функцию приспособленности $f(x)$, и порождают следующее поколение $P_{t+1}$ применением к отобранным кандидатам операторов вариации — мутации (случайного локального изменения) и, опционально, рекомбинации (объединения характеристик нескольких родителей) — с систематическим смещением в сторону более приспособленных кандидатов, реализуемым оператором отбора (селекции).

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

Примеры

Пример 1: биологическая аналогия по пунктам. Проведи прямое соответствие между понятиями эволюционной биологии и оптимизации. Особь (organism) — это одно конкретное решение задачи, например конкретный набор гиперпараметров нейросети. Ген (gene) — одна изменяемая координата решения, например значение конкретного гиперпараметра. Генотип (genotype) — полное представление решения в том виде, в котором его обрабатывает алгоритм (вектор чисел, битовая строка). Приспособленность (fitness) особи в биологии — вероятность выжить и оставить потомство; в оптимизации — значение целевой функции на этом решении. Поколение (generation) в биологии — смена особей во времени; в оптимизации — одна итерация внешнего цикла алгоритма. Это прямое, почти буквальное соответствие и есть причина, по которой такие алгоритмы вообще называют «эволюционными», а не просто «популяционными методами стохастической оптимизации» (хотя по сути это было бы столь же точным названием).

Пример 2: где аналогия работает не буквально. Биологическая эволюция не имеет цели — она слепой процесс без заранее заданного критерия «лучше/хуже», кроме самого факта выживания и размножения в конкретной среде. Эволюционный алгоритм, напротив, всегда оптимизирует явно заданную человеком функцию приспособленности — то есть у него есть чёткая, заранее известная цель, которой у биологической эволюции никогда не было. Кроме того, биологическая эволюция работает на населении из миллиардов особей и миллионов поколений; типичный эволюционный алгоритм в машинном обучении оперирует популяцией из десятков-сотен кандидатов и десятками-сотнями поколений — счёт на много порядков скромнее. Аналогия полезна для интуиции, но не стоит требовать от неё буквального совпадения масштабов или механизмов — эволюционные алгоритмы заимствуют у биологии общую схему процесса, а не его детальную биохимию.

Пример 3: «выживание сильнейшего» на простом числовом примере. Пусть задача — максимизировать $f(x) = -(x-5)^2$ (единственный максимум в точке $x=5$, значение $0$). У тебя есть три кандидата: $x_1=2$ с приспособленностью $f(x_1) = -9$, $x_2=6$ с приспособленностью $f(x_2)=-1$, $x_3=9$ с приспособленностью $f(x_3)=-16$. «Выживание сильнейшего» здесь означает: $x_2$ — самый приспособленный из троих (его приспособленность ближе всего к нулю), значит именно вокруг него, а не вокруг $x_1$ или $x_3$, с наибольшей вероятностью будут построены новые кандидаты следующего поколения — например, $x_2' = 6 + \varepsilon$, где $\varepsilon$ — небольшое случайное отклонение (мутация). Ни одного градиента для этого решения не потребовалось — только сравнение трёх чисел между собой.

Почему это важно

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

Популяция решений и функция приспособленности

Интуиция

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

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

Формальное определение

Популяция (population). Множество $P_t = \{x_1, \dots, x_\lambda\}$ из $\lambda$ кандидатов-решений на поколении $t$, где каждый $x_i$ представлен в некотором закодированном виде (генотипе), подходящем для применения операторов мутации и рекомбинации — чаще всего это вектор вещественных чисел, битовая строка фиксированной длины или иная структура данных, соответствующая структуре решаемой задачи.

Функция приспособленности (fitness function) $f: X \to \mathbb{R}$ ставит в соответствие каждому кандидату-решению $x$ одно вещественное число, отражающее качество этого решения относительно цели оптимизации: чем выше приспособленность (в задаче максимизации) или чем ниже (если её трактуют как штраф в задаче минимизации), тем более «удачным» и «конкурентоспособным» считается кандидат при отборе родителей следующего поколения.

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

Примеры

Пример 1: кодирование решения под задачу. Для задачи настройки трёх гиперпараметров нейросети — скорости обучения $\eta \in (0, 1)$, числа слоёв $L \in \{1, \dots, 10\}$ и коэффициента регуляризации $\lambda \in (0, 1)$ — одна особь популяции естественно кодируется вектором из трёх чисел: $x = (\eta, L, \lambda)$, например $x = (0{,}003,\ 5,\ 0{,}01)$. Это и есть генотип конкретной особи: три «гена», каждый со своим допустимым диапазоном значений и своим типом (два вещественных, один целочисленный). Популяция из 20 особей — это просто список из 20 таких троек, каждая со своим набором значений.

Пример 2: разница между сырым значением и приспособленностью. Пусть цель — обучить модель классификации так, чтобы максимизировать точность (accuracy) на валидационной выборке, но при этом держать число параметров модели небольшим (чтобы она помещалась на мобильное устройство). Сырое значение точности для кандидата с архитектурой $x$ может быть $\text{acc}(x) = 0{,}94$ при 12 миллионах параметров. Если просто взять $f(x) = \text{acc}(x)$, эволюция быстро скатится к максимально большим сетям, игнорируя ограничение по размеру. Правильная функция приспособленности учитывает оба критерия сразу, например через штраф: $f(x) = \text{acc}(x) - \beta \cdot \dfrac{\text{params}(x)}{10^7}$, где $\beta$ — коэффициент, задающий, насколько сильно штрафуется каждый лишний миллион параметров. При $\beta = 0{,}02$ приспособленность той же особи составит $f(x) = 0{,}94 - 0{,}02 \cdot 1{,}2 = 0{,}94 - 0{,}024 = 0{,}916$ — сеть с меньшим числом параметров при той же точности получит более высокую приспособленность и будет иметь преимущество при отборе.

Пример 3: почему нельзя просто использовать отрицательную ошибку без осмысления масштаба. Пусть задача — минимизировать среднеквадратичную ошибку прогноза $\text{MSE}(x)$, а приспособленность определена наивно как $f(x) = -\text{MSE}(x)$. Для кандидата $x_1$ с $\text{MSE}=0{,}002$ приспособленность будет $-0{,}002$, а для кандидата $x_2$ с $\text{MSE}=1{,}5$ — приспособленность $-1{,}5$. Формально всё корректно: $x_1$ приспособленнее $x_2$. Проблема возникает при попытке использовать пропорциональный отбор (например, рулеточную селекцию из следующего раздела) напрямую на этих отрицательных числах — вероятность, пропорциональная отрицательному числу, не имеет смысла. Приспособленность в этом случае обычно сдвигают в положительную область, например $f'(x) = C - \text{MSE}(x)$ для некоторой достаточно большой константы $C$, чтобы все значения стали положительными и пригодными для расчёта пропорциональных вероятностей отбора.

Почему это важно

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

Операторы отбора: как выбрать родителей

Интуиция

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

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

Формальное определение

Турнирный отбор (tournament selection) с размером турнира $k$: из популяции $P_t$ случайным образом (обычно с возвращением) выбирается $k$ особей, и среди них побеждает та, у которой наибольшая приспособленность; победитель становится одним из родителей следующего поколения. Процедура повторяется независимо столько раз, сколько родителей требуется для формирования следующего поколения.

Рулеточный отбор (roulette wheel selection), он же отбор, пропорциональный приспособленности: вероятность выбрать особь $x_i$ в качестве родителя равна

$$p_i = \frac{f(x_i)}{\sum_{j=1}^{\lambda} f(x_j)}$$

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

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

Примеры

Пример 1: расчёт вероятностей рулеточного отбора. Пусть популяция из четырёх особей имеет приспособленности $f = [5, 15, 20, 10]$ (все положительны, ничего сдвигать не нужно). Сумма приспособленностей: $5+15+20+10 = 50$. Вероятности отбора: $p_1 = 5/50 = 0{,}1$, $p_2 = 15/50 = 0{,}3$, $p_3 = 20/50 = 0{,}4$, $p_4 = 10/50 = 0{,}2$. Самая приспособленная особь (третья) выбирается родителем в 4 раза чаще самой слабой (первой), но у первой всё же есть реальный шанс в 10% на каждый отдельный розыгрыш рулетки.

Пример 2: та же популяция, но с отрицательной приспособленностью, требующей сдвига. Вернись к популяции из раздела о полном цикле: $x = [1, 3, 10, 15]$ с приспособленностью $f(x) = -(x-7)^2$, дающей значения $[-36, -16, -9, -64]$. Напрямую делить на сумму нельзя — сумма отрицательна, а вероятности получатся отрицательными или больше единицы. Сдвинем все значения так, чтобы минимум стал положительным: добавим константу $65$ (на единицу больше модуля минимума), получив сдвинутую приспособленность $[29, 49, 56, 1]$. Сумма: $29+49+56+1=135$. Вероятности: $p_1 = 29/135 \approx 0{,}215$, $p_2 = 49/135 \approx 0{,}363$, $p_3 = 56/135 \approx 0{,}415$, $p_4 = 1/135 \approx 0{,}007$. Обрати внимание, насколько слабый шанс остался у худшей особи ($x=15$) после сдвига — константа сдвига напрямую влияет на итоговое распределение вероятностей и её выбор — не такая уж тривиальная деталь реализации.

Пример 3: сравнение силы отбора при разном размере турнира. Предположим, в популяции из $N=10$ особей есть ровно одна, безоговорочно лучшая по приспособленности, и она побеждает в любом турнире, в котором участвует (упрощающее, но полезное для интуиции допущение). При турнирах с возвращением вероятность того, что лучшая особь попадёт в случайно выбранную группу из $k$ участников хотя бы один раз, равна $P = 1 - \left(\dfrac{N-1}{N}\right)^k$. При $k=2$: $P = 1 - (0{,}9)^2 = 1 - 0{,}81 = 0{,}19$ — лучшая особь выигрывает конкретный розыгрыш турнира лишь в 19% случаев. При $k=5$: $P = 1 - (0{,}9)^5 = 1 - 0{,}590 = 0{,}41$ — уже 41%. Чем больше размер турнира, тем чаще побеждает действительно лучшая особь, а значит, тем сильнее популяция концентрируется вокруг текущих лидеров и тем быстрее теряет разнообразие остальных решений.

Почему это важно

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

Полный цикл эволюционного алгоритма

Интуиция

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

Формальное определение

Полный цикл эволюционного алгоритма.

  1. Инициализация. Сгенерировать стартовую популяцию $P_0$ из $\lambda$ случайных кандидатов-решений, обычно равномерно в допустимой области значений каждого гена.
  2. Оценка приспособленности. Вычислить $f(x_i)$ для каждого кандидата $x_i \in P_t$.
  3. Отбор. С помощью оператора отбора (турнирного, рулеточного или иного) выбрать особей, которые станут родителями для нового поколения, с вероятностью, смещённой в сторону более приспособленных.
  4. Создание нового поколения. Применить к отобранным родителям операторы вариации — мутацию (небольшое случайное изменение генов) и, опционально, рекомбинацию (объединение генов нескольких родителей в одного потомка) — чтобы получить новую популяцию $P_{t+1}$.
  5. Проверка критерия остановки. Если достигнут лимит поколений, приемлемое качество приспособленности или популяция перестала улучшаться — остановиться и вернуть лучшего найденного кандидата. Иначе — вернуться к шагу 2 с $t \leftarrow t+1$.
population = initialize_random(size=lambda)

for generation in range(max_generations):
    fitness = [evaluate(individual) for individual in population]

    if stopping_criterion_met(fitness):
        break

    parents = select(population, fitness)      # турнир или рулетка
    offspring = []
    for pair in pairs(parents):
        child = recombine(pair)                 # опционально
        child = mutate(child)                   # почти всегда
        offspring.append(child)

    population = offspring                      # новое поколение

return best_individual(population)

Обрати внимание на структуру цикла: шаги 2–4 повторяются столько раз, сколько отведено поколений, а вся «эволюционность» алгоритма сосредоточена именно в повторяющемся взаимодействии оценки и отбора — без него шаги 1 и 4 сами по себе были бы просто генератором случайных мутаций без какого-либо направленного улучшения.

Примеры

Пример 1: инициализация под конкретную задачу. Для оптимизации трёх гиперпараметров $\eta \in (0{,}0001,\ 0{,}1)$, $L \in \{1,\dots,10\}$, $\lambda_{\text{reg}} \in (0,\ 0{,}5)$ инициализация популяции из 30 особей означает генерацию 30 независимых троек, каждая координата которых взята равномерно случайно из своего диапазона: например, первая особь $x_1 = (0{,}013,\ 4,\ 0{,}21)$, вторая $x_2 = (0{,}0007,\ 9,\ 0{,}05)$, и так далее. Никакой предварительной логики «эти значения лучше» на этом шаге не закладывается сознательно — весь смысл случайной инициализации в том, чтобы стартовая популяция покрывала пространство поиска максимально широко, прежде чем отбор начнёт сужать её к удачным областям.

Пример 2: критерии остановки на практике. В реальных системах NAS цикл эволюции редко останавливают по абстрактному «пока не сойдётся» — вместо этого чаще всего используют жёсткий бюджет: фиксированное число поколений (например, 50) или фиксированный вычислительный бюджет (например, 2000 GPU-часов суммарно на обучение всех оценённых архитектур за весь прогон). Причина прагматична: каждая оценка приспособленности в NAS означает полное обучение нейросети, и позволить эволюции работать «пока сама не остановится» означало бы неконтролируемые и потенциально огромные вычислительные затраты — значит, критерий остановки часто определяется не математической сходимостью, а бюджетом.

Пример 3: полный числовой прогон игрушечной задачи на три поколения. Вернёмся к задаче максимизации $f(x) = -(x-7)^2$ (оптимум в $x=7$) с популяцией из четырёх целочисленных особей и турнирным отбором размера 2, арифметической рекомбинацией (усреднением с округлением) и редкой мутацией $\pm 1$.

Поколение 0. Популяция: $[1,\ 3,\ 10,\ 15]$. Приспособленность: $f(1)=-36$, $f(3)=-16$, $f(10)=-9$, $f(15)=-64$. Турнир $\{1,10\}$ → побеждает $10$; турнир $\{3,15\}$ → побеждает $3$; турнир $\{1,3\}$ → побеждает $3$; турнир $\{10,15\}$ → побеждает $10$. Родительские пары: $(10,3)$ и $(3,10)$. Рекомбинация первой пары с весами $0{,}5$ и $0{,}8$ даёт потомков $\text{round}(0{,}5{\cdot}10+0{,}5{\cdot}3)=7$ и $\text{round}(0{,}8{\cdot}10+0{,}2{\cdot}3)=9$. Рекомбинация второй пары с весами $0{,}4$ и $0{,}9$ даёт потомков $\text{round}(0{,}4{\cdot}3+0{,}6{\cdot}10)=7$ и $\text{round}(0{,}9{\cdot}3+0{,}1{\cdot}10)=4$. До мутации: $[7,\ 9,\ 7,\ 4]$. Применим мутацию к двум из них: $9 \to 8$, $4 \to 5$.

Поколение 1. Популяция: $[7,\ 8,\ 7,\ 5]$. Приспособленность: $f(7)=0$, $f(8)=-1$, $f(7)=0$, $f(5)=-4$. Лучшая приспособленность подскочила с $-9$ (лучшая в поколении 0) до $0$ — оптимум уже найден одной из особей! Турниры дают родителей $(7,7,8,7)$ в разных парах (лидирующие $x=7$ побеждают почти всегда). Рекомбинация пары $(7,7)$ даёт потомков $7$ и $7$ при любых весах (родители идентичны). Рекомбинация пары $(8,7)$ с весами $0{,}5$ и $0{,}3$ даёт $\text{round}(7{,}5)=8$ и $\text{round}(7{,}3)=7$. До мутации: $[7,\ 7,\ 8,\ 7]$. Мутация меняет первого потомка: $7 \to 6$.

Поколение 2. Популяция: $[6,\ 7,\ 8,\ 7]$. Приспособленность: $f(6)=-1$, $f(7)=0$, $f(8)=-1$, $f(7)=0$. Лучшая приспособленность осталась на оптимальном уровне $0$, а средняя приспособленность популяции выросла с $-1{,}25$ (поколение 1) до $-0{,}5$ (поколение 2) — популяция не только нашла оптимум, но и продолжает концентрироваться вокруг него, при этом мутация не даёт ей полностью схлопнуться в одну точку. За три поколения и всего $16$ вычислений приспособленности (по 4 на каждое из четырёх поколений, включая нулевое) алгоритм нашёл точный оптимум и удерживает популяцию рядом с ним.

Почему это важно

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

Эволюционные алгоритмы как методы нулевого порядка

Интуиция

Вспомни из прошлого урока: методы нулевого порядка — это методы, которые оптимизируют функцию, используя только её значения, без единой производной. Эволюционные алгоритмы — самый яркий и, вероятно, самый широко применяемый представитель этого класса в современном машинном обучении. Присмотрись внимательно к полному циклу из предыдущего раздела: ни на одном из пяти его шагов ни разу не потребовалось вычислить $\nabla f(x)$ — ни явно через аналитическую формулу, ни через автоматическое дифференцирование. Единственное, что действительно нужно на каждом шаге, — это способность вычислить одно число $f(x)$ для конкретного кандидата $x$. Всё остальное — сравнения этих чисел между собой (кто приспособленнее) и случайные операции над самими кандидатами (мутация, рекомбинация), не над градиентом.

Формальное определение

Свойство нулевого порядка эволюционных алгоритмов. Эволюционный алгоритм взаимодействует с целевой функцией исключительно через оракул значений $x \mapsto f(x)$ (black-box function evaluation) и не требует ни аналитического выражения функции, ни её дифференцируемости, ни даже непрерывности — единственное требование состоит в возможности вычислить $f(x)$ для произвольного допустимого $x$ и сравнить полученные значения между собой.

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

Примеры

Пример 1: почему в NAS градиент по архитектуре не определён. Архитектура нейросети описывается дискретными решениями: сколько слоёв использовать (целое число), какой тип операции применить в каждом блоке (свёртка $3\times3$, свёртка $5\times5$, пуллинг — категориальный выбор из конечного списка), сколько нейронов в слое (целое число). Понятие производной $\dfrac{\partial \text{accuracy}}{\partial (\text{тип операции})}$ математически не определено — «тип операции» не принадлежит непрерывному числовому пространству, по которому можно было бы брать предел отношения приращений. Единственное, что реально можно сделать с архитектурой, — это взять её целиком, обучить сеть с такой архитектурой на данных и получить одно число — точность на валидации. Это классический сценарий чёрного ящика, для которого методы нулевого порядка, включая эволюционные алгоритмы, — не просто один из вариантов, а фактически необходимость.

Пример 2: NeuroEvolution и обучение с подкреплением с недифференцируемой наградой. В некоторых задачах обучения с подкреплением сигнал награды приходит только в конце целого эпизода — например, итоговый счёт в игре — и связь между конкретными действиями политики на протяжении сотен шагов и этим финальным числом крайне непрямая, а среда (эмулятор игры, физический симулятор с недифференцируемыми столкновениями) может быть в принципе не дифференцируема по параметрам политики. Стратегии эволюции — прямые потомки идей Рехенберга и Швефеля — применяются здесь именно как оптимизаторы нулевого порядка: параметры политики (веса небольшой нейросети или вектор параметров) мутируются, каждая мутированная версия прогоняется через полный эпизод в среде, итоговая награда используется как приспособленность — ни одного обратного прохода через граф вычислений, ни одной производной по весам политики не требуется вовсе.

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

Почему это важно

Понимание эволюционных алгоритмов как частного случая методов нулевого порядка — это не просто теоретическая классификация ради красоты, а прямой практический ориентир: когда именно вообще стоит браться за эволюционный подход. Если целевая функция дифференцируема и её градиент доступен дёшево (как почти всегда при обучении весов обычной нейросети на размеченных данных) — методы первого порядка вроде Adam из урока 293 почти всегда быстрее и надёжнее сойдутся к хорошему решению, и городить вокруг них эволюционный поиск было бы неоправданной тратой вычислений. Эволюционные алгоритмы раскрывают свою силу именно там, где градиент недоступен в принципе — в дискретных архитектурных решениях NAS, в недифференцируемых средах NeuroEvolution, в конвейерах с непрозрачной внешней бизнес-логикой. Знание этой границы применимости избавляет от соблазна применять эволюцию «на всякий случай» там, где обычный градиентный метод справился бы на порядки быстрее.

Баланс исследования и использования

Интуиция

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

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

Формальное определение

Баланс исследования и использования (exploration–exploitation trade-off). Эффективность эволюционного поиска определяется соотношением между разнообразием популяции (её способностью представлять широкий спектр разных областей пространства решений — исследование) и концентрацией популяции вокруг текущих лучших найденных решений (её способностью уточнять и улучшать уже найденные удачные области — использование). Параметры отбора (сила селекционного давления) и вариации (интенсивность мутации, наличие и характер рекомбинации) — это рычаги, которыми алгоритм явно настраивает эту границу; ни одна фиксированная настройка не является оптимальной сразу для всех задач и для всех стадий одного и того же поиска.

Примеры

Пример 1: как размер турнира сдвигает баланс. В разделе про операторы отбора уже было показано, что при $N=10$ и допущении «лучшая особь всегда побеждает при участии» вероятность её выигрыша в одном розыгрыше турнира равна $19\%$ при $k=2$ и $41\%$ при $k=5$. Меньший турнир ($k=2$) означает более слабое селекционное давление — популяция сохраняет больше разнообразия дольше, склоняясь в сторону исследования. Больший турнир ($k=5$) означает более сильное давление — популяция быстрее концентрируется вокруг текущих лидеров, склоняясь в сторону использования, с риском преждевременной сходимости к неглобальному оптимуму, если он не единственный «холм» в пространстве решений.

Пример 2: адаптивная (самонастраивающаяся) мутация. Возьмём задачу оптимизации вещественного параметра, где на старте поиска разумно делать большие шаги мутации (например, $\pm 2{,}0$), чтобы быстро исследовать широкую область пространства, а ближе к найденному хорошему решению — делать шаги значительно мельче (например, $\pm 0{,}05$), чтобы точно настроить решение, не «перепрыгивая» через уже найденный узкий оптимум. Одна из идей, впервые предложенных ещё в стратегиях эволюции Рехенберга и Швефеля, — так называемое правило одной пятой (1/5 success rule): если доля успешных мутаций (тех, что улучшили приспособленность потомка по сравнению с родителем) за последние несколько поколений превышает $1/5$, размер шага мутации увеличивают (популяция явно ещё далека от оптимума и может позволить себе более смелое исследование), а если доля успешных мутаций падает ниже $1/5$ — шаг уменьшают (популяция уже близко к оптимуму, и грубые шаги только мешают точной настройке). Это конкретный, исторически ранний пример автоматической, самонастраивающейся балансировки exploration и exploitation прямо внутри алгоритма, без ручного вмешательства человека на каждом поколении.

Пример 3: наблюдаемое падение разнообразия в разобранном трёхпоколенческом примере. Пересмотри числовой пример полного цикла из предыдущего раздела: население поколения 0 было разбросано по значениям $[1, 3, 10, 15]$ — размах в 14 единиц. Уже к поколению 2 популяция сузилась до $[6, 7, 8, 7]$ — размах всего 2 единицы. Это яркая иллюстрация того, как за считаные поколения даже небольшая, но систематическая склонность отбора к лучшим особям резко сокращает разнообразие популяции — исследование почти полностью сменилось использованием. Для этой простой одномодальной задачи (у $f(x)=-(x-7)^2$ ровно один максимум) это отличный исход: нет риска пропустить более удачную область, потому что более удачной области попросту не существует. Но для многомодальной задачи с несколькими локальными максимумами то же самое быстрое сужение разнообразия обернулось бы риском застрять вокруг первого найденного, но не самого лучшего «холма», так и не исследовав остальные.

Почему это важно

Баланс исследования и использования — это не абстрактная теоретическая тонкость, а тот самый параметр, который на практике чаще всего определяет, найдёт эволюционный алгоритм действительно хорошее решение или застрянет в посредственном локальном оптимуме. В реальных системах NAS и NeuroEvolution с их дорогостоящей оценкой каждого отдельного кандидата (часы обучения на GPU за одну-единственную оценку приспособленности) цена ошибки в эту сторону особенно высока: слишком агрессивный отбор без достаточного исследования может «на автопилоте» довести систему до вполне рабочей, но далеко не лучшей из возможных архитектур, а обнаружить это можно только после того, как вычислительный бюджет уже потрачен. Именно поэтому практически ни одна серьёзная реализация эволюционного поиска не использует голый жёсткий отбор без какого-либо механизма поддержания разнообразия — элитизм, сохраняющий лучших без потерь, комбинируется с достаточно щедрой мутацией, а иногда и с явными техниками сохранения разнообразия популяции, о некоторых из которых пойдёт речь в следующем уроке про генетические алгоритмы.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Для задачи максимизации $f(x) = -(x-4)^2$ вычисли приспособленность трёх кандидатов: $x_1=1$, $x_2=4$, $x_3=7$. Какой кандидат самый приспособленный?

Задание 2: Опиши генотип одной особи для задачи оптимизации четырёх гиперпараметров модели градиентного бустинга: число деревьев (целое, 50–500), максимальная глубина (целое, 2–10), скорость обучения (вещественное, 0,001–0,3), доля признаков на дерево (вещественное, 0,3–1,0).

Задание 3: Популяция из пяти особей имеет приспособленности $f = [12, 8, 25, 3, 17]$. Какая особь самая приспособленная, а какая — самая слабая?

Задание 4: Для популяции с приспособленностями $f = [5, 15, 20, 10]$ вычисли вероятности отбора при рулеточной селекции.

Задание 5: В турнирном отборе с размером турнира $k=2$ случайно выбранная пара — особи с приспособленностью $-16$ и $-9$ (задача максимизации). Кто побеждает?

Задание 6: Родитель имеет значение гена $x=12$. Примени мутацию $\pm 1$, выбрав направление $+1$. Каково значение гена потомка?

Задание 7: Два родителя имеют значения гена $x_1=8$ и $x_2=20$. Примени арифметическую рекомбинацию (усреднение) для получения потомка.

Задание 8: Популяция состоит из 8 особей, и для формирования следующего поколения из 8 потомков используются пары родителей, каждая пара даёт двух потомков. Сколько пар родителей нужно отобрать?

Задание 9: Какие из перечисленных сценариев подходят для оптимизации эволюционным (нулевого порядка) алгоритмом, а какие лучше решать градиентным методом: (а) обучение весов обычной полносвязной сети на размеченных данных; (б) подбор дискретного числа слоёв и типа операций в архитектуре сети; (в) настройка весов политики агента, где награда приходит только в конце эпизода в недифференцируемой игровой среде?

Задание 10: Перечисли пять шагов полного цикла эволюционного алгоритма в правильном порядке.

Продвинутые задания (11–20)

Задание 11: В популяции из $N=20$ особей есть одна безоговорочно лучшая, побеждающая в любом турнире, где она участвует. Вычисли вероятность её победы в одном розыгрыше турнира с возвращением при $k=3$.

Задание 12: Для популяции с приспособленностями $f = [-20, -5, -30, -2]$ (задача максимизации) подбери сдвигающую константу и вычисли вероятности рулеточного отбора.

Задание 13: Продолжи числовой пример полного цикла из урока (поколение 2: $[6,7,8,7]$, приспособленность $f(x)=-(x-7)^2$ даёт $[-1,0,-1,0]$) на поколение 3, считая, что все четыре турнира выбирают особей с $x=7$ родителями, а рекомбинация и мутация не меняют значений. Что произойдёт с популяцией?

Задание 14: Объясни, почему элитизм (гарантированное сохранение лучшей найденной особи в следующем поколении без изменений) не даёт лучшему найденному значению приспособленности когда-либо ухудшаться от поколения к поколению.

Задание 15: Сравни селекционное давление турнирного отбора при $k=2$ и $k=8$ в популяции из $N=20$ (используя формулу из задания 11). Как это повлияет на скорость потери разнообразия популяции?

Задание 16: В задаче NAS архитектура кодируется как $x = (\text{num\_layers}, \text{filters\_per\_layer}, \text{activation\_type})$. Почему нельзя вычислить $\partial \, \text{accuracy} / \partial \, \text{activation\_type}$ и как это связано с необходимостью эволюционного подхода?

Задание 17: Стратегия эволюции использует правило одной пятой: если доля успешных мутаций за последние несколько поколений выше $1/5$, шаг мутации увеличивают, если ниже — уменьшают. За последние 20 мутаций 3 оказались успешными. Что должно произойти с шагом мутации?

Задание 18: Для оценки приспособленности в NAS нужно обучить сеть, что занимает 2 GPU-часа на одну особь. Популяция $\lambda=40$, эволюция идёт 25 поколений без переиспользования уже оценённых особей. Посчитай суммарные вычислительные затраты в GPU-часах.

Задание 19: Популяция потеряла разнообразие: все 30 особей отличаются друг от друга не более чем на 1% по каждому гену, а лучшая найденная приспособленность не улучшается уже 15 поколений подряд. Как это называется и какие два рычага можно применить для исправления?

Задание 20: Объясни своими словами разницу между рекомбинацией (кроссовером) и мутацией как операторами вариации.

Задания-челленджи (21–30)

Задание 21: Спроектируй функцию приспособленности для задачи NAS, где нужно одновременно максимизировать точность классификации и минимизировать задержку инференса на мобильном устройстве (в миллисекундах). Приведи конкретную формулу с коэффициентом.

Задание 22: Почему высокий шаг мутации помогает выбраться из локального оптимума, но одновременно рискует разрушить уже найденное хорошее решение? Приведи численный пример на функции с двумя локальными максимумами.

Задание 23: Сравни бюджет вычислений эволюционного алгоритма и случайного поиска (из предыдущего урока) при одинаковом суммарном числе оценок функции на дорогой задаче NAS. Почему эволюционный подход обычно эффективнее при том же бюджете?

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

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

Задание 26: В островной модели (island model) популяция делится на несколько изолированных подпопуляций, которые эволюционируют независимо, лишь изредка обмениваясь лучшими особями (миграция). Почему это помогает бороться с преждевременной сходимостью по сравнению с одной большой популяцией?

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

Задание 28: Почему в задачах с очень дорогой оценкой приспособленности (часы обучения нейросети на одну особь) особенно важно не делать популяцию слишком большой, и как это связано с общим компромиссом между шириной исследования и глубиной использования при ограниченном бюджете?

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

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

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

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

Как выглядит: «раз популяция большая и поколений много, эволюция точно найдёт лучшее решение».

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

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

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

Как выглядит: использовать одну лишь точность модели как приспособленность, забывая про ограничения на размер, задержку или иные требования.

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

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

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

Как выглядит: формула $p_i = f(x_i) / \sum_j f(x_j)$ применяется без проверки, что все $f(x_i)$ положительны.

Почему возникает: формула рулеточного отбора запоминается механически, а требование положительности значений часто не проговаривается явно при первом знакомстве с методом.

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

Ошибка 4. Считают, что чем сильнее селекционное давление (больше размер турнира, резче рулетка), тем алгоритм всегда лучше и быстрее находит хорошее решение.

Как выглядит: «поставим турнир размера 10 вместо 2, чтобы точно отбирались только лучшие».

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

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

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

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

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

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

Ошибка 6. Не отличают понятие «поколение» алгоритма от понятия «итерация» градиентного метода и путают их сравнимость по вычислительной стоимости.

Как выглядит: «эволюция сошлась за 20 поколений, а градиентный спуск потребовал 2000 итераций — значит, эволюция в сто раз эффективнее».

Почему возникает: сравнивается число внешних циклов алгоритмов без учёта того, что одно поколение эволюционного алгоритма требует $\lambda$ оценок приспособленности (а в NAS каждая такая оценка — это полное обучение целой сети), тогда как одна итерация градиентного спуска — это, как правило, всего один шаг по одной точке.

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

Главное запомнить

  • Эволюционные алгоритмы — семейство методов стохастической оптимизации, вдохновлённых биологической эволюцией: популяция кандидатов-решений улучшается через повторяющийся цикл отбора наиболее приспособленных и создания нового поколения через мутацию и рекомбинацию.

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

  • Функция приспособленности (fitness function) — прямой аналог целевой функции классической оптимизации; её корректное проектирование, включая учёт всех побочных ограничений задачи, критичнее для итогового результата, чем выбор конкретного оператора отбора.

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

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

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

  • Именно свойство нулевого порядка делает эволюционные алгоритмы естественным инструментом для NeuroEvolution (эволюционный поиск весов или архитектуры нейросети там, где градиент недоступен, например в недифференцируемых средах обучения с подкреплением) и для Neural Architecture Search (поиск дискретных архитектурных решений, для которых понятие градиента попросту не определено).

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

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

Связь с темами курса

Что нужно было знать до этого урока

Этот урок прямо продолжает урок 294 про методы нулевого порядка: без понимания того, что значит оптимизировать функцию, зная только её значения в отдельных точках (без единой производной), мотивация всего эволюционного подхода — «работать с чёрным ящиком приспособленности вместо градиента» — повисает в воздухе. Случайный поиск и метод Нелдера — Мида из того же урока — полезный контраст: они тоже методы нулевого порядка, но не используют популяцию и направленную вариацию, что и объясняет, почему на дорогих, сложно устроенных пространствах поиска (архитектуры сетей, политики агентов) эволюционные алгоритмы часто оказываются эффективнее.

Что изучить дальше

Следующий урок 296 переходит от общей идеи к самой известной и детально проработанной разновидности эволюционных алгоритмов — генетическим алгоритмам, предложенным Джоном Холландом. Ты увидишь конкретное битовое кодирование решений, конкретные операторы кроссовера (одноточечный, многоточечный, равномерный) и мутации отдельных битов, а также теоретический результат — теорему о схемах Холланда, — объясняющий математически, почему генетические алгоритмы вообще способны эффективно исследовать пространство поиска. Все понятия этого урока — популяция, приспособленность, отбор, полный цикл, баланс exploration/exploitation — останутся в силе и просто получат конкретную, детальную реализацию.

Где это нужно в жизни

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

🏗️ Neural Architecture Search (NAS). Поиск оптимальной архитектуры нейросети — числа слоёв, типов операций, ширины каждого блока — по своей природе дискретная, недифференцируемая задача; эволюционные алгоритмы (наряду с байесовской оптимизацией и обучением с подкреплением как альтернативными подходами к тому же поиску) — один из стандартных инструментов, которыми промышленные исследовательские команды находят архитектуры, конкурирующие с вручную спроектированными сетями.

⚙️ AutoML и автоматическая настройка конвейеров. За пределами отдельно взятой архитектуры сети эволюционные алгоритмы применяются для оптимизации целых конвейеров машинного обучения — выбора алгоритма предобработки, модели и её гиперпараметров одновременно, — там, где пространство решений смешанное (дискретные и непрерывные переменные сразу) и единой дифференцируемой формулы для всего конвейера не существует.

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

Интересные факты

  • Стратегии эволюции Рехенберга и Швефеля изначально проверялись не на компьютере, а буквально в аэродинамической трубе: исследователи вручную изготавливали физические детали разной формы, продували их и записывали сопротивление — первый в истории «прогон» эволюционного алгоритма занимал часы ручного труда на одну-единственную оценку приспособленности, а не миллисекунды вычислений.

  • Правило одной пятой (1/5 success rule), которым стратегии эволюции автоматически регулируют шаг мутации, было выведено Рехенбергом теоретически для двух простых модельных задач ещё в конце 1960-х годов — и, несмотря на свою простоту, тот же принцип самоадаптации шага в различных модификациях используется в современных вариантах эволюционных стратегий вплоть до наших дней.

  • OpenAI в 2017 году опубликовала исследование, показавшее, что стратегии эволюции — прямые потомки идей Рехенберга и Швефеля 1960-х годов — способны обучать нейросетевых агентов играть в сложные видеоигры почти так же эффективно, как современные градиентные методы обучения с подкреплением, при этом заметно лучше распараллеливаясь на тысячи вычислительных узлов, поскольку оценки приспособленности разных особей популяции полностью независимы друг от друга.

  • Лоуренс Фогель, один из создателей эволюционного программирования, ставил перед собой не узкую задачу оптимизации, а куда более амбициозную цель — создание искусственного интеллекта через эволюцию предсказывающих автоматов; сегодня, спустя более шестидесяти лет, задача предсказания последовательностей и генерация текста решается совершенно другими методами (трансформерами), но сама идея «эволюционировать структуру решения, а не только его параметры» напрямую предвосхитила современный Neural Architecture Search.

Лайфхаки

  • Прежде чем браться за эволюционный алгоритм, честно задай себе вопрос: доступен ли для этой задачи дешёвый градиент? Если да — начни с градиентного метода (Adam, L-BFGS) и переходи к эволюции только тогда, когда столкнёшься с реальной причиной недифференцируемости (дискретный выбор, недифференцируемая среда, чёрный ящик).

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

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

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

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

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

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

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!