Размещено на http://www.allbest.ru/

Пермский филиал федерального государственного автономного образовательного учреждения высшего образования

«Национальный исследовательский университет

«Высшая школа экономики»

Факультет экономики, менеджмента и бизнес-информатики

Выпускная квалификационная работа

по направлению подготовки 38.03.05 Бизнес-информатика

СРАВНИТЕЛЬНЫЙ АНАЛИЗ РАСПРЕДЕЛЕННЫХ АЛГОРИТМОВ В СРЕДЕ АГЕНТНОГО МОДЕЛИРОВАНИЯ NETLOGO

Некрасов Константин Сергеевич

Руководитель доцент кафедры

информационных технологий в бизнесе

Е. Б. Замятина

Пермь, 2020 год



Аннотация

Данная работа представляет собой результат анализа волновых распределенных алгоритмов. В работе представлен сравнительный анализ алгоритмов, которые реализованы в среде NetLogo. Кроме того, проведен анализ сред имитационного моделирования среди программ AnyLogic, Repast и NetLogo. После анализа среди представленных программ была выбрана среда имитационного моделирования NetLogo. Также представлена реализация моделей трёх волновых алгоритмов с пошаговым пояснением действий. В итоге было составлено руководство для обучения студентов теме распределенных алгоритмов. Руководство позволяет наглядно понять назначение и особенности использования конкретного алгоритма, и его сложность. Также мануал включает в себя демонстрацию работы алгоритмов и инструкцию для написания их в среде имитационного моделирования NetLogo.

Автором данной работы является студент Высшей Школы Экономики Некрасов Константин Сергеевич. Научным руководителем является доцент кафедры информационных технологий в бизнесе Елена Борисовна Замятина.

Текст работы представлен на 42 страницах, включает в себя 3 главы, 40 иллюстраций и 1 таблицу со сравнительным анализом таких программ как NetLogo, AnyLogic и Repast. Приложение включается в себя 61 страницу.



Оглавление

имитационный моделирование программа алгоритм

Введение

1. Изучение предметной области распределенных систем и имитационного моделирования

1.1 Распределенные системы

1.2 Семейство волновых алгоритмов

1.3 Имитационное моделирование

1.4 Дискретно-событийное моделирование

1.5 Системная динамика

1.6 Агентное моделирование

2. Описание и проектирование волновых алгоритмов

2.1 Сравнение сред имитационного моделирования

2.1.1 Критерии оценки СИМ

2.1.2 СИМ Repast

2.1.3 СИМ AnyLogic

2.1.4 СИМ NetLogo

2.1.5 Сравнение систем имитационного моделирования

2.2 Проектирование волновых алгоритмов

2.2.1 Древесный алгоритм

2.2.2 Алгоритм эха

2.2.3 Кольцевой алгоритм

2.2.4 Фазовый алгоритм

2.2.5 Алгоритм Финна

3. Реализация волновых алгоритмов в NetLogo

3.1 Реализация кольцевого алгоритма

3.2 Древесный алгоритм

3.3 Алгоритм эха

3.4 Фазовый алгоритм

3.5 Алгоритм Финна

Заключение

Библиографический список

Приложение А Техническое задание

Приложение Б Руководство по разработке алгоритмов

Кольцевой алгоритм

Древесный алгоритм

Алгоритм Эха

Фазовый алгоритм

Алгоритм Финна



Введение

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

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

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

В данной работе рассмотрено такое семейство распределенных алгоритмов как волновое. Далее выбранное семейство алгоритмов проанализировано и реализовано в среде агентного моделирования Netlogo. Кроме того, составлено руководство для реализации моделей волновых алгоритмов в СИМ NetLogo. Руководство включает в себя описание алгоритмов, особенности и эффективности алгоритмов, а также инструкции к написанию кода на языке Logo, который используется в среде имитационного моделирования NetLogo.

Актуальность данной работы заключается в том, чтобы создать модели, которые будут имитировать распределенные алгоритмы с целью обучения студентов в учебных заведениях и демонстрации устройства работы таких алгоритмов.

Итак, объект исследования - волновые алгоритмы.

Предмет исследования - особенности функционирования различных алгоритмов из семейства волновых алгоритмов с анализом их эффективности и надежности.

Целью данной работы является создание программных средств на языке NetLogo для демонстрации работы алгоритмов. Предполагается сопроводить программное разработанное программное обеспечение подробным описанием с целью использования в учебном процессе.

Для достижения поставленной цели требуется выполнить следующие задачи:

1. Рассмотреть предметную область распределенных алгоритмов и сред имитационного моделирования.

2. Рассмотреть виды волновых алгоритмов и проанализировать их.

3. Сравнить среды имитационного моделирования для выявления более подходящей СИМ (системы имитационного моделирования) для выполнения поставленной задачи.

4. Составить требования к разработке имитационных моделей волновых алгоритмов.

5. Проектирование имитационных моделей волновых алгоритмов в СИМ NetLogo для демонстрации их работы.

6. Представить описание алгоритмов и их реализацию в СИМ NetLogo.

Работа будет иметь структуру, описанную ниже.

Глава 1 - разбор предметной области распределенных систем, волновых алгоритмов и имитационного моделирования.

Глава 2 - анализ и описание волновых алгоритмов, подготовка и проектирование имитационных моделей алгоритмов.

Глава 3 - разработка имитационных моделей для волновых алгоритмов и написание руководства по использованию разработанного программного обеспечения.



1. Изучение предметной области распределенных систем и имитационного моделирования

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

1.1 Распределенные системы

