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

Генетический алгоритм имитирует эволюцию: популяция решений скрещивается, мутирует и отбирается, постепенно становясь всё лучше.

Генетический алгоритм (ГА) — метаэвристика, эволюционирующая популяцию решений через отбор, скрещивание (кроссовер) и мутацию, направляя её к оптимуму.

Дарвин на службе оптимизации

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

Словарь эволюции

Цикл ГА

Один шаг эволюции: (1) оценить fitness всех особей; (2) отбор — выбрать родителей (турнир: берём двух случайных, побеждает приспособленный); (3) кроссовер — разрезать хромосомы родителей и склеить крест-накрест; (4) мутация — с малой вероятностью перевернуть случайный бит; (5) собрать новое поколение. Повторять.

Реализация: максимизация функции

Найдём $\max f(x)=-(x-3)^2+10$ по целым $x\in[0,31]$, кодируя $x$ пятью битами. Оптимум очевиден ($x=3$, $f=10$) — это позволяет проверить, что ГА его находит.

import random

def fitness(x):
    return -(x - 3) ** 2 + 10
def decode(bits):
    return int("".join(str(b) for b in bits), 2)

random.seed(7)
POP, GENES = 8, 5
pop = [[random.randint(0, 1) for _ in range(GENES)] for _ in range(POP)]

def select(pop):
    a, b = random.sample(pop, 2)
    return a if fitness(decode(a)) > fitness(decode(b)) else b

for gen in range(1, 16):
    pop.sort(key=lambda b: -fitness(decode(b)))
    if gen in (1, 5, 10, 15):
        best = pop[0]
        print(f"поколение {gen:2d}: лучший x={decode(best)} f={fitness(decode(best))}")
    new = [pop[0]]                       # элитизм
    while len(new) < POP:
        p1, p2 = select(pop), select(pop)
        cut = random.randint(1, GENES - 1)
        child = p1[:cut] + p2[cut:]      # кроссовер
        if random.random() < 0.2:        # мутация
            m = random.randint(0, GENES - 1)
            child[m] ^= 1
        new.append(child)
    pop = new

pop.sort(key=lambda b: -fitness(decode(b)))
print("Итог: x =", decode(pop[0]), " f =", fitness(decode(pop[0])))

Вывод:

поколение  1: лучший x=1 f=6
поколение  5: лучший x=1 f=6
поколение 10: лучший x=3 f=10
поколение 15: лучший x=3 f=10
Итог: x = 3  f = 10

За $10$ поколений популяция доэволюционировала до оптимума $x=3$. Заметьте роль элитизма: лучшее решение никогда не теряется, даже если кроссовер и мутация в каком-то поколении не дали улучшения.

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

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

Как работает под капотом

Почему ГА работает? Гипотеза схем (schema theorem) Холланда: короткие удачные «строительные блоки» (фрагменты хромосомы, связанные с высоким fitness) экспоненциально размножаются в популяции под действием отбора, а кроссовер их рекомбинирует. ГА не использует ни градиент, ни структуру задачи — только значения fitness, поэтому применим к чему угодно: расписаниям, схемам, архитектурам нейросетей. Цена — много вычислений fitness и отсутствие гарантий.

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

• Нет элитизма. Без переноса лучшей особи ГА может «забыть» найденное хорошее решение.
• Слишком сильный отбор. Преждевременная сходимость: популяция клонируется и застывает.
• Кодировка без смысла. Если близкие решения кодируются далёкими хромосомами, кроссовер ломает хорошие блоки.

Итоги

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