Генетические алгоритмы: селекция, кроссовер, мутация

В предыдущей статье — https://courses.digitable.life/post/sbse/02-local-search/ — мы разобрали методы, которые двигают одно решение по ландшафту приспособленности. У них есть общая слабость: одна точка видит только свою окрестность. Имитация отжига борется с этим случайностью, tabu search — памятью, но обе всё равно идут одной траекторией, и на «изрезанном» ландшафте с тысячами локальных оптимумов это дорого.

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

Зачем нужна популяция: интуиция

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

Локальный поиск начинает с одной конфигурации и пробует переключать флаги по одному. Если удачная комбинация требует одновременного включения -flto и -fuse-linker-plugin, а по отдельности каждый из них ухудшает результат, hill climbing туда не дойдёт никогда: это дефект от эпистаза — взаимозависимости генов, при которой одиночные шаги ведут в яму.

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

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

Канонический цикл

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

Селекция: единственный источник давления отбора

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

Формально силу селекции измеряют давлением отбора (selection pressure). Полезная практическая мера — takeover time: за сколько поколений копии одной лучшей особи заполнят популяцию, если отключить кроссовер и мутацию. Для турнирной селекции с размером турнира k это примерно ln(N) / ln(k) поколений. При N = 100 и k = 2 — около 7 поколений, при k = 10 — около 2. Разница между «алгоритм успевает исследовать» и «алгоритм схлопнулся на третьем поколении».

Пропорциональная (рулеточная) селекция

Классика из книги Голдберга: вероятность выбрать особь i равна f(i) / Σf(j). Красиво, но в реальных задачах SBSE ломается по трём причинам.

Первая — чувствительность к сдвигу шкалы. Пусть фитнесы [1, 2, 3] — отношение шансов 1:2:3. Прибавим к целевой функции константу 1000 (например, поменяли «покрытие в долях» на «покрытие плюс базовая стоимость»): [1001, 1002, 1003] — шансы почти равны, отбор выродился в случайный. Целевая функция изменилась на константу, поведение алгоритма — до неузнаваемости.

Вторая — «супер-особь». Если одна особь имеет фитнес 500, а остальные 99 — по 1, она забирает 83% всех родительских слотов и захватывает популяцию за одно-два поколения.

Третья — не работает с минимизацией и отрицательными значениями без искусственных преобразований вроде f' = f_max − f, которые сами меняют давление отбора от поколения к поколению.

Смягчают это масштабированием (линейное scaling, sigma-scaling, Boltzmann selection), но каждое добавляет свой гиперпараметр.

Ранговая селекция

Сортируем популяцию и назначаем вероятность по рангу, а не по значению фитнеса. Линейное ранжирование: особь ранга r (0 — худшая, N−1 — лучшая) получает вес

w(r) = 2 − s + 2·(s − 1)·r / (N − 1),   s ∈ [1.0, 2.0]

Параметр s задаёт давление: при s = 1 все равны, при s = 2 лучшая получает вдвое больше среднего. Ранжирование убирает обе проблемы рулетки — оно инвариантно к монотонным преобразованиям фитнеса. Цена: сортировка O(N log N) на поколение и потеря информации о том, насколько одна особь лучше другой.

Турнирная селекция — практический выбор по умолчанию

Берём k случайных особей равновероятно, побеждает лучшая. Всё.

def tournament_select(pop, k, rnd):
    """Турнир размера k. O(k), не требует сортировки и нормировки."""
    best = rnd.choice(pop)
    for _ in range(k - 1):
        challenger = rnd.choice(pop)
        if challenger.fitness > best.fitness:
            best = challenger
    return best

Почему именно её используют в EvoSuite, GenProg, NSGA-II и почти во всём современном SBSE:

• Инвариантна к шкале. Нужен только оператор сравнения. Работает с минимизацией, отрицательными значениями, лексикографическими и Парето-сравнениями без изменений.
• O(k) на выбор, без сортировки и без суммирования по популяции — важно при N в тысячах.
• Давление настраивается одним понятным числом. k = 2 — мягко (типично для многокритериальных задач), k = 3…5 — рабочий диапазон, k ≥ 7 — агрессивно.
• Тривиально параллелится: турниры независимы.
• Вероятность, что худшая особь вообще не попадёт ни в один турнир, ненулевая — популяция сохраняет разнообразие лучше, чем при жадном отборе.