Часто при определении распределенной системы во главу угла ставят разделение ее функций между несколькими компьютерами. При таком подходе распределенной является любая вычислительная система, где обработка данных разделена между двумя и более компьютерами. Несколько более узко распределенную систему можно определить как набор соединенных каналами связи независимых компьютеров, которые с точки зрения пользователя некоторого программного обеспечения выглядят единым целым [1].

Существует несколько причин, по которым распределенные системы оказываются более предпочтительны, либо их применение становится неизбежным [2]:

1. Обмен информацией.

2. Совместное использование ресурсов.

3. Повышение надежности за счет дублирования.

4. Повышение производительности за счет параллельного выполнения.

5. Упрощение проектирования за счет специализации.



1.2 Семейство волновых алгоритмов

При работе с большим количеством процессов и сотрудников всегда встаёт вопрос об организации работы, то есть связь всех процессов и их синхронизация. Это делается с целью обмена информацией, при условии, что один отдельно взятый процесс задействует только часть необходимых данных. Для таких случаев очень важно уметь использовать волновые алгоритмы, которые помогают решать такие задачи, связывать несколько процессов вместе используя схему, которая была предписана для таких случаев ранее.

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

Инициаторами называются стартовые процессы, которые начинают выполнение алгоритма по какому-либо условию. То есть инициатор запускает распространение информации или же отправку сообщения.

Неинициаторы же ответственны за то, чтобы принять сообщение от инициатора и продолжить исполнение алгоритма.

Распределенные системы работают с помощью программ, которые под них создают. Программы для распределенных систем должны основываться на правильных, гибких и эффективных алгоритмах. Основные волновые алгоритмы выделяют следующие (в данной работе будут реализованы не все):

1. Кольцевой алгоритм.

2. Древесный алгоритм.

3. Алгоритм эха.

4. Алгоритм опроса.

5. Фазовый алгоритм.

6. Алгоритм Финна.

1.3 Имитационное моделирование

Известно, что имитационное моделирование находит свое применение в самых широких областях производства, науки, бизнеса. Действительно, очень многие исследования нуждаются в проведении различных имитационных экспериментов. Их целью является прогнозирование поведения изучаемого объекта или системы, которая является сложной и динамической. Такие имитационные эксперименты предоставляют возможность рассмотреть ситуацию с различных сторон, при этом используя различные вводные данные. Тем самым повышая вероятность принять верное решение, например, в современных реалиях ведения бизнеса и организации предприятия [3]. Так в результате проведения экспериментов выявляется самый выгодный способ ведения бизнеса и организации структуры предприятия. После этого есть смысл проверить значения таких параметров для бизнес-процессов как затраты, оперативность бизнес-операций. С такой целью целесообразно сымитировать поведение модернизированного бизнес-процесса, определяя при этом результативность модернизации по ключевым показателям. Таким образом, системы имитационного моделирования являются неотъемлемой частью систем поддержки принятия решений (СППР). Также в автоматизированном проектировании имитационное моделирование играет немаловажную роль.

Существует три вида имитационного моделирования [4]:

1. Агентное моделирование.

2. Дискретно-событийное моделирование.

3. Системная динамика.

В данной работе рассматривается именно агентное моделирование.



Рисунок 1.1 Виды имитационного моделирования

1.4 Дискретно-событийное моделирование

При анализировании различных процессов иногда используют способ рассмотрения отдельно взятых этапов в процессе. То есть весь процесс разбивается на конкретные главные этапы. Такой способ анализа процессов называется дискретно-событийным моделированием [5]. Чаще всего данный способ моделирования используют для процессно-ориентированного моделирования. Это значит, что динамика таких моделей представляется в виде последовательно идущих операций (их обычно различают на прибытие, задержку и захват ресурсов), которые осуществляют деятельность над различными сущностями (обычно транзактами или заявками). Такие сущности обычно несут в себе некие документы, пакеты данных, звонки и другую информацию. При этом сущности не контролируют своё поведение, но имеют атрибуты, которые могут повлиять на процессы, которые обрабатывают данные сущности, а также накапливают статистику.

При таком виде моделирования весь процесс разбивается на объекты, которые в дальнейшем и моделируются индивидуально. Такие объекты являются отдельными сущностями, но всё-таки большинство деталей в моделировании не учитываются. С помощью такой технологии моделирования принято моделировать различные бизнес-процессы. Пример такого подхода к моделированию показан на рисунке 1.2.

Рисунок 1.2 Пример дискретно-событийного моделирования

1.5 Системная динамика

Данный способ имитационного моделирования встречается в самых различных исследованиях и стезях бизнеса. Системная динамика [6] даёт возможность смоделировать системы высокой сложности и на высоком уровне абстракции, то есть не рассматривая мельчайшие детали. К примеру, мельчайшими деталями могут являться свойства отдельно взятых продуктов, событий или людей. Модели, построенные таким способом имитирования, дают возможность сложить общее представление о системах и являются отличным решением для стратегического планирования.

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

Разные взаимозависимости внутри модели часто показывают в виде циклом, которые также называются циклами обратной связи. Такие циклы являются самой базовой концепцией такого вида имитационного моделирования. Примером может послужить маркетинг в компании. В той ситуации, когда компания вкладывает большее количество средств в маркетинг, он в свою очередь увеличивает прибыль компании, а исходя из этого позволяет вкладывать всё большие средства в маркетинг. Данный цикл обратной связи как пример показан на рисунке 1.3.

Рисунок 1.3 Пример цикла обратной связи в системной динамике

1.6 Агентное моделирование

