Генетический алгоритм: эволюция на коленке

Вместо предисловия

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

Кстати, один из учеников Голланда, Джон Коз, в 1992 году выпустил «Genetic Programming», где предложил эволюционировать не просто параметры, а целые программы. Благодаря ему генетическое программирование стало коммерчески успешной темой, а не только академической игрушкой.

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

Шаг 1. Кодируем задачу – «хромосома на заказ»

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

Какой тип хромосомы выбрать?

• Бинарный – классический, как у дедушки Холланда. Всё решение – последовательность нулей и единиц. Просто, как палка. Годится для задач, где надо выбирать «да/нет» или если вы готовы колдовать с кодированием чисел в биты.
• Целочисленный / вещественный – каждый ген сразу число. Удобно, если ищете параметры (например, коэффициенты регулятора или размеры детали). Не надо ваять преобразователей туда-сюда.
• Перестановочный – когда решение – это порядок элементов. Классика: коммивояжёр, расписания, укладка рюкзака. Тут кроссовер и мутации должны быть осторожными, чтобы не получить два одинаковых города в маршруте.

Главное правило: любая хромосома должна однозначно превращаться в решение, которое можно оценить. Для каждого набора генов у вас должна быть функция приспособленности (она же целевая функция, она же fitness). Чем больше число, тем лучше? Или чем меньше – зависит от задачи. Главное, чтобы можно было сравнивать.

Ну и зафиксируйте длину хромосомы и диапазоны генов. Иначе ваши дети родятся мутантами, которых даже мать не признает.

Шаг 2. Структура популяции: сколько бездарей брать в оборот

Популяция – это множество хромосом, с которыми вы работаете на текущем шаге (поколении). Размер популяции – это параметр, которым вы можете крутить.

• Слишком мало (10-20) – быстрая деградация. Все особи станут похожи друг на друга как родные братья, вы свалитесь в локальный минимум и будете плакать.
• Слишком много (>500) – каждое поколение будет считаться до скончания века.

Нормальный диапазон – 50–200 для большинства бытовых задач. Начинайте с этого, а потом подстраивайте под свой кошелёк по процессорному времени.

Также вам понадобятся:

• Максимальное количество поколений – когда остановить эволюцию. Можно поставить 500, можно 10000. Я обычно смотрю: если 20 поколений подряд приспособленность не меняется – выхожу, дальше бесполезно.
• Количество запусков – полезная вещь. ГА – вероятностная дрянь. Если запустить один раз, может не повезти с начальной популяцией. Делаем несколько независимых прогонов (например, 5–10), запоминаем лучшую особь из каждого, а потом либо берём абсолютного победителя, либо скрещиваем между собой элиту этих прогонов и ещё раз прогоняем. Это как пересдать экзамен: вероятность получить пятёрку возрастает.

Шаг 3. Отбор родителей – кого, зачем и почему

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

Обязательно знать:

• Турнирный отбор. Берёте случайных k особей (обычно 2–5), смотрите у кого приспособленность выше, объявляете победителя. Повторяете, пока не наберёте пап и мам. Чем больше k, тем жёстче давление: выживают только крутые. При малом k (например, 2) – демократия, шансы уравниваются.
• Пропорциональный отбор (рулетка). Вероятность стать родителем пропорциональна значению фитнеса. Если у вас задача на минимум, лучше преобразовать в «максимум» (например, 1/fitness). Проблема: если одна особь в десять раз лучше других, она будет размножаться как кролик, популяция потеряет разнообразие за пару поколений. Поэтому иногда используют ранговый отбор – сначала сортируете всех по фитнесу, потом назначаете вероятность не по абсолютному значению, а по месту в очереди (лучший получает N, второй N-1, и т.д.). Это компенсирует перекосы.
• Панмиксия – скрещиваем кого попало, хоть соседскую кошку с мусорным баком. Даёт максимум разнообразия, но скорость сходимости – черепашья.
• Инбридинг – скрещиваем близких родственников (похожие хромосомы). Быстро закрепляет удачные признаки, но есть риск получить наследственные заболевания (преждевременная сходимость).
• Аутбридинг – наоборот, стараемся скрещивать максимально далёкие особи. Вышибает из локальных минимумов, но может разрушить уже найденные хорошие комбинации.

