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

Термины

Термин	Что это такое	Зачем нужно в генетическом алгоритме
Ген (gene)	Самый маленький параметр, который можно менять отдельно (число, буква, бит).	На генах выполняется мутация — крошечные случайные изменения.
Хромосома (chromosome)	Логически связанная группа генов, наследуемая «пачкой».	Позволяет обмениваться целыми блоками параметров при скрещивании, не ломая их внутренние связи.
Геном (genome)	Полный набор всех хромосом одной особи; полностью описывает решение.	На геноме считают фитнес — оценивают, насколько хороша вся особь.
Популяция (population)	Множество геномов, которые существуют одновременно в одной итерации алгоритма.	Даёт разнообразие: из неё выбирают родителей, из детей формируют новое поколение.

Операции

Оценка (fitness)

Оценка - это определение успешности популяции. Оценка принимает геном и возвращает одно число, которое показывает - насколько данный геном успешен.

Примеры:

• Пройденное расстояние
• Сколько символов на своем месте и так далее.

Тонкости:

• Добавлять штрафы за недопустимые решения. Если геном попадает в недопустимое решение, то давать решению низкий балл или 0 - такое решение быстро вымрет.
• Смягчать фитнес-значение. Если у одного генома фитнесс = 1000, а у другого = 2, то такая селекция захлебнётся. Можно логарифмировать или делить на максимум, что смягчить разброс.
• Добавлять seed. Полезно для отладки симуляции: иначе удача (или неудача) может мешать настроить эволюцию.

Отбор (selection)

Мы научились оценивать геном и теперь можем выбрать - какие геномы показали лучшие результаты и готовы^

• стать частью следующего поколения (элита)
• стать родителями для следущего этапа (скрещивание)
• и то, и другое

Отбор проще воспринимать как "победителей", которые пройдут на следующий этап соревнований.

Важно:

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

Скрещивание (crossover)

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

Результатом скрещивания 2 родителей становятся 2 новых ребенка, которые унаследовали "удачные" гены.

Генный crossover

Проходим по всем генам ребёнка и подбрасываем монетку - берем значение из A или B.

Где полезно:

• Бинарные строки, перестановки фиксированной длины
• Каждый ген независим и рвать хромосому нельзя

Плюсы:

• Максимальное разнообразие, можно быстро получить решение.

Минусы:

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

Хромосомный crossover

Разрез внутри хромосомы

• Одноточечный: режем в случайном месте, меняем хвосты местами.
• Двухточечный: вырезаем посередине.

Где полезно:

• Вектор вещественных чисел, где соседние параметры работают вместе
• Строки (сохранить часть слова как блок)

Обмен целых хромосом

Геном может состоять из хромосом, отвечающих за разные части генома (например, отдельный геном для физики, отдельный для сенсоров и так далее).

Плюсы:

• Сохраняем "биохимию" неизменной, геном остается составным.
• Просто обеспечить валидность.

Минусы:

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

Геномный crossover

• Shuffle-crossover - меняем порядок нескольких хромосом.
• Combo-crossover -

Когда нужен:

• Эволюция сложных систем, где разные хромосомы описывают очень разные части

Как выбрать уровень:

Ситуация	Рекомендуемый уровень
Все гены независимы, одинакового типа	Генный (uniform)
Есть логические блоки, внутри важен порядок	Хромосомный с разрезом внутри блока
Геном = несколько разнородных модулей	Геномный (обмен целых хромосом или комбинированный)

Варианты комбинаций:

• Сначала 50% пар проходят крупный обмен хромосом, остальные 50% - мелкой смешивание генов.

Параметры

• crossover rate (частота скрещивания) - доля родителей, которые не просто копируются, а именно скрещиваются.
• cut point bias - режем ближе к краю или к середине?
• elite replication (копирование элитных геномов) - лучшие геномы комируются, сохраняя рекорд

Мутация (mutation)

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

Для этого существует мутация: мы чуть-чуть с некоторым шансом изменяем отдельные части генома, которые могут открыть варианты отсутствующие в популяции.

Зачем нужна мутация

• Все геномы могут рано или поздно стать похожими друг на друга
• Если исходная популяция не содержит "лучшее" значение, то оно никогда и не появится
• Популяция может застрять в локальном максимуме/минимуме (что иногда может быть хорошо, но не идеально)

Баланс

В мутации очень важен баланс:

• Слишком мало -> популяция слипнется, нет новизны
• Слишком много -> всё приверщается в шум и хорошие решения разрушаются мутированием

Обычно начинают с ~1% на ген и немного подкручивают.

Пример техник

Наименование	Описание	Лучший тип генов
Swap	Поменяй местами	Бинарные данные
Flip	Поменять на противоположное	Битовая инверсия
Gaussian noice	Добавь немного белого шума	Углы, коэффиценты, веса
Random re-initialise	Замени случайным значением из диапазона	Число, буква, enum
Creep / Step-size	Прибавить/убавить шаг	Целочисленные параметры
Boundary mutation	Толкаем ген в min/max	Крайние значения часто оказываются оптимальными
Scramble mutation	Перетасовать случайный диапазон	Перестановочные гены (маршруты, расписания)
Inversion mutation	Перевернуть порядок элементов	Перестановки / строки

Можно настроить две скорости мутации: грубая и тонкая.

Так же полезно включить логи, что проследить изменения.

Параметры

• mutation rate - вероястность применить мутацию (например, 0.5 - 5% на ген)
• mutation strength - сила изменения (+-1 для целых чисел, +-1 градус для углов и так далее)

Важно

• Мутация - маленькое, редкое, но постоянное изменение
• Она поддерживает разнообразие и помогает расширять пространство решений
• Настройка содержит две части: как часто менять и насколько менять
• Важно следить, чтобы мутация не сломала особь, сделав её невалидной

Логи

Поле	Зачем нужно
gen – поколение	Позволяет отследить динамику по времени
id – идентификатор особи	Связывает события: рождение → мутации → попадание в элиту
event	init, crossover, mutation, elite, discard, …
parents	Список ID родителей (или null для стартовой популяции)
op_info	Что именно произошло: точка разреза 7, gene[2] += −0.014, swap(3,7)
fitness	Итоговый балл ребёнка после всех правок
best_so_far	Лучший fitness с начала эксперимента (удобно видеть, «зажглась» ли эволюция)

Пример JSON:

{"gen":0,"id":0007,"event":"init",
 "op_info":"random_vec","fitness":3.18,"best_so_far":3.18}

{"gen":4,"id":0432,"event":"crossover",
 "parents":[0121,0179],
 "op_info":"one-point cut=5","fitness":6.42,"best_so_far":6.42}

{"gen":4,"id":0432,"event":"mutation",
 "op_info":"gaussian gene[2]: 0.151→0.124 (σ=0.05)",
 "fitness":6.73,"best_so_far":6.73}

{"gen":4,"id":0432,"event":"elite",
 "op_info":"kept as top-1","fitness":6.73,"best_so_far":6.73}

Пример CSV:

gen,id,parentA,parentB,event,details,fitness,best
0,0007,,,init,rand,[3.18],3.18
4,0432,0121,0179,xover,cut@5,[6.42],6.42
4,0432,,,,mut,gauss g2 0.151→0.124,[6.73],6.73
4,0432,,,,elite,---,[6.73],6.73