Агентное моделирование - это один из методов имитационного моделирования, рассматривающий поведение децентрализованных агентов. Кроме того, данный метод исследует как такое поведение определяет поведение всей системы как единое целое. В отличие от системной динамики аналитик определяет поведение агентов на индивидуальном уровне, а глобальное поведение возникает как результат деятельности множества агентов (моделирование «снизу вверх») [7]. Агентное моделирование применяется в огромном количестве различных сфер деятельности. Оно может использоваться в социологии, политологии и многих других.

Изначально в агентном моделировании задаются параметры агентов, которые в свою очередь являются активными объектами. Такие активные объекты могут являться чем угодно. Единственное условие для них -- это иметь значение для исследуемой системы. К примеру, агентами в наших моделях будут являться действующие лица в распределенных системах (обычно это компьютеры в компьютерных сетях).

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

Существует не так много программ, которые выступают средами имитационного моделирования, в данной работе будут рассмотрены следующие:

1. Repast [8].

2. Anylogic [9].

3. NetLogo [10].

Рисунок 1.4 Пример модели в Anylogic об обслуживании клиента в компании

Рисунок 1.5 Пример интерфейса в Netlogo



2. Описание и проектирование волновых алгоритмов

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

2.1 Сравнение сред имитационного моделирования

Существует множество различных сред имитационного моделирования (СИМ), далее приведены критерии оценки, а также сравнение таких сред имитационного моделирования, как: NetLogo, AnyLogic и Repast.

2.1.1 Критерии оценки СИМ

Основываясь на статье о современных СИМ [11,17,18,19] далее приведены критерии оценки систем имитационного моделирования.

Для сравнения систем имитационного моделирования в статье Джелла Никукарана [12] предложено сравнение СИМ по наличию следующих функций:

1. Построение модели.

2. Выполнение.

3. Отладка.

4. Анимация.

5. Вывод результатов.

Далее каждая функция рассмотрена более подробно с точки зрения того какие возможности может предоставить система имитационного моделирования.

Функция «построение модели» отвечает за все возможности, с помощью которой в СИМ можно промоделировать необходимый бизнес-процесс, то есть построить модель, которая будет визуализировать или имитировать вид бизнес-процесса. Все подгруппы данного критерия показаны на рисунке 2.1.

Рисунок 2.1 Функция «построение модели»

Функция «выполнение» отвечает за то, как ведет себя необходимый бизнес-процесс в различных заданных ситуациях. Например, возможность изучить как выполняется модель с изменением базы генератора случайных чисел или с изначально заданными значениями. Все подгруппы данного критерия показаны на рисунке 2.2.

Рисунок 2.2 Функция «выполнение»

Функция «отладка» отвечает за то, как СИМ справляется с выявлением различных ошибок, которые возникают в процессе моделирования и работы имитации. Все подгруппы критерия показаны на рисунке 2.3.

Рисунок 2.3 Функция «отладка»

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

Рисунок 2.4 Критерий «анимация»

Критерий «вывод результатов» отвечает за то, как система имитационного моделирования формирует отчётность по результатам выполнения определенного бизнес-процесса, в каких видах можно получить результаты (вывод на печать, табличная версия), а также как СИМ анализирует полученные результаты. Все подгруппы данного критерия показаны на рисунке 2.5.

Рисунок 2.5 Критерий «вывод результатов»

Большинство данных критериев являются нечисловыми, то есть не поддаются количественной оценке, поэтому оценка будет производиться путём сравнения различных параметров систем имитационного моделирования. К примеру, не в каждой СИМ имеется графический редактор, следовательно его наличие будет записан как положительная оценка определенного критерия. Исходя из теста различных СИМ будет выявлена та имитационная среда, что будет наиболее удобна в решении конкретно нашей поставленной задачи.

2.1.2 СИМ Repast

The Recursive Porous Agent Simulation Toolkit (Repast) - это бесплатно распространяющаяся и широко используемая СИМ, которая также включает различные библиотеки для агентного моделирования. Данная программа была разработана в Чикагском университете. Repast включает в себя реализацию на нескольких языках программирования позволяя пользователю более гибко строить имитационные модели Существует 3 версии Repast [13] Каждая из них имеет упор на определенный язык программирования (Python, Java и Microsoft.NET).

Repast Py - версия программы для агентного моделирования, которое даёт возможность строить имитационные модели с помощью графического интерфейса и описания взаимодействия агентов используя скрипты в языке Python.

Repast J - это СИМ, которая использует язык программирования Java. Она служит для того, чтобы разрабатывать крупномасштабные агентные модели. Также включает в себя календарь события для параллельного планирования во времени. Пример на рисунке 2.6.

Repast Microsoft.NET - СИМ, реализрованная на языке C#. С помощью неё можно перенести все функции Repast J на платформу.NET и создавать дальнейшие модели с использованием любого языка программирования, который поддерживается на.NET.

Рисунок 2.6 Интерфейс Repast

2.1.3 СИМ AnyLogic

AnyLogic - это разработка для имитационного моделирования, включающий в себя все три самых популярных метода моделирования. Данное программное обеспечение было разработано российской группой TheAnylogic Company на языке программирования Java. Не так давно был запущен сервис AnyLogic Cloud, который даёт возможность выкладывать имитационные модели в веб-пространство и тем самым демонстрировать его другим людям без каких-либо затрат во времени. Веб-сервис показан на рисунке 2.7.

AnyLogic имеет в себе графический язык, который даёт возможность апгрейдить уже построенные модели языком Java. Кроме того, в данном ПО интегрирован компилятор Java, тем самым позволяя создавать Java апплеты. Интерфейс программы представлен на рисунке 2.8.

Рисунок 2.7 Веб-сервис AnyLogic Cloud

Рисунок 2.8 Интерфейс AnyLogic

AnyLogic имеет множество положительных сторон:

1. Интегрированное ПО для анализа данных, а также набор возможностей для бизнес-графики для демонстрирования моделей.

2. С помощью языка Java есть возможность доопределить функции любых элементов модели.

3. Огромное количество видов экспериментов с моделью (варьирование параметров, простой и сравнительный прогон).

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

2.1.4 СИМ NetLogo

NetLogo - это мультиагентная среда имитационного моделирования, основанная на языке Logo [10]. Данное ПО было разработано усилиями Массачусетского университета и компании BBN. Язык часто используется для обучения, так как не сложен в работе, но при этом остаётся мощным решением для разработки имитационных моделей. Интерфейс данной программы показан на рисунке 2.9.



Рисунок 2.9 Интерфейс NetLogo

Огромный плюс данной программы в том, что синтаксис довольно минималистичен и он лёгок в изучении, тем самым не будет проблемы создать несложную модель с образовательной целью. Также NetLogo имеет обширную библиотеку встроенных моделей для различных целей (образование, исследование, развлечение). Кроме того, есть возможность контактировать со специализированным программным обеспечением, таким как GoGo board. Разработанная модель показана на рисунке 2.10.



Рисунок 2.10 Модель в NetLogo

2.1.5 Сравнение систем имитационного моделирования

Далее приведено сравнение вышеописанных сред имитационного моделирования и выбрана одна из предложенных. Нужно сказать, что в расчёт были взяты только основные критерии оценки, чтобы не нагружать анализ и процесс выбора СИМ. Оценочный анализ приведен в таблице 2.1.

Таблица 2.1

Оценочный анализ СИМ

Критерий	AnyLogic	Repast	NetLogo
Наличие визуального конструктора	1	1	1
Отладка	1	1	1
Ресурсоёмкость (количество времени и знаний)	0,5	0	1
Наличие агентного подхода моделирования	1	1	1
Модули и библиотеки системных алгоритмов	0	1	1
Ручное масштабирование модели	1	0	1
Программное масштабирование модели	1	1	1
Сложность освоения (+ значит лёгок, - значит сложен в освоении)	0,5	0	1
Кроссплатформенность	1	1	1
Анализ построенных моделей	1	0,5	0,5
Отчётность	1	0,5	0
Итого	9	8	9,5

Подводя итог анализа сред имитационного моделирования хочется сказать, что все выбранные СИМ (AnyLogic, Repast, NetLogo) подходят для построения моделей и решения именно поставленной конкретной задачи, разница между ними незначительна. AnyLogic считается одной из лучших СИМ в данным момент, но исходя из того что прошлая курсовая работа была основана на моделировании в AnyLogic хотелось рассмотреть и другое программное обеспечение в данной сфере. Кроме того, NetLogo считается всемирно признанным ПО именно для работы с распределенными системами и учитывая, что NetLogo получило наивысший балл в оценочном анализе, было принято решение моделировать волновые алгоритмы в NetLogo.

2.2 Проектирование волновых алгоритмов

Далее приведено описание работы каждого выбранного волнового алгоритма, а также построены к ним блок-схемы. Информация о волновых алгоритмах была взята из учебного пособия по распределенным системам и алгоритмам [14] и из статьи по волновым алгоритмам [15].

2.2.1 Древесный алгоритм

Древесный алгоритм - это алгоритм из семейства волновых алгоритмов. Его смысл в том, что все листья, то есть процессы, которые являются вершинами дерева, запускают алгоритм и являются инициаторами. Все остальные процессы являются неактивными (неинициаторы).

Алгоритм начинается с того, что все листовые процессы отправляют сообщение вверх остальным неактивным процессам в дереве. Те процессы, что были неактивны и получили сообщение, становятся активными и тем самым становятся инициаторами, чтобы передавать сообщение дальше. И так далее волнами каждый процесс в дереве получает сообщение и после этого алгоритм завершает свою работу. Работа алгоритма в виде блок-схемы представлена на рисунке 2.11.

Рисунок 2.11 Блок-схема древесного алгоритма

2.2.2 Алгоритм эха

Алгоритм эха -- это централизованный волновой алгоритм в сетях с произвольной топологией. Смысл данного алгоритма в том, что инициатором служит один процесс, а все остальные процессы являются неактивными.

Алгоритм начинается с того, что инициатор начинает отправку сообщения всем соседним процессам, которые находятся в состоянии неактивности. Посредством волн инициаторы передают сообщение всем своим соседям кроме процесса, который передал этот сигнал или уже является активным. После неопределенного числа волн сообщение получает каждый процесс и алгоритм заканчивает свою работу. Работа данного алгоритма представлена на рисунке 2.12.

Рисунок 2.12 Блок-схема алгоритма эха

2.2.3 Кольцевой алгоритм

Кольцевой алгоритм - это алгоритм, который можно использовать в гамильтоновой сети или графе. Гамильтонов граф - это замкнутый путь, тот же цикл, где необходимо пройти через каждую вершину графа.

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

Рисунок 2.13 Блок-схема кольцевого алгоритма

На этом этап проектирования заканчивается, далее будет приведена реализация вышеперечисленных алгоритмов.

2.2.4 Фазовый алгоритм

Фазовый алгоритм является децентрализованным алгоритмом, который подходит для сетей, в которых используется произвольная топология. Такой алгоритм подходит для ориентированных сетей.

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

Данный алгоритм применяется для любой ориентированной сети, данные в которой передаются в одну сторону. В таком случае соседями любой вершины будут как инициаторы, так и неинициаторы. Также по каждому каналу должно передаваться такое количество сообщений, которое не превышает длину сети. Двунаправленные связи тоже могут присутствовать, но они должны быть заданы парой параллельных встречных однонаправленных каналов. Блок-схема фазового алгоритма показана на рисунке 2.14.