Самый простой и надёжный способ – турнир с k=3. Не надо изобретать велосипед, если вы только начинаете.

Шаг 4. Кроссинговер: как правильно мешать гены

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

Основные способы:

• Одноточечный. Выбираете одну точку разреза (от 1 до длины-1). Меняете хвосты. Всё гениальное – просто. Но есть риск сломать удачные комбинации генов, которые находились рядом.
• Двухточечный. Два разреза, меняется кусок между ними. Чуть сложнее, но сохраняет концы хромосом, что иногда полезно.
• Однородный (универсальный). Проходите по каждому гену и с вероятностью 0.5 берёте его от первого родителя, иначе от второго. Можно играться с вероятностью (например, 0.6 от лучшего родителя). Перемешивает всё так, что бабушка не отличит.

Что выбрать? Если ваши гены не сильно связаны между собой (например, параметры независимы), однородный кроссовер подойдет. Если есть смысл в порядке генов – лучше двухточечный. Для бинарных строк классика – одноточечный или двухточечный.

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

Шаг 5. Мутация: ломай всё, чтобы стать лучше

Мутация – это ваша страховка от вырождения. Иногда в популяции теряются полезные гены, и мутация может их вернуть. Или случайно найти локальный максимум, мимо которого прошёл кроссовер.

Параметры мутации:

• Шанс мутации – вероятность того, что конкретная особь подвергнется мутации. Обычно берут 0.01–0.1. Если поставить 0.5 – получится хаос, эволюция не сойдётся.
• Сила мутации – насколько сильно изменится ген. Для бинарных хромосом – просто инвертируем бит. Для вещественных – можно добавить случайное значение из нормального распределения с маленькой дисперсией (например, N(0, sigma), где sigma = 0.1 * диапазон гена). Или просто сдвинуть на случайную величину в пределах 5–10% от диапазона.

Лучше делать мутацию на уровне генов: для каждого гена с вероятностью p_mut (например, 0.01 / длина хромосомы) применяем изменение. Это называется «погенная мутация».

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

Шаг 6. Селекция (формирование нового поколения)

Вы наделали детей. Старую популяцию надо куда-то девать. Полностью выбрасывать? А как же хорошие решения, которые мы нашли? Тут на сцену выходит элитизм.

Обязательно знать:

• Элитарный метод. Берёте E лучших особей из старого поколения (например, 2 штуки) и гарантированно переносите их в новое поколение без изменений. Это не даёт эволюции откатиться назад.
• Адаптивный элитизм. Можно сделать элиту динамической: eliteCount = populationSize / 10. Чем больше популяция, тем больше элиты. И важный порядок: элита добавляется до основных операций скрещивания и мутации, а потом участвует в формировании следующего поколения наравне с потомками. Это якорь, который не даёт откатиться.
• Вытеснение. Заменяете старых особей потомками. Бывает, что заменяете всех (полная замена). А бывает, что заменяете только худших (например, пополам). Баланс между стабильностью и обновлением.
• Усечение. Оставляете только топ p штук из старой популяции, а остальных выкидываете. Жёсткий отбор. Быстро сжимает популяцию, годится только если у вас уже есть приличное разнообразие.
• Турнирная селекция для поколения. Многократно проводите турниры и победителей вставляете в новую популяцию. Получите новое поколение, где все почти победители.
• Пропорциональная селекция. Как рулетка при отборе родителей, но теперь формируете целиком следующее поколение. Сильное давление, разнообразие теряется быстро.
• Ранговая селекция. То же, что пропорциональная, но по рангу. Мягче.
• Отжиг. Допускаете, что в новое поколение может попасть особь с худшей приспособленностью, но с некоторой вероятностью, которая уменьшается с каждым поколением. Это как «дайте шанс молодым талантам» – помогает не застревать в локальных минимумах.

Самый простой рецепт:

• Сохраняем 2 лучших особи (элита).
• Остальные места заполняем детьми, полученными от родителей (выбранных турниром или рулеткой).
• Новое поколение = элита + потомки.

Таким образом, размер популяции остаётся постоянным, что удобно.

Шаг 7. Алгоритм целиком (псевдокод для любого языка)