Ещё один аккуратный вариант — стохастическая универсальная выборка (SUS, Baker 1987): одна «рулетка» с N равноотстоящими указателями вместо N независимых бросков. Она даёт то же математическое ожидание, что и рулетка, но с минимальной дисперсией — особь с ожиданием 2.7 копий получит 2 или 3, но никогда 0 или 7. Если пропорциональная селекция всё же нужна, берите SUS, а не наивные N бросков.

Элитизм

Отдельно от селекции родителей стоит вопрос: гарантируем ли мы, что лучшая особь доживёт до следующего поколения. Без элитизма ГА не монотонен — лучшее решение может быть потеряно кроссовером и мутацией. Копирование 1–2 лучших особей без изменений (elitism) стоит почти ничего и превращает алгоритм в монотонный по лучшему найденному значению. Это буквально однострочная правка, которую забывают чаще всего.

Не путайте элитизм с высоким давлением отбора: e = 1 при k = 3 — здоровая конфигурация, e = 20 из 100 — уже почти детерминированный поиск.

Кроссовер: рекомбинация

Битовые строки

Одноточечный. Выбираем позицию разреза c, потомок 1 = префикс P1 + суффикс P2. Имеет позиционное смещение (positional bias): гены, стоящие рядом, почти всегда наследуются вместе, а гены с концов строки разрываются почти всегда. Если ваше кодирование не гарантирует, что связанные параметры лежат рядом (а обычно не гарантирует), это скрытое искажение.

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

Равномерный. Каждый ген независимо берётся от одного из родителей с p = 0.5. Никакого позиционного смещения, максимальная перемешивающая способность. Обратная сторона — разрушение длинных блоков: блок из 10 связанных генов переживает равномерный кроссовер с вероятностью 2⁻⁹. Если вы верите, что в вашей задаче есть длинные строительные блоки, берите двухточечный; если структура неизвестна или гены слабо связаны — равномерный.

def uniform_crossover(p1, p2, rnd):
    """Равномерный кроссовер: O(L) времени, O(L) памяти на потомка."""
    c1, c2 = list(p1), list(p2)
    for i in range(len(p1)):
        if rnd.random() < 0.5:
            c1[i], c2[i] = c2[i], c1[i]
    return c1, c2

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

Перестановки: почему нельзя брать одноточечный

Если хромосома — порядок выполнения тестов или маршрут, наивный кроссовер порождает невалидные особи: [1,2,3|4,5] × [5,4,3|2,1] → [1,2,3,2,1], где тест 2 идёт дважды, а 4 и 5 потеряны. Нужны операторы, сохраняющие перестановочность: PMX (partially mapped), OX (order), CX (cycle).

def pmx(p1, p2, rnd):
    """Partially Mapped Crossover. Гарантирует валидную перестановку. O(n^2) в этой
    наивной реализации из-за index(); на практике заменяется позиционным индексом до O(n)."""
    n = len(p1)
    a, b = sorted(rnd.sample(range(n), 2))
    child = [None] * n
    child[a:b + 1] = list(p1[a:b + 1])          # переносим сегмент первого родителя
    inside = set(child[a:b + 1])
    for i in range(a, b + 1):                    # разрешаем конфликты второго родителя
        v = p2[i]
        if v in inside:
            continue
        j = i
        while a <= j <= b:                       # идём по цепочке отображений
            j = list(p2).index(p1[j])
        child[j] = v
    for i in range(n):                           # остальное копируем как есть
        if child[i] is None:
            child[i] = p2[i]
    return child

Проверка на 2000 случайных парах даёт валидную перестановку в 100% случаев. Это тот тест, который стоит написать первым: самая частая ошибка в ГА — оператор, тихо порождающий невалидные особи, которые потом получают штрафной фитнес и незаметно отравляют популяцию.

Вещественные векторы: SBX

Для непрерывных параметров арифметическое усреднение (x1+x2)/2 катастрофично — оно схлопывает разнообразие за несколько поколений. Стандарт де-факто — SBX (Simulated Binary Crossover, Deb & Agrawal 1995), имитирующий поведение одноточечного кроссовера на двоичном коде:

