Поиграем в эволюцию? Генетические алгоритмы в скринсейвере

в 8:01, , рубрики: c++, game development, SFML, эволюция, метки: , ,

Последний месяц в армии. Постепенно освобождается время для разных интересных проектов. Остается только определиться, чем именно занять мозги. Закончил читать «Эгоистичный ген» Ричарда Докинза и идея была сформулирована – хочу сделать визуализацию, использующую принципы эволюции.

image
Рисунок 1. Популяция бактерий перестраивает среду под свои нужды.

Итак, вперед!

  • Чашка Петри и идея программы
  • Язык программирования, среда, библиотеки
  • Рабочая версия, слишком простая
  • Дополнительные идеи
  • Первые интересные результаты
  • Оптимизация, конфиг
  • Программирование поведения
  • Полезные фичи
  • Разбор полетов, планы
  • Ссылки на программу, исходники, инструкции
Чашка Петри и идея программы

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

С самой чашкой Петри (игровым полем) все было ясно с самого начала – двумерный массив концентраций пищи, яда и феромона, который каждый кадр медленно смешивается (обычным blur’ом). Игровое поле замкнутое – представляет собой поверхность тора. А вот с реализацией бактерий не все так просто. Если они будут дискретно располагаться на поле, каждая в определенной ячейке, я получу очередной клеточный автомат, только со сложными правилами. Поэтому стоит сделать для них элементарную физическую модель – без коллизий, но с float-координатами, скоростью и трением. А пища, яд или феромон, с которыми взаимодействует бактерия, будет выбираться из ближайшей клетки поля.

Бактерии получают энергию из питательной среды, способны выделять яд и феромон. Накопленная пища тратится ежесекундно, любое действие (движение, повороты, выделение) тоже тратит внутренние ресурсы. Бактерии размножаются бесполо, простым делением, после того, как накопили определенное количество пищи. Помимо этого у организма есть очки жизни, уменьшающиеся в ядовитой среде или во время голода. Умирающая бактерия оставляет после себя небольшой запас пищи. Яд будет сдерживать размножение бактерий, а сигнальное вещество позволит одному существу сообщить другим: «эта территория уже занята, добывать пропитание здесь не выгодно» (чем больше бактерий в одном месте, тем больше там концентрация феромона и, вероятно, тем меньше там пищи).
Идея сформулирована, пора приступать к реализации.

Язык программирования, среда, библиотеки

Я немного схитрил и в качестве отправной точки использовал свой недавний проект, в ядре которого было все мне необходимое – работа с конфигами, мышью, клавиатурой и камерой. Язык – С++11 (GCC 4.8.1, на MinGW), среда разработки – NetBeans 7.4 (и иногда Sublime Text 3) В качестве библиотеки для работы с графикой (OpenGL) выбрал SFML 2.1, а для сохранения конфигов – jsoncpp. К сожалению, в начале разработки не было возможности установить систему контроля версий и это сильно портило жизнь. Как только такая возможность появилась – mercurial с tortoiseHg. Как видите, все кроссплатформенно и при желании можно будет поиграться и на других системах (на данный момент под рукой только XP).

Рабочая версия, слишком простая

Поле для жидкостей я изначально сделал как массивы чисел с плавающей точкой, из-за этого самым медленным куском программы стало размытие этого поля на CPU. Впрочем, об оптимизациях позднее. Движения у бактерий очень простые, по сути, всю физику успешно обрабатывает вот этот кусок кода (ССЫЛКА НА ИНТЕГРИРОВАНИЕ ВЕРЛЕ):

Math::Vector tmp = this->position;
this->position += this->position - this->old_position;
this->old_position = this->position - (1.0f - this->settings.friction) * (this->position - tmp);

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

MOVE, ROTATE_LEFT, ROTATE_RIGHT, CREATE_FEROMON, CREATE_POISON

Каждое действие – число с плавающей точкой, его значение определяет «силу» движения. Таким образом, при клонировании бактерии значение любого действия может с некоторой вероятностью измениться.

