Введение в распределенное моделирование в среде NetLogo

ВВЕДЕНИЕ 

В РАСПРЕДЕЛЕННОЕ 
МОДЕЛИРОВАНИЕ В 

СРЕДЕ NETLOGO

Н. М. Ершов

Москва, 2018

УДК 004.4.24
ББК 32.972.1

Е80

Е80 Н. М. Ершов

Введение в распределенное моделирование в среде NetLogo. – М.: 
ДМК Пресс, 2018. – 264 с.

ISBN 978-5-94074-827-4

Книга посвящена разработке распределенных естественных 

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

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

библиографических ссылок.

Издание ориентировано на студентов, старшеклассников и всех, 

интересующихся тематикой математического и компьютерного 
моделирования.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой 

бы то ни было форме и какими бы то ни было средствами без письменного разрешения 
владельцев авторских прав. 

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

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

ISBN 978-5-94074-827-4
© Н. М. Ершов, 2018
© Оформление, издание, ДМК Пресс, 2018

Оглавление

Введение. . . . . . . . . . . . . . . . . . . . . .7
Естественные вычисления (7) Среда
моделирования NetLogo (7) Структура
книги (9)

ГЛАВА 1
Задача Бюффона. . . . . . . . . . . .11

Методы Монте-Карло (11) Задача
Бюффона (12) Построение модели (13)
Упражнения (19)

ГЛАВА 2
Интегрирование методом
Монте-Карло . . . . . . . . . . . . . . . . 23

Площади и интегралы (23) Метод
Монте-Карло (24) Геометрический
подход (25) Построение модели (26)
Упражнения (29)

ГЛАВА 3
Броуновское движение. . . . . . .33

Открытие явления (33) Случайные
блуждания (34) Построение
модели (35) Упражнения (41)

ГЛАВА 4
Задача о разорении игрока . . . 45

Постановка задачи (45) Марковские
цепи (47) Построение модели (48)
Упражнения (52)

ГЛАВА 5
Метод имитации отжига. . . . .57

Отжиг металлов (57) Алгоритм
Метрополиса (58) Метод имитации
отжига (59) Построение модели (60)
Упражнения (65)

ГЛАВА 6
Модель Рейнолдса. . . . . . . . . . .69

Роевой интеллект (69) Модель
Рейнолдса (70) Построение модели (71)
Упражнения (75)

ГЛАВА 7
Метод роя частиц . . . . . . . . . . . 79

Роевая оптимизация (79) Метод роя
частиц (80) Построение модели (81)
Упражнения (86)

ГЛАВА 8
Алгоритм бактериального
поиска. . . . . . . . . . . . . . . . . . . . . . .91

Хемотаксис бактерий (91) Алгоритм
бактериального поиска (92) Роевое
поведение бактерий (93) Построение
модели (94) Упражнения (98)

ГЛАВА 9
Пчелиный алгоритм. . . . . . . .101

Поведение пчел в природе (101) Алгоритм пчелиного поиска (102) Построение модели (103) Упражнения (107)

ГЛАВА 10
Модель муравьиной
колонии. . . . . . . . . . . . . . . . . . . .111

Коллективное поведение
муравьев (111) Стигмергия (111)
Эксперимент с двумя мостами (112)
Построение модели (113)
Упражнения (118)

ГЛАВА 11
Муравьиные алгоритмы . . . .121

Основная идея (121) Задача
коммивояжера (122) Построение
модели (123) Упражнения (130)

ГЛАВА 12
Роевая робототехника. . . . . .133

Принципы организации (133) Сортировка предметов (134) Построение
модели (135) Упражнения (140)

ГЛАВА 13
Генетические алгоритмы . . . 143

Понятие генетического алгоритма (143) Генетические операторы (144) Построение модели (145)
Упражнения (151)

ГЛАВА 14
Клеточные генетические
алгоритмы . . . . . . . . . . . . . . . . .155

Проблема потери разнообразия (155)
Островная модель (156) Клеточная
модель (156) Построение модели (158)
Упражнения (163)

