Предыдущие части: Заключение, Генетическая Мона Лиза
В прошлой части я вроде как подвёл итог и заявил, что продолжать разработку в этом направлении бесполезно.
Однако тема графических генетических алгоритмов меня всё никак не отпускает, поэтому последние недели две я провёл в попытках что-то изменить в коде, чтобы сделать его более эффективным.
Как оказалось, в моей собственной реализации были ошибки, которые было трудно обнаружить. Алгоритм вроде бы работал, но очень плохо сходился. А я думал, что это происходит из-за моих изменений алгоритма, и откатывал их назад.
После устранения ошибок стало возможным спокойно пробовать разные варианты алгоритма и его оптимизации.
Я беру разные изображения, но эталоном для проверки служит именно Мона Лиза. Постоянно наблюдая за одной и той же картинкой, я заметил одну удивительную вещь.
Полигоны генерируются случайно, и поэтому любой полигон может попасть на любое место. Например, маленький тёмный полигон может случайно попасть на место левого глаза. Потом другой маленький тёмный полигон может попасть на место правого глаза, и тогда это внесёт вклад в появление глаз на лице:
Однако в реальности этого практически никогда не происходит. Глаза начинают появляться в виде такой тёмной полоски:
А через довольно продолжительное время их разделяет треугольник:
После этого начинает формироваться нос. Нос никогда не появляется раньше глаз, по каким-то причинам. То есть, вот эта полоска и вот этот треугольник являются устойчивыми генами, которые проявляются при любом запуске.
Следовательно, вывод о том, что скрещивание бесполезно, был преждевременным. Если в каждой хромосоме популяции будут проявляться устойчивые гены, значит между ними теоретически можно провести скрещивание с прогнозируемым позитивным исходом.
Остальные наблюдения касались влияния настроек алгоритма на скорость и точность достижения результата.
Треугольники против полигонов
Использовать в качестве генов треугольники или N-угольники (полигоны) – почти не принципиально. Единственное, что размер хромосомы ограничен, скажем, 150 генами. При этом 1 полигон может заменить собой сразу несколько треугольников, а треугольник может быть только треугольником. Следовательно, 150 десятиугольников это совсем не то что 150 треугольников – возможностей для формирования картинки у них значительно больше. В связи с этим, если в алгоритме используются треугольники, размер хромосомы нужно увеличить раза в два.
С другой стороны, треугольникам легче мутировать. Полигоны могут принимать самые жуткие формы:
Мы можем даже не догадываться, что совершенно далёкие друг от друга части картинки нарисованы одним полигоном. Поэтому при мутации, скажем, цвета такого полигона цвет в других частях картинки будет непредсказуемо меняться, что будет зачастую ухудшать рейтинг хромосомы. А раз рейтинг ухудшается, то мутации придётся всё время отбрасывать, и следовательно, такой полигон окажется застрявшим практически навсегда.
Треугольник же предельно простой геометрически. Он тоже может накрыть собой половину картинки, но этот вариант гораздо более предсказуем, а маленькие треугольники в разных частях картинки абсолютно не связаны друг с другом и поэтому каждый может мутировать независимо. Я проведу ещё несколько тестов с многоугольниками и, если не увижу значительных улучшений, окончательно перейду на треугольники.
Застой эволюции
С новыми алгоритмами картинка начинает проявляться практически мгновенно:
Мы не видим глаза, нос, рот, но уже видно лицо и волосы. С течением времени вся картинка становится лучше и лучше, а вот глаза... так и остаются тёмной горизонтальной полоской поперек лица.
Эта загадка мучила меня сильней всего. Дело в том, что когда я смотрел работу уже готовой программы EvoLisa (ссылки в конце), она всегда доводила дело до конца. На картинке, пусть и через долгое время, появлялось что-то похожее на глаза. У меня же постоянно оставалась или эта полоска, или просто пятна вместо глаз.
Я никак не мог понять, почему это происходит. Я полностью изучил исходный код трёх разных программ, но не нашёл никаких особенностей. У меня был точно такой же код. Кроме того, все тонкие настройки я тоже перенёс.
С самого начала моя программа работала идентично тем программам, и результаты были очень похожи. Но ближе к концу она застревала в состоянии, когда глаза (и нос, и рот) не появлялись уже никак, хотя всё остальное потихоньку улучшалось.
Я так и не понял, почему оно работало в оригинальных программах. Но мне пришлось найти свой выход из этой ситуации.
Для начала я представил, что происходит с алгоритмом. Исходное состояние это чёрный квадрат, и пока полигонов мало, практически любой новый полигон, любого размера, будет повышать рейтинг. Потом, когда количество полигонов переваливает за 50, картинка становится менее подвижной. Случайные изменения в ней уже не так часто ведут к повышению рейтинга.
Чтобы на картинке появился глаз, нужно, чтобы в конкретном месте появился маленький (буквально 2x2 пиксела) тёмный полигон. Но полигоны генерируются случайно, а потому могут иметь любой размер. И конечно, в 99% случаев этот размер будет гораздо больше требуемого. Большой полигон можно было бы оставить, чтобы он мутировал в маленький. Но так как он сразу при появлении ухудшает рейтинг, этот вариант отбрасывается.
Поэтому я сделал так: пока картинка находится на начальных стадиях, вероятность появления новых полигонов пропорционально снижается. Когда идут грубые наброски, достаточно всего нескольких больших полигонов.
Когда картинка начинает детализироваться, я пропорционально повышаю вероятность появления новых полигонов. Это даёт лишний шанс появиться глазам и прочим мелким деталям.
Кроме того, так же пропорционально уменьшается размер новых полигонов. В начале они могут быть любые, а ближе к концу, когда вся площадь картинки уже поделена между устойчивыми полигонами, возможный размер снижается вплоть до 32x32 пиксела. Новый полигон не может быть больше этого размера. Но появившись, он затем может мутировать хоть в в гиганта или совсем схлопнуться.
И... дело сразу пошло! Теперь во всех запусках у Моны стали стабильно появляться глаза, нос и рот.
Счастью нет предела. Приятно, когда спустя столько времени и бесплодных попыток что-то начало работать.
Я также занимался оптимизаций скорости рисования полигонов и подсчёта рейтинга. Об этом расскажу в следующем выпуске.
Ссылки
1. Оригинальная программа Evo Lisa (код на До-диез и исполняемый файл)
https://rogerjohansson.blog/2008/12/11/genetic-programming-mona-lisa-source-code-and-binaries/
2. Портированная на C++ Evo Lisa (код идентичный, результаты тоже, но не совсем)
http://www.ggsoft.org/archives/genetic_test.zip
Я, в свою очередь, портировал это всё на чистый C и SDL2, но выкладывать пока не буду, код очень грязный, так как пробовалось много разных вариантов.