Очевидно, что с таким «сложным» поведением каши не сваришь, но результат получился еще плачевнее, чем хотелось бы. Все бактерии, выделяющие яд, быстро погибали, не оставляя потомства. На выделяемый феромон никто (кроме меня) не обращал внимания (у бактерий пока не было сенсоров). В результате все только плыли, пожирая еду под собой и при накоплении необходимой для размножения пищи создавали еще таких же бестолковых существ.

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

image
Рисунок 2. Быстрое клонирование и ядовитая среда

Дополнительные идеи

Судя по всему, идея с токсичным «ядом» и сигнальным «феромоном» работает из рук вон плохо:

  • Не выгодно производить яд, который убивает производителя и его потомков.
  • Не выгодно производить феромон (и при наличии рецепторов тоже), который выдает наличие бактерии, но не сообщает о ее «виде»

Я отказался от двух независимых веществ с разными свойствами и вместо них сделал у каждой бактерии «точку идеальной среды» — соотношение двух жидкостей (POISON и FEROMON, названия оставил различными для удобства), при котором окружающая среда не наносит бактерии повреждений. Чем сильнее отличается соотношение, тем токсичнее эта смесь для существа. Значение этой точки (resist) передается от родительской бактерии к дочерней с небольшими искажениями.

image
Схема 1. Идеальная среда для организма

Первые интересные результаты

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

image
Рисунок 3. Две различные популяции перестраивают окружающую среду

Оптимизация

Результат получается интересным, но скорость оставляет желать лучшего: 50 — 60 миллисекунд на фрейм дают 16-20 FPS. Для профилирования я использую gprof, но и без него ясно, что самое узкое место программы – размытие массива «жидкостей» на CPU. А текущая реализация (3 жидкости разных цветов, должны размываться и выводиться на экран) так и просится быть переписанной на GPU. В SFML очень просто работать с шейдерами и рендером в текстуру. Один недостаток – нет поддержки floating-point текстур. Так что переводим все жидкости из float (от -1.0 до 1.0) в unsigned char (0, 255) и храним как sf::Image. При обновлении поля рендерим его в текстуру, с шейдером размытия. Пишем GLSL фрагментный шейдер (для начала достаточно обычного среднего арифметического текущего текселя и его соседей, возможно, с некоторыми коэффициентами):

uniform sampler2D texture;

uniform float blurSize;
uniform float horizontalPass;
uniform float sigma;
uniform float width;
uniform float height;

vec2 ranged(vec2 v)
{
	if (v.x < 0.0)
		v.x += 1.0;
	else if (v.x >= 1.0)
		v.x -= 1.0;

	if (v.y < 0.0)
		v.y += 1.0;
	else if (v.y >= 1.0)
		v.y -= 1.0;

	return v;
}

void main()
{
	vec2 texcoordOffset = vec2(1.0, 1.0) / vec2(width, height);

	float k0 = 1.0;
	float k1 = 0.5;
	float k2 = 0.357;

	vec4 avgValue =
		texture2D(texture, gl_TexCoord[0].st) * k0 +
		texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, -1.0))) * k1 +
		texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, -1.0))) * k1 +
		texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, 1.0))) * k1 +
		texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, 1.0))) * k1 +
		texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, 0.0))) * k2 +
		texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, 0.0))) * k2 +
		texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(0.0, -1.0))) * k2 +
		texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(0.0, 1.0))) * k2;

	gl_FragColor = avgValue / (k0 + 4.0 * k1 + 4.0 * k2);
}

Скорость работы сразу же увеличилась в 2 — 2.5 раза. Просторы для оптимизаций остаются. Пользуясь gprof, находим еще несколько узких мест.

Но все-таки, самое неприятное бутылочное горлышко – магические числа в коде, из-за которых приходится пересобирать проект каждый раз при изменении настроек. Перенести все настройки в json-конфиг достаточно просто, а результат того стоит.

image
Рисунок 5. Перестройка среды схожими популяциями

image
Рисунок 6. Медленное разрастание колонии

Программирование поведения

