Генетическое программирование 2.0 "В поисках контролируемой мутации"

Глядя на то, что вышло из прошлых экспериментов, задал начальные параметры генома, таким образом, чтобы потомки менялись поменьше, а геномы были более разнообразными.

Смотрю сейчас на это и понимаю, как я был наивен...

Следующая же популяции, на 198-м поколении, выдала особь с 98% успеха. Рассмотрев её геном, заключил, что она тоже совсем не мутировала а прирастала случайными операциями, которые очень удачно легли.

Счастливая популяция, топ-6:

Что же это такое? Почему программы с геномом, допускающим мутации, не выживают?

Массовые расследования показали, что программа с набором генов, меняющих хоть что-то, сильно искажает холст от поколения к поколению. Параметры, в таких особях, принимали астрономические значения. Было принято решение, задать для каждого гена диапазон предельных значений — минимум и максимум. Чтобы совсем не запутать нарисую табличку настроек генома:

За одно упростил нашего художника, забрал инструкцию смены цвета.

Такая инструкция влияла на все последующие макания кисти до следующей смены цвета. Поэтому её мутация могла сильно изменить результат.

Отправил это всё в свой эволюционный комбайн, получил 94,5% на выходе. И снова выжил геном без мутаций. Его мутирующие конкуренты опять оказались слишком нестабильными.

В итоге я провёл целый комплекс мероприятий:

Случайный диапазон изменений

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

Например, ген мутации параметров постановил, что конкретная инструкция "перемещение кисти на 1 влево и 3 вверх" должна измениться на 60%, раньше, к 1 и 3, прибавилось/отнялось 0.6 и 1.8 соответственно, теперь, величины изменения будут лежать в пределах [0; 0.6] и [0; 1.8], какие конкретно они примут значения решит судьба генератор случайных чисел.

Счастливчики и неудачники

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

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

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

Чтобы отличать, чудом выживших, на снимках поколения, добавил звёздочку (*) перед количеством инструкций программы. Так же там появилась информация о геноме: <кол-во генов мутирующих инструкции>:<кол-во генов мутирующих геном>.

Турнирный метод отбора

О всех своих перипетиях я рассказывал жене, в этом месте она сказала, что как раз переводит в книге главу, где автор пишет о борьбе за разнообразие. Чтобы его увеличить они не просто отбирают самых лучших, а разбивают всех на группы, среди которых проводят турнир, метод поэтому называется "турнирный". Все участники группы собираются в пары, остаться в которых должен только один, выживает сильнейший.

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

Первый раз разбил на три группы: альфачи, бетты и гаммы. Если, из-за нечётности группы, кто-то не находил себе противника ему записывался автовин. Метод рабочий, средний показатель популяции растёт, смотреть снимки стало гораздо интересней, можно было даже на поздних поколениях увидеть разнообразных представителей. Вот, например, 5 особей от разных групп, 155-го поколения, отобранных по турнирному методу:

Был забавный эпизод: один геном убил в себе всякую способность к изменениям, даже к появлению новых инструкций и заполнил собой всю последнюю группу. Из поколения в поколение он просто копировал себя 1 в 1. Паразитировал на популяции, не давая никаких шансов получить из этой группы хоть что-нибудь. Когда я пошёл смотреть его в базе, строка, описывающая его геном, имела длину 666 байт.

Есть конечно и минусы: скорость роста среднего показателя значительно ниже.

На графике одна популяция с методом отбора "лучшие из лучших" (best) и три с турнирным методом по 5, 3 и 1-й группе, смотрим их средние значения:

Оптимизация кода

Устав ждать очередное поколение, решил по оптимизировать код. Расставил таймеры, нашёл узкие места. Самыми ресурсоёмкими, "внезапно", оказались два процесса: получение нового поколения и выполнение инструкций программ. С удивлением обнаружил, что конструкция foreach(range(...)) работает гораздо медленнее for(...). Но самый большой прирост производительности случился когда я перенастроил всё c PHP 5.5 на PHP7. Всё ускорилось в разы, ребята вообще молодцы.

Что там с мутациями?

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

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

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

За одно сделал значения генов и параметров инструкций дробными. Чтобы они могли накапливать даже незначительные изменения, которые со временем могут проявиться на холсте. Параметры генов свёл к минимуму, например, количество изменяемых при мутациях инструкций равно 2.

Запустил генерацию поколений. И о чудо! Оно заработало! Мутирующие геномы стали занимать лидирующие позиции, среднее по популяции росло. Я был рад. Наблюдал за изменениями, ждал особо высокого процента совпадений, как вдруг одно из поколений резко снизило показатели. По началу они начали немного выравниваться, потом снова провал и дальше только деградация.

Понятно, что случайные мутации могут изменить рисунок, но почему так резко? Да тут попахивает расследованием!

Для детального разбора я взял самую лучшую особь того поколения после которого случился спад. Это родитель и его потомок:

Мы помним, что согласно параметрам, должно мутировать только две инструкции за раз. Операции сильно связаны друг с другом, изменится какое-нибудь ранее перемещение кисти вся картинка может сместится, что тут и случилось. Но действительно ли на картинке всего два изменения инструкций? Сравнение программ показало, что их гораздо больше. Как такое может быть? Детально рассмотрел процесс создания потомка по шагам и нашёл чудесный баг:

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

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

На сегодня всё.

В планах:
* посмотреть что теперь будет при увеличении мута-силы
* сделать инструкции менее связными
* таки добавить художнику возможность создавать фукнции

Как и обещал выкладываю в общий доступ https://github.com/zapominai/GeneticProgram