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

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

Вспомни урок 294 про методы нулевого порядка: там ты сравнивал поиск по сетке (grid search) и случайный поиск (random search) для подбора гиперпараметров модели. Поиск по сетке перебирает все комбинации по сетке — надёжно, но экспоненциально дорого с ростом числа гиперпараметров. Случайный поиск сэмплирует случайно — эффективнее в высоких размерностях, но каждая новая попытка никак не учитывает результаты предыдущих: удачную комбинацию learning_rate=0.01, max_depth=7 со счётом 0.94 он забывает точно так же, как неудачную с 0.61. Генетический алгоритм предлагает третий путь: он тоже стартует со случайной популяции комбинаций гиперпараметров, но затем обучается на собственной истории — скрещивает удачные комбинации между собой, слегка мутирует их и год за годом сдвигает популяцию в сторону более высокого фитнеса. Он не строит вероятностную модель поверхности качества, как байесовская оптимизация из урока 299, зато не требует ни градиента, ни предположений о гладкости функции — работает буквально с чёрным ящиком, будь то дискретные, непрерывные или смешанные гиперпараметры одновременно.

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

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

История

В 1975 году в Мичиганском университете вышла книга Джона Холланда (John H. Holland) «Adaptation in Natural and Artificial Systems» («Адаптация в естественных и искусственных системах») — работа, которую принято считать точкой рождения генетических алгоритмов как формальной дисциплины. Важная деталь, которую часто упускают: Холланд по образованию не был специалистом по оптимизации в привычном смысле — он занимался теорией адаптивных систем и хотел понять на математическом уровне, как вообще сложные адаптивные системы (от иммунной системы до экономики) обучаются реагировать на меняющуюся среду. Оптимизация функции была для него скорее частным, демонстрационным случаем куда более общей теории, чем самоцелью — отсюда и строгость, с которой он подошёл к формализации: именно Холланд первым доказал теорему шаблонов, о которой пойдёт речь дальше в этом уроке, — математическое обоснование того, почему популяция битовых строк действительно способна находить хорошие решения, а не просто случайно блуждать.

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

Настоящая волна практического интереса пришла позже, во второй половине 1980-х годов, когда вычислительные мощности наконец позволили гонять популяции из сотен и тысяч особей на протяжении сотен поколений за разумное время. Огромную роль здесь сыграл ученик Холланда Дэвид Голдберг (David E. Goldberg): его книга 1989 года «Genetic Algorithms in Search, Optimization, and Machine Learning» стала настольной для целого поколения инженеров и на десятилетия вперёд определила и обозначения, и учебные примеры (включая классическую задачу максимизации $f(x) = x^2$ на битовой строке — ты разберёшь её вариант в этом уроке), которыми до сих пор пользуются в курсах по эволюционным вычислениям. Голдберг применял генетические алгоритмы к вполне практическим инженерным задачам — например, к оптимизации управления газопроводными компрессорными станциями, — и именно этот прикладной успех убедил индустрию, что метод не остаётся лабораторной игрушкой.

Кодирование решения: хромосома как ДНК задачи

Интуиция

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

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

Хромосома. Пусть решение задачи описывается $n$ независимыми характеристиками. Хромосома особи — это упорядоченный набор $x = (g_1, g_2, \dots, g_n)$, где каждый ген $g_i$ принимает значение из некоторого допустимого алфавита (например, $\{0,1\}$ для битового кодирования или отрезка вещественных чисел $[a_i, b_i]$ для вещественного кодирования). Популяция $P(t) = \{x_1, x_2, \dots, x_m\}$ в поколении $t$ — это множество из $m$ таких хромосом, а фитнес-функция $f(x) \to \mathbb{R}$ ставит в соответствие каждой хромосоме число, показывающее, насколько хорошо закодированное ею решение справляется с задачей.

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

Примеры

Пример 1: битовая строка для числовой оптимизации. Пусть нужно максимизировать функцию $f(x) = x^2$ на целых числах $x \in [0, 31]$. Поскольку $31 = 2^5 - 1$, любое такое число однозначно кодируется пятью битами. Хромосома $x = 27$ в этом кодировании — это строка $11011$: старший бит слева отвечает за $2^4=16$, следующий — за $2^3=8$, и так далее, так что $16+8+0+2+1=27$. Каждый ген здесь — это один бит, а фитнес особи прямо вычисляется из декодированного числа: $f(11011) = 27^2 = 729$. Это тот самый учебный пример, который ты полностью разберёшь по шагам чуть дальше в этом уроке.