def sbx(x1, x2, lo, hi, eta, rnd):
    """SBX. eta большой (20) — потомки жмутся к родителям, малый (2) — разлетаются."""
    u = rnd.random()
    beta = (2 * u) ** (1 / (eta + 1)) if u <= 0.5 else (1 / (2 * (1 - u))) ** (1 / (eta + 1))
    c1 = 0.5 * ((1 + beta) * x1 + (1 - beta) * x2)
    c2 = 0.5 * ((1 - beta) * x1 + (1 + beta) * x2)
    return min(max(c1, lo), hi), min(max(c2, lo), hi)

Ключевое свойство: среднее потомков равно среднему родителей (проверено численно: при родителях 2.0 и 8.0 и 10 000 прогонов среднее потомков = 5.00), но разброс сохраняется. eta = 20 — стандарт в NSGA-II, к которому мы вернёмся в https://courses.digitable.life/post/sbse/05-multi-objective/.

Теорема схем и её место

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

Относиться к этому стоит как к полезной интуиции, а не к доказательству эффективности. Теорема даёт нижнюю оценку только на одно поколение и не учитывает разрушение схем самой рекомбинацией; критика подробно разобрана у Whitley, «A Genetic Algorithm Tutorial» и в работах по «обманчивым» (deceptive) функциям, где ГА систематически сходится к худшему оптимуму. Практический вывод один и он конструктивный: проектируйте кодирование так, чтобы взаимозависимые параметры лежали в хромосоме рядом — см. https://courses.digitable.life/post/sbse/01-search-space-and-fitness/.

Мутация: страховка от вырождения

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

Стандартная ставка для битовых строк — p_m = 1/L, где L — длина хромосомы. При этом:

• ожидаемое число флипов на потомка равно ровно 1;
• вероятность, что потомок вообще не мутирует, равна (1 − 1/L)^L → 1/e ≈ 0.368.

То есть примерно 37% потомков проходят без изменений, а остальные получают в среднем небольшое возмущение. Это не случайное совпадение, а хорошо изученный компромисс: теория runtime-анализа ГА (Droste, Jansen, Wegener) показывает, что для функции OneMax 1/L даёт оптимальный порядок Θ(L log L) вычислений фитнеса.

Для вещественных генов используют гауссову мутацию x' = x + N(0, σ) (σ — доля диапазона, часто 0.1) или полиномиальную мутацию из семейства NSGA-II. Для деревьев и программ — свои операторы, о которых пойдёт речь в https://courses.digitable.life/post/sbse/04-genetic-programming/.

Типичные ошибки:

• p_m как вероятность на особь, а не на ген. Читаешь «p_m = 0.01», ставишь 0.01 на ген при L = 500 — получаешь 5 флипов на потомка, поиск превращается в случайное блуждание. Всегда явно фиксируйте семантику в имени переменной.
• Мутация без учёта границ. Значение уходит за допустимый диапазон, фитнес-функция либо падает, либо молча возвращает мусор. Всегда clamp или reflect.
• Слишком маленькая p_m «чтобы не портить хорошие решения». Ровно тот случай, когда ГА красиво сходится за 20 поколений и не улучшается следующие 500.

Замещение: кто доживёт до следующего поколения

Три основные схемы:

(μ + λ) по построению элитарна и потому склонна к преждевременной сходимости на многомодальных задачах; (μ, λ) намеренно «забывает» родителей, что помогает выбираться из локальных оптимумов — та же логика, что у имитации отжига в https://courses.digitable.life/post/sbse/02-local-search/.

Дублирование — незаметная проблема steady-state: без проверки на клонов популяция быстро набивается копиями одной особи, и N = 100 фактически превращается в N = 6. Дешёвое лекарство — не принимать потомка, генотипически идентичного кому-то из популяции (достаточно множества хешей).

Полная реализация: минимизация тестового набора

Возьмём настоящую задачу SBSE — test suite minimization. Дан набор из 60 тестов, каждый покрывает подмножество из 40 требований и имеет стоимость прогона. Нужно выбрать подмножество, покрывающее максимум требований при минимальной стоимости. Это NP-трудная задача (обобщение покрытия множества), и она идеально ложится на битовую хромосому: ген i = «включён ли тест i».