ГЛАВА 15
Элементарные клеточные
автоматы . . . . . . . . . . . . . . . . . . 167

Клеточные автоматы (167) Элементарные автоматы (168) Классификация элементарных автоматов (169)
Построение модели (170)
Упражнения (173)

ГЛАВА 16
Игра «Жизнь» . . . . . . . . . . . . 177

Двумерные клеточные автоматы (177)
Игра «Жизнь» (178) Построение
модели (179) Упражнения (183)

ГЛАВА 17
Блочные клеточные
автоматы . . . . . . . . . . . . . . . . . . 187

Законы сохранения (187) Блочные
автоматы (188) Клеточный газ (188)
Построение модели (190)
Упражнения (195)

ГЛАВА 18
Марковские системы . . . . . . .199

Одномерный случай (199) Двумерные
М-системы (200) Построение
модели (201) Упражнения (208)

ГЛАВА 19
Системы Линденмайера . . . .211

D0L-системы (211) Графическая
интерпретация (212) Построение
модели (213) Упражнения (218)

ГЛАВА 20
Сети Петри . . . . . . . . . . . . . . . . 221

Понятие сети Петри (221)
Параллелизм в сетях Петри (222)
Моделирование трафика (222)
Построение модели (224)
Упражнения (230)

ГЛАВА 21
Перцептрон Розенблатта . . .233

Искусственный нейрон (233)
Нейронные сети (234) Перцептрон
Розенблатта (235) Построение
модели (236) Упражнения (243)

ПРИЛОЖЕНИЕ
Словарь NetLogo. . . . . . . . . . .247

Введение

Естественные вычисления • Тематика настоящего издания связана с проблемами построения и визуализации так называемых естественных
вычислительных моделей. Естественные вычисления1 — это относительно новый раздел приклад1 Англ. — Natural Computing.
ной науки, образовавшийся на стыке математики,
информатики и естественных наук (прежде всего
биологии). Под естественными вычислениями принято понимать различные математические и компьютерные модели, прообразом которых являются разнообразные природные системы и процессы.
Сюда входят как классические модели, например
клеточные автоматы, нейронные сети и генетические алгоритмы, так и относительно новые, в частности модели роевого интеллекта.
Отличительной особенностью практически всех
такого рода моделей является их распределенность,
или многоагентность. Каждая модель состоит, как
правило, из большого числа относительно просто
устроенных объектов — агентов. Сложное нетриви
РИС. 1 Системный эффект

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

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

Введение

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

РИС. 2 Ури Виленски

В качестве такой системы в настоящем учебнике предлагается использовать среду многоагентного моделирования NetLogo, разработанную в конце 1990-х годов американским ученым и педагогом Ури Виленски2. В основу этой свободно рас2
U.
Wilensky,
W.
Rand,
An
introduction
to
agent-based
modeling: Modeling natural, social
and
engineered
complex
systems
with
NetLogo,
Cambridge:
MIT
Press, 2015.

пространяемой среды положен язык программирования NetLogo — отдаленный потомок языка черепашьей графики Logo, разработанного с образовательными целями еще в 1960-х годах одним
из классиков искусственного интеллекта Сеймуром
Пейпертом3.
3 По состоянию на июнь 2010 года
насчитывалось порядка 250 реализаций Logo с момента создания
языка!

РИС. 3 Сеймур Пейперт

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

РИС. 4 Модель NetLogo «Wolf Sheep Predation»

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

Введение
9

