Искусственная жизнь

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



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

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

Для того чтобы этот процесс показать была написана на C# моделька, в которой сотни особей живут, умирают, передают друг-другу гены, изобретают всякие мемы, и учатся им друг у друга. Искусственная жизнь умеет совместно охотиться или отлынивать от работы, убеждать соплеменников отдать больше совместно нажитой добычи, учиться более эффективно охотиться и кооперироваться с другими охотниками. Конкурировать с соседними племенами за еду. Хотеть и уметь учиться у других, а так же хотеть и уметь учить. Стремиться наказывать халявщиков не желающих охотится, и отдельно учится определять того ли ты наказал. Ещё будущие геты умеют заниматься всякой бессмысленной фигнёй, и отращивать себе память в мозгу. Всё это они умеют как в виде генов, которые они передают потомству при заведении виртуальных детёнышей, так и приобретая соответствующие приёмы мемы, которые живут в популяции свой жизнью, используя мозги обитателей симуляции как свою среду обитания. В общем запуская симуляцию вы делаете примерно то же самое, что забыв в раковине не помытую посуду ставите эволюционный эксперимент. Только с графиками и возможностью сравнить свои результаты с результатами серьёзных учёных.

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

Часть первая, про Оптимизацию.

Make it work, Make it right, Make it fast! Kent Beck
Автором симулятора был сын нашего учителя Михаил JellicleFencer Марков. В комментариях под статьей он выложил ссылку на репозиторий: jelliclefencer.visualstudio.com/_git/TribeSim. Написать то он её написал, причём так чтобы происходящее внутри было понятно любому биологу без комментариев. Но времени на то чтобы заниматься оптимизацией у него явно не было. В результате залезши внутрь я в порядке хобби ускорил работу симуляции в 10-20 раз даже не прибегая к unsafe коду и прочим излишествам и потрогав пока только половину тормозящих мест. Читаемость снизилась, надеюсь, не критично. Азур меня почему-то не любит, поэтому я форкнулся на гитхаб вот сюда: github.com/kraidiky/TribeSim и там можно по коммитам проследить как я отъедал в куче мест по 5-15% прироста.

Я планирую ещё какое-то время продолжить этим заниматься и приглашаю желающих поучаствовать в этом занятии. Для этого надо форкнуть репозиторий, сделать коду хорошо, после чего отправить Pull Request. Честно то говоря никогда раньше так не делал за больше чем 20 лет программистской карьеры. Так что если я что-то делаю неправильно поправляйте.

Только давайте с развёрнутыми комментариями, без unsafe и экстримизма. Представьте, что читать и использовать этот код предстоит универовскому профессору, у которого в руках ваша зачётка. :)

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

Есть ещё одно занятие, которое я давно хочу: стримы с разбором кода. Это как транслировать свои игры в твиче, только с аудиторией в 1000 раз меньше. :)))


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

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

Часть вторая, про Биологию.

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

Если вам интересно позапускать симуляцию с разными настройками и посмотреть какую культуру вам вырастит свой собственный легион Гетов добро пожаловать в комментарии. Выкладывайте свои trsim-ы, показывайте графики с наблюдениями и сравнениями, какие ваши изменения приводят к каким эффектам. Удалось ли воспроизвести результаты показанные Марковым к статье? Какие опыты вы бы сами хотели поставить?

Я хотел тут расписать значение всяких параметров модели, но это длинно и не очень интересно. Вместо этого поставьте брейкпоинт в функции World.SimulateYear, загрузите trsim allFeatures и пройдите один год симуляции по шагам. Сразу поймёте что там к чему и зачем.

Часть третья, про Мечты.

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

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

В генетике такое представлено в полный рост, неспособность дать плодовитое потомство является самым простым критерием вида, лишь иногда дающим сбои в виде лигров. Мало кто знает, что то же самое наблюдается и внутри одного вида. Некоторые существа научились оценивать своё генетическое расстояние до потенциального партнёра и корректировать в связи с этим свои репродуктивные стратегии. Самый запомнившийся мне пример, когда дрозофилы оказавшись в состоянии пищевого стресса чаще выбирают в партнёры своих ближайших родственников, я ссылочки сейчас найти не могу, к сожалению, может позже отыщется. Но интересно что поведение мух очень логично, близкородственное скрещивание позволяет легче проявится странным рецессивным мутациям среди которых может найтись что-то полезное в сложившейся непростой жизненной ситуации. Люди селекционеры поступают точно так же. И мухи не только научились узнавать степень родства, но и научились этим пользоваться. Вообще не стоит мушек недооценивать. Строго показано, что у них может вырабатываться культура и передаваться из поколения в поколение.

В статье Маркова и Куликова (см. обзор: "Видообразование личное дело каждого" ) описывается распространённое сейчас предположение, что оценка генетического расстояния делается по запаху молекул имунной системы и приводятся примеры других животных которые так умеют. Например рыбы колюшки и мы с вами. Некоторые исследования показывают что люди с помощью вомероназального органа способны по запаху неосознанно оценить потенциального партнёра на степень родства слишком близкие и слишком далёкие непривлекательны на запах. Есть правда и другие исследования. Тема продолжает изучаться.

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

А есть ли у вас какие-нибудь интересные идеи, которые можно проверить в моделировании с помощью марковского симулятора после небольшой доработки. Делимся идеями, обсуждаем в комментах.

Часть третья, про Сингулярность.

Сам Александр Владимирович оговаривается, что в их модели не получилось увидеть стремительного гиперболического разгона мощности культуры, свойственного истории человечества. Также он упомянул, что есть идея поискать условия такого роста в виде комплексов взаимно усиливающих друг друга мемов. У меня же есть несколько иное предположение. Посмотреть про сингулярность можно очень меня вдохновившее выступление Панова на GF2045. А с ещё более скептическим взглядом ознакомиться в паре статьей Сергея Карелова "Техносингулярность становится технорелигией" и её второй части.

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

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

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

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

Заключение:

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

Идея

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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


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

Если количество пищи становится меньше заданного стационарного значения, то в конце текущего такта времени в пространстве будет сгенерировано 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. Энергетическая стоимость действий агентов

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

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

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

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


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

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

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

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

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

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

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

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



1. Зачем нам вероятности?
2. Постановка задачи
3. Подсчет способов расстановки агентов
4. Моделирование вероятностей методом Монте-Карло
5. Что получилось?

1. Зачем нам вероятности?

Как уследить за Dракошами

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

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

Напомню, агенты могут совершать шесть разных действий: Pass, Step 1, Step 2, Eat, Attack, Sex. Для каждого из них можно рассчитывать долю агентов, которые его совершает в течении каждого такта времени: , , , , , . Эти шесть параметров позволят понять, что делают Dракоши.

Все действия кроме Pass могут быть успешными или неуспешными, в зависимости от сложившейся ситуации в текущей и в соседних ячейках, а также от желаний соседа по занимаемой ячейке. Для отслеживания успешности используются четыре параметра: , , , . Они показывают какая доля из совершенных действий была успешной. При этом оба действия Step 1 и Step 2 учитываются в одном параметре .

Индексы осознанности или зачем нам вероятности

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

Так успешность действий Step 1/2 определяется наличием в ячейке, которую агент выбрал для перемещения, свободного места (всего в ячейках есть по два места для агентов). И будет зависеть как от правильности выбора агента, так и от количества агентов в пространстве. Текущее количество агентов удобно отслеживать с помощью параметра плотность агентов в пространстве, которая равна отношению количества агентов к количеству ячеек в пространстве. Когда агентов в пространстве мало, плотность близка к нулю и вероятность того, что в выбранной агентом ячейке будет свободное место близка к единице. Поэтому несмотря на наличие или отсутствие осознанности у агентов при низкой плотности агентов () успешность действий Step 1/2 будет высокой (). По мере увеличения количества агентов вероятность обнаружить в выбранной случайно ячейке свободное место снижается вместе с успешностью , если только выбор ячейки для совершения шага не будет делаться осознано. Когда количество агентов будет близко к максимальной емкости пространства () вероятность найти свободное место станет близкой к нулю (). Можно ввести параметр осознанности действий Step 1/2, который рассчитаем, как разность между текущей успешностью и вероятностью обнаружить свободное место в ячейке :

Здесь обозначает вероятность присутствия в выбранной ячейке двух агентов.
Таким же образом успешность действий Attack и Sex будет зависеть от вероятности () что агент обнаружит в ячейке, которую он занимает, еще одного агента.
Осознанность совершения атаки можно определить как превышение успешности над вероятностью :

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

2. Постановка задачи

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

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

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

Во втором подходе использовалось понятие частотной вероятности. Расчеты выполнялись с применением метода Монте-Карло. Вероятно, есть и другие способы вычислить эти вероятности, и возможно даже более простые. Буду благодарен за наводку на таковые.

3. Подсчет способов расстановки агентов

Вывод рекуррентной формулы

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

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

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

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

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

Количество способов заполнить ячейку агентами это сочетание без повторений из по :

Поместив агентов в ячейку , останется еще агентов для расстановки в ячейки с по . И каждому будет соответствовать способов расстановки оставшихся агентов. Произведение даёт нам количество способов разместить агентов в ячейке и агентов по остальным ячейкам. Суммируя по всем допустимым значениям , получим искомое количество способов расстановки:

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

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

  

• Для последней ячейки так же есть только один способ расставить агентов оставить все агентов в ней, но только если им хватит места:
  
  

  

• Если места не хватает для размещения агентов в ячейках с по , то способов заполнить ячейку нету:
  
  

  

Теперь можем записать выражения для вероятности :

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

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

Выражения для вероятности :

где это количество способов расстановки агентов, при которых в ячейку попадает предельное для этой ячейки количество агентов:

Упрощение и переход приведенному виду

Количество расстановок очень быстро растет и уже для чисел двойной точности не хватит. Даже если воспользоваться пакетами символьных вычислений с произвольной точностью (например, Symbolic Math Toolbox и Variable-precision arithmetic в среде MatLab) останется проблема переполнения стека вызовов рекуррентной функции при больших размерах пространства. Поэтому полученные выше выражения необходимо преобразовать. А еще лучше вывести формулу, с помощью которой сразу вычисляется без необходимости считать предыдущие значения.

Первое что можно сделать это вынести из-под знака суммы .

Но прежде введем обозначение приведенного количества расстановок агентов по ячейкам, которое в раз меньше:

И можем сократить выражения для вероятностей на факториал:

Где

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

• , при , ;
• , при , ;
• , при , ;
• , при .

Полученные выражения для приведенных количеств расстановок смотрятся поинтереснее т.к. коэффициенты в рекуррентной формуле постоянны и не растут со скоростью факториала как в формулах выше. Но все равно быстро и надежно вычислить вероятности при размерах пространства порядка 10⁴ не очень получится.


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


Готовые выражения для вероятностей теперь зависят только от приведенного количества способов расстановки агентов одного вида :

Построение производящей функции

Осталось научится рассчитывать элементы последовательности для произвольно больших значений и . Порывшись в учебниках по комбинаторике я нашёл довольно популярный и мощный метод для решения всяческих комбинаторных вопросов метод производящих функций.

Хорошим пособием для начинающих комбинаторов по производящим функциям можно назвать учебник Ландо С.К. [3]. Еще один ресурс типа справочник по производящим функциям. И еще вот этот пост на хабре. Но наиболее полезными для меня были видео лекции Игоря Клейна по производящим функциям, выложенные тут.

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


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

$$display$$\left\{ \begin{array}{} f_{0,0}=1 \\ f_{i,0}=f_{i-1,0} \\ f_{i,1}=f_{i-1,1}+f_{i-1,0} \\ f_{i,n}=f_{i-1,n}+f_{i-1,n-1}+\frac{1}{2}f_{i-1,n-2}, \text{ при } n\geqslant 2 \\ f_{i,n}=0, \text{ при } n>2i \end{array} \right.$$display$$

Наша последовательность зависит от двух индексов: количество ячеек в пространстве для расстановки агентов, ; количество агентов для расстановки в ячейках, . Поэтому и производящая функция ей нужна двумерная .

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

Теперь дело за малым, разложить полученную производящую функцию в ряд по степеням . Собственно, произвести элементы последовательности:

Теперь все что нам нужно это выделить коэффициент при , это и будет искомое выражение для элемента последовательности :

Для этого необходимо сгруппировать все слагаемые, у которых степень равна . Пределы суммирования при этом будут следующими: при , ; при , .

В результате получим два выражения, одно для чётного :

и одно для нечетного :

Полученные выражения уже можно попробовать вычислить, но так как биноминальные коэффициенты, которые входят в них, всё же растут довольно быстро, для расчетов необходимо воспользовался инструментами символьных вычислений MatLab.

4. Моделирование вероятностей методом Монте-Карло

Метод Монте-Карло или метод статистических испытаний это большая группа численных методов решения математических задач (причем не только вероятностной природы) при помощи моделирования случайных величин. Один из вариантов метода Монте-Карло предполагает что смоделированная случайная величина с известным распределением (зачастую равномерно распределённая на отрезке 0..1) используется для установления статистических характеристик других случайных величин или для приближённой оценки некоторого значения . Во втором случае придумывается некоторая случайная величина , такая что ее мат. ожидание равно искомой величине . Тогда рассчитав независимых значений случайной величины , , , определяют величину как среднее арифметическое выборки , , [2].

Для установления статистических характеристик случайных величин, например, для определения вероятности случайного события , можно реализовать другой вариант метода Монте-Карло. Когда проводится моделирование такой случайной величины , которая равна при реализации случайного события на испытании , или равна если события не наступило. При проведении независимых испытаний частота события , равная , стремится к искомой вероятности по мере роста количества испытаний [3]. Если для моделирования случайной величины в модели полностью или частично воспроизводится изучаемый естественный процесс, то такой подход так же называют имитационным моделированием.

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

Обзор алгоритма

В рамках метода Монте-Карло поставленная в разделе 2 задача сводится к оценке частоты реализации соответствующих событий. Так вероятность это частота обнаружения агентами соседей по ячейке. А вероятность это частота обнаружения ячеек с двумя агентами.

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



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

Частота обнаружения ячеек с двумя агентами (вероятность ) это просто:

Можно предложить несколько вариантов реализации этапа пересаживания:

• Scenario 1 почти полная имитация: для пересаживания случайно выбираются 50% агентов и каждый из них пересаживается в одну из 18 соседних клеток выбранных случайно;
• Scenario 2 пересаживаются все агенты и каждый из них пересаживается в одну из 18 соседних клеток выбранную случайно;
• Scenario 3 для пересаживания случайно выбираются 50% агентов и каждый из них пересаживается в случайную ячейку пространства;
• Scenario 4 пересаживаются все агенты и каждый из них пересаживается в случайную ячейку пространства;

Scenario 1 назван почти полной имитацией процессов в настоящем мире Dракош, так как доля агентов совершающих действия Step 1/2 различна для каждого такта времени и может иметь любое значение а не только 50%. Ниже мы посмотрим, как результаты вычислений зависят от сценария пересаживания агентов.

Процесс начинаем со случайной расстановки агентов по ячейкам. Затем в цикле раз повторяются два этапа:

1. Пересаживаем агентов согласно выбранного сценария;
2. Определяем количество заполненных ячеек и соответствующие значения и .

Возникает вопрос: сколько же раз необходимо повторить цикл? С ростом неопределенность вычислений убывает пропорционально . Т.е. для увеличения точности в 10 раз необходимо увеличить количество испытаний в 100 раз. Метод Монте-Карло похож на натурные физические эксперименты в том плане что точность результатов можно определить только после получения результата эксперимента. Точнее случайную составляющую неопределенности. И так же как в натурном эксперименте ею можно управлять изменяя количество измерений.

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

Горизонтальной чертой отмечено точное значение, рассчитанное способом, описанным в разделе 3.

По результатам расчетов получены следующие значения неопределенности (надежность 99.7%):

• Для неопределенность составила 0.0014 (0.24%);
• Для 0.00047 (0.080%);
• Для 0.00015 (0.025%);
• Для 0.000066 (0.011%);

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

Результаты Монте-Карло

Давайте посмотрим, как зависит рассчитываемые значения вероятностей от используемого сценария пересаживания агентов. Ниже показаны результаты вычислений для разных сценариев, при и () и количестве испытаний по .

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

5. Что получилось?

На графике ниже показаны зависимость вероятностей и от плотности агентов в пространстве. Синяя и красная области это массивы данных, насчитанные методом Монте-Карло (по 1000 итераций для каждого значения ). Черные линии это точные значения, вычисленные методом, описанным в разделе 3.

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

Теперь можем посмотреть, как выглядит успешность действий Step 1/2, Attack и Sex при полностью случайном (неосознанном) поведении агентов. А точнее на вторые слагаемые в выражениях для индексов осознанности, которые как раз и задают базовый уровень успешности, обусловленный вероятностями обнаружения агентов в пространстве:

Для однозначности примем что частота действия Sex (т.е. если партнер был замечен в ячейке, то он принимает участие в размножении 18+ content).

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

1. Ландо С.К. Лекции о производящих функциях. 2007. 144 c.
2. Соболь И.М. Численные методы Монте-Карло. 1973. 312 с.
3. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний (Монте-Карло) и его реализация на цифровых вычислительных машинах. 1961. 226 с.

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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. Размер кружков пропорционален возрасту агентов.



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


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

• знакомая уже плотность агентов в пространстве, которая равна отношению количества агентов к количеству ячеек в пространстве. Изменяется от 0 до 2 Dr/cell;
• средний по популяции запас энергии агента, kJ;
• средний по популяции возраст агентов;
• среднее по популяции поколение агентов;
• , относительная рождаемость и смертность агентов. Изменяется от 0% до 100%;
• , , , , , средняя по популяции частота совершения действий, которые совершают соответствующее действие в течении каждого такта времени. Изменяется от 0 до 1, но их сумма равна 1;
• , , , успешность действий или доля агентов успешно совершивших вы-бранное действие. Изменяется от 0 до 1;
• , , индексы осознанности действий описанные в части 2. Изменяются от 0 до 1;
• индекс осознанности действия Eat, разность между успешностью и вероятностью обнаружить в ячейке еду:
  

  

  
  где это количество ячеек, в которых в данный момент есть хотя бы один cake, полное количество ячеек в пространстве. изменяется от 0 до 1;
• индекс осознанности выбора направления движения, сейчас он оценивает степень корреляции между направлением шага и направлением с максимальным градиентом количества пищи в пространстве. Изменяется от -1 до 1;

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

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

Взрыв самая короткая эпоха в развитии популяции Тупиков. В течении этой эпохи происходит первичная селекция агентов увеличивается доля агентов, боле часто совершающих попытки размножения (см. граф. 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). К концу второй эпохи большинство агентов почти растратило свой запас энергии и начинается массовое вымирание. После которого начинается новая эпоха.

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

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

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

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

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

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

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

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

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

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



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

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

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



При значениях плотности агентов больше 1.3 Dr/cell в четвертой эпохе (спустя достаточное время порядка тактов) популяция становится агрессивной: действие 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 такой упрощенной моделью можно еще много чего интересного проделать. Но не терпится уже поэкспериментировать с эволюционирующими нейронными сетями.

С интересом слежу за темой симуляции живого посредством компьютерных программ. Нейросети демонстрируют огромный прогресс переваривая гигабайты информации.
Обучение нейронных сетей, в части требуемых ресурсов, далеко ушло от среднего по мощности настольного компьютера. Поэтому всегда интересны "игрушечные" проекты с быстрой обратной связью в части обучения нейросетей. А лучше всего, чтобы нейросеть сама и обучалась без заметных усилий со стороны разработчика. Этой весной был приятно удивлен обнаружив статью Job Talle о нейроэволюции кальмаров.

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

Начнем с источников:

Оригинальная статья взятая за основу при программировании кальмаров(осьминогов)

Перевод вышеуказанной статью на Хабре.

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

или так:

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

Когда все уже готово, рассказано и показано, остается вопрос, а как эта программа работает на самом деле.
Поэтому решил переписать код изначально созданный под JavaScript на более близкий мне с++. Как всегда бывает с чужим кодом, сначала многое было непонятно. Чего стоит такой вот пассаж:

простыми словами автор программы включил в индекс нейрона и его тип, зачем этот прием из 80-х годов непонятно. Вроде сейчас памяти хватает в компьютерах.
Но в целом прототип заработал и стал выглядеть примерно так:

Щупальца удлинил относительно оригинальных вариантов, показалось более гармонично.
Но картинка выглядела слишком схематично.
Решил добавить для гладкости сплайны по точкам щупалец и сдвиг точек сплайна от центральной линии щупальца в зависимости от расстояния от тела кальмара.

выглядит неплохо, но переход щупальца к телу хотелось увидеть более естественным, добавил более сильный отступ от центра щупальца:

в итоге остановился на таком варианте:

Но кальмары скорее всего не прозрачные, поэтому картинка больше про медуз:

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

или в движении:

и более мультипликационно:

Дело сделано в 2D, но 3D все еще мейнстрим, поэтому переходим к следующему этапу. Сначала понять как буду крепить щупальца:

Решил сначала физику переписать с нуля:

Видно, что опирается на щупальца, добавил коллизии щупалец и прочее из набора физического движка. Потянуло на проверенный временем Bullet Physics Library:

Но вскоре решил не трогать то, что работало изначально и просто добавил еще одно измерение в первоначальную физику:

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

Конечный результат, что-то из фильма "Матрица":