import random
from dataclasses import dataclass
from typing import Callable, List, Sequence

Genome = List[int]

@dataclass
class Individual:
    genome: Genome
    fitness: float = float("-inf")

@dataclass
class GAConfig:
    pop_size: int = 100
    generations: int = 300
    p_crossover: float = 0.9      # вероятность рекомбинации пары
    p_mutation: float | None = None   # None -> 1/L, каноническая ставка
    tournament_k: int = 3
    elitism: int = 2
    seed: int | None = None

def bitflip_mutate(g: Genome, p: float, rnd: random.Random) -> Genome:
    """Побитовая мутация: каждый ген независимо инвертируется с вероятностью p."""
    return [1 - bit if rnd.random() < p else bit for bit in g]

def run_ga(length: int, fitness: Callable[[Genome], float], cfg: GAConfig):
    rnd = random.Random(cfg.seed)
    p_mut = cfg.p_mutation if cfg.p_mutation is not None else 1.0 / length

    # --- инициализация: равномерно случайные особи ---
    pop = [Individual([rnd.randint(0, 1) for _ in range(length)]) for _ in range(cfg.pop_size)]
    for ind in pop:
        ind.fitness = fitness(ind.genome)
    evals = cfg.pop_size
    best = max(pop, key=lambda i: i.fitness)

    for _ in range(cfg.generations):
        pop.sort(key=lambda i: i.fitness, reverse=True)

        # --- элитизм: лучшие переходят без изменений и БЕЗ переоценки ---
        offspring = [Individual(list(pop[i].genome), pop[i].fitness) for i in range(cfg.elitism)]

        while len(offspring) < cfg.pop_size:
            p1 = tournament_select(pop, cfg.tournament_k, rnd)
            p2 = tournament_select(pop, cfg.tournament_k, rnd)
            if rnd.random() < cfg.p_crossover:
                g1, g2 = uniform_crossover(p1.genome, p2.genome, rnd)
            else:
                g1, g2 = list(p1.genome), list(p2.genome)   # клонируем без рекомбинации
            for g in (g1, g2):
                if len(offspring) < cfg.pop_size:
                    offspring.append(Individual(bitflip_mutate(g, p_mut, rnd)))

        # --- оценка только новых особей: элита уже посчитана ---
        for ind in offspring:
            if ind.fitness == float("-inf"):
                ind.fitness = fitness(ind.genome)
                evals += 1

        pop = offspring
        gen_best = max(pop, key=lambda i: i.fitness)
        if gen_best.fitness > best.fitness:
            best = Individual(list(gen_best.genome), gen_best.fitness)

    return best, evals