Пример 2: вещественный вектор для подбора гиперпараметров. Настраиваешь градиентный бустинг и хочешь подобрать сразу три гиперпараметра: скорость обучения, максимальную глубину дерева и число деревьев. Хромосома здесь — не битовая строка, а вектор вещественных и целых чисел: $x = (\text{learning\_rate},\ \text{max\_depth},\ \text{n\_estimators})$, например $x = (0{,}05,\ 7,\ 150)$. Фитнес — это точность (или AUC, или отрицательное значение функции потерь) модели с такими гиперпараметрами на валидационной выборке. Заметь принципиальное отличие от битового кодирования: здесь каждый ген живёт в своём собственном допустимом диапазоне ($\text{learning\_rate} \in [0{,}001, 0{,}3]$, $\text{max\_depth} \in \{2, \dots, 15\}$, $\text{n\_estimators} \in \{50, \dots, 500\}$), и операторы кроссовера с мутацией должны это уважать — иначе получится невалидная конфигурация модели.

Пример 3: битовая маска для отбора признаков. Есть датасет с 8 исходными и производными признаками, и ты хочешь автоматически найти, какое их подмножество даёт лучшую модель — задача комбинаторная, признаков может быть слишком много для полного перебора всех $2^8 = 256$ подмножеств вручную при дорогой модели (а при 30 признаках это уже больше миллиарда комбинаций). Хромосома здесь снова битовая строка длины 8, но семантика битов другая: $g_i = 1$ означает «включить признак $i$ в модель», $g_i = 0$ — «исключить». Хромосома $10110001$ означает: использовать признаки 1, 3, 4 и 8, отбросить остальные. Фитнес — качество модели, обученной именно на этом подмножестве признаков (возможно, со штрафом за число признаков, чтобы поощрять более простые модели).

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

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

Оператор кроссовера: как рождаются новые решения

Интуиция

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

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

Одноточечный кроссовер (single-point crossover). Для двух родительских хромосом длины $l$ случайно выбирается точка разреза $k \in \{1, \dots, l-1\}$. Первый потомок получает первые $k$ генов от первого родителя и оставшиеся $l-k$ генов от второго; второй потомок — наоборот.

Двухточечный кроссовер (two-point crossover). Случайно выбираются две точки разреза $k_1 < k_2$, хромосома делится на три сегмента. Потомки получаются обменом среднего сегмента между родителями, а крайние сегменты остаются как у «своего» родителя.

Равномерный кроссовер (uniform crossover). Для каждого гена $i$ независимо (обычно с вероятностью $0{,}5$) выбирается, от какого из двух родителей его унаследует первый потомок; второй потомок получает во всех этих позициях гены от другого родителя. Формально: генерируется случайная бинарная маска $m = (m_1, \dots, m_l)$, и $\text{потомок}_1[i] = \text{родитель}_1[i]$, если $m_i = 1$, иначе $\text{потомок}_1[i] = \text{родитель}_2[i]$.

Общее для всех трёх видов: оператор кроссовера применяется не всегда, а с некоторой вероятностью кроссовера $p_c$ (обычно $0{,}6$–$0{,}9$) — если испытание не сработало, потомки просто становятся копиями родителей без изменений.

Примеры

Пример 1: одноточечный кроссовер. Пусть родители — восьмибитные строки $P_1 = 11011010$ и $P_2 = 00110101$, точка разреза выбрана после 4-го гена. Тогда:

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

Пример 2: двухточечный кроссовер. Те же по духу родители $P_1 = 11011010$ и $P_2 = 00110101$, точки разреза — после 2-го и после 6-го гена, то есть меняется только средний сегмент (гены с 3-го по 6-й):

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

Пример 3: равномерный кроссовер. Родители $P_1 = 101101$ и $P_2 = 010010$, случайная маска $m = 101100$ (единица — берём ген от $P_1$, ноль — от $P_2$):

Обрати внимание: $\text{потомок}_1$ и $\text{потомок}_2$ на каждой позиции получили ровно те два значения, что были у родителей, просто в разной комбинации — а вот сама комбинация может «перемешать» гены гораздо сильнее, чем один или два разреза, потому что решение о происхождении каждого гена принимается независимо.

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

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

Оператор мутации и элитизм: баланс исследования и сохранения лучшего

Интуиция

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

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

Мутация (bit-flip mutation для битового кодирования). Каждый ген $g_i$ хромосомы независимо с вероятностью $p_m$ (обычно $p_m \approx 1/l$, где $l$ — длина хромосомы, то есть в среднем один бит на хромосому за поколение) инвертируется: $g_i \to 1 - g_i$.

