Введение в распределенное моделирование в среде 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.