Пользователь
0,0
рейтинг
2 января 2014 в 13:05

Разработка → Генерация абстрактных изображений с помощью генетических алгоритмов из песочницы

Привет, хабр!


Этим летом я принял участие в Научно-образовательной школе МГУ, которая проводится Московским Государственным Университетом и Лабораторией Научного Творчества СУНЦ МГУ. В этой статье я хотел бы рассказать вам о проекте, который я разработал во время школы на спецкурсе по программированию под руководством MAD_GooZe.
image
Для нетерпеливых

Идея проекта


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

Принцип работы


Итак, как вы, наверное, знаете, генетические алгоритмы основываются на принципах эволюции. Они позволяют решать задачи, «идеальное» решение которых не определено, или метод прямого его получения не известен. Обычно, реализации таких алгоритмов состоят из следующих этапов:
  1. Генерация случайного поколения особей-решений
  2. Выбор наиболее качественных особей поколения
  3. Скрещивание особей для получения их потомков
  4. Мутация потомков
  5. Получение нового поколения

Расскажем о реализации этих шагов в нашем проекте.

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

Мы будем представлять картинки в цветовом пространстве RGB, в котором цвет каждого пикселя представляется с помощью 3 компонент – красной, зелёной и синей, каждая из которых принадлежит промежутку [0; 255]. Будем задавать изображение, как набор трех функций r(x, y), g(x,y), b(x,y) — по одной функции на каждую компоненту цвета. Как нарисовать картинку по этим функциям?

  1. Обойдем все пиксели изображения и найдем для них значения этих функций, в качестве аргументов передав координаты пикселя по осям x и y;
  2. Отдельно для каждой функции нормализуем полученные значения, т. е приведём их к промежутку от 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 – максимальная глубина дерева, в данный узел помещается элемент без потомка (т. е. константа или координата, в отличие от функций, которые обязаны иметь потомки, так как они являются их аргументами). Данная формула была подобрана экспериментально, исходя из следующих требований:
    1. Функция увеличивает своё значение с увеличением n;
    2. При n = N , т. е. глубина функции не может превысить максимальную;
    3. Субъективный критерий, который заключается в том, чтобы изображения генерировались не слишком простыми и не слишком сложными


  • Никто не мешает генерироваться константным функциям (которые не зависят от своих аргументов). В этом случае значение компоненты устанавливается в 0 для всех пикселей.


Пример случайно сгенерированного поколения:
image

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

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

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

Скрещивание

После выставления оценки необходимо провести скрещивание особей, чтобы получить новое поколение. Для получения изображения-потомка необходимо 2 родителя. Вероятность каждой особи стать родителем прямо пропорциональна ее оценке.
Используемый здесь алгоритм скрещивания является разновидностью многоточечного скрещивания, приспособленного под данную задачу, т. е. гены потомка – набор из частей генов родителей, взятых в определённом порядке, причем:
  • В результате скрещивания не может получиться некорректная функция
  • Изображение с большей оценкой вносит больший вклад в потомка

Примеры скрещивания:



Мутация

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


Формирование нового поколения

30% лучших изображений переносится в новое поколение из старого, чтобы случайно не потерять их гены. А остальные изображения в поколении — результат скрещивания. Это позволяет сохранить баланс между разнообразием особей и преемственностью «качественных» генов.
image

Техническая реализация


Реализация этого проекта написана на JavaScript. Изображения отрисовываются на canvas, их обсчет происходит в web workers, для ускорения работы.

Результаты


С этим проектом я участвовал в конференции научных работ школьников Ученые Будущего, и занял там 4 место, что для ученика 8 класса, наверное, неплохо :).

Ссылки по теме



