Агентне моделювання — зграї, епідемії, мурашині колонії та емерджентний трафік

Моделювання знизу вгору проти зверху вниз

Класичні математичні моделі описують системи зверху вниз: записують рівняння для агрегованих величин (загальна кількість заражених, середня швидкість, середня температура), розв'язують їх і зчитують поведінку. Це потужно й ефективно. Але це не працює добре, коли важлива індивідуальна неоднорідність, коли має значення просторова структура або коли агенти мають пам'ять чи адаптивні стратегії.

Агентне моделювання (АМ) обирає протилежний підхід: задає правила для кожного окремого агента, запускає тисячі агентів одночасно і дозволяє колективній поведінці виникнути. Глобальний патерн ніколи не програмується явно — він виникає з локальних взаємодій. Справжня сила АМ полягає в розриві між цими двома підходами: багато систем породжують агреговану поведінку, яка математично еквівалентна звичайним диференціальним рівнянням зверху вниз за певних умов, але розходиться з ними, щойно припущення (однорідне змішування, нескінченна популяція, відсутність просторової структури) перестають виконуватися.

Частина 1: зграйна поведінка

Симуляція Boids — три правила, нескінченна складність

1986 року Крейг Рейнольдс опублікував статтю, яка назавжди змінила комп'ютерну графіку. Він показав, що реалістична зграйна поведінка — узори руху шпаків, щільні клубки риб'ячих косяків — виникає лише з трьох локальних правил, застосованих до кожного агента: розділення, вирівнювання та згуртованість. Жодної глобальної хореографії, жодного центрального керування, жодної явної структури зграї.

Для кожного boid i розглядаємо сусідів у радіусі R:

1. Розділення (уникати скупчення):
   f_sep = -Σⱼ (p_j - p_i) / |p_j - p_i|²   для |p_j-p_i| < r_sep
   Веде геть від сусідніх boid

2. Вирівнювання (рух до середнього напрямку):
   f_ali = (Σⱼ v_j / |N|) - v_i              для j ∈ сусіди
   Веде до середньої швидкості сусідства

3. Згуртованість (рух до центру мас):
   f_coh = (Σⱼ p_j / |N|) - p_i - v_i        для j ∈ сусіди
   Веде до середньої позиції сусідства

Сумарне прискорення:
   a_i = w_sep·f_sep + w_ali·f_ali + w_coh·f_coh

Оновлення швидкості:
   v_i += a_i · dt;   |v_i| = clamp(|v_i|, v_min, v_max)
   p_i += v_i · dt

Просторовий хеш для пошуку сусідів за O(1) на boid:
  Наївно: O(n²) порівнянь; Просторовий хеш: O(n·k), k=середня к-ть сусідів
  Критично: 500 boid → 125 000 пар → 5×: 15 625 000 (майже непридатно)

З цих трьох правил симуляція Boids відтворює всі ознаки справжньої зграйної поведінки: щільний формаційний політ, розділення та злиття навколо перешкод, хвилеподібні брижі крізь зграю та витягнуту «колонну» форму під час крейсерського польоту. Регулюйте вагу кожного правила незалежно — підніміть розділення дуже високо, і зграя вибухає; виставте згуртованість на максимум, і вона стискається в щільну кулю. Правильна точка балансу дає моторошну, скоординовану поведінку, що спостерігається в природі.

Частина 2: поширення епідемій

Модель SIR — математика спалахів

Модель SIR, сформульована Кермаком і Маккендріком 1927 року, є основою математичної епідеміології. Кожна модель реагування на пандемію — розширення SIR для COVID-19, SEIR для грипу, метапопуляційні моделі денге — походить із цих трьох рівнянь. Розуміння SIR означає розуміння порогів колективного імунітету, форми епідемічних кривих і того, чому вакцинація 70% населення може запобігти спалахам, навіть якщо 30% людей залишаються сприйнятливими.

