Недавно по сети прошел всплеск упоминаний игры Жизнь, в связи в основном с тем, что умер ее создатель.
Время сейчас такое, все стали интересоваться биологией, везде эти графики выживания, ну и у меня из закромов памяти вдруг выбралась интересная модель, по которой когда-то писал курсовую.
Модель похожа на Жизнь тем, что это такой же циклический процесс, на который можно смотреть как на огонь, бесконечно медитировать и размышлять о вечном.
Это — Хищник-жертва, вполне себе серьезная модель из прикладной математики (Predator-prey в англоязычном мире).
Суть процесса заключается в том, что в некотором лесу живет стадо оленей (в альтернативной версии — зайцев, но не суть), которые едят в волю и размножаются безудержно, и рано или поздно заполоняют всю территорию.
Однако в том же лесу есть еще и хищники, которые питаются этими оленями (волки, но для зайцев — обычно лисы).
Пара хищников, оказавшаяся в этом изобильном лесу, очень бодро размножается по экспоненте в соответствии с законом Мальтуса, но в какой-то момент ресурсы-олени начинают иссякать, волки — голодать и вымирать, экспонента стремительно летит вниз и там выживают только самые стойкие.
Загнанные было в угол олени поднимают головы, включают свою экспоненту и начинают доминировать над лесом, но пережившие пост волки на свежем мясе находят в себе силы на новую волну рождаемости… и так по кругу и до бесконечности.
Вот график (утащен с Википедии):
Математическая модель этого процесса была описана в начале 20ого века Лоткой и Вольтеррой и названа в их честь.
Почему эта модель существует уже сотню лет и все равно актуальна?
Основных причины две: она очень простая и описывает процесс достаточно реалистично.
У модели всего четыре параметра:
Модель содержит минимальную нелинейность и считается аналитически. При удачно подобранных параметрах она устойчива (ни олени, ни волки до конца не вымирают) и реалистично описывает динамику колебаний в популяциях.
За сто лет было много попыток сделать что-то более реалистичное — но любое повышение сложности ведет к нелинейной системе более высокого уровня и дальше все упирается в непробиваемые интегральные уравнения, которые решить можно только численными методами.
Есть еще один метод — просто запрограммировать этот процесс как игру.
На самом деле такой подход называется мультиагентным моделированием и вполне годится, чтобы сдать курсовую.
Хочется, чтобы программа имела визуализацию, не только на машине автора, но у как можно большей аудитории, причем чтобы оно все само, при минимальных усилиях и все такое.
Логично, что решением будет запустить программу в браузере и, следовательно, писать ее придется на javascript.
Ну а чтобы не плодить зоопарк технологий, сервер тоже на нем напишем.
Стандартные шаги по установке node.js и всего необходимого описаны на Гитхабе.
Переходим к самому интересному — размножению. Без хищников у нас мальтузианская модель в условиях ограниченных ресурсов (в мире математики описывается логистической функцией или уравнением Ферхюльста), ее теперь как-то надо применить к агентам.
Можно подобрать вероятностные коэффициенты к каждому оленю и все должно получиться.
Но чем хорошо агентное моделирование — можно задавать именно поведение, не ограничивая себя несколькими коэффициентами.
В общем, модель оленей жизни выглядит так:
Дальше сделаем легкий тестовый апп, который создает лесной мир 20x20, запускает в самый центр оленя, и прогоняет 100 циклов, каждый раз печатая статус в csv.
Получившийся csv-файл загоним в Google Spreadsheet и сгенерим график:
Вполне себе экспоненточка получается. Видим, что численность стабилизируется на 200+ оленей, это легко объяснить тем, что необходимость движения требует для оленя не менее двух клеток, а площадь всего леса — 400.
Максимальный прирост случается довольно рано — на 14-15 ходу, а последние 20 ходов численность стоит на месте с незначительнеми колебаниями.
В целом, что хочется подчеркнуть — простейшая агентная модель ведет себя очень реалистично, вполне похожа на логистическую кривую, разбавленную легким шумом.
Но мы сюда не столько за цифрами пришли, сколько за картинками на которые можно смотреть и расслабляться.
Итак, пришло время сделать страничку с картой и графиками, а прогон модели перенести на сервер.
Ставим express и socket.io, а рисовать будем прямо на html5 canvas (с js-движками я не знаком, да и задача не особо сложная).
Смотрим и нервничаем от того, как олени буквально заполоняют лес за считанные итерации, а потом ассимптотически флуктуируют вокруг максимума.
С одной стороны, это всего лишь модель, но кое-где это реальная проблема — достаточно погуглить deers overpopulation и удивиться обилию материала на эту тему.
Эта модель не учитывает деградацию леса, но на самом деле олени довольно жадные потребители — они выедают побеги, вытаптывают землю и в общем разрушают свои леса.
Что делать хозяину леса в таком случае?
Он покупает волков, вешает на каждого gps-датчик и молится, чтобы они не пропали.
Пора внедрить волка и в нашу модель.
Надо решить две вещи — как волк ест и размножается.
Охотиться просто, когда есть на кого — если в любой соседней клетке есть олень — просто едим его.
Если оленя нет, то можно выжить какой-то период времени.
Для начала положим, что есть волк может каждый ход, но если за два хода не удалось — на обочину эволюции.
С размножением вариантов побольше.
Для начала — уберем деликатность, пусть волки размножаются всегда когда есть свободное место.
И добавим ограничение — голодные волки не размножаются.
Дадим оленям немного размножиться и закинем волка в толпу:
Модель получилась, мягко говоря, неустойчивая — волки моментально выкосили всех оленей и быстренько сами вымерли.
Одно расстройство, никакого дзена.
Надо что-то менять.
Режет глаз, какими взрывными темпами плодятся волки.
Немного усложним им жизнь — поставим условие, что размножаться можно только, если на соседних клетках оленей больше чем волков.
И забросим волков, когда оленья популяция достигает максимума.
Эта попытка удалась намного лучше.
Баланс хищников и жертв постоянно в движении, оленья популяция сильно сократилась и теперь даже близко не подбирается к своему максимуму.
Однако случиться может всякое, и почти каждый раз происходит так, что волки умудряются вымереть, а олени вновь торжествующе заполоняют чащу.
Вот в этом прогоне волки продержались долго:
Придется закрутить гайки размножения еще сильней.
Поставим теперь условие: рядом должны быть олени, но не должно быть волков.
Такие вот нежные волки, не терпят конкуренции.
Система получается более устойчивой.
В сравнении с предыдущим графиком пики сглажены как у оленей, так и у волков.
В общем, понятно куда двигаться, чтобы получился такой же гладкий график как в Википедии.
В итоге приходим к банальному выводу — размножаться надо сознательно, а не по максимуму.
Звучит как реклама гедонизма, но можно и дальше понижать плодовитость волков в расчете «на повышение качества и продолжительности их жизни»…
В качестве эпилога — инструкция по развертыванию.
Она очень короткая:
1. Пишем простенький докер-файл:
2. docker build. -t predator-prey
3. docker run -p 8081:8081 predator-prey
Для самых ленивых я собрал и выложил образ на Docker Hub
Если не хочется возиться с докером — на странице репо (ссылка ниже) есть инструкция по установке с нуля.
Время сейчас такое, все стали интересоваться биологией, везде эти графики выживания, ну и у меня из закромов памяти вдруг выбралась интересная модель, по которой когда-то писал курсовую.
Модель похожа на Жизнь тем, что это такой же циклический процесс, на который можно смотреть как на огонь, бесконечно медитировать и размышлять о вечном.
Это — Хищник-жертва, вполне себе серьезная модель из прикладной математики (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
Если не хочется возиться с докером — на странице репо (ссылка ниже) есть инструкция по установке с нуля.