Рисунок 2.14 Блок-схема фазового алгоритма

2.2.5 Алгоритм Финна

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

В процессе р формируются два множества отличительных признаков Incp, и Nincp. Incp обозначает множество таких процессов q, что некоторое событие в q предшествует самому последнему событию, случившемуся в р, a Nlncp обозначает множество таких процессов q, что у каждого соседа г процесса q какое-нибудь событие в г предшествует самому последнему событию, случившемуся в р. Блок-схема алгоритма показана на рисунке 2.15.

Рисунок 2.15 Блок-схема алгоритма Финна

На этом этап проектирования заканчивается, далее приведена реализация.



3. Реализация волновых алгоритмов в NetLogo

В данной главе обсуждаются волновые алгоритмы, которые уже были спроектированы выше и далее идёт их разработка в системе имитационного агентного моделирования NetLogo. Реализация велась с помощью NetLogo User Manual [16].

3.1 Реализация кольцевого алгоритма

Для начала необходимо создать несколько несвязанных агентов или «черепашек», которые будут отвечать за процессы в алгоритме. Созданные агенты показаны на рисунке 3.1.

Рисунок 3.1 Созданные агенты

Далее для данного алгоритма необходимо, чтобы у каждого процесса было по 2 связи, через которые потом будет производиться передача сообщений. Данная функция будет создана через функцию create-link-with внутри программы NetLogo. Получившаяся картина показана на рисунке 3.2.

Рисунок 3.2 Процессы со связями

Далее случайно выбирается один процесс, который будет являться инициатором, его цвет будет отображён как красный. Для этого внутри программы выбирается агент с нулевым номером и помечается красным цветом. Получившаяся картина показана на рисунке 3.3.



Рисунок 3.3 Появление инициатора

После этого, по цепочке идёт передача сообщения от инициатора к одному из связанных с ним неактивному процессу. Теперь ранее неактивный процесс становится инициатором и загорается красным цветом, далее он будет передавать сообщение. Изначальный инициатор загорается серым цветом для того, чтобы пользователь понимал, что в этом процессе уже было сообщение, но в данный момент он не является инициатором. Данная ситуация показана на рисунке 3.4.



Рисунок 3.4 Появление нового инициатора

Далее двигаясь по цепочке каждый из процессов, получит информацию и передаст его следующему. Рисунок 3.5 показывает ситуацию на 4 тик.

Рисунок 3.5 Ситуация на 4 тик

Итого, после того как все процессы получат информацию и передадут дальше, изначальный инициатор получит информацию всех процессов в данном алгоритме. Если предположить, что каждый наш агент является компьютером в офисной сети,

Рисунок 3.6 Последний тик алгоритма

а изначальный инициатор является директором компании, то исходя из полученной информации всех компьютеров в сети, директор будет принимать решение. Последний тик данного алгоритма показан на рисунке 3.6.

3.2 Древесный алгоритм

Для данного алгоритма необходимо создать несколько агентов и задать листовым процессам вид инициаторов, то есть красный цвет. Данный вид показан на рисунке 3.7.



Рисунок 3.7 Изначальный древесный алгоритм

Далее за одну волну инициаторы передают информацию вверх по дереву, а сами переходят в состояние распространивших сообщение, то есть становятся серыми. Результат данного этапа показан на рисунке 3.8.

Рисунок 3.8 Передача информации

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

Рисунок 3.9 Конец выполнения древесного алгоритма

По итогу выполнения древесного алгоритма каждый агент в системе получил сообщение.

3.3 Алгоритм эха

В данном алгоритме инициатором выступает один процесс, который передаёт сообщение соседним неактивным процессам. Изначальные данные алгоритма показаны на рисунке 3.10.



Рисунок 3.10 Начало алгоритма эха

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

Рисунок 3.11 Этап передачи сообщения

После этого передача сообщения продолжается, а те процессы, которые приняли сообщение, начинают передавать его другим неактивным процессам, пока не закончится алгоритм. Конец данного алгоритма представлен на рисунке 3.12.

Рисунок 3.12 Завершение алгоритма эха

Таким образом были построены все вышеперечисленные волновые алгоритмы.

3.4 Фазовый алгоритм

Необходимо создать агентов, которые имеют размер 3, синий цвет и форму кружков. Также необходимо с помощью команды «layout-circle turtles (world-width / 2 - 10)» расположить их по кругу, а кроме этого, задать инициатора. Полученная модель показана на рисунке 3.13.



Рисунок 3.13 Начальное состояние модели

Далее необходимо задать код, который будет передавать цвет от одного агента к другому, при этом инициатор является красным, затем переходит в неактивное состояние, а агент, который принял сообщение «загорается» красным, то есть становится активным. Этот алгоритм проходит до тех пор, пока один из агентов не передаст сообщение количество (n-4) раз. То есть на один меньше, чем количество агентов в цепочке. Второй этап выполнения алгоритма показан на рисунке 3.14.



Рисунок 3.14 Второй этап выполнения алгоритма

Третий этап выполнения алгоритма показан на рисунке 3.15.

Рисунок 3.15 третий этап выполнения алгоритма

Далее на рисунке 3.16 показан последний этап выполнения алгоритма.



Рисунок 3.16 Последний этап выполнения алгоритма

После данного этапа алгоритм закончил своё выполнение, так как нижний агент принял и передал 3 сообщения, то есть (n - 4).

3.6 Алгоритм Финна