Змінні стану (частки популяції):
  S = Сприйнятливі   dS/dt = -β·S·I
  I = Заражені       dI/dt =  β·S·I - γ·I
  R = Одужалі        dR/dt =  γ·I
  S + I + R = 1

Параметри:
  β = швидкість передачі  [контакти⁻¹·день⁻¹]
  γ = швидкість одужання  [день⁻¹]  ≡ 1/D, D = період заразності

Базове репродуктивне число:
  R₀ = β/γ = β·D
  R₀ > 1   → епідемія зростає       (кожен випадок заражає >1 інших)
  R₀ < 1   → епідемія згасає
  R₀ = 1   → ендемічна рівновага

Поріг колективного імунітету:
  p_c = 1 - 1/R₀   (потрібна частка вакцинованих)
  Кір (R₀≈15):        p_c = 93%
  COVID-19 (R₀≈2.5):  p_c = 60%

Кінцевий розмір (частка, що зрештою заразиться):
  r_∞ задовольняє: ln(1-r_∞)/r_∞ = -R₀

Розширення SEIR:
  Додаємо E (експоновані/латентні): dE/dt = β·S·I - σ·E
  σ = швидкість переходу з експонованого в заразний стан (1/латентний період)

Симуляція SIR показує одночасно розв'язок диференціальних рівнянь (агреговані криві) та агентну версію, де окремі люди рухаються по сітці й заражають сусідів при контакті. Два представлення розходяться, коли має значення просторове групування: в агентній версії щільні скупчення сприйнятливих осіб утворюють локалізовані спалахи, що зберігаються після того, як агрегована крива SIR уже вирівнялася. Опустіть R₀ нижче 1, щоб побачити, як епідемія згасає сама, не досягнувши всієї популяції.

Частина 3: стигмергія — оптимізація мурашиної колонії

Симуляція Ants — феромонна комунікація

Мурашина колонія не має центрального планувальника, проте вона дивовижно ефективно розв'язує задачу найкоротшого шляху між гніздом і джерелом їжі. Механізм — стигмергія: агенти змінюють спільне середовище (відкладаючи феромон), а інші агенти реагують на ці зміни середовища. Ця непряма комунікація, опосередкована середовищем, а не прямим контактом, породжує глобально оптимальні рішення з локально простих правил.

Правило оновлення феромону:
  τᵢⱼ ← (1-ρ)·τᵢⱼ + Σᵏ Δτᵢⱼᵏ
  ρ     = швидкість випаровування ∈ (0,1)    (забування)
  Δτᵢⱼᵏ = Q/Lᵏ, якщо мурашка k використала ребро (i,j), інакше 0
  Q     = константа сили феромону
  Lᵏ    = загальна довжина шляху мурашки k

Ймовірнісний вибір шляху:
  P(ребро j | у вузлі i) = [τᵢⱼ]^α · [η᷊ⱼ]^β / Σₗ [τᵢₗ]^α · [ηᵢₗ]^β
  η᷊ⱼ = 1/dᵢⱼ (евристика: перевага коротким ребрам)
  α   = вага важливості феромону
  β   = вага важливості евристики

Позитивний зворотний зв'язок (петля скорочення):
  Коротший шлях → більше проходжень за час → більше феромону
  → вища ймовірність вибору майбутніми мурахами →
  → обирається ще коротший ефективний шлях → ...

Збіжність:
  Занадто високе ρ: мурахи не тримаються встановлених шляхів (випадково)
  Занадто низьке ρ: застарілий феромон захоплює мурах у неоптимальних шляхах
  Оптимум: ρ ≈ 0.1–0.3 для більшості задач

У симуляції Ants спостерігайте, як феромонні стежки формуються в реальному часі, поки мурахи випадково досліджують територію, знаходять їжу і повертаються до гнізда. Перша мурашка, що знаходить їжу, обирає випадковий, звивистий шлях. Наступні мурахи, що натраплять на її феромонну стежку, з більшою ймовірністю підуть нею. З часом петля позитивного зворотного зв'язку обирає майже оптимальний маршрут — той, що експериментально підтверджено як наближення до найкоротшого шляху з точністю до кількох відсотків. Поставте стіну посеред стежки й подивіться, як колонія обходить її.

