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

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

Подсказка пришла с неожиданной стороны. В 1986 г. американский аниматор Крейг Рейнольдс показал, что для того, чтобы движение птиц выглядело скоординированным, достаточно, чтобы каждая птица следовала трем простым правилам: «равнению» (alignment), «разделению» (separation) и «связанности» (cohesion). «Равнение» означает, что птица старается повернуться так, чтобы направление ее движения совпадало с направлением движения соседей. Увидев поблизости товарок, птица стремится подлететь к ним — это и есть «связанность». Наконец, когда птица подлетает к соседкам слишком близко, вступает в силу третье правило — «разделение» — и птица поворачивается, избегая столкновения. Кроме того, у птицы есть поле зрения и расстояние, на которое она способна «видеть».

Равнение

Разделение

Связность

На ориентацию «стрелки», изображающей птицу влияют три правила: равнение, разделение и связанность

Модель образования стаи

Рейнольдс назвал придуманных им созданий — boids (от англ. birds и droid). Уже вскоре, в фильме «Бэтмен возвращается» (1992 г.) с их помощью моделировалось движение стай летучих мышей и пингвинов. Сейчас boids — стандартный прием, реализованный во многих редакторах 3D-графики, например, в Blender.

Чтобы увидеть, как это работает, скачайте пакет [[https://ccl.northwestern.edu/netlogo/NetLogo]] (потребуется бесплатная регистрация) и посмотрите модель Flocking в библиотеке моделей (раздел Biology). Журавлиный «клин» возникает, когда поле зрения птиц у̀же кругового (например, равно 180 градусам).

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

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

Доставка пищи в муравейник (модель Ants из NetLogo)

Способность муравьиной колонии обнаруживать кратчайший путь вдохновила итальянца Марко Дориго в середине 1990-х на создание нового метода оптимизации — муравьиного алгоритма. Сегодня с помощью таких алгоритмов решаются сложные комбинаторные задачи, вроде задачи коммивояжера и задачи оптимизации транспортных маршрутов. А вслед за муравьиными алгоритмами появились: роевой интеллект (англ. swarm intelligence. Думаю, источник вдохновения понятен), эволюционные алгоритмы и другие подражания природе. В результате образовалось целое направление — «природные вычисления» (natural compuing).

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

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

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

Модель Traffic Basic из библиотеки Netlogo

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

Фрагмент модели городской транспортной сети

В каждом из рассмотренных примеров мы имели дело с некими сущностями, которые взаимодействовали друг с другом по заданным правилам. Эти сущности называют агентами, а изучение поведения систем, состоящих из агентов — агентным моделированием (англ. agent-based modeling, ABM). По сути, агентное моделирование — это компьютерная игра, только играют в нее ученые.

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

Особенно интересны приложения агентного моделирования в общественных науках, где традиционный подход мало чего достиг. Так, в 1971 г. американский экономист Томас Шеллинг провел простой эксперимент, который можно считать первым примером агентного моделирования. Его интересовали причины сохраняющейся в США расовой сегрегации. К тому времени законы, ограничивающие права чернокожих, уже были отменены, а подавляющее большинство американцев вовсе не были расистами. В то же время им (а, наверное, не только им) было не безразлично, в каком окружении они живут: никто не хотел быть единственным черным или белым человеком в округе.

Шеллинг нарисовал на листке бумаги сетку из квадратов (а вы можете использовать модель Segregation из NetLogo). Каждый квадрат представлял собой участок с домом. Предполагая, что белые и черные семьи живут вместе в одном районе, Шеллинг случайным образом отметил некоторые квадраты белыми и черными маркерами. Затем он предположил, что каждая семья предпочла бы иметь ближайшими соседями людей своей расы. Если количество соседей другого цвета становилось более 50 %, то семья переезжала на новое место.

На основании одного этого правила, Шеллинг стал перемещать маркеры по сетке до тех пор, пока не осталось ни одного, имеющего более 50 % соседей другого цвета. К удивлению ученого, сетка оказалась полностью разделена: все белые маркеры оказались в одной области, а все черные — в другой. Скромное естественное желание иметь соседями хотя бы нескольких человек с определенными отличительными чертами произвело значительный эффект — резкое разделение населения.

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

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

Что почитать

  1. Boids. Background and Update by Craig Reynolds: [[http://www.red3d.com/cwr/boids/]]
  2. Resnick M. Turtles, termites and traffic jams: explorations in massively parallel microworlds, MIT, 1994, 170 p.
  3. Штовба С. Д. Муравьиные алгоритмы, Exponenta Pro. Математика в приложениях, 2003, №4, с.70-75.
  4. Dorigo М., Thomas Stutzle. Ant Colony Optimization, MIT, 2004, 305 p.
  5. Bonabeau E., Dorigo M., Theraula G. Swarm Intelligence. From Natural to Artificial Systems, 1999, 320 p.
  6. Алгоритм роя частиц: [[http://habrahabr.ru/blogs/algorithm/105639/]]
  7. Карр Н.Дж. Великий переход. Что готовит революция облачных технологий, Манн, Иванов и Фербер, 2014, 272 с.
  8. Batten D. Discovering Artificial Economics: How Agents Learn and Economies Evolve, Westview Press, 2000, 314 p.


Комментарии

comments powered by Disqus