На данный момент бактерия не может сменить свое поведение. Массив actions, определяющий ее действия, слегка меняется только у потомков бактерии, оставаясь константным на протяжении ее жизни. В целом, поведение популяции постепенно меняется, за счет эволюционного процесса – вредные мутации отсекаются, полезные – накапливаются. Но польза здесь – очень относительное понятие.

Например, бактерия находится в среде {FEROMON = -0.5, POISON = 0.2}, а ее идеальная среда {FEROMON = 0.6, POISON = 0.6}. Значит, ей выгодно производить в небольшом количестве оба вещества, чтобы приблизить окружающую среду к идеальной. Но она не сможет остановиться, и через некоторое время, продолжив синтезировать яд и феромон, удалится от идеала и погубит себя. Что, если «научить бактерию» следить за окружающей средой и принимать решения?

Остается решить, каким образом это сделать. Есть идея ассемблеро-подобного языка, чьи инструкции и будут составлять генокод бактерии. Но в таком случае понадобится множество мутаций для перехода от одной полезной программы действий к другой, а подавляющее большинство мутаций и вовсе будут летальны.

Возможно, нейросети? Я попробовал для каждой бактерии сделать мозг из маленького перцептрона в 2 слоя и несколькими обратными связями. Веса связей при создании первых бактерий – случайные и мутируют у их потомков. Получилось еще хуже, чем без мозга вообще. Я не расчитывал, что этот маленький эксперимент принесет положительные результаты – каюсь, с нейросетями любых видов практически никогда не работал. Предполагаю, что эволюционный отбор просто не способен был оставить наиболее приспособленные нейросети, т.к. окружающая среда вокруг бактерий слишком агрессивна для продолжительной жизни, а нейросети на первых порах совершенно не обучены и выдают бессмысленные, или даже вредные для бактерии команды.

Вскоре появилась новая идея – условия. Условие в моем случае выглядит так:
1 Рецептор – какие именно входные данные будут влиять на результат: FOOD, FEROMON, POISON, SPEED, FAT, LIFE, FEROMON_RESIST, POISON_RESIST;
2 Условный интервал – интервал, значений рецептора, в котором условие будет считаться истинным
3 Действие – на что именно влияет условие: MOVE, ROTATE_LEFT, ROTATE_RIGHT, CREATE_FEROMON, CREATE_POISON
4 Операция – как будет изменяться действие при выполнении условия: APPEND (к значению действия добавляется «сила воздействия»), DEDUCT (из значения действия вычитается «сила воздействия»), CLEAR (значение действия становится равным нулю)
5 Сила воздействия – число, на которое будет меняться действие.

Итак, условие: 

RECEPTOR[min, max], ACTION,OPERATION,VALUE.

Возьмем ситуацию с бактерией в среде {-0.5, 0.2} и с идеальной средой {0.6, 0.6}. Такой набор условий обеспечит ей создание и поддержание идеальной среды:

FEROMON[-1.0,-0.4] CREATE_FEROMON APPEND 0.1
FEROMON[0.6,1.0] CREATE_FEROMON DEDUCT 0.1
POISON[-1.0,-0.5] CREATE_ POISON APPEND 0.1
POISON [0.7,1.0] CREATE_ POISON DEDUCT 0.1

А такие условия позволят достаточно эффективно добывать пищу:

FOOD [0.0, 2.0] MOVE APPEND 1.0 // Двигаться, если пищи вокруг мало
FOOD [2.0, 10.0] MOVE CLEAR 0.0 // Остановиться, если пищи вокруг много

Написал отдельный класс DNA, хранящий всю генетическую информацию. При размножении бактерий каждый ген может с определенной вероятностью быть удален или дублирован. Существует вероятность добавления новых, радномных генов-условий. Помимо набора условий, в ДНК хранится максимальная скорость бактерии и значение идеальной среды. Попробовал размножение бактерий сделать еще одним действием, для активации которого также нужно использовать условия, но результат оказался унылым. А вот одна особенность использования таких «условных» генов показалось мне любопытным. Например, какой-то бактерии выгодно постоянно вращаться с небольшой скоростью. Но при движении все рецепторы будут менять свои значения, как бактерии указывать, что ей нужно вращаться всегда? Эволюция иногда отбирала тех особей, чьи условия были заведомо истинными, например, POSION_RESIST[0.3, 0.6] при сопротивляемости к яду 0.4. С одной стороны, такой подход позволяет бактериям выполнять определенное действие в не зависимости от окружающей среды и показателей рецепторов, с другой – ограничивает мутационную изменчивость идеальной среды (так как те бактерии, чья сопротивляемость выходит из определенных пределов, теряют все свои безусловные действия).

Кстати, вызов одного условия тоже тратит запасы пищи, поэтому создавать большое количество мусорных генов-условий эволюционно невыгодно. Можно заметить зависимость (просматривая ДНК отдельных бактерий) – чем больше пищи, тем больше мусорных генов хранится в ДНК.

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

image
Рисунок 7. Поглощение пищи популяцией с условным поведением.

Полезные фичи

Нельзя было не добавить в программу интерактивности. Например, возможность рисовать ядом, пищей или феромоном. Опишу все возможности управления:

  1. Управление камерой:
    1. Скролл – приближение/удаление камеры
    2. Drag с нажатым скроллом – перемещение камеры
  2. Рисование:
    1. Левая кнопка мыши – рисовать текущей кистью
    2. Вверх – изменить размер кисти
    3. Вниз – изменить «чернила»
    4. Очистить экран от всех жидкостей — q
  3. Визуализация:
    1. Отобразить/показать бактерии – пробел
    2. Сохранять каждый кадр в *.png – F8
    3. Умирающие бактерии краснеют, а голодающие – приобретают циановый оттенок
  4. Скорость:
    1. Переключить режим работы (медленно/быстро/пауза) – правая кнопка мыши
  5. Информация:
    1. Получить информацию о ДНК ближайшей к мыши бактерии (лучше использовать при остановке времени, 1/0 перед геном –выполнялось ли условие в последнем фрейме) – i
  6. Настройки программы:
    1. Настройки окна – data/settings.json
    2. Настройки папки сохранения кадров – data/screensaver.json
    3. Настройки поля, бактерий и т.д. – ai.json (при повреждении или удалении файла он автоматически восстановится)
Разбор полетов, планы

Программа изначально создавалась как микро-прототип, поиграться на 15 минут. Но затянуло. Поэтому у кода есть все недостатки прототипа, которые, впрочем, планирую устранить. Результат получился не таким красивым, как промежуточные версии (без ДНК и с разноцветными популяциями), стоит задуматься другими вариантами визуализации, например, окрашивать бактерии в зависимости от их происхождения. Еще одна важная проблема – отсутствие балансировки количества пищи: сложно подобрать настройки так, чтобы программа могла проработать всю ночь, а популяции не вымерли.

Вот что я хочу изменить в ближайшее время:

  1. Восстановление floating-point значений клеток поля (но все еще на видеокарте), чтобы убрать постоянную конвертацию (с потерями) из float в uchar
  2. Оптимизация. Много узких мест, например, клонирование бактерий.
  3. Распараллеливание. Программа работает в одном потоке, в то время как программа должна отлично распараллеливаться.
  4. Автобаланс веществ. Добавление пищи на поле при необходимости
  5. «Эдемский сад». Отбор самых успешных бактерий для их последующей культивации.
Ссылки на программу, исходники, инструкции

Последняя собранная версия программы
Исходники программы (в папке run лежит собранная версия), вам понадобятся SFML 2.1 и jsoncpp. Следует заметить, что до последнего момента я использовал в качестве вектора b2vec2 из box2d(наследие прошлого проекта) и только в последних коммитах заменил его на самописный вектор. Поэтому, если появится желание собрать старую версию — перенесите туда новый Math::Vector из core/math/vector.h

Играетесь с настройками в ai.json, запускаете ai.exe и следите за эволюцией (или активно вмешиваетесь).

Приятной эволюции!

Автор: nightrain912

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js