Частина 4: цикли популяцій — динаміка хижак-жертва

Симуляція «Хижак-жертва» — Лотка-Вольтерра у двох вимірах

Дані про популяції рисі та зайця-біляка, зібрані компанією Hudson's Bay між 1845 і 1935 роками, показують регулярні коливання з періодом близько 10 років. Віто Вольтерра й Альфред Лотка, працюючи незалежно один від одного у 1920-х роках, вивели просту пару диференціальних рівнянь, що дає точнісінько такі коливання — не знаючи про дані щодо зайців. Рівняння Лотки-Вольтерри — одна з найвідоміших моделей в екології і досі є основою сучасної динаміки популяцій.

Класичні рівняння:
  dN/dt = αN - βNP       (жертва: росте, гине при поїданні)
  dP/dt = δNP - γP       (хижак: росте при годуванні, гине природно)

  N = популяція жертв;  P = популяція хижаків
  α = швидкість росту жертв
  β = швидкість хижацтва (на зустріч хижак-жертва)
  δ = ефективність хижака (жертва перетворюється на хижаків)
  γ = швидкість смертності хижаків

Рівновага:
  N* = γ/δ   (жертва в рівновазі)
  P* = α/β   (хижак у рівновазі)

Збережена величина (перший інтеграл):
  V = δN - γ·ln(N) + βP - α·ln(P) = константа
  → Замкнені орбіти у фазовій площині (нейтральна стійкість)

Парадокс Лотки-Вольтерри:
  Збільшення швидкості росту жертв α → підвищує рівновагу хижака, а не жертви
  «Парадокс збагачення»: додавання поживних речовин дестабілізує цикл

Реальні розширення:
  Логістичний ріст: α → α(1-N/K)     (місткість середовища)
  Типи Голлінга II/III: насичувальна функціональна відповідь
  Розенцвейг-МакАртур: веде до граничних циклів, хаосу

Симуляція «Хижак-жертва» запускає рівняння Лотки-Вольтерри поряд з агентною просторовою версією, де окремі жертви й хижаки рухаються по сітці. Розв'язок диференціальних рівнянь дає ідеальні замкнені орбіти у фазовому просторі; агентна версія показує нерегулярні коливання з випадковими вимираннями — саме різницю між ідеалізованими моделями та реальними екологічними системами. Додайте просторову структуру (плямисте середовище проживання, коридори) і спостерігайте метапопуляційну поведінку, яка дозволяє тим, хто вижив, перезаселяти вимерлі ділянки.

Частина 5: міська динаміка — злипання автобусів і ріст міст

Злипання автобусів — чому автобуси їздять парами

Злипання автобусів — один із найелегантніших прикладів емерджентної дисфункції в міських системах. Навіть коли автобуси заплановані з ідеально рівними інтервалами, невеликі випадкові затримки змушують задній автобус забирати більше пасажирів (оскільки інтервал зріс), сповільнюючи його ще більше й примушуючи передній автобус їхати швидше (оскільки в нього менше зупинок). Результат неминучий: автобуси збираються в пари. Жоден водій не поводиться погано — злипання є властивістю системи, а не агентів.

Інтервал (часовий проміжок між автобусами):
  h_i = час з моменту попереднього автобуса на тій самій зупинці

Час посадки залежить від інтервалу:
  T_board(i) = λ · h_i   (λ = швидкість прибуття пасажирів за одиницю часу)

Час стоянки автобуса на зупинці s:
  d_s(i) = d_min + T_board(i)/μ   (μ = швидкість посадки за секунду)