Мутация для вещественного кодирования (гауссовская мутация). Ген $g_i \in \mathbb{R}$ с вероятностью $p_m$ получает добавку случайного шума: $g_i \to g_i + \delta$, где $\delta \sim \mathcal{N}(0, \sigma^2)$, после чего результат обрезается (clipping) до допустимого диапазона гена.

Элитизм. Пусть $P(t)$ — популяция поколения $t$, отсортированная по убыванию фитнеса. Элитизм порядка $k$ означает, что $k$ лучших особей $\{x_1, \dots, x_k\} \subset P(t)$ копируются в $P(t+1)$ без изменений, а оставшиеся $m - k$ мест заполняются потомками, полученными обычным циклом «селекция → кроссовер → мутация».

Примеры

Пример 1: bit-flip мутация на битовой строке. Хромосома $x = 11001010$ (длина $l=8$), вероятность мутации $p_m = 0{,}05$ на ген. Ожидаемое число мутировавших генов: $l \cdot p_m = 8 \cdot 0{,}05 = 0{,}4$ — то есть в среднем меньше одного бита за поколение, что и есть типичный разумный масштаб. Допустим, в конкретном испытании мутировал только 4-й ген (был $0$, стал $1$): новая хромосома — $11011010$. Всего один перевёрнутый бит может заметно сдвинуть декодированное число, если это старший разряд, или почти не изменить его, если разряд младший, — вероятность мутации не «целится» в важные позиции, она одинакова для всех.

Пример 2: гауссовская мутация на векторе гиперпараметров. Хромосома для подбора гиперпараметров: $x = (\text{learning\_rate}=0{,}05,\ \text{max\_depth}=7,\ \text{n\_estimators}=150)$. Применяем мутацию к первому гену с шумом $\mathcal{N}(0, \sigma=0{,}01)$: пусть случайно выпало $\delta = 0{,}008$, тогда новое значение $\text{learning\_rate} = 0{,}05 + 0{,}008 = 0{,}058$. Если бы шум оказался отрицательным и увёл значение ниже допустимого минимума (скажем, ниже $0{,}001$), реализация обрезала бы результат до границы диапазона — без такого клиппинга мутация может предложить физически бессмысленную конфигурацию модели.

Пример 3: почему без элитизма легко потерять лучшее решение. Пусть популяция из 4 особей имеет фитнес $\{90,\ 85,\ 95,\ 60\}$ — лучшая особь даёт 95. Допустим, при формировании нового поколения без элитизма лучшая особь не попала в число выбранных родителей (селекция стохастична, и с ненулевой вероятностью это случается — особенно при небольшой популяции), а всем четырём потомкам не повезло с кроссовером и мутацией, и их фитнес оказался $\{70,\ 80,\ 75,\ 65\}$. Без элитизма лучший результат, доступный алгоритму на следующем шаге, — уже не 95, а всего 80: алгоритм фактически откатился назад. С элитизмом порядка $k=1$ особь с фитнесом 95 копируется в следующее поколение без изменений независимо от того, как прошли селекция, кроссовер и мутация — новое поколение гарантированно содержит фитнес не хуже $\{95,\ 70,\ 80,\ 75\}$, и лучший результат за всю историю запуска никогда не уменьшается от поколения к поколению.

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

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

Полный пошаговый пример: три поколения эволюции на конкретных числах

Интуиция

Все определения выше складываются в цельную картину только тогда, когда видишь их одновременно в работе, шаг за шагом, на одних и тех же числах. Дальше — классическая учебная задача, восходящая к примерам из книги Голдберга: максимизировать $f(x) = x^2$ для целых $x$ на отрезке $[0, 31]$, где хромосома — это 5-битная битовая строка, кодирующая $x$ в двоичной системе. Популяция состоит из 4 особей, используется одноточечный кроссовер с вероятностью $p_c$, bit-flip мутация с малой вероятностью на ген и элитизм порядка $k=1$ (лучшая особь поколения всегда копируется без изменений). Задача выбрана предельно простой намеренно: на ней видно всю механику алгоритма, при этом все числа проверяются в уме или на бумаге.

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

Один шаг цикла генетического алгоритма. Дана популяция $P(t)$ из $m$ хромосом.

1. Вычислить $f(x)$ для каждой особи; найти среднее $\bar f(t)$ и максимум.
2. Сохранить $k$ лучших особей как элиту для $P(t+1)$.
3. Сформировать пул родителей селекцией, пропорциональной фитнесу (roulette wheel): ожидаемое число копий особи $x$ в пуле — $f(x)/\bar f(t)$.
4. Разбить пул на пары, применить кроссовер (с вероятностью $p_c$) и получить потомков.
5. Применить мутацию к потомкам (элита мутации не подвергается).
6. $P(t+1)$ = элита + отобранные потомки, заполняющие оставшиеся $m-k$ мест.

Примеры

Поколение 0 → поколение 1.

Стартовая популяция и её фитнес:

Суммарный фитнес $= 169+576+64+361=1170$, средний $\bar f(0) = 1170/4 = 292{,}5$, лучший результат — особь B с фитнесом $576$.

Ожидаемое число копий каждой особи в пуле родителей ($f(x)/\bar f(0)$): A — $169/292{,}5 \approx 0{,}58$; B — $576/292{,}5 \approx 1{,}97$; C — $64/292{,}5 \approx 0{,}22$; D — $361/292{,}5 \approx 1{,}23$. Особь C с почти нулевым ожидаемым числом копий в пул не попадает; реалистичный пул родителей: B, B, D, A.

Элитизм: особь B (11000, фитнес 576) копируется в следующее поколение без изменений.

Кроссовер, пара 1 (B, D), точка разреза после 2-го гена:

Кроссовер, пара 2 (B, A), точка разреза после 3-го гена:

Свободных мест, помимо элиты, всего три (популяция — 4 особи), а потомков получилось четыре — отбрасываем худшего, $\text{потомок}_4 = 12\ (144)$, и оставляем $\{27\ (729),\ 16\ (256),\ 25\ (625)\}$.

Мутация: применяем bit-flip с $p_m=0{,}05$ на ген к трём неэлитным потомкам ($3 \times 5 = 15$ генов, ожидаемое число мутаций $\approx 0{,}75$). Пусть мутировал один бит у особи $16 = 10000$ — 4-й ген перевернулся с $0$ на $1$: $10000 \to 10010 = 18\ (324)$.

Итог, поколение 1:

Суммарный фитнес $=576+729+625+324=2254$, средний $\bar f(1) = 563{,}5$ (был $292{,}5$), лучший результат — $729$ (был $576$). Уже за одно поколение и средний, и лучший фитнес заметно выросли.

Поколение 1 → поколение 2. Обозначим особей поколения 1 как $P_1=24\ (576)$, $P_2=27\ (729,\ \text{лучшая})$, $P_3=25\ (625)$, $P_4=18\ (324,\ \text{слабейшая})$. Ожидаемые числа копий относительно $\bar f(1)=563{,}5$: $P_1\approx1{,}02$, $P_2\approx1{,}29$, $P_3\approx1{,}11$, $P_4\approx0{,}58$ — слабейшая $P_4$ в пул родителей не проходит. Пул: $P_2, P_2, P_3, P_1$.

Элитизм: $P_2$ (11011, фитнес 729) копируется без изменений.

Кроссовер, пара 1 ($P_2$, $P_3$), точка разреза после 3-го гена: $P_2 = 110|11$, $P_3 = 110|01$ → $\text{потомок}_a = 110|01 = 25\ (625)$, $\text{потомок}_b = 110|11 = 27\ (729)$.

Кроссовер, пара 2 ($P_2$, $P_1$), точка разреза после 2-го гена: $P_2 = 11|011$, $P_1 = 11|000$ → $\text{потомок}_c = 11|000 = 24\ (576)$, $\text{потомок}_d = 11|011 = 27\ (729)$.

Из четырёх потомков $\{25\ (625),\ 27\ (729),\ 24\ (576),\ 27\ (729)\}$ отбрасываем худшего, $24\ (576)$, оставляем $\{25\ (625),\ 27\ (729),\ 27\ (729)\}$.

Мутация: из трёх неэлитных потомков мутировал один ген у особи $25=11001$ — 3-й ген перевернулся с $0$ на $1$: $11001 \to 11101 = 29\ (841)$.

Итог, поколение 2:

Суммарный фитнес $=729+729+729+841=3028$, средний $\bar f(2) = 757$ (был $563{,}5$), лучший результат — $841$ (был $729$). Сводная картина по всем трём поколениям:

Лучший результат ни разу не уменьшился — это прямое следствие элитизма — и он неуклонно приближается к истинному максимуму задачи: $x=31$ даёт $f(31)=961$.

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

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

Теорема шаблонов: почему хорошие строительные блоки побеждают

Интуиция