Статья подготовлена в рамках Научно-образовательной школы МГУ вместе с моим руководителем MAD_GooZe.
@nbashaev
карма
17,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (18)

  • +14
    C проектом похожим на этот почти полностью (я не обвиняю никого, бывает что одни и те же идеи приходят разным людям в разное время) уже выступал один ученый в 1979 году, зовут его Karl Sims. Вот ссылка на его сайт: www.karlsims.com/. Он придумал даже специальный язык для генетического программирования и написал нужный софт. За это он был награжден кучей премий и получил ряд патентов.

    А вот тут jhlabs.com/java/art.html есть демо, где вы сами можете обучить систему.
  • 0
    <offtop>Что-то народ из песочницы активизировался) Либо отошли от нового года и увидели инвайты))</offtop>
    • –2
      Каждый год так. Я год ждал конца декабря, что бы НЛО выдало мне инвайт :-)
      В конце декабря и начале января НЛО «аппрувит» все мало-мальски адекватные посты.
  • +2
    Теперь осталось поменять прямую генерацию растра по формуле на фрактал — и будет счастье :)
    • 0
      И еще добавить временное измерение, чтобы генерировать анимированные изображения.
  • 0
    А можете рассказать (идейно), как скрещиваются функции?
    • 0
      Я не люблю философствовать, так что вот код:

      function cross(headNode1, headNode2, prob) { // Пусть r1, r2 - оценки изображений, тогда prob = r1 / (r1+r2)
      
              var newHeadNode = new Node();
              var children = [];
              
              // Скрещивание производится отдельно для каждой пары узлов
              var mainNode, addNode; // В паре выделяем главный и побочный узел
              var newProb = 0;
              var types = "";
      
      
              if ( probability(prob) ) { // С вероятностью prob
      
                      mainNode = headNode1;
                      addNode = headNode2;
                      newProb = prob;
      
              } else {
      
                      mainNode = headNode2;
                      addNode = headNode1;
                      newProb = 1 - prob;
      
              }
      
      
              newHeadNode.setValue( mainNode.getValue() );
              newHeadNode.type = mainNode.type;
      
              types = mainNode.type + "; " + addNode.type;
      
      
      
              switch (types) {
                      case "const; const":
                      case "const; coord":
                      case "coord; const":
                      case "coord; coord":
                      case "const; func1":
                      case "coord; func1":
                      case "func1; const":
                      case "func1; coord":
                      case "const; func2":
                      case "coord; func2":
                      case "func2; const":
                      case "func2; coord":
      
                              for (var i = 0; i < mainNode.getNumOfChildren(); i++) {
      
                                      children[i] = mainNode.getChildByNumber(i);
      
                              }
      
                              break;
      
      
                      case "func1; func1":
      
                              children = [
                                      cross(
                                              mainNode.getChildByNumber(0),
                                              addNode.getChildByNumber(0),
                                              newProb
                                      )
                              ];
      
                              break;
      
      
                      case "func1; func2":
      
                              children = [
                                      cross(
                                              mainNode.getChildByNumber(0),
                                              addNode.getChildByNumber( randInt(0, 1) ),
                                              newProb
                                      )
                              ];
      
                              break;
      
      
                      case "func2; func1":
      
                              children = [
                                      cross(
                                              mainNode.getChildByNumber(0),
                                              addNode.getChildByNumber(0),
                                              newProb
                                      ),
      
                                      cross(
                                              mainNode.getChildByNumber(1),
                                              addNode.getChildByNumber(0),
                                              newProb
                                      )
                              ];
                              
                              break;
      
      
                      case "func2; func2":
      
                              children = [
                                      cross(
                                              mainNode.getChildByNumber(0),
                                              addNode.getChildByNumber(0),
                                              newProb
                                      ),
      
                                      cross(
                                              mainNode.getChildByNumber(1),
                                              addNode.getChildByNumber(1),
                                              newProb
                                      )
                              ];
      
                              break;
      
      
                      default:
      
                              children = [];
                              break;
              }
      
      
      
      
              for (var i = 0; i < children.length; i++) {
      
                      newHeadNode.addNode(children[i]);
      
              }
      
      
              return newHeadNode;
      }
      
      
      • +16
        Не надо так больше делать, используйте спойлер, пожалуйста.
        • +3
          Буду знать, спасибо.
      • 0
        Спасибо, идея понятна. Но лучше было бы это спрятать под спойлер.
  • +4
    Вот теперь у меня есть у «умное название» для ошибок в процессе программирования графики…
    Оказывается, что я «генерирую абстрактных изображений с помощью генетических алгоритмов».
  • +2
    Напомнило — в мульте «Магазинчик БО» заяц Бо писал программу, которая выдаст идеальное изображение.
    Программа выдала, и всю серию герои потом залипали на эту картинку.
  • +2
    Очень странно, что Ваш преподаватель не знал, например, про эту работу Кенета Стенли по CPPN en.m.wikipedia.org/wiki/Compositional_pattern-producing_network.
  • +1
    Для тех кто еще не видел концептуальный скринсейвер — electric sheep. Очень красиво и как раз генерируются картинки (вернее анимация) с помощью генетических алгоритмов, а отбором выступают пользователи, голосуя за понравившиеся варианты.
  • 0
    Прелесть генетических алгоритмов в том, что можно использовать fitness function, а вы самостоятельно оцениваете красивость картинок. Скажите, 100 поколений по 100 «осыбей» вы тоже оценивать вручную будете?
    • –1
      Конечно, было бы довольно любопытно разработать такую fitness function, более того, это даже можно сделать, например, рассмотрев наилучшие изображения и попытавшись выделить среди них какие-то подмножества (сомневаюсь, что существуют некий единый образ идеального изображения). Но это будет уже совсем другой проект. Поэтому данная работа имеет право на существования не в виде промежуточного звена, а в качестве самостоятельного исследования.
  • –1
    x*y рулит.
  • +2
    Генофонд вымирает, картинки стремятся стать одинаковыми.

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