Привет!
Этим летом я принял участие в Научно-образовательной школе МГУ, которая проводится Московским Государственным Университетом и Лабораторией Научного Творчества СУНЦ МГУ. В этой статье я хотел бы рассказать вам о проекте, который я разработал во время школы на спецкурсе по программированию под руководством MAD_GooZe.
Для нетерпеливых
Идея проекта
Итак, у нас возникла идея сделать что-нибудь интересное, используя генетические алгоритмы. Например — попытаться генерировать красивые абстрактные изображения. К слову сказать, до начала работы над этим проектом, я был знаком с генетическими алгоритмами весьма посредственно, но пообщавшись с руководителем и почитав некоторые статьи в интернете, я ринулся в бой.
Принцип работы
Итак, как вы, наверное, знаете, генетические алгоритмы основываются на принципах эволюции. Они позволяют решать задачи, «идеальное» решение которых не определено, или метод прямого его получения не известен. Обычно, реализации таких алгоритмов состоят из следующих этапов:
- Генерация случайного поколения особей-решений
- Выбор наиболее качественных особей поколения
- Скрещивание особей для получения их потомков
- Мутация потомков
- Получение нового поколения
Расскажем о реализации этих шагов в нашем проекте.
О представлении изображений
Мы будем представлять картинки в цветовом пространстве RGB, в котором цвет каждого пикселя представляется с помощью 3 компонент – красной, зелёной и синей, каждая из которых принадлежит промежутку [0; 255]. Будем задавать изображение, как набор трех функций r(x, y), g(x,y), b(x,y) — по одной функции на каждую компоненту цвета. Как нарисовать картинку по этим функциям?
- Обойдем все пиксели изображения и найдем для них значения этих функций, в качестве аргументов передав координаты пикселя по осям x и y;
- Отдельно для каждой функции нормализуем полученные значения, т. е приведём их к промежутку от 0 до 255, по формуле
, и округлим.
Формулы же мы будем представлять в виде деревьев. Например, так:
Генерация случайного поколения изображений
Так как функции мы представляем в виде деревьев, мы можем легко сгенерировать начальное поколение. Каждую функцию просто собираем из составных частей (других функций, констант и аргументов). Используются такие функции-примитивы:
| Унарные | Бинарные |
|---|---|
| |a| | a + b |
| cos(a) | a — b |
| sin(a) | a * b |
| ln(a) | a / b |
| arccos(a) | a mod b |
| arcsin(a) |
При этом, тут есть некоторые особенности:
- Мы не можем генерировать слишком сложные функции, так как это повлечёт за собой проблему производительности. Поэтому вводится такой параметр, как максимальная глубина дерева функции. Экспериментально подобранным оптимальным значением этого параметра является число 6, так как слишком глубокие (а значит сложные) функции помимо упомянутой проблемы так же при генерации изображений дают рябь, которая снижает их качество, а слишком простые функции порождают примитивные изображения.
- Во-вторых, для достижения разнообразия первого поколения сгенерированные функции должны быть не похожи друг на друга своей структурой, т. е. количеством и расположением развилок, а так же длиной ветвей. Поэтому был придуман следующий способ генерации изображений. С вероятностью
, где n – глубина текущего узла, а N – максимальная глубина дерева, в данный узел помещается элемент без потомка (т. е. константа или координата, в отличие от функций, которые обязаны иметь потомки, так как они являются их аргументами). Данная формула была подобрана экспериментально, исходя из следующих требований:
- Функция увеличивает своё значение с увеличением n;
- При n = N
, т. е. глубина функции не может превысить максимальную; - Субъективный критерий, который заключается в том, чтобы изображения генерировались не слишком простыми и не слишком сложными
- Никто не мешает генерироваться константным функциям (которые не зависят от своих аргументов). В этом случае значение компоненты устанавливается в 0 для всех пикселей.
Пример случайно сгенерированного поколения:
Вполне ожидаемо, что практически все случайные изображения выглядят скучновато. Для исправления этого печального факта нам, собственно, и нужны генетические алгоритмы.
Кстати, отдельное изображение каждого канала тоже выглядит не интересно, но втроём они образуют красивые цветовые эффекты.
Оценка изображений в поколении
После генерации первого поколения необходимо провести оценку полученных решений. Оценивать «красивость» изображений автоматически несколько затруднительно, поэтому это задача ложится на плечи пользователя: сначала он выбирает самое понравившееся из полученных изображений (ему выставляется максимальная оценка), затем наилучшее из оставшихся и так далее.
Скрещивание
После выставления оценки необходимо провести скрещивание особей, чтобы получить новое поколение. Для получения изображения-потомка необходимо 2 родителя. Вероятность каждой особи стать родителем прямо пропорциональна ее оценке.
Используемый здесь алгоритм скрещивания является разновидностью многоточечного скрещивания, приспособленного под данную задачу, т. е. гены потомка – набор из частей генов родителей, взятых в определённом порядке, причем:
- В результате скрещивания не может получиться некорректная функция
- Изображение с большей оценкой вносит больший вклад в потомка
Примеры скрещивания:
Мутация
После получения потомка необходимо его мутировать, чтобы не терялось разнообразие поколений. Мутация применяется ко всем потомкам и заключается в следующем – обходятся все 3 функции изображения и в каждой из них константы/координаты с определённой вероятностью меняются на другие константы/координаты.
Пример мутации:
Формирование нового поколения
30% лучших изображений переносится в новое поколение из старого, чтобы случайно не потерять их гены. А остальные изображения в поколении — результат скрещивания. Это позволяет сохранить баланс между разнообразием особей и преемственностью «качественных» генов.
Техническая реализация
Реализация этого проекта написана на JavaScript. Изображения отрисовываются на canvas, их обсчет происходит в web workers, для ускорения работы.
Результаты
С этим проектом я участвовал в конференции научных работ школьников Ученые Будущего, и занял там 4 место, что для ученика 8 класса, наверное, неплохо :).
Ссылки по теме
- Создание картинок с помощью градиентов
- Генератор визуальных интерфейсов
- Генерация картинок, отдаленно похожих на лица людей
Статья подготовлена в рамках Научно-образовательной школы МГУ вместе с моим руководителем MAD_GooZe.
Автор: nbashaev
