Предыдущие части: Строковый генетический алгоритм, Введение в генетические алгоритмы
В предыдущей части мы наладили хранение хромосом и генерацию случайных хромосом.
Нужно сразу исправить ситуацию с хранением: нам нужна не только хромосома, но и её рейтинг. А поэтому сделаем класс Chromosome, у которого будет три свойства:
- rating – рейтинг хромосомы
- size – размер хромосомы (длина массива генов)
- genes – массив генов хромосомы (то, что раньше было самой хромосомой)
Все хромосомы – одинакового размера, тем не менее мы будем в каждой хранить свойство size, потому что так удобней (оно всё время нужно).
Глобальную переменную genes, в которой хранится генофонд, переименуем в gene_pool, чтобы не путать со свойством genes класса Chromosome.
Функцию для создания случайной хромосомы create_random_chromosome() сделаем методом класса Chromosome и переименуем в set_random_genes().
И чуть изменим метод create_population(): теперь он будет помещать в список не байтовые массивы, а целые объекты класса Chromosome:
Далее, нам нужна функция для вычисления рейтинга – расстояния между двумя строками. Напишем сразу для всей популяции, так как других применений у неё нет:
Теперь сделаем сортировку хромосом по рейтингу. Это обычная сортировка пузырьком:
Наконец, для собственного удобства сделаем более аккуратный вывод популяции на печать с порядковым номером и рейтингом:
Создаём популяцию, вычисляем рейтинги, сортируем, и печатаем:
И можно уже посмотреть на вывод:
Несмотря на полную случайность, первая строка имеет рейтинг 37. Значит, у неё совпадают целых 6 символов из 43.
Селекция
Под селекцией понимается выбор хромосом-родителей для создания потомков, но этот этап в большинстве руководств по генетическим алгоритмам очень скудно описан. Опущены некоторые моменты, которые мы сейчас рассмотрим.
Во-первых, есть два подхода к воспроизводству популяции:
- популяция полностью заменяется новой популяцией, созданной из потомков
- в популяции сохраняется часть родителей, а оставшаяся часть заполняется потомками
Во-вторых, есть селекция, а есть подбор пар. Селекция определяет, кто вообще может быть родителем, а подбор пар делается специальными методами и определяет, конкретно кто с конкретно кем будет спариваться.
Этот момент практически везде называется просто селекцией.
В нашем случае мы для селекции возьмем метод элит. У нас будет элита в виде лучшей половины популяции, которая будет переходить в новую популяцию и порождать потомков, чтобы заполнить вторую половину новой популяции.
Список хромосом уже отсортирован по рейтингу и поэтому задача селекции решена (берём топ-10), но ради будущей реализации других методов нам надо сделать формальный отбор. То есть – поместим наших избранников в список "выживших".
Заведём для выживших список фиксированной длины заранее и будем им пользоваться всё время:
survivors = [None] * (population_size // 2)
И напишем функцию select(), которая просто копирует первую половину популяции в отдельный список:
Обращаю внимание, что объекты-хромосомы как таковые не копируются, копируются только ссылки на них. Теперь добавим в код селекцию:
select(population, survivors)
И приступим к размножению.
Подбор пар
Cреди выживших нужно отобрать пары родителей, для того чтобы получить от них потомков и восстановить вторую половину популяции.
Чтобы опять же не утяжелять первую версию алгоритма, мы выберем метод панмиксии. Это когда каждый может спариться с каждым с одинаковой вероятностью.
Метод get_parent_index() возвращает нам индекс (то есть позицию в массиве parents) случайно выбранного родителя:
Первым параметром мы передаём массив, из которого надо выбирать, а вторым параметром – позицию, которую надо исключить из выбора. Дело в том, что когда мы выберем первого родителя, второго родителя надо выбрать так, чтобы он не совпадал с первым.
Скрещивание (кроссинговер)
Получив двух родителей, мы можем провести скрещивание. Его суть в том, чтобы каким-то образом перемешать гены двух родителей и получить новую хромосому-потомка.
Здесь также есть куча методов, и мы опять возьмём что попроще. Это будет одноточечный кроссинговер.
Мы выбираем случайную позицию внутри хромосомы, и потомок получает гены родителя №1 от начала и до этой позиции, и гены родителя №2 от этой позиции и до конца.
Каждые два родителя порождают пару потомков. То есть функцию cross() мы вызываем дважды: сначала с (родитель1, родитель2), затем с (родитель2, родитель1).
Теперь, имея функции для выбора родителей и для скрещивания, пишем функцию, которая заполняет вторую половину популяции потомками (родители сохраняются в первой половине).
Мутация
Осталось сделать функцию мутации. Отметим, что мутация может происходить сразу при скрещивании в некоторых методах, ну а мы просто сделаем её отдельным шагом. Для этого определим, сколько хромосом из популяции должно мутировать, и сколько генов должно мутировать в каждой хромосоме.
Я на тестах выяснил, что можно подвергать мутации хоть 50% популяции, но вот количество генов лучше задать 1. Это значит, что за 1 раз мутирует только один символ в строке. Были нередки случаи, когда строка была уже почти правильная, то есть отличалась всего одним символом, но если после мутации в ней меняется больше чем один символ, мы наоборот удаляемся от цели.
Эволюция
Осталось сделать цикл повторений, включив в него все шаги:
При достижении целевой строки у первой хромосомы в списке будет рейтинг 0. Обнаружив такое условие, мы прекращаем цикл, так как цель достигнута. Мы также печатаем текущую популяцию на каждом шаге цикла:
Как можно видеть, результат был достигнут на 848 шаге цикла. Обычно цикл продолжается от 700 до 1000 шагов.
Собственно, на этом всё. Далее можно просто менять методы селекции, отбора родителей, скрещивания и мутации на другие. Особо интересным методам можно будет даже посвятить отдельный выпуск.
В следующий раз мы попробуем реализовать другой генетический алгоритм – представление любого изображения в виде набора цветных треугольников. Это значительно интереснее и сложнее.
Полный исходный текст на Python
P.S. На других языках я этот алгоритм не делал, потому что никому было не интересно.