Структура книги • Каждая глава издания посвящена рассмотрению какой-нибудь одной модели (либо семейства моделей). В первых параграфах главы дается теоретическое описание модели,
после чего идет подробное, фактически пошаговое
описание процесса построения этой модели в среде
NetLogo4.
4
Для
разработки
моделей
автором использовалась версия 6.0
среды NetLogo.
В конце каждой главы приводится список заданий для самостоятельной проработки изложенного в главе материала: технические упражнения
по доработке построенной модели, задания по численному исследованию поведения данной модели
и «творческие» задания по разработке и визуализации аналогичных моделей.
Изложение материала учебника сопровождается большим числом иллюстраций, таблиц, графиков и библиографических ссылок. В приложении
к учебнику дается краткое описание всех конструкций языка NetLogo, использовавшихся при построении моделей. Более полная документация доступна
через систему помощи среды или на официальном
сайте NetLogo. Крайне полезным также будет изучение моделей из большой библиотеки готовых моделей NetLogo, включающей в себя, в частности,
примеры использования многих конструкций языка и интерфейса NetLogo.
Автор с благодарностью примет конструктивные или доброжелательные комментарии, отзывы
и пожелания, которые читатель сможет оставить
по адресу netlogo.tutorial@gmail.com.

ГЛАВА 1

Задача Бюффона

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

РИС. 1.1 Станислав Улам

чаще всего под статистической обработкой понимается вычисление математического ожидания и, возможно, среднеквадратичного отклонения. Автором
метода Монте-Карло (как вычислительного алгоритма) является американский математик Станислав Улам.
Идея алгоритма пришла Уламу в то время, когда он лежал в больнице и занимался раскладыванием карточного пасьянса Кэнфилд (аналог нашей
Косынки). Он попытался найти вероятность того,

РИС. 1.2 Начальная конфигурация в пасьянсе Кэнфилд

что этот пасьянс сойдется. Однако эта задача оказалась слишком сложной для методов теории вероятностей. Тогда ему и пришла в голову мысль
применить следующий подход — надо разложить
пасьянс n раз и определить количество m тех случаев, когда пасьянс сошелся. Тогда отношение m/n
(так называемое выборочное среднее) и даст приближенную оценку искомой вероятности. Этот алгоритм был практически сразу применен к задаче
вычисления многомерных определенных интегралов; заметим, что эта задача до сих пор остается
одним из важнейших применений метода Монте
РИС. 1.3 Николас Метрополис

Карло, мы рассмотрим ее подробнее в следующей
главе.
Название метода было придумано Николасом
Метрополисом, коллегой Улама, как утверждает

Глава 1

ся, в честь его дяди — страстного игрока в рулетку.
В 1949 году они с Уламом опубликовали совместную статью, которая так и называлась — «Метод
Монте-Карло»1.
1
N.
Metropolis,
S.
Ulam,
The
Monte Carlo Method, Journal of the
American
Statistical
Association,
Vol. 44, No. 247, 1949, p. 335–341.

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

РИС. 1.4 Жорж-Луи Леклерк,
граф де Бюффон

Тем не менее методы Монте-Карло применяются и для решения детерминированных задач. Идея
состоит в том, что нужная нам (детерминированная) величина связывается с некоторыми статистическими параметрами, найденными при проведении серии случайных экспериментов. К этому классу задач как раз и относится вычисление определенных интегралов (т.е. площадей, объемов и т.д.).
Классической же иллюстрацией такого подхода является задача Бюффона2, которая была поставлена
2 Buffon’s needle problem.
и решена задолго до официального появления метода Монте-Карло.

Задача Бюффона • В этой задаче у нас имеется
плоская поверхность, на которой проведены

h

l

РИС. 1.5 Задача Бюффона

параллельные прямые, отстоящие друг от друга на
заданное расстояние h (рис. 1.5). Простым примером такой модели может служить дощатый пол или
разлинованный лист бумаги.
На эту поверхность бросаются иголки (мы, однако, будем бросать спички), длина которых l меньше расстояния h. Каждая спичка может пересечь
какую-нибудь прямую (зеленая спичка) или не пересечь ни одну из них (красная спичка). Вероятность p того, что спичка пересечет некоторую прямую, может быть вычислена аналитически3:
3 В нахождении этой вероятности,
собственно, и заключалась оригинальная задача Бюффона.

p = 2l

πh.
(1.1)

Если теперь провести большую серию таких экспериментов по бросанию спичек и подсчитать частоту (выборочное среднее) ˆp = n/m тех случаев,