У наблюдательного человека к этому моменту должен появиться закономерный вопрос: генетический алгоритм явно оценивает фитнес лишь у нескольких особей за раз — в нашем примере всего у четырёх, — так почему же он ведёт себя умнее, чем случайный перебор? Ответ, который дал сам Холланд, звучит неожиданно: генетический алгоритм неявно оценивает не только сами хромосомы популяции, но и огромное число шаблонов (schemas) — частичных, не до конца определённых образцов вроде «строка начинается с $11$, а дальше неважно что». Каждая конкретная хромосома одновременно является представителем сразу многих таких шаблонов, и оценивая фитнес одной хромосомы, алгоритм косвенно получает информацию сразу обо всех шаблонах, которым она соответствует. Теорема шаблонов формализует интуицию «короткие шаблоны с высоким фитнесом имеют тенденцию встречаться в популяции всё чаще от поколения к поколению» — то есть объясняет, почему хорошие «строительные блоки» решения распространяются в популяции сами, без явного указания алгоритму, что именно в них хорошего.

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

Шаблон (schema) — это строка над алфавитом $\{0, 1, *\}$ той же длины $l$, что и хромосомы популяции, где $*$ означает «любое значение». Хромосома соответствует шаблону, если совпадает с ним во всех зафиксированных (не звёздочных) позициях. Порядок шаблона $o(H)$ — число зафиксированных позиций. Определяющая длина $\delta(H)$ — расстояние между первой и последней зафиксированной позицией.