Классический ГА сдохнет в локальном минимуме быстрее, чем вы скажете «популяция выродилась». Вот что делают умные люди.

• Детектор летаргии Если в течение N поколений целевая функция не улучшается (или улучшается микроскопически), алгоритм добавляет несколько случайных особей (рестарт). Это встряска — как влить свежую кровь в вырождающуюся династию.
• Контроль разнообразия Считаете, насколько особи похожи друг на друга (можно по среднему попарному расстоянию Хэмминга или Евклида). Если разнообразие упало ниже порога — снова добавляете случайных особей. Более агрессивно, чем просто повышение вероятности мутации.
• Локальное улучшение После скрещивания и мутации, до окончательного отбора, к каждой особи применяется эвристическое локальное улучшение. Это не эволюция, это «допиливание напильником». Ускоряет сходимость и поднимает качество финального решения.

Шаг 8. Алгоритм целиком (псевдокод для любого языка)

Теперь соберём всё вместе. Даже на бейсике заведётся, если переписать аккуратно.

# Параметры
POP_SIZE = 100
MAX_GENERATIONS = 500
MUTATION_RATE = 0.05      # вероятность мутации на особь (вид 1)
MUTATION_STRENGTH = 0.1   # для вещественных генов
ELITE_COUNT = 2
TOURNAMENT_SIZE = 3

# Создать начальную популяцию (случайными хромосомами)
population = create_population(POP_SIZE)

# Основной цикл эволюции
for gen in range(MAX_GENERATIONS):
    # Оценить каждого
    for ind in population:
        ind.fitness = fitness(ind.chromosome)

    # Сортировка по убыванию фитнеса (если чем больше, тем лучше)
    population.sort(key=lambda x: x.fitness, reverse=True)

    # Элита
    new_population = population[:ELITE_COUNT].copy()

    # Пока не набрали новую популяцию
    while len(new_population) < POP_SIZE:
        # 1. Отбор родителей (турнир)
        parent1 = tournament(population, TOURNAMENT_SIZE)
        parent2 = tournament(population, TOURNAMENT_SIZE)

        # 2. Кроссинговер
        if random() < 0.7:   # вероятность кроссовера (70%)
            child1, child2 = crossingover(parent1, parent2)
        else:
            child1, child2 = parent1.copy(), parent2.copy()

        # 3. Мутация
        mutation(child1, MUTATION_RATE, MUTATION_STRENGTH)
        mutation(child2, MUTATION_RATE, MUTATION_STRENGTH)

        new_population.append(child1)
        if len(new_population) < POP_SIZE:
            new_population.append(child2)

    population = new_population

    # Логгируем лучший фитнес
    print(f"Поколение {gen}: лучший = {population[0].fitness}")

# Результат
best = population[0].chromosome

Функции create_population, fitness, tournament, crossingover, mutation и, конечно, fitness вы пишете сами под свои типы данных.

Шаг 9. Вариации и ловушки

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

Что делать, если ГА не работает?

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

Когда ГА не стоит использовать?

• Если задача решается за O(1) аналитически – не позорьтесь.
• Если у вас всего 2–3 параметра и градиентный спуск работает – используйте его.
• Если нужно гарантированное глобальное решение на сложной функции – ГА не гарант, он вероятностный. Придётся запускать 100 раз и надеяться.
• Если ваша целевая функция гладкая и выпуклая — забудьте про ГА. Градиентный спуск (или, на худой конец, метод Ньютона) отработает в разы быстрее, точнее и без ваших танцев с бубном вокруг размера популяции и вероятности мутации. ГА становится эффективным именно там, где производную не взять, поверхность вся в разрывах и локальных пиках, а само пространство поиска — дискретно и грязно.

Вместо заключения

Генетический алгоритм – это оружие массового поражения в руках ленивого, но умного программиста. Он прощает неаккуратную постановку, работает с дискретными и негладкими пространствами, не требует производных и вообще красив.

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

Пока вы тут запускаете свой ГА для подбора коэффициентов, упаковки коробок или оборудования, серьёзные дядьки проектируют космические аппараты.

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

Вывод: если ГА подходит для космоса, для вашей задачи склада или лабы по оптимизации он подойдёт тем более. Главное — не налажать с параметрами и вовремя добавить механизмы борьбы с преждевременной сходимостью.