Необходимо задать код, который создаёт модель, а также будет передавать цвет от одного агента к другому, при этом инициатор является красным, затем переходит в неактивное состояние, а агент, который принял сообщение «загорается» красным, то есть становится активным. Кроме того, необходимо задать связи между процессами. Модель показана на рисунке 3.17.



Рисунок 3.17 Изначальная модель алгоритма

Далее на рисунке 3.18. показан второй этап выполнения алгоритма (после одного нажатия кнопки «go».

Рисунок 3.18 Второй этап выполнения алгоритма

На рисунке 3.19. показан четвёртый этап выполнения алгоритма.

Рисунок 3.19 Четвёртый этап выполнения алгоритма

Последний этап выполнения алгоритма показан на рисунке 3.20. Агент 3 остался активным, так как было получено сообщение от агента 0. Процесс 2 остаётся активны и отсылает данные, которые полностью определены агенту 0, который являлся изначальным инициатором. Произошло оповещение всех агентов (процессов) в сети. Алгоритм завершил свою работу.



Рисунок 3.20 Последний этап выполнения алгоритма

Таким образом были построены все вышеперечисленные волновые алгоритмы.



Заключение

В ходе работы была изучена предметная область распределенных систем, в частности волновые алгоритмы. Кроме того, рассмотрена предметная область имитационного моделирования с углублением именно на метод агентного моделирования. Также был проведён сравнительный анализ трёх сред имитационного моделирования, используя различные критерии оценки СИМ. Сравнительный анализ включал такие среды моделирования, как: NetLogo, AnyLogic и Repast. По итогу анализа решено было выбрать NetLogo как среду разработки для поставленной задачи.

Для пяти видов волновых алгоритмов (кольцевой алгоритм, древесный алгоритм, фазовый алгоритма, алгоритм эха и алгоритм Финна) были построены блок-схемы и как итог работы были построены имитационные модели, которые наглядно показывают работу волновых алгоритмов. В дальнейшем данные имитационные модели будут использованы для описания руководства пользователя.

Построенные имитационные модели можно успешно применять для обучения студентов распределенным алгоритмам.



Библиографический список

1. Обзор распределенных систем [Электронный ресурс]. Режим доступа _ http://masters.donntu.org/2008/fvti/prihodko/library/dist2.htm Дата обращения: 23.02.20.

2. Тель Ж. Введение в распределенные алгоритмы, Изд-во МЦНМО, Москва. 2009. с. 616.

3. Емельянов А. А., Власова Е. А., Дума Р.В. Имитационное моделирование экономических процессов: Учебное пособие. М.: Финансы и статистика, 2002 [Электронный ресурс]. Режим доступа - http://simulation.su/uploads/files/default/immod-2009-1-19-26.pdf. Дата обращения: 30. 02. 20.

4. Виды имитационного моделирования [Электронный ресурс]. Режим доступа _ https://studbooks.net/2274235/informatika/vidy_imitatsionnogo_modelirovaniya. Дата обращения: 02. 03. 20.

5. N. S. Matloff, Introduction to Discrete-Event Simulation and the SimPy Language, 2013 [Электронный ресурс]. Режим доступа _ http://heather.cs.ucdavis.edu/~matloff/156/PLN/DESimIntro.pdf. Дата обращения: 02. 03. 20.

6. Борщёв А. От системной динамики и традиционного ИМ - к практическим агентным моделям: причины, технология, инструменты [Электронный ресурс]. Режим доступа - http://gpss.ru/paper/borshevarc.pdf. Дата обращения 05. 03. 20.

7. Лебедюк Э. А., Агентное моделирование: состояние и перспективы [Электронный ресурс]. Режим доступа - http://simulation.su/uploads/files/default/2017-lebeduk-1.pdf. Дата обращения: 07. 03. 20.

8. Charles M., Michel J., Tutorial on agent-based modeling and simulation part 2: how to model with agents [Электронный ресурс]. Режим доступа - http://www2.hawaii.edu/~nreed/ics606/papers/Macal06model.pdf. Дата обращения: 13. 03. 20.

9. Сharles M., Everything you need to know about agent-based modelling and simulation [Электронный ресурс]. Режим доступа - https://www.researchgate.net/publication/302923196_Everything_you_need_to_know_about_agent-based_modelling_and_simulation. Дата обращения: 13. 03. 20.

10. Carbo J., Agent-based simulation with NetLogo to evaluate ambient intelligence scenarios [Электронный ресурс]. Режим доступа - https://link.springer.com/article/jos.2016.10. Дата обращения: 15. 03. 20.

11. Современные системы имитационного моделирования и критерии их оценки [Электронный ресурс]. Режим доступа - http://simulation.su/uploads/files/default/2019-dadenkov-kon.pdf. Дата обращения: 30. 03. 20.

12. Джелал Никукаран, Критерии оценки СИМ [Электронный ресурс]. Режим обращения - http://simulation.su/uploads/files/default/obzor-2010-guravlev.pdf. Дата обращения: 30. 03. 20

13. Michael J. and Charles M., Escaping the Accidents of History: An Overview of Arti?cial Life Modeling with Repast [Электронный ресурс]. Режим доступа - https://link.springer.com/chapter/10.1007/1-84628-214-4_6. Дата обращения: 25. 03. 20

14. А. И. Миков, Е. Б. Замятина, Распределенные системы и алгоритмы, 2007 [Электронный ресурс]. Режим доступа - http://window.edu.ru/resource/466/57466. Дата обращения: 31. 03. 20.

15. Е. Б. Замятина, Д. Ф. Каримов, Волновые алгоритмы [Статья]

16. NetLogo 6.1.1 User Manual [Электронный ресурс], Режим доступа - https://ccl.northwestern.edu/netlogo/docs/dictionary.html. Дата обращения: 10. 04. 20.

17. Замятина Е.Б. Современные теории имитационного моделирования: Специальный курс. Пермь: ПГУ, 2007. 119 с. http://window.edu.ru/resource/717/41717

18. Замятина Е.Б. Системы имитационного моделирования и машинная имитация: теоретические основы и реализация. Методичсекое пособие / Е.Б. Замятина, В.В. Ланин, Л.Н. Лядова, А.Н. Фирсов ; Федер. агентство по образованию, ГОУВПО "Перм. гос. ун-т", Пермь, 2007 - 304 с.

19. Замятина Е.Б. Современные теории и системы имитационного моделирования: учеб.-метод. пособие / Е.Б. Замятина, В.В. Ланин, Л.Н. Лядова, А.Н. Фирсов ; Федер. агентство по образованию, ГОУВПО "Перм. гос. ун-т", 2007 г.,- 100 с.



Приложение А Техническое задание

Пермский филиал федерального государственного автономного

образовательного учреждения высшего образования

«Национальный исследовательский университет

«Высшая школа экономики»

Техническое задание на разработку моделей волновых алгоритмов в среде имитационного моделирования NetLogo

Тема: «Сравнительный анализ распределенных алгоритмов в среде агентного моделирования NetLogo».

НИУ ВШЭ-БИ-16-1

Пермь, 2020

Аннотация

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

В данном документе приводится следующая информация:

1. Введение

2. Основания для разработки

3. Назначение разработки

4. Требования к программе

5. Требования к программной документации

6. Технико-экономические показатели

7. Стадии и этапы разработки

8. Порядок контроля и приемки

Г.1. Введение

Г.1.1. Наименование задачи

Наименование задачи: “Построение имитационных моделей волновых алгоритмов”.

Г.1.2. Назначение и область применения

Модели предназначены для обучения студентов высших учебных заведений.

Г.2. Основание для разработки

Разработка ведется на основании документа ГОСТ 19.201-78 ЕСПД. Организация, утвердившая этот документ - Государственный комитет СССР по стандартам от 18 декабря 1978 г. N 3351 дата введения установлена 01.01.80. Наименование темы разработки - исследование имитационных моделей социальный сетей.

Г.3. Назначение разработки

В разделе представлена информация о функциональном и эксплуатационном назначении моделей.

Г.3.1. Функциональное назначение

Функциональным назначением моделей является демонстрация пользователю работы пяти видов волновых алгоритмов: кольцевой, древесный, алгоритм Финна, фазовый алгоритм и алгоритм эха.

Г.3.2. Эксплуатационное назначение

Имитационные модели должны эксплуатироваться в обучающих целях.

Конечными пользователями программы должны являться студенты высших учебных заведений.

Г.4. Требования к программе

В данном разделе представлены различного рода требования к программе (функциональные, к надежности, к эксплуатации и т. д.).

Г.4.1. Требования к функциональным характеристикам

Возможность моделирования волновых алгоритмов с различным количеством процессов.

Г.4.2. Требования к надежности

Г.4.2.1. Требования к обеспечению надежного функционирования программы

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

· организацией бесперебойного питания технических средств;

· использованием лицензионного программного обеспечения;

· регулярным выполнением рекомендаций Министерства труда и социального развития РФ, изложенных в Постановлении от 23 июля 1998 г. “Об утверждении межотраслевых типовых норм времени на работы по сервисному обслуживанию ПЭВМ и оргтехники и сопровождению программных средств»;

· регулярным выполнением требований ГОСТ 51188-98. Защита информации. Испытания программных средств на наличие компьютерных вирусов.

Г.4.2.2. Время восстановления после отказа

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

Г.4.2.3. Отказы из-за некорректных действий оператора

Отказы в выполнении моделей не предоставляется.

Г.4.3. Условия эксплуатации

Г.4.3.1. Климатические условия эксплуатации

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

Г.4.3.2. Требования к квалификации и численности персонала

Минимальное количество персонала, требуемого для работы программы, должно составлять не менее 2 штатных единиц -- системный администратор и конечный пользователь программы -- оператор. Системный администратор должен иметь высшее профильное образование и сертификаты компании-производителя операционной системы. В перечень задач, выполняемых системным администратором, должны входить:

· задача поддержания работоспособности технических средств;

· задачи установки (инсталляции) и поддержания работоспособности системных программных средств -- операционной системы;

· задача установки (инсталляции) программы.

· задача создания резервных копий базы данных.

Г.4.4. Требования к составу и параметрам технических средств

В состав технических средств должен входить персональный компьютер, включающий в себя: процессор intel 3 поколения (для комфортного пользования программой), оперативную память объемом 4 Гигабайт, операционную систему Windows 7 и выше, а также NetLogo версии 6.6.1 или выше.

Г.4.5. Требования к информационной и программной совместимости

Г.4.5.1. Требования к информационным структурам и методам решения

Использованы возможности программы для имитационного моделирования NetLogo.

Г.4.5.2. Требования к исходным кодам и языкам программирования

Модели выполняются в СИМ NetLogo на языке Logo.

Г.4.5.3. Требования к программным средствам, используемым программой

Необходимо иметь только программу NetLogo.

Г.4.5.4. Требования к защите информации и программ

Требования к защите информации и программ не предъявляются.

Г.4.5. Специальные требования

Специальные требования к данной программе не предъявляются.

Г.6. Стадии и этапы разработки

Г.6.1. Стадии разработки

Разработка должна быть проведена в три стадии:

1. разработка технического задания;

2. проектирование алгоритмов;

3. разработка моделей.

Г.6.2. Этапы разработки

На стадии разработки технического задания должен быть выполнен этап разработки технического задания. На стадии рабочего проектирования должны быть построены блок-схемы алгоритмов, а также описана работа алгоритмов.

На стадии внедрения должен быть выполнен этап разработки подготовка и передача программы.

Г.6.3. Содержание работ по этапам

На этапе разработки технического задания должны быть выполнены перечисленные ниже работы:

1. постановка задачи;

2. определение и уточнение требований к техническим средствам;

3. определение требований к программе;

4. определение стадий, этапов и сроков разработки программы и документации на неё;

5. согласование и утверждение технического задания.

На этапе разработки программы должна быть выполнена работа по программированию (кодированию) и отладке программы.

На этапе разработки программной документации должна быть выполнена разработка программных документов в соответствии с требованиями к составу документации.

На этапе испытаний программы должны быть выполнены перечисленные ниже виды работ:

1. разработка, согласование и утверждение, и методики испытаний;
проведение приемо-сдаточных испытаний;

2. корректировка программы и программной документации по результатам испытаний.

На этапе подготовки и передачи программы должна быть выполнена подготовка и передаче программы и программной документации в эксплуатацию на объектах Заказчика.

Г.7. Порядок контроля и приемки

Г.7.1. Виды испытаний

Виды испытаний не предоставляются.

Г.7.2. Общие требования к приемке работы

Необходимо иметь спроектированные и реализованные алгоритмы в СИМ NetLogo.



Приложение Б Руководство по разработке алгоритмов

Кольцевой алгоритм

Кольцевой алгоритм - это алгоритм, который можно использовать в гамильтоновой сети или графе. Гамильтонов граф - это замкнутый путь, тот же цикл, где необходимо пройти через каждую вершину графа.

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

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

Описание алгоритма

Этап 1. Задание начальных данных

Задать глобальные переменные: globals [n]

Breed [nodes node] задать класс nodes которые будут иметь в себе всех агентов

Nodes-own [state] присвоить классу nodes состояния state

Задать необходимый фон (pcolor = white), размер и цвет агентам (nodes)

Этап 2. Цикл соединения процессов между собой

Repeat (num - 1) цикл повторяется num-1 раз

В цикле: обращение к агенту с номером b: create-link-with node (b - 1) создать соединительные линии между nodes

Задать каждому node свой state и номер (n), который обращается к node

Создать переменную num, которая принимает количество nodes с рычажка

Этап 3. Функция GO (передача информации)

Создать функцию «go» которая выполняет 1 действие алгоритма (1 tick)

Функция «Go»:

Если n меньше num выполнить:

Node n меняет цвет на серый (информацию получил и передал) и передать красный цвет следующему агенту (то есть передать информацию)

Блок-схема кольцевого алгоритма

Блок-схема кольцевого алгоритма

Инструкция по написанию кода кольцевого алгоритма в NetLogo:

При первом входе в программу перед пользователем появляется окно, которое показано на рисунке 1. Чтобы начать описывать модель необходимо перейти во вкладку «Код». Вкладка «Код» показана на рисунке 2.

Рисунок 1 Главное окно NetLogo

Рисунок 2 Вкладка «Код»

Для того, чтобы создать кнопку, которая будет создавать модель необходимо выйти на главное окно программы и нажать кнопку «Добавить», которая показана на рисунке 3.

Рисунок 3 Выбор добавляемого объекта

При добавлении необходимо выбрать пункт «Кнопка» и перетащить на рабочую поверхность программы. Необходимо дать название кнопки и описание, показано на рисунке 4. Назовём «setup».

Рисунок 4 Описание кнопки

После этого необходимо нажать «Ок», и кнопка появится на рабочей области программы. Пока она «горит» красным, так как её функция ещё не была описана с помощью кода. Созданная кнопка показана на рисунке 5.

Рисунок 5 Созданная кнопка «setup»

Далее для описания созданной кнопки переходим во вкладку «Код». Чтобы описать функцию необходимо написать код, показанный на рисунке 6.

Рисунок 6 Код кнопки «Setup»

Чтобы обратиться к кнопке необходимо написать «to (название кнопки)». Каждая такая функция должна заканчиваться словом end. На рисунке показан код, где строка «clear-all» отвечает за очищение поля модели, ask patches [set pcolor white] отвечает за замену чёрного фона модели на белый, а reset-ticks сбрасывает тики внутри программы до значения 0. На рисунке 7 показана работа кнопки, которую мы описали.

Рисунок 7 Работа кнопки «setup»

Далее таким же образом, как и кнопку, с помощью «Добавить» необходимо создать «рычажок», который будет называться «num» и будет передавать количество созданных агентов. Заданные данные для «рычажка» показаны на рисунке 8, где «num» - название, минимум это минимальное значение «num», максимум это максимальное значение, а строка значение отвечает за то какое значение «num» будет принимать изначально.



Рисунок 8 Параметры «num»

Теперь с помощью переменной «num» можно передавать количество заданных агентов. Далее необходимо написать код для появления агентов. Снова необходимо открыть вкладку «Код» и написать код, который показан на рисунке 9.

Рисунок 9 Код кнопки «Setup»

Данный код создаёт агентов, которые называются «turtles». Строка set-default-shape turtles «circle» задаёт форму агентов. В данном случае форма была выбрана в виде кружка (circle). Функция create-turtles num создаёт такое количество агентов, которое было задано на «рычажке». Кроме того, можно задать начальные параметры для агентов. В данном случае был задан синий цвет и размер 2. Работа кнопки «setup» показана на рисунке 10.

...