Часть 3. Dракоши. Раса Тупиков или стохастическая модель мультиагентной системы

в 10:38, , рубрики: Без рубрики

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

image

Кто такие Dракоши смотрите в первой части. Во второй части описаны способы расчета вероятности успешного совершения действий при случайном поведении агентов.

1. Зачем нужна раса Тупиков?
2. Особенности расы Тупиков
3. Жизнь Тупиков
4. Реформирования вселенной Dракош

1. Зачем нужна раса Тупиков?

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

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

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

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

2. Особенности расы Тупиков

В отличии от полноценных Dракош у Тупиков всего две хромосомы:

  • Prob – хромосома с вероятностей действий. Состоит из семи элементов – генов. Первый ген задает вероятность мутации отдельных генов в обоих хромосомах. Остальные гены задают вероятность совершить одно из шести действий, поэтому сумма их значений равна единице.
  • Color – хромосома цвета агента. Строго говоря в данной модели не нужна, т.к. не оказывает никакого влияния ни на поведение агентов ни на их плодовитость. Но я ее оставил что бы использовать для визуализации агентов.

На старте моделирования гены хромосомы Prob инициируется случайным значением равномерно распределенными на отрезке 0..1, затем сумма значений генов со второго по седьмой нормируется на единицу. А гены хромосомы Color – значениями 0.5 (т.е. все по началу серые).

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

3. Жизнь Тупиков

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

На старте в пространстве случайным образом размещается 12500 агентов ($RDr=1.25$ Dr/cell). У каждого агента имеется в распоряжении 50 kJ энергии.

На рисунке в качестве примера показано 3 примера изменения плотности агентов в пространстве с течением времени.

image

Анализируя этот график можно выделить четыре характерных эпохи:

  1. «Взрыв» – эпоха характеризуется резким ростом численности агентов от начального значения до предельной численности пространства (в течении примерно 50 тактов). Происходит это за счет тех агентов, у которых вероятность действия Sex довольно высокая и их начального запаса энергии хватает на несколько циклов размножения.
  2. «Максимальное плато» – после заполнения пространства дальнейшее размножение и увеличения численности агентов возможно только взамен тех, которые умерли и освободили места для детёнышей. В течении примерно 300 тактов времени плотность агентов держится вблизи максимума. К концу этого этапа агенты расходуют большую часть начального запаса энергии и начинается массовое вымирание. Плотность агентов быстро падает, примерно еще за 300 тактов.
  3. «Бутылочное горлышко» – на этом этапе после резкого падения численности агентов продолжает уже медленно уменьшатся до минимального значения – 0.25-0.30 Dr/cell. После прохождения минимума плотность увеличивается почти до своего равновесного значения. Длительность этого этапа варьируется в широких пределах – 2000-3000 тактов.
  4. «Устойчивое развитие» – когда плотность достигает значений чуть более 1.0 Dr/cell происходит резкое изменение динамики системы. Быстрой рост численности сменяется медленным ее увеличением с небольшими флуктуациями. Постепенно рост численности агентов замедляется и плотность приближается к равновесному значению – 1.23-1.24 Dr/cell. Наступает динамическое равновесие: рождаемость уравновешивается смертностью.

Ниже показано четыре скриншота демонстрирующих состояние пространства для каждого из обозначенных моментов времени. Сине-бирюзово-желтым градиентом отмечено распределение пищи в пространстве. Серые ячейки не содержат еды. А агенты обозначены цветными кружками согласно их хромосоме Color. Размер кружков пропорционален возрасту агентов.

image

А в этом ролике показано происходящее на участке пространства 15х15 ячеек в течении 20000 тактов времени.

Для отслеживания и анализа происходящего были использованы следующие параметры:

  • $RDr$ – знакомая уже плотность агентов в пространстве, которая равна отношению количества агентов к количеству ячеек в пространстве. Изменяется от 0 до 2 Dr/cell;
  • $En_{Mean}$ – средний по популяции запас энергии агента, kJ;
  • $Age_{Mean}$ – средний по популяции возраст агентов;
  • $Gen_{Mean}$ – среднее по популяции поколение агентов;
  • $Birth$, $Death$ – относительная рождаемость и смертность агентов. Изменяется от 0% до 100%;
  • $f_{Pass}$, $f_{Stp1}$, $f_{Stp2}$, $f_{Eat}$, $f_{Att}$, $f_{Sex}$ – средняя по популяции частота совершения действий, которые совершают соответствующее действие в течении каждого такта времени. Изменяется от 0 до 1, но их сумма равна 1;
  • $L_{Stp}$, $L_{Eat}$, $L_{Att}$, $L_{Sex}$ – успешность действий или доля агентов успешно совершивших вы-бранное действие. Изменяется от 0 до 1;
  • $I_{Stp}$, $I_{Att}$, $I_{Sex}$ – индексы осознанности действий описанные в части 2. Изменяются от 0 до 1;
  • $I_{Food}$ – индекс осознанности действия Eat, разность между успешностью $L_{Eat}$ и вероятностью обнаружить в ячейке еду:

    $I_{Food}=L_{Eat}-frac{C_{Food}}{S}$

    где $C_{Food}$ – это количество ячеек, в которых в данный момент есть хотя бы один cake, $S$ – полное количество ячеек в пространстве. $I_{Food}$ изменяется от 0 до 1;

  • $I_{CrlStpFd}$ – индекс осознанности выбора направления движения, сейчас он оценивает степень корреляции между направлением шага и направлением с максимальным градиентом количества пищи в пространстве. Изменяется от -1 до 1;

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

«Взрыв» и «Максимальное плато»

image
«Взрыв» – самая короткая эпоха в развитии популяции Тупиков. В течении этой эпохи происходит первичная селекция агентов – увеличивается доля агентов, боле часто совершающих попытки размножения (см. граф. Action frequency выше). Начальный запас энергии (50 kJ) позволяет агентам размножатся, даже если они вообще не будут пополнять его. Размножение происходит до полного заполнения пространства (см. граф. Density of Agents). Когда плотность агентов приближается к 2.0 Dr/cell успешность размножения стремится к нулю, т.к. для новых агентов просто не найти места.

Так начинается эпоха «Максимального плато», когда численность держится у предельного значения. При этом агенты не оставляют попыток размножится, частота действия Sex после первой эпохи остается наибольшей. Но успешность этого действия очень низкая (см. граф. Part of Luck Action). А успешными такие попытки становятся только когда кто-то из агентов умирает и освобождает место в пространстве для нового агента. На графике Birth & Death Rate это выглядит как совпадение линий смертности и рождаемости во время второй эпохи.

Действие Sex становится не очень выгодным, когда его успешность близка к нулю и его частота, как и частота действия Attack снижаются. Начиная с этой эпохи самым модным на долгое время становится действие Eat – его частота начинает расти. Но все равно запас энергии у агентов продолжает снижаться, хоть и не так быстро, как в первую эпоху (см. граф. Energy of Agents). К концу второй эпохи большинство агентов почти растратило свой запас энергии и начинается массовое вымирание. После которого начинается новая эпоха.

«Бутылочное горлышко»

image

Массовое вымирание на рубеже второй и третьей эпохи связано с вымиранием активно размножающихся агентов. На граф. Action frequency это видно как снижение частоты действия Sex во время массового вымирания. Это обусловлено тем, что активное размножение чрезвычайно сильно снижает запас энергии агента, даже неуспешная попытка размножения требует лишь немного меньше энергии чем самое энергоемкое действие – Attack.

В течении третьей эпохи активно начинает увеличиваться доля агентов пытающихся поесть (см. граф. Action frequency). При этом доля агентов совершающих энергозатратные действия – Attack, Step 2 – наоборот, уменьшается. Это приводит к тому, что запас энергии у агентов постепенно начинает расти.

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

Но на этот раз плотность агентов не достигает предельного значения. С ростом плотности агентов стационарное количество еды в пространстве уменьшается. В результате чего успешность питания снижается (см. граф. Part of Luck Action). При чем это снижение имеет место на всем протяжении третей эпохи и как видно на графике осознанности питания (см. граф. Awareness Indicators) его нельзя полностью объяснить уменьшением количества участков с пищей (успешность действия Eat меньше вероятности обнаружить еду). Скорее всего это объясняется тем, что интенсивно питающиеся агенты выедают пищу в своих ячейках и относительно реже перемещаются в соседние ячейки.

«Устойчивое развитие»

image

После демографического бума наступает динамическое равновесие – рождаемость и смертность уравновешивают друг друга – начинается четвертая эпоха. Рост количества агентов замедляется и постепенно плотность агентов приближается к стационарному значению – 1.23-1.24 Dr/cell. Интенсивность питания после усиленного роста в начале эпохи постепенно выходит на постоянное значение около $f_{Eat}≈0.850$. Для остальных действий частота составляет:

$f_{Pass}≈0.033$
$f_{Step1}≈0.058$
$f_{Step2}≈0.004$
$f_{Att}≈0.021$
$f_{Sex}≈0.044$

4. Реформирование Вселенной Dракош

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

Первое что я поменял это зависимость стационарного количества пищи в пространстве от плотности агентов. На каждом такте времени количество еды в пространстве корректируется (выкладывается или убирается) таким образом что бы приближаться к этому стационарному значению.

image

И то при каких значениях плотности агентов эта зависимость достигает значений порядка 8-14% от максимального (20 cake/cell) определяет значение стационарной плотности агентов в четвертую эпоху. «Смещая» эту кривую вправо-влево можно «выбрать» значение стационарной плотности агентов.

Высокое значение плотность агентов выгодно тем, что у большой популяции больший объемом генетических вариантов одновременно участвует в отборе. Но при очень высоких плотностях заполнения пространства успешность таких действий как Step1/2 и Sex снижаются и отбор смещается в сторону малоподвижных, прожорливых и агрессивных агентов.

На следующем рисунке показано как изменяется стационарные значения частоты действий Step 1 и Attack в зависимости от стационарной плотности (планки погрешностей указывают стандартное отклонение по популяции).

image

При значениях плотности агентов больше 1.3 Dr/cell в четвертой эпохе (спустя достаточное время – порядка $10^4$ тактов) популяция становится агрессивной: действие Attack – становится вторым по частоте совершения после действия Eat. При этом частота совершения шагов сильно уменьшается, и агенты очень редко перемещаются. По-видимому, это связано с тем, что при значениях плотности больше 1.0545 Dr/cell вероятность успешной атаки становится больше вероятности успешного шага (см. часть 2, раздел 5). В этом случае у агента больше шансов совершить успешную атаку и выбить три порции пищи из соседнего по ячейке агента чем попытаться переместится в соседнюю ячейку в надежде найти там свободное место и еду (напомню, агенты все еще совершают действия вслепую). Но когда плотность увеличивается больше 1.3 Dr/cell превышение вероятности успешной атаки над вероятностью успешного шага становится достаточно существенным что бы отбор поспособствовал закреплению в популяции более агрессивного поведения.

В итоге я остановился на значениях стационарной плотности агентов 1.23-1.24 Dr/cell. При этой плотности вероятность успешной атаки уже выше вероятности успешного шага (на 17%), но установившееся значения частоты совершения действий Step 1/2 почти втрое больше частоты действия Att.

Вторым изменением было увеличение энергоемкости пищи с 50 J/cake до 75 J/cake. И вместе с ним увеличен минимальный жизненно необходимый минимум энергии у агента: с 500 J до 750 J. Так же для сохранения баланса изменил энергетическую стоимость действия Att: с 55 J до 100 J.

Эти изменения привели к тому, что минимальная плотность агентов в третью эпоху увеличилась с 0.07-0.1 Dr/cell до 0.25-0.3 Dr/cell и сократилась длительность третей эпохи. В остальном поведение модели осталось прежним.

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

Что бы интенсифицировать появление новых генетических вариантов в популяции я решился ввести «плату» за возраст – дополнительную потерю энергии. До 7000 тактов она меньше 2 J, а после 10000 тактов становится больше 15 J. В результате чего максимальный возраст агентов в четвертую эпоху стал чуть более 10000 тактов, а средний около 3000 тактов. А скорость смены поколений стала почти постоянной (см. график Generation of Agents для 4й эпохи).

На этом, думаю, можно завершить исследование расы Тупиков и перейти к самому интересному – реализации полноценных Dракош. Хотя не сомневаюсь, что и c такой упрощенной моделью можно еще много чего интересного проделать. Но не терпится уже поэкспериментировать с эволюционирующими нейронными сетями.

Автор: TRSloz

Источник


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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js