Генерация Абстрактных Изображений С Помощью Генетических Алгоритмов

Привет, хабр! Этим летом я принял участие в Научно-педагогическая школа МГУ , который проводят Московский государственный университет и Лаборатория научного творчества ЮНЦ МГУ .

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

Генерация Абстрактных Изображений С Помощью Генетических Алгоритмов

Для нетерпеливых

Идея проекта

И у нас возникла идея сделать что-то интересное, используя генетические алгоритмы.

Например, попробуйте создать красивые абстрактные изображения.

Кстати, до начала работы над этим проектом я был весьма посредственно знаком с генетическими алгоритмами, но пообщавшись с руководителем и прочитав несколько статей в Интернете, я ринулся в бой.

Принцип действия

Итак, как вы, наверное, знаете, генетические алгоритмы основаны на принципах эволюции.

Они позволяют решать задачи, для которых не определено «идеальное» решение или неизвестен метод непосредственного его получения.

Обычно реализации таких алгоритмов состоят из следующих этапов:

Генерация случайной генерации индивидуумов решения
Отбор самых качественных особей поколения
Скрещивание особей для получения потомков
Мутация потомков
Получение нового поколения

Давайте поговорим о реализации этих шагов в нашем проекте.

О представлении изображений

Мы будем представлять изображения в цветовом пространстве RGB, в котором цвет каждого пикселя представлен тремя компонентами — красным, зеленым и синим, каждый из которых принадлежит интервалу [0; 255].

Определим изображение как набор трёх функций r(x, y), g(x,y), b(x,y) — по одной функции для каждой цветовой составляющей.

Как нарисовать картинку на основе этих функций?

Генерация Абстрактных Изображений С Помощью Генетических Алгоритмов

Пройдемся по всем пикселям изображения и найдем для них значения этих функций, передав в качестве аргументов координаты пикселей по осям x и y;
Отдельно для каждой функции нормализуем полученные значения, то есть приведем их в диапазон от 0 до 255, по формуле

, и округляем его.

Формулы представим в виде деревьев.

Например, вот так:

Генерация Абстрактных Изображений С Помощью Генетических Алгоритмов

Генерация случайной генерации изображений

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

Мы просто собираем каждую функцию из ее составных частей (других функций, констант и аргументов).

Используются следующие примитивные функции:

Унарный	Двоичный
\|а\|	а+б
потому что (а)	а - б
грех(а)	а*б
пер(а)	а/б
арккос(а)	мод б
арксисин(а)

В то же время есть некоторые особенности:

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

Экспериментально выбранным оптимальным значением этого параметра является число 6, так как слишком глубокие (и, следовательно, сложные) функции, помимо упомянутой проблемы, создают еще и рябь при формировании изображений, что снижает их качество, а слишком простые функции генерируют примитивные изображения.
Во-вторых, для достижения разнообразия первого поколения генерируемые функции должны отличаться друг от друга по своей структуре, т. е.
количеству и расположению вилок, а также длине ветвей.
Поэтому был придуман следующий метод генерации изображений.
С вероятностью

, где n — глубина текущего узла, а N — максимальная глубина дерева, в этот узел помещается элемент без дочернего элемента (т. е.
константа или координата, в отличие от функций, которые должны иметь дочерние элементы, поскольку они являются их аргументы).
Данная формула была выбрана экспериментально исходя из следующих требований:
1. Функция увеличивает свое значение по мере увеличения n;
2. Когда n = N
  
  , т.е.
  глубина функции не может превышать максимальную;
3. Субъективный критерий: создаваемые изображения не являются ни слишком простыми, ни слишком сложными.
Никто не мешает генерировать константные функции (которые не зависят от своих аргументов).
В этом случае значение компонента устанавливается равным 0 для всех пикселей.

Пример случайно сгенерированной генерации:

Генерация Абстрактных Изображений С Помощью Генетических Алгоритмов

Вполне ожидаемо, что почти все случайные изображения выглядят немного скучно.

Чтобы исправить этот печальный факт, нам действительно нужны генетические алгоритмы.

Кстати, отдельное изображение каждого канала тоже выглядит неинтересно, но зато они втроем образуют красивые цветовые эффекты.

Генерация Абстрактных Изображений С Помощью Генетических Алгоритмов

Оценка изображений за поколение

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

Автоматически оценить «красоту» изображений несколько сложно, поэтому эта задача ложится на плечи пользователя: сначала он выбирает наиболее понравившееся из полученных изображений (ему присваивается максимальный рейтинг), затем лучшее из оставшихся , и так далее.

Скрещивание

После проведения оценки необходимо скрестить особей для получения нового поколения.

Для получения изображения ребенка необходимы 2 родителя.

Вероятность того, что каждый человек станет родителем, прямо пропорциональна его баллу.

Используемый здесь алгоритм скрещивания представляет собой адаптированный для этой задачи тип многоточечного скрещивания, т.е.

гены потомка представляют собой набор частей генов родителей, взятых в определенном порядке, и:

Пересечение не может привести к неправильной функции
Изображение с более высоким баллом приносит больше пользы ребенку

Примеры пересечений:

Генерация Абстрактных Изображений С Помощью Генетических Алгоритмов

Мутация

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

Мутация применяется ко всем потомкам и заключается в следующем: обходят все 3 функции изображения и в каждой из них константы/координаты меняются на другие константы/координаты с определенной вероятностью.

Пример мутации:

Генерация Абстрактных Изображений С Помощью Генетических Алгоритмов