Підсилення збурення:
  Якщо автобус i затримується на δ:
    - h_i зростає → більше пасажирів → довша стоянка на кожній зупинці
    - h_{i+1} зменшується → менше пасажирів → коротша стоянка
  Наступне коло: h_i зростає ще більше → нестабільна лавина

Критерій злипання:
  Система злипається, якщо ∂h_i/∂(затримка) > 1  (збурення підсилюються)
  Це виконується щоразу, коли λ/μ достатньо велике

Стратегії керування:
  Утримання на основі інтервалу: тримати передній автобус, якщо h < h_min
  Оптимальне керування (Даганцо, 2009): мінімізувати сумарне очікування пасажирів
  Диспетчеризація за GPS у реальному часі: сучасні транспортні системи це використовують

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

Симуляція росту міста — просторова економіка

Міста ростуть за самопідсилювальною логікою: економічна активність приваблює працівників, працівники створюють попит, попит приваблює більше бізнесу, щільність бізнесу підвищує вартість землі, а вартість землі концентрує забудову. Цей зворотний зв'язок, формалізований у міській економіці, породжує степеневе масштабування розподілів розмірів міст (закон Ципфа), фрактальну структуру дорожніх мереж і концентричну кільцеву структуру землекористування.

Закон Ципфа (правило ранг-розмір):
  Населення міста з рангом r: P(r) = P₁ / r^α
  Емпірично: α ≈ 1 для більшості країн
  США (2020): Нью-Йорк≈8.3М, Лос-Анджелес≈3.9М, Чикаго≈2.7М → ранг×нас ≈ конст

Кляйберівське масштабування міського метаболізму:
  Y ∝ N^β     (Y = економічний результат, N = населення)
  β > 1:      суперлінійно → міста стають непропорційно продуктивними
  β ≈ 1.15    (патенти, ВВП, зарплати)
  β ≈ 0.85    (інфраструктура: дороги, труби)

Моноцентрична модель Алонсо-Мута-Міллса:
  Градієнт орендної плати: R(x) = R(0) - t·x  (R спадає з відстанню x від центру)
  t = вартість поїздки на роботу за одиницю відстані
  Результат: щільність максимальна в центрі, спадає експоненційно назовні

Клітинний автомат землекористування (модель SLEUTH):
  Ймовірність поширення забудови:
    P = f(нахил, винятки, забудовані сусіди, відстань до доріг)
  Калібрований до реальних міст за історичними супутниковими знімками

Симуляція росту міста реалізує модель землекористування на клітинному автоматі, де клітинки переходять із сільського в приміський і міський статус залежно від щільності сусідства, доступу до доріг і нахилу рельєфу. Розмістіть початкове економічне зерно (гавань, залізничний вузол) і спостерігайте, як місто зароджується, розповзається вздовж транспортних коридорів і самоорганізується в характерну кільцеву структуру — усе з локальних правил без жодного глобального плану.

Колекція агентного моделювання

Зв'язки між колекціями

Агентне мислення пов'язує всю платформу. Алгоритм Boids — прямий предок симуляції натовпу — ті самі три правила керування, застосовані до пішоходів, що орієнтуються в коридорах і виходах. Модель епідемії SIR має ту саму математичну форму, що й диференціальні рівняння хижак-жертва — обидві є двозмінними нелінійними системами з граничноцикловою поведінкою. Феромони мурашиної колонії — це біологічна реалізація градієнтного спуску, що керує навчанням нейронних мереж: обидві системи слідують градієнтам концентрації для пошуку оптимумів. Виникнення росту міста пов'язане з симуляцією перколяції — міське поширення є спрямованим процесом перколяції на ґратці землекористування, а межа міста в симуляції росту — це саме фронт перколяційного кластера. Усі ці системи ілюструють один і той самий глибокий принцип: локальні правила, повторювані для багатьох агентів упродовж багатьох часових кроків, надійно породжують глобальний порядок, який ніколи не був явно спроєктований.

Алгоритми та методи в цій колекції