Dракоши. Часть 1. Эволюционная модель мультиагентной системы на базе нейронной сети. Введение

Идея

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

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

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

• Эволюционирующие цветные прямоугольники;
• Эволюционирующие часы;
• Нейронные муравейчики Александра Панчина
• Научные публикации М. Бурцева и В. Редько, популярный рассказ о его работе был в передаче с Гордоном.

Мне же хочется создать имитационную модель с несколько более сложной механикой и соответственно с более широким набором возможностей развития и усложнения. Основные особенности разрабатываемой модели:

1. Моделируется эволюция популяции агентов – Dракош, представляющих собой искусственные нейронные сети, структура и параметры которых определяются хромосомами агента;
2. Агенты могут перемещаться и взаимодействовать в торообразном двумерном пространстве (противоположные стороны квадрата замкнуты друг на друга). При этом пространство разбито на ячейки, в которых может одновременно размещаться не более двух агентов;
3. Время в мире Dракош дискретно;
4. В пространстве неравномерно распределяется ограниченный ресурс – cake, который служит источником энергии агентам.
5. Агенты могут выполнять действия (движение, питание, размножение, атака), при этом расходуется запасенная ранее энергия;
6. Решение о следующем действии является выходным сигналом нейронной сети. Входные сигналы поступают от трех видов рецепторов: «глаза» для наблюдения еды в окрестности агента, «глаза» для наблюдения других агентов, «рецептор» оставшегося запаса энергии;
7. В популяции агентов реализуется половое размножение, с кроссинговером хромосом и их мутациями. В ходе мутаций случайным образом изменяется генотип агентов, который определяет размер, структуру и параметры их нейронной сети;
8. Агенты, у которых запас энергии стал меньше минимально необходимого для выживания погибают. Остаток энергии, который был у агента на момент смерти выпадает в ячейку пространства в виде «лепешек».

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

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

В первой части я опишу устройство и механику вселенной Dракош и расскажу какие потенциальные возможности есть у агентов.

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

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

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

Вселенная Dракош

Агенты обитают в двумерном пространстве, которое свернуто в тор, что бы у него не было краев и агенты всегда могли двигаться, не натыкаясь на препятствия (Рис. 1).


Рисунок 1.Тор. Для получения развертки тор разрезается вдоль выделенных окружностей и разворачивается на плоскость в виде прямоугольника.

Все доступное для агентов пространство разбито на шестигранные клетки (Рис. 2). Их мир выглядит как пчелиные соты. При моделировании я использовал размер мира 100×100 клеток (общая площадь 10 000 клеток). В одной клетке может одновременно находится не более двух агентов. Если какой-то агент в процессе движения пересекает одну из границ прямоугольника, то он возвращается в прямоугольник с противоположной стороны, как будто он ползает по бублику.

Кроме агентов в клетках находится питательный ресурс – cake, который могут поедать агенты. Еда генерируется в клетках в соответствии со специальным алгоритмом.

Еда для Dракош

В каждой клетке может находится произвольное количество целых cake (рис. 2). За один такт времени агент может съесть один cake, это пополнит его запасы энергии на 50 J – энергетическая емкость пищи.

UPD 1: В ходе экспериментов с стохастической моделью агентов энергоемкость была увеличена до 75 J.


Рисунок 2. Пример расположения порции пищи в пространстве. Серые клетки не содержат еды, тёмно-синие содержат 1 cake, жёлтая – 15 cake.

Количество пищи в пространстве постоянно изменяется. Имеются механизмы деградации и разрастания пищи в пространстве, которые необходимы для поддержания стационарного количества еды в пространстве. Эти механизмы выступают в роли фактора, ограничивающего доступность ресурсов и заодно обеспечивающих изменяемость среды обитания. Количество пищи изменяется вследствие следующих процессов:

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

Среднее суммарное количество пищи в пространстве зависит от плотности заселения агентами. Когда плотность заполнения пространства агентами меньше одного агента на одну клетку (1 Dr/cell), то стационарная плотность еды в пространстве составляет 20 cake/cell (или 1000 J/cell в энергетических единицах). Но если агентов становится больше одного на клетку стационарное количество пищи в пространстве, которое может поддерживаться в пространстве, будет уменьшается. И когда агенты полностью заполняют пространство (2 Dr/cell) стационарное количество пищи становится равным нулю (рис. 3).


Рисунок 3. Зависимость стационарного количества пищи от плотности агентов в пространстве

UPD 1: В ходе экспериментов с стохастической моделью была изменена.

Если количество пищи становится меньше заданного стационарного значения, то в конце текущего такта времени в пространстве будет сгенерировано 50% текущего недостатка пищи. Необходимый объем пищи генерируется порциями в случайном месте, случайного объема (но не меньше 250 cake). Такие порции генерируются пока не будет выложено в пространство необходимое количество еды.

Если количество пищи превысит заданное стационарное значение, то в конце текущего такта времени количество пищи в случайно выбранных группах смежных клеток будет уменьшено. Группа состоит из 19 клеток (рис. 4). Количество таких групп выбирается таким что бы избыток пищи уменьшился на 10%. Это можно интерпретировать как невозможность поддерживать избыточное количество пищи в пространстве, в результате чего она деградирует. C течением времени количество пищи в пространстве будет стремится к заданному стационарному значению.

Такой алгоритм генерирования пищи позволяет не допустить «перенаселения».

Устройство Dракош

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

• имя агента, уникальное на всем протяжении моделирования натуральное число;
• имеющийся у агента запас энергии, который выражается целым числом J;
• номер ячейки, в которой находится агент;
• возраст агента, натуральное число, которое в конце каждого такта времени увеличивается на единицу;
• поколение агента, натуральное число. При рождении агента этот параметр задается на единицу больше поколения одного из родителей (из двух выбирается тот родитель, у которого эта характеристика больше);

Каждый агент имеет по три хромосомы, две из которых задают параметры его нейронной сети:

1. Хромосома WEIGHTS – матрица весов нейронов скрытого слоя;
2. Хромосома BIAS – вектор смещений нейронов скрытого слоя;
3. Хромосома COLOR – задает три компонента цвета агента – красный, зеленый, синий. Эти три хромосомы наследуются при размножении.

У агентов имеются четыре группы рецепторов, которые передают информацию из окружающей и внутренней среды на входные слои нейронной сети агентов.

• наличия пищи в соседних ячейках (19 рецепторов) – позволяют агенту получать информацию о количестве пищи рядом с ним (рис. 4);
• наличия агентов в соседних ячейках (19 рецепторов) – позволяют агенту получать информацию о количестве других агентов рядом с ним (рис. 4);
• цвета соседнего агента (3 рецептора) и собственного цвета (3 рецептора) – позволяют агенту получать информацию о цвете второго агента в клетке, если такой есть и о своем цвете;
• текущего запаса энергии у агента (1 рецептор);

Рисунок 4. Схема ячеек, которые видны агенту, показан фиолетовым кругом в центре. В каждую из этих клеток агент может совершить шаг. С 1й по 6ю –длина шага равна одной клетке. С 7й по 18ю – шаг длиной в две клетки.

Выходы нейронной сети соединены с группой эффекторов, состояние которых определяет действие, которое агент совершит в текущий такт времени. Агенты могут совершить одно из шести действий: pass, step 1, step 2, eat, attack, sex.

Pass – бездействие – агент не совершает никаких действий, оставаясь на месте. Это действие всегда успешно.

Step 1, Step 2 – агент совершает попытку шагнуть в одну из 18 соседних клеток (рис. 4). Step 1 – шаг длинной в одну клетку. Step 2 – шаг длиной в две клетки. Если в выбранной агентом клетке есть свободное место, то действие успешно и агент перемещается на новое место, иначе действие не успешно и агент остается на старом месте.

Eat – попытка скушать пищу в текущей клетке. Если в клетке есть еда, действие успешно и агент съедает 1 cake и увеличивает свой запас энергии на 50 J.

Attack – попытка ударить агента в текущей клетке. Если в клетке с агентом есть второй, то действие успешно и соседний агент теряет 150 J и в ячейку выпадает 3 cake.

Sex – агент пытается спарится с агентом в текущей клетке. Спаривание будет успешным только в том случае если в ячейке находится еще один агент, и он так же совершает действие Sex. В этом случае оба агента-родителя теряют по 1/3 своего запаса энергии (в дополнение к затратам энергии на функционирование нейронной сети и совершение действия, см. табл. 1). Новорожденный агент получает по 1/3 запаса энергии от каждого родителя. Действие будет успешным если новорожденный получит достаточно энергии для выживания – больше 500 J, иначе он сразу же умирает. Третьим условием успешности действия Sex является выбор агентом-родителем (который дал большую часть энергии – самки) соседней ячейки со свободным местом для размещения новорожденного агента. В случае если в этой ячейке нет свободного места, то действие Sex считается не успешным, и новорожденный погибает. В случае гибели новорожденного его запас энергии превращается в еду и помещается в клетку с родителями.

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

Таблица 1. Энергетическая стоимость действий агентов

Действие	Успешность	Изменение запаса энергии агента, J
Pass	+	— e0
Step 1	+	— e0 — 9
Step 2	+	— e0 — 24
Step 1/2	-	— e0 — 4
Eat	+	+ 50 — e0 — 3
Eat	-	— e0 — 3
Attack		— e0 — 49
Sex	+ / -	— e0 — 34

Самым дешевым с точки зрения энергозатрат является действие Pass. Количество затрачиваемой на бездействие энергии (e₀) определяется размером нейронной сети агента. Чем больше нейронов в скрытом слое, тем больше затраты энергии на функционирование нейронной сети. Эти потери энергии имеют место и при любом другом выбранном действии. Зависимость фоновых энергозатрат от количества нейронов позволит ограничить рост вычислительных затрат без ощутимого роста приспособленности агентов.

Когда запас энергии агента становится меньше 500 J – агент погибает, и остаток его энергии выбрасывается в клетку, которую он занимал.

UPD 1: В ходе экспериментов с стохастической моделью были изменены энергетические стоимости.

Энергетическая модель вселенной Dракош

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


Рисунок 5. Схема потоков энергии в модели Dракош

Еда в пространство поступает извне системы с потоком food in. Так же есть два внутренних потока пополняющих запас еды в пространстве: harm, dead. Первый из них обусловлен потерями энергии агентами, которые подверглись атаке соседнего агента. Потерянная ими энергия выпадает в виде эквивалентного количества cake в клетке с потерпевшим агентом. Второй поток – еда, появляющаяся в клетке после смерти агента, количество которой эквивалентно остатку энергии агента перед смертью.

Еда из пространства потребляется агентами, которые успешно совершают действие Eat – поток eating. Затраченная на совершение действий энергия покидает систему – поток used. Второй путь, которым энергия покидает систему – поток spoiled food, который связан с деградирующим избытком еды в пространстве.

Естественный отбор

Во вселенной Dракош действует естественный отбор.

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

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