Фитнес-функция — скаляризация двух целей с весом (о том, почему это компромисс и когда лучше честный Парето-подход, — в https://courses.digitable.life/post/sbse/05-multi-objective/):

def make_fitness(coverage, cost, n_reqs):
    """coverage[i] — множество требований, покрываемых тестом i; cost[i] — стоимость."""
    total_cost = sum(cost)

    def fitness(g: Genome) -> float:
        covered, c = set(), 0.0
        for i, bit in enumerate(g):
            if bit:
                covered |= coverage[i]
                c += cost[i]
        # покрытие максимизируем, нормированную стоимость штрафуем с весом 0.3
        return len(covered) / n_reqs - 0.3 * (c / total_cost)

    return fitness

Реальный прогон (seed=42, 60 тестов, 40 требований, 300 поколений):

fitness=0.9779  tests=9/60  coverage=40/40  cost=11.3/153.1  evals=29500
случайный поиск при том же бюджете 29500 оценок: 0.9234

ГА нашёл 9 тестов из 60, покрывающих все 40 требований за 7% исходной стоимости. Случайный поиск при том же числе вычислений фитнеса застрял на 0.9234. Этот замер — обязательный ритуал: если ваш ГА не бьёт случайный поиск при равном бюджете, он не работает, и почти всегда виновата фитнес-функция, а не операторы (см. https://courses.digitable.life/post/sbse/01-search-space-and-fitness/).

Сложность

Пусть N — размер популяции, G — число поколений, L — длина хромосомы, C_f — стоимость одной оценки фитнеса.

• Время: O(G · (N · C_f + N · L + N log N)). Слагаемое N log N — сортировка для элитизма (убирается частичной выборкой за O(N)), N · L — операторы.
• На практике доминирует G · N · C_f. В SBSE C_f — это компиляция, запуск тестов, прогон инструментированного бинаря: миллисекунды в лучшем случае, минуты в худшем. Всё остальное — шум.
• Память: O(N · L) — две популяции одновременно.

Отсюда следуют все практические оптимизации: кэшировать фитнес (мемоизация по хешу генома — в задачах с дискретным кодированием повторы составляют 20–60% оценок), не переоценивать элиту, инкрементально пересчитывать фитнес там, где мутация затронула один ген, и параллелить оценку поколения — N оценок независимы, что даёт почти линейное ускорение до N ядер.

Настройка параметров

Разумные стартовые значения, подтверждённые эмпирикой SBSE:

Главный совет по настройке: сравнивайте конфигурации по числу вычислений фитнеса, а не по числу поколений, иначе N = 500 «выиграет» у N = 50 просто потому, что потратил в 10 раз больше ресурсов. И поскольку ГА стохастичен, любое сравнение требует 30+ независимых прогонов с разными seed и непараметрического статистического теста (Манна — Уитни) с оценкой величины эффекта (Vargha — Delaney Â₁₂) — это методологический стандарт, описанный в Arcuri & Briand, «A Hitchhiker’s Guide to Statistical Tests for Assessing Randomized Algorithms in Software Engineering». Один прогон не доказывает ничего.

Диагностика: преждевременная сходимость

Самая частая патология ГА — популяция схлопывается в клонов задолго до исчерпания бюджета. Симптом виден по метрике разнообразия, а не по фитнесу:

import math

def population_entropy(pop) -> float:
    """Средняя по генам энтропия Шеннона для битовых хромосом.
    1.0 — максимальное разнообразие, 0.0 — все особи идентичны. O(N*L)."""
    n, L = len(pop), len(pop[0])
    total = 0.0
    for j in range(L):
        p1 = sum(ind[j] for ind in pop) / n
        p0 = 1.0 - p1
        for p in (p0, p1):
            if p > 0:
                total -= p * math.log2(p)
    return total / L

Замеры: случайная популяция даёт 0.989, полностью сошедшаяся — 0.000, два разошедшихся кластера — 1.000. Логируйте эту величину каждое поколение рядом с лучшим и средним фитнесом. Падение энтропии ниже ~0.2 при неулучшающемся лучшем фитнесе — сигнал, что дальнейшие поколения бесполезны.

Что делать:

1. Снизить давление отбора — уменьшить k, уменьшить элитизм.
2. Fitness sharing / crowding — штрафовать особей за близость к другим, искусственно поддерживая ниши.
3. Рестарт — сохранить лучшего, перегенерировать остальных случайно. Грубо, но часто эффективнее тонких методов.
4. Островная модель — самое надёжное средство.

Островная модель

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

Островная модель — редкий случай, когда параллелизм не просто ускоряет, а улучшает качество поиска: изоляция сохраняет разнообразие, которого одна большая популяция того же суммарного размера не удержала бы. Типичные настройки: интервал миграции 10–50 поколений, доля мигрантов 2–10%, топология «кольцо».

Типичные ошибки

1. Нет элитизма. Лучшее решение теряется, кривая сходимости «прыгает». Одна строчка кода лечит.
2. p_m на особь вместо гена. Ошибка чтения статьи, превращающая ГА в случайный поиск.
3. Кроссовер, порождающий невалидные особи. Особенно с перестановками и деревьями. Пишите property-based тест: «потомок любых двух валидных родителей валиден».
4. Сравнение по поколениям, а не по бюджету оценок. Систематически завышает оценку больших популяций.
5. Один прогон вместо 30. ГА стохастичен; без статистики выводы не имеют смысла.
6. Плоский фитнес. «Тест упал / не упал» — 0 и 1, градиента нет, ГА вырождается в случайный поиск. Нужен непрерывный сигнал вроде branch distance — https://courses.digitable.life/post/sbse/01-search-space-and-fitness/.
7. Переоценка детерминированного фитнеса у элиты. Впустую сжигает бюджет, иногда десятки процентов.
8. Отсутствие кэша фитнеса при дискретном кодировании, где повторы неизбежны.
9. Ручной тюнинг «на глазок» на одном экземпляре задачи. Параметры переобучаются под конкретный бенчмарк и разваливаются на реальных данных.
10. Игнорирование дублей в steady-state — эффективный размер популяции падает в разы.

Как это применяют в проде

• EvoSuite — генерация JUnit-тестов для Java. Использует ГА с турнирной селекцией и специализированным представлением (хромосома — набор тестов переменной длины). Ключевой сдвиг последних лет — переход от «один ГА на одну цель покрытия» к whole test suite generation, оптимизирующему покрытие всех ветвей сразу. Детали — в https://courses.digitable.life/post/sbse/07-test-generation/.
• GenProg — автоматическое исправление программ. Хромосома — последовательность правок AST, фитнес — доля прошедших тестов. Подробно в https://courses.digitable.life/post/sbse/08-automated-program-repair/.
• Sapienz (Meta) — многокритериальный поиск последовательностей UI-событий для Android; работает на продовой инфраструктуре Meta и находит падения до релиза. Статья ISSTA 2016.
• Приоритизация регрессионных тестов — упорядочить прогон так, чтобы дефекты находились раньше. Хромосома-перестановка, метрика APFD, кроссоверы PMX/OX — ровно то, что мы разобрали выше.
• Поиск гиперпараметров и конфигураций — от флагов компилятора до настроек JVM; здесь ГА конкурирует с байесовской оптимизацией и часто выигрывает на дискретных пространствах с большим числом взаимозависимых параметров.

Практический совет по инструментам: не пишите ГА с нуля для продовой задачи. Возьмите DEAP или jMetalPy на Python, jMetal на Java. Написать свой ГА полезно ровно один раз — чтобы понять, что происходит внутри, как мы и сделали выше.

Мини-итог

• ГА ведёт поиск популяцией и добавляет к арсеналу рекомбинацию — операцию, недоступную методам локального поиска.
• Селекция — единственный источник давления отбора. Турнирная селекция с k = 3 — разумный дефолт: инвариантна к шкале фитнеса, O(k), один понятный параметр.
• Кроссовер эксплуатирует найденное, мутация исследует и страхует от необратимой потери аллелей. Стандарт: p_c ≈ 0.9, p_m = 1/L на ген.
• Элитизм обязателен — иначе алгоритм не монотонен.
• Стоимость — O(G · N · C_f), и в SBSE всё определяется C_f. Отсюда кэширование, отказ от переоценки элиты и параллелизм.
• Главный враг — преждевременная сходимость. Измеряйте разнообразие (энтропия популяции), а не только фитнес; лечите островной моделью, снижением давления, рестартом.
• Любое утверждение «стало лучше» доказывается 30+ прогонами и статистическим тестом при равном бюджете оценок.

Источники

• Holland J. H. Adaptation in Natural and Artificial Systems, 1975 — первоисточник.
• Goldberg D. E. Genetic Algorithms in Search, Optimization and Machine Learning, 1989 — классический учебник.
• Eiben A. E., Smith J. E. Introduction to Evolutionary Computing, 2-е изд., 2015 — лучший современный учебник; страница книги.
• Whitley D. A Genetic Algorithm Tutorial — PDF, в том числе трезвая критика теоремы схем.
• Deb K., Agrawal R. B. Simulated Binary Crossover for Continuous Search Space, 1995.
• Arcuri A., Briand L. A Hitchhiker’s Guide to Statistical Tests…, STVR 2014 — DOI.
• Harman M., Mansouri S. A., Zhang Y. Search-Based Software Engineering: Trends, Techniques and Applications, ACM Computing Surveys 2012 — DOI.
• Документация DEAP и jMetal.

Что дальше

Мы работали с хромосомами фиксированной длины — битовыми строками, векторами, перестановками. Но что, если решением должна быть сама программа — выражение, формула, дерево вызовов переменного размера? Тогда одноточечный кроссовер и bit-flip мутация неприменимы, и нужны операторы, работающие с древовидными структурами.

Об этом — следующая статья: Генетическое программирование.