Теорема шаблонов (Holland's Schema Theorem). Пусть $m(H, t)$ — число особей популяции $P(t)$, соответствующих шаблону $H$, $f(H)$ — средний фитнес этих особей, $\bar f(t)$ — средний фитнес всей популяции, $p_c$ — вероятность кроссовера, $p_m$ — вероятность мутации на ген, $l$ — длина хромосомы. Тогда ожидаемое число представителей шаблона $H$ в следующем поколении ограничено снизу:

$$E[m(H, t+1)] \;\geq\; m(H,t) \cdot \frac{f(H)}{\bar f(t)} \cdot \left[1 - p_c \cdot \frac{\delta(H)}{l-1} - o(H) \cdot p_m\right]$$

Смысл неравенства: число копий шаблона растёт пропорционально тому, насколько он лучше среднего по популяции ($f(H)/\bar f(t)$), но штрафуется двумя членами разрушения — кроссовер может разорвать длинный шаблон, разрезав хромосому между его зафиксированными позициями (штраф зависит от $\delta(H)$, определяющей длины), а мутация может случайно испортить любую из зафиксированных позиций (штраф зависит от $o(H)$, порядка шаблона). Отсюда прямой вывод: короткие, малопорядковые шаблоны выше среднего фитнеса почти не разрушаются и экспоненциально растут в числе представителей от поколения к поколению — именно их принято называть «строительными блоками» решения.

Примеры

Пример 1: порядок и определяющая длина конкретного шаблона. Возьмём шаблон $H = 11{*}{*}{*}$ для хромосом длины $l=5$. Зафиксированы позиции 1 и 2, значит порядок $o(H) = 2$. Определяющая длина — расстояние между первой и последней зафиксированной позицией: $\delta(H) = 2 - 1 = 1$. Это короткий шаблон низкого порядка — по теореме он почти не подвержен разрушению ни кроссовером (разрез должен попасть ровно между позициями 1 и 2, что при $l-1=4$ возможных точках разреза — лишь один шанс из четырёх), ни мутацией (нужно, чтобы мутировала одна из всего двух позиций).

Пример 2: численный расчёт коэффициента сохранения. Пусть $p_c = 0{,}6$, $p_m = 0{,}05$, $l=5$, шаблон $H=11{*}{*}{*}$ с $\delta(H)=1$, $o(H)=2$ (как в примере 1). Штрафующий множитель:

Даже с учётом риска разрушения кроссовером и мутацией, шаблон сохраняет $75\%$ своего «права на рост» — если он при этом хотя бы немного лучше среднего по фитнесу, число его представителей в следующем поколении в ожидании не падает, а растёт.

Пример 3: тот же шаблон на данных полного примера этого урока. Возьмём шаблон $H = 11{*}{*}{*}$ и посчитаем $m(H,t)$ по трём поколениям из предыдущего раздела. Поколение 0: соответствует только B ($11000$) — $m(H,0)=1$. Поколение 1: соответствуют элита $24=11000$, потомок $27=11011$ и потомок $25=11001$ — не соответствует лишь мутировавший $18=10010$ (начинается с $10$) — $m(H,1)=3$. Поколение 2: соответствуют все четыре особи, включая мутировавшую $29=11101$ (её первые два гена всё ещё $11$) — $m(H,2)=4$. Число представителей шаблона выросло $1 \to 3 \to 4$ — ровно то поведение, которое предсказывает теорема: короткий шаблон с фитнесом ощутимо выше среднего популяции (особи, начинающиеся с $11$, и есть кандидаты с наибольшим $x$, а значит и с наибольшим $f(x)=x^2$) закономерно распространяется по популяции без какого-либо явного указания алгоритму искать именно эту комбинацию битов.

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

Теорема шаблонов — это не просто красивая алгебра, а ответ на главный концептуальный вопрос о генетических алгоритмах: почему поиск, оценивающий явно лишь горстку особей за раз, ведёт себя не как случайный перебор, а как направленный процесс. Идея о том, что оценка одной хромосомы неявно даёт информацию сразу о множестве шаблонов, которым она соответствует, получила у Холланда название неявного параллелизма (implicit parallelism) — при явной оценке $m$ особей алгоритм полезно обрабатывает информацию о гораздо большем числе шаблонов одновременно. Именно на этом наблюдении строится гипотеза строительных блоков (building block hypothesis): генетический алгоритм ищет хорошее решение, комбинируя короткие, проверенные временем удачные фрагменты, а не собирая решение с нуля. У этой картины есть и честные ограничения — существуют специально сконструированные «обманчивые» (deceptive) задачи, где короткие шаблоны с высоким локальным фитнесом сознательно уводят поиск в сторону от глобального оптимума, и на таких задачах интуиция теоремы шаблонов работает против алгоритма, а не на него. Но для подавляющего большинства практических задач, включая подбор гиперпараметров и отбор признаков, именно эта склонность к распространению коротких удачных фрагментов — а не удача и не полный перебор — объясняет, почему генетический алгоритм на практике из поколения в поколение стабильно улучшает фитнес.

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

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

Задание 1: Запиши число $x=21$ в виде 5-битной хромосомы (как в примерах урока).

Задание 2: Для родителей $P_1 = 110101$ и $P_2 = 001011$ выполни одноточечный кроссовер с точкой разреза после 3-го гена.

Задание 3: Для родителей $P_1 = 11100110$ и $P_2 = 00011001$ выполни двухточечный кроссовер с точками разреза после 2-го и после 5-го гена.

Задание 4: Для родителей $P_1 = 1010$ и $P_2 = 0101$ и маски $m=1100$ вычисли $\text{потомок}_1$ равномерного кроссовера ($1$ в маске — берём ген от $P_1$, $0$ — от $P_2$).

Задание 5: Хромосома длины $l=10$, вероятность мутации на ген $p_m=0{,}02$. Вычисли ожидаемое число мутировавших генов.

Задание 6: Популяция из 5 особей имеет фитнес $\{40,\ 55,\ 90,\ 30,\ 70\}$. Опиши, что сделает элитизм порядка $k=2$ при переходе к следующему поколению.

Задание 7: Для хромосомы $x=15$ (5 бит, задача $f(x)=x^2$ на $[0,31]$) вычисли фитнес.

Задание 8: Популяция из трёх особей имеет фитнес $\{20,\ 50,\ 30\}$. Вычисли вероятность выбора каждой особи при рулеточной (фитнес-пропорциональной) селекции.

Задание 9: Запиши пример хромосомы для подбора двух гиперпараметров случайного леса: числа деревьев (n_estimators) в диапазоне $[50, 300]$ и максимальной глубины (max_depth) в диапазоне $[2, 20]$.

Задание 10: Объясни своими словами разницу между терминами «хромосома», «ген» и «аллель» на примере хромосомы $x=(0{,}05,\ 7,\ 150)$ из примера этого урока.

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

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

Задание 12: Какие из хромосом $\{11010,\ 10100,\ 11110,\ 01010,\ 11011\}$ соответствуют шаблону $H = 1{*}{*}1{*}$?

Задание 13: Вычисли порядок $o(H)$ и определяющую длину $\delta(H)$ шаблона $H = {*}1{*}{*}0{*}1$ (длина хромосомы $l=7$).

Задание 14: Для шаблона из задания 13 ($o(H)=3$, $\delta(H)=5$, $l=7$) вычисли штрафующий множитель теоремы шаблонов при $p_c=0{,}7$, $p_m=0{,}01$.

Задание 15: Объясни, как преждевременная сходимость связана с потерей разнообразия популяции, и почему увеличение $p_m$ — не единственный способ с ней бороться.

Задание 16: Популяция $\{A{:}90,\ B{:}60,\ C{:}85,\ D{:}75,\ E{:}95\}$. Проведи турнирную селекцию с размером турнира 3 для случайно выбранной тройки $\{B, D, E\}$: кто победит?

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

Задание 18: Популяция из 4 особей: фитнес $\{40,\ 120,\ 80,\ 160\}$. Вычисли ожидаемое число копий каждой особи в пуле родителей (фитнес-пропорциональная селекция).

Задание 19: Придумай свой числовой пример (популяция из 3 особей с разным фитнесом), на котором отсутствие элитизма приводит к потере лучшей на сегодня особи в следующем поколении.

Задание 20: Объясни компромисс между высокой $p_c$ и высокой $p_m$: что произойдёт с популяцией, если задать $p_c \approx 0$, $p_m \approx 0{,}5$?

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

Задание 21: Для непрерывной хромосомы $x=(\text{learning\_rate}=0{,}08,\ \text{subsample}=0{,}7)$ предложи, как выглядела бы гауссовская мутация с $\sigma=0{,}02$ для второго гена, если случайный шум оказался $\delta=-0{,}05$, а допустимый диапазон $\text{subsample}\in[0{,}5,\ 1{,}0]$.

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

Задание 23: Возьми свежую стартовую популяцию $\{A{=}00101\ (5),\ B{=}10110\ (22),\ C{=}01111\ (15),\ D{=}11001\ (25)\}$ для задачи $f(x)=x^2$. Вычисли фитнес каждой особи и найди лучшую.

Задание 24: Для условий задания 23 объясни, почему генетический алгоритм с большой вероятностью более выгоден, чем случайный поиск (random search) из урока 294, если фитнес-функция — это не $x^2$, а качество модели с несколькими взаимодействующими гиперпараметрами.

Задание 25: Выполни самостоятельно один полный шаг эволюции: популяция $\{01010\ (10,\ f{=}100),\ 11100\ (28,\ f{=}784),\ 00110\ (6,\ f{=}36),\ 10101\ (21,\ f{=}441)\}$, элитизм $k=1$, кроссовер пары (лучшая, вторая по фитнесу) с точкой разреза после 3-го гена. Найди элиту и потомков этой пары до мутации.

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

Задание 27: Сформулируй гипотезу строительных блоков (building block hypothesis) своими словами и укажи одно её известное ограничение.

Задание 28: Для задачи коммивояжёра (хромосома — перестановка городов) объясни, почему обычный одноточечный кроссовер битовых строк напрямую неприменим, и опиши на словах, чем его заменяют.

Задание 29: Для хромосомы длины $l$ над алфавитом $\{0,1\}$ вычисли общее число различных шаблонов (с учётом символа $*$), которым может соответствовать одна конкретная хромосома, для $l=5$.

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

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

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

Как выглядит: «Запустим GA подольше — и он точно найдёт лучшее возможное решение».

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

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

Ошибка 2. Задают слишком высокую вероятность мутации, рассуждая «больше разнообразия — всегда лучше».

Как выглядит: $p_m > 0{,}3$–$0{,}5$ на ген для битового кодирования.

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

Как правильно: для битового кодирования типичный разумный диапазон — $p_m \approx 1/l$ до нескольких процентов на ген; слишком высокая мутация разрушает удачные комбинации генов быстрее, чем кроссовер успевает их создавать, и алгоритм вырождается в почти случайный перебор.

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

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

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

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

Ошибка 4. Применяют стандартный одноточечный или равномерный кроссовер битовых строк к хромосомам-перестановкам (маршрут, порядок операций) без модификации.

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

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

Как правильно: для представлений с ограничениями (каждый ген встречается ровно один раз, сумма генов равна константе и так далее) обычный кроссовер почти наверняка создаёт невалидных потомков — нужны специализированные операторы, сохраняющие структуру, например Order Crossover (OX) или Partially Matched Crossover (PMX) для перестановок.

Ошибка 5. Путают гиперпараметры самого генетического алгоритма (размер популяции, $p_c$, $p_m$, $k$ элитизма) с гиперпараметрами модели, которую этот GA настраивает.

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

Почему возникает: конечная цель (гиперпараметры модели) заслоняет тот факт, что инструмент поиска (GA) сам требует настройки.

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

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

Как выглядит: «поставим популяцию 1000 вместо 50 — так надёжнее».

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

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

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

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

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

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

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

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

• В полном пошаговом примере этого урока средний фитнес популяции вырос с $292{,}5$ до $757$ за два поколения, а лучший результат монотонно вырос с $576$ до $841$ — конкретная иллюстрация того, как совместно работают все четыре компонента алгоритма.

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

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

• Гипотеза строительных блоков — не универсальный закон: на специально сконструированных обманчивых (deceptive) задачах короткие удачные шаблоны могут уводить поиск от глобального оптимума, а не к нему.

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

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

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

Этот урок напрямую опирается на урок 295, где были введены общие понятия эволюционных алгоритмов — популяция, фитнес-функция, цикл селекция → скрещивание → мутация. Без этой рамки было бы неясно, зачем вообще нужны конкретные операторы кроссовера и мутации, разобранные здесь на числах. Также пригодился урок 294 про методы нулевого порядка — именно там впервые прозвучало сравнение поиска по сетке и случайного поиска, относительно которого генетический алгоритм и позиционируется как третий, более «обучаемый» подход к подбору гиперпараметров чёрного ящика.

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

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

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

🎛 Подбор гиперпараметров моделей. Библиотеки вроде TPOT и DEAP используют генетические алгоритмы для автоматического подбора не только гиперпараметров, но и целых пайплайнов предобработки и моделирования — как альтернатива поиску по сетке и случайному поиску из урока 294, особенно когда гиперпараметры сильно взаимодействуют друг с другом.

🧩 Эволюционный отбор и конструирование признаков. Хромосома в виде битовой маски «использовать/не использовать признак» или более сложного кодирования комбинаций признаков (сумм, произведений, логарифмов существующих столбцов) позволяет автоматически искать полезные новые признаки и отбрасывать бесполезные, когда исходных признаков слишком много для ручного перебора.

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

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

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

• Книга Джона Холланда 1975 года, заложившая основы генетических алгоритмов, была принята научным сообществом далеко не сразу: по-настоящему массовый практический интерес к методу пришёл только во второй половине 1980-х годов, когда вычислительные мощности позволили гонять популяции из сотен особей на протяжении сотен поколений за разумное время — идея почти на десять лет опередила доступное железо.

• В 2006 году NASA использовало генетический алгоритм для проектирования формы антенны спутника ST5 — эволюция «вырастила» несимметричную, визуально странную конструкцию, которую вряд ли предложил бы инженер вручную, но она превзошла антенны обычной формы по требуемым характеристикам излучения; эта антенна стала одним из самых известных примеров эволюционного дизайна, реально полетевших в космос.

• В конце 1980-х исследователь Дэнни Хиллис (Danny Hillis) применил коэволюционный генетический алгоритм — где фитнес одной популяции зависел от результатов состязания с другой, постоянно эволюционирующей популяцией «противников», — к задаче поиска эффективных сортирующих сетей, и это позволило найти сети, использующие меньше операций сравнения, чем лучшие на тот момент результаты, полученные людьми вручную.

• Ученик и коллега исследователей школы Холланда, Джон Коза (John Koza), в 1992 году выпустил книгу, формально заложившую основы генетического программирования, — направления, где эволюционируют не векторы чисел, а деревья программного кода или формул; на нём и построены современные подходы к автоматической символьной регрессии.

• «Неявный параллелизм», о котором говорил Холланд в связи с теоремой шаблонов, — это утверждение, что генетический алгоритм с популяцией из $m$ особей неявно обрабатывает информацию о существенно большем числе шаблонов одновременно, хотя явно вычисляет фитнес лишь для $m$ хромосом за поколение; именно это наблюдение отличает генетический алгоритм от буквально случайного перебора той же мощности.

Лайфхаки

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

• Начинай с типичных стартовых значений: размер популяции $50$–$200$, $p_c \approx 0{,}6$–$0{,}9$, $p_m \approx 1/l$ для битового кодирования (или порядка нескольких процентов на ген для вещественного) — это не универсальные константы, но разумная отправная точка для первого эксперимента, прежде чем настраивать их под конкретную задачу.

• Всегда включай элитизм хотя бы порядка $k=1$: стоимость почти нулевая, а выгода — гарантия того, что лучшее найденное решение не потеряется из-за неудачного стечения случайностей в кроссовере или мутации, что особенно важно, когда одно вычисление фитнеса означает полное обучение модели.

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

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

• Если решение имеет структурные ограничения (перестановка, сумма компонент равна константе, взаимоисключающие значения), не пытайся применить стандартный битовый кроссовер и мутацию «в лоб» — либо используй специализированные операторы, сохраняющие валидность (Order Crossover, PMX и аналоги), либо добавь шаг «ремонта» (repair), который чинит невалидного потомка сразу после применения операторов.

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