Предыдущая часть: Что могут треугольники
Вот и дошли руки до практической реализации генетического алгоритма на треугольниках.
Я использовал язык C, библиотеку SDL2 и ранее написанный код для растеризации треугольника с поддержкой прозрачности, всё уже описано и заостряться на этом не буду.
Код программы я поместил на github.
В качестве примера я использовал программу автора Youtube-канала "Two Minute Papers", исходники которой можно скачать отсюда:
https://users.cg.tuwien.ac.at/zsolnai/wp/wp-content/uploads/2014/02/genetic_mona.zip
Оттуда меня интересовала общая информация про генетический отбор, то есть тип отбора, критерий успешности и применяемые мутации.
Программу я написал полностью с нуля, так как у меня другая графическая библиотека и другой подход к хранению данных.
Описание алгоритма
Мы берём некоторое изображение, по традиции это портрет Моны Лизы:
и пытаемся получить такое же изображение с помощью набора цветных полупрозрачных треугольников:
Генетическая популяция состоит из хромосом, а каждая хромосома – из набора генов, где один ген это один треугольник. У треугольника есть координаты вершин, цвет и прозрачность. В данной реализации прозрачность не является варьируемым параметром, то есть задана константой.
Первоначально треугольники генерируются случайным образом, и одна хромосома, состоящая из 150 треугольников-генов, выглядит примерно так:
Мутации генов – это случайные изменения координат и цвета треугольников. Применяя мутации, мы должны добиться такого расположения и цвета треугольников, чтобы они наиболее точно совпадали с заданным изображением.
Критерий успешности
Каждая хромосома имеет рейтинг, то есть критерий успешности. Чтобы его посчитать, хромосома рисуется в отдельной области памяти, затем мы проходим по этой области, берём каждый пиксел и считаем RGB-разницу с пикселом целевой картинки:
diff_r = r1 - r2;
diff_g = g1 - g2;
diff_b = b1 - b2;
diff = diff_r * diff_r + diff_g * diff_g + diff_b * diff_b;
Эта разница складывается для каждого пиксела, в результате чего мы получаем суммарное отклонение (расстояние) хромосомы от целевой картинки. Чем меньше расстояние, тем лучше рейтинг.
В формуле присутствуют квадраты (фактически мы считаем расстояние в цветовом 3D-пространстве по формуле Пифагора). Поэтому максимальная разница для одного пиксела может составить 255*255*3, или 195075. В картинке размером 500*500 пикселов общая разница может составить 195075*500*500, или 48 768 750 000. Это число не помещается в 32-битное целое, поэтому нужно использовать 64-битное.
Внимание! При написании программы я допустил именно эту ошибку! Я указал тип переменной diff как long, а нужно было long long! Эта ошибка попала на git. Сейчас уже исправлена.
Чтобы посчитать расстояние по правилам, нужно добавить взятие квадратного корня. Но так как это затратная операция, её никто не делает. А сравнивать рейтинги можно и в виде суммы квадратов.
Отбор, скрещивание и мутации
Популяция состоит из 30 хромосом. На каждом этапе эволюции мы отбираем 25% наиболее удачных (отсортированных по рейтингу) хромосом и сохраняем их для следующего шага. Остальные хромосомы заменяются на новые. Новые экземпляры мы получаем путём скрещивания любых двух старых или путём мутации.
С вероятностью 95% мы попадаем в ветку скрещивания, а иначе в ветку мутации.
В ветке скрещивания с вероятностью 50% выбирается либо одноточечный кроссоверинг, либо равномерный кроссоверинг.
В одноточечном кроссоверинге мы выбираем случайную позицию в массиве треугольников. Гены первого родителя копируются от начала и до этой точки, а гены второго родителя копируются от этой точки и до конца.
В равномерном кроссоверинге каждый ген равновероятно может унаследоваться либо от первого, либо от второго родителя.
Мутация изменяет каждую координату (отдельно x, y) каждой вершины треугольника с вероятностью 25%, прибавляя к ней случайное число от -X до +X.
Дополнительно, с вероятностью 50%, делается изменение компонентов цвета.
Также, если мы попали в ветку мутации, с вероятностью 25% делается полная мутация, то есть хромосома инициализируется с нуля.
Результат
На каждом шаге эволюции на экран выводится одна самая удачная хромосома (первая в отсортированном списке). Это делается в реальном времени, поэтому трансформацию можно наблюдать живьём:
Проблемы
Программа сделана для работы с картинками любого размера, но по факту работает медленно и очень плохо масштабируется. Это значит, что дожидаться результата на больших картинках придётся очень долго (сутками). Приемлемый размер – 200*200 пикселов. Можно ускорить работу, задав при старте (в командной строке) меньше треугольников в хромосоме и меньше хромосом в популяции, но это также изменит вид финального результата.
Кроме того, у алгоритма странная избирательность по сравнению с оригинальной программой, которую я взял за основу. Если оригинальная программа хорошо работает с любыми картинками, моя почему-то на некоторых картинках долго не может прийти к результату. Иногда программа будто бы стоит на месте и ничего не меняется, но если долго ждать, то всё-таки цель становится ближе.
Думаю, дело тут в параметрах мутации, Нет, оказалось, что я всё-таки забыл ещё кое-где изменить тип рейтинга на 64-битный.
Оригинальная программа работает с OpenGL и мультипоточностью и поэтому существенно быстрее. Нет, оказалось, что есть другая программа, также написанная с использованием SDL2, которая работает ещё быстрее, хотя её графический код практически идентичен моей. Так что буду разбираться. Очень интересно понять, где у меня затык.
Читайте дальше: