Как стать автором
Обновить

Модель «Хищник-жертва» на Node.js

Время на прочтение 5 мин
Количество просмотров 13K
Недавно по сети прошел всплеск упоминаний игры Жизнь, в связи в основном с тем, что умер ее создатель.

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

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

Это — Хищник-жертва, вполне себе серьезная модель из прикладной математики (Predator-prey в англоязычном мире).

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

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

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

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

Вот график (утащен с Википедии):



Математическая модель этого процесса была описана в начале 20ого века Лоткой и Вольтеррой и названа в их честь.

Почему эта модель существует уже сотню лет и все равно актуальна?

Основных причины две: она очень простая и описывает процесс достаточно реалистично.

У модели всего четыре параметра:

  • альфа) скорость размножения оленей
  • бета) скорость поедания оленей волками
  • гамма) скорость вымирания голодных волков
  • дельта) скорость размножения сытых волков

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

За сто лет было много попыток сделать что-то более реалистичное — но любое повышение сложности ведет к нелинейной системе более высокого уровня и дальше все упирается в непробиваемые интегральные уравнения, которые решить можно только численными методами.

Есть еще один метод — просто запрограммировать этот процесс как игру.

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

Выбираем технологию


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

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

Стандартные шаги по установке node.js и всего необходимого описаны на Гитхабе.

Модель оленьего роста


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

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

В общем, модель оленей жизни выглядит так:

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

  breed(u) {
    var spots = MapUtil.get_adj(u.point, this.W, this.H)
    if (!spots || spots.length < 1)
      return false
    var free = spots.filter(p => !this.GM.get(p))
    if (free.length < spots.length)
      return false
    var spot = _.sample(spots)
    if (!spot)
      return false
    var born = new Wild(u.kind)
    born.move(spot)
    this.add_wild(born)
    this.born.push(born)
  }

Дальше сделаем легкий тестовый апп, который создает лесной мир 20x20, запускает в самый центр оленя, и прогоняет 100 циклов, каждый раз печатая статус в csv.

Получившийся csv-файл загоним в Google Spreadsheet и сгенерим график:



Вполне себе экспоненточка получается. Видим, что численность стабилизируется на 200+ оленей, это легко объяснить тем, что необходимость движения требует для оленя не менее двух клеток, а площадь всего леса — 400.

Максимальный прирост случается довольно рано — на 14-15 ходу, а последние 20 ходов численность стоит на месте с незначительнеми колебаниями.

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

Но мы сюда не столько за цифрами пришли, сколько за картинками на которые можно смотреть и расслабляться.

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

Ставим express и socket.io, а рисовать будем прямо на html5 canvas (с js-движками я не знаком, да и задача не особо сложная).

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



С одной стороны, это всего лишь модель, но кое-где это реальная проблема — достаточно погуглить deers overpopulation и удивиться обилию материала на эту тему.

Эта модель не учитывает деградацию леса, но на самом деле олени довольно жадные потребители — они выедают побеги, вытаптывают землю и в общем разрушают свои леса.

Что делать хозяину леса в таком случае?

Он покупает волков, вешает на каждого gps-датчик и молится, чтобы они не пропали.

Волки


Пора внедрить волка и в нашу модель.

Надо решить две вещи — как волк ест и размножается.

Охотиться просто, когда есть на кого — если в любой соседней клетке есть олень — просто едим его.

Если оленя нет, то можно выжить какой-то период времени.

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

С размножением вариантов побольше.

Для начала — уберем деликатность, пусть волки размножаются всегда когда есть свободное место.

И добавим ограничение — голодные волки не размножаются.

Первый блин


Дадим оленям немного размножиться и закинем волка в толпу:



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

Одно расстройство, никакого дзена.

Вторая попытка


Надо что-то менять.

Режет глаз, какими взрывными темпами плодятся волки.

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

    var preys = spots.map(p => this.GM.get(p)).filter(u => u && u.kind == Wilds.DEER)
    var preds = spots.map(p => this.GM.get(p)).filter(u => u && u.kind == Wilds.WOLF)
    if (preys.length <= preds.length)
      return false

И забросим волков, когда оленья популяция достигает максимума.

Эта попытка удалась намного лучше.

Баланс хищников и жертв постоянно в движении, оленья популяция сильно сократилась и теперь даже близко не подбирается к своему максимуму.



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

Вот в этом прогоне волки продержались долго:



Третий круг


Придется закрутить гайки размножения еще сильней.

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

Система получается более устойчивой.

В сравнении с предыдущим графиком пики сглажены как у оленей, так и у волков.



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



Развертывание


В качестве эпилога — инструкция по развертыванию.

Она очень короткая:

1. Пишем простенький докер-файл:

FROM node:14
ADD https://github.com/tprlab/predator-prey/archive/master.zip /
RUN unzip /master.zip
WORKDIR /predator-prey-master
RUN npm install
EXPOSE 8081
CMD ["node", "server.js"]

2. docker build. -t predator-prey

3. docker run -p 8081:8081 predator-prey

Для самых ленивых я собрал и выложил образ на Docker Hub

Если не хочется возиться с докером — на странице репо (ссылка ниже) есть инструкция по установке с нуля.

Ссылки


Теги:
Хабы:
+7
Комментарии 10
Комментарии Комментарии 10

Публикации

Истории

Работа

Ближайшие события

DI CONF SMM — большая конференция по соцсетям в России
Дата 2 марта
Время 09:30 – 18:00
Место
Краснодар Онлайн
Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн