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

Содержание

Введение

1. Анализ методов и средств моделирования мультиагентных схем

2. Разработка архитектуры лабораторного комплекса

3. Анализ и разработка моделей для выполнения лабораторных работ

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

5. Разработка и реализация программных модулей

5.1 Описание проводимого тестирования

5.2 Тестирование лабораторной работы «Climatechange»

5.3 Тестирование лабораторной работы «ElFarol»

5.4 Тестирование лабораторной работы «Pagerank»

6. Экспериментальное тестирование и отладка программного комплекса

6.1 Описание проводимого тестирования

6.2 Тестирование лабораторной работы «Climatechange»

6.3 Тестирование лабораторной работы «ElFarol»

6.4 Тестирование лабораторной работы «Pagerank»

6.5 Тестирование лабораторной работы «Turingmachine»

7. Разработка руководства пользователя

7.1 Лабораторная работа «Climatechange»

7.2 Лабораторная работа «ElFarol»

7.3 Лабораторная работа «Pagerank»

7.4 Лабораторная работа «Turingmachine»

8. Оценка качества разработанного программного продукта

Заключение

Список использованных источников

Введение

программный продукт моделирование мультиагентный

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

В действительности же за этим внешним всемогуществом скрываются чрезвычайно трудоемкие программные системы, которые по-прежнему требуют огромного рутинного труда системных аналитиков, руководителей проектов, программистов, тестировщиков программного кода, дизайнеров и многих других специалистов. Таким образом, возникает ситуация, когда информационные системы становятся огромными, труднопонимаемыми и трудномодифицируемыми, поглощающими значительные финансовые и интеллектуальные ресурсы, которые далеко не всегда обеспечивают нужный для заказчика результат. Выход из этой ситуации существует в направлении создания программно-информационных систем, наделенных свойствами разумности, гибкости и автономности, которые стали интенсивно исследоваться и развиваться в конце 20 века и получили название «Мультиагентные системы» [1].

Термин «агент» происходит от латинского глагола agree, что означает «действовать», «двигать», «править», «управлять». Также термин «агент» может означать деятеля или лицо, действующего по поручению или полномочию другого. Это определение правильно выражает суть и современных интеллектуальных компьютерных агентов, которые могут автономно функционировать от имени своего владельца (человека-пользователя или другой вычислительной системы) и решать самые разнообразные задачи по обработке информации. Для успешной работы агент должен обладать достаточными интеллектуальными ресурсами, чтобы в сфере своих задач замещать действия человека-владельца, должен иметь возможности взаимодействия с владельцем или пользователем для получения соответствующих знаний и передачи результатов, должен ориентироваться в среде своего существования и принимать необходимые решения [2].

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

1. Анализ методов и средств моделирования мультиагентных систем

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

Рассмотрим такую систему, как AgentBuilder. AgentBuilder - интегрированный набор инструментов для создания интеллектуальных программных агентов. Он состоит из двух основных компонентов: инструментария и системы времени выполнения. Набор инструментов AgentBuilder включает инструменты для управления процессом разработки программного обеспечения на основе агентов, анализа области операций с агентами, проектирования и разработки сетей агентов связи, определения поведения отдельных агентов, а также программного обеспечения для отладки и тестирования агентов. Система Run-Time включает механизм агента, который обеспечивает среду для выполнения программного обеспечения агента.

Агенты, созданные с помощью AgentBuilder, обмениваются данными с помощью языка запросов и манипуляции (KQML) и поддерживают функции, определенные для KQML [3]. Кроме того, AgentBuilder позволяет разработчику определять новые межагентные коммуникационные команды, соответствующие его конкретным потребностям.

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

Компоненты, существующие в программе: инструменты управления проектами, онтологический менеджер, менеджер агентства, менеджер агента и отладчик агента.

В общем, AgentBuilder позволяет разработчикам программного обеспечения без каких-либо знаний в интеллектуальных системах или технологиях интеллектуальных агентов быстро и легко создавать интеллектуальные приложения на основе агентов. AgentBuilder сокращает время разработки и затраты на разработку и упрощает разработку высокопроизводительных, надежных агентных систем [4].

Следующей рассмотрим такую систему как Cafun. Cafun - это программа, которая позволяет создавать симуляции сложных систем в простой форме.Cafun реализован на языке программирования Java, что позволяет ему работать в таких операционных системах, как Unix, Linux или Windows. Для запуска программы необходимо специальное программное обеспечение под названием Java Runtime Environment или JRE [5].

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

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

Cafun использует концепцию клеточных автоматов. Здесь выражение «вселенная» было заменено на «решетку», потому что оно представляет весь виртуальный мир, в котором происходит симуляция, и понятие «правило» было изменено на «мутацию», поскольку оно учитывает переход на другой тип ячейки. Cafun следует объектно-ориентированному подходу для описания законов клеточного автомата. Вместо того, чтобы ссылаться на таблицу правил, Cafun суммирует их в наборе типов ячеек, которые имеют отдельные мутации. Каждая ячейка во вселенной Cafun считается экземпляром такого типа клеток. Кроме того, Cafun позволяет типам клеток быть абстрактными. Типы абстрактных ячеек не могут быть созданы клетками, но они могут быть реализованы действительными типами ячеек, что делает их наследовать все их мутации. Это позволяет суммировать общие мутации разных типов клеток в один абстрактный тип ячейки. Кроме того, он делает ячейки полиморфными, поскольку они ведут себя как экземпляр их фактического типа ячейки, а также экземпляры абстрактных типов ячеек, которые он реализует. Этот вид полиморфизма особенно полезен при определении условий мутаций, поскольку он позволяет им ссылаться на абстрактные черты, разделяемые клетками разных типов клеток [6].

Также рассмотрим такую систему, как NetLogo. NetLogo- это кроссплатформенная программируемая среда для моделирования естественных и социальных явлений. Данная среда - это следующее поколение серии мультиагентных языков моделирования, включая StarLogo и StarLogoT. NetLogo работает на виртуальной машине Java, поэтому работает на всех основных платформах (Mac, Windows, Linux и др.). Он запускается как настольное приложение. Также поддерживается операция с командной строкой [7].

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

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

Также NetLogo имеет обширную документацию и учебные пособия. В нем имеется библиотека моделей, в которой содержится большой набор предварительно написанных симуляций. Эти симуляции касаются областей контента в естественных и социальных науках, включая биологию и медицину, физику и химию, математику и информатику, а также экономику и социальную психологию[8].

В NetLogoимеется удобный интерфейс с кнопками, рычажками, переключателями, выборщиками, текстовыми полями, заметками и выходной областью. Также существует вкладка «Информация» для аннотации модели форматированным текстом и изображениями. К тому же здесь используется инструмент BehaviorSpaceс открытым кодом для сбора данных из нескольких параллельных прогонов модели [9].

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

2. Разработка архитектуры лабораторного комплекса

Представим структурную схему и прямую сложности для комплекса лабораторных работ. Схема представлена на рисунке 2.1.

Рисунок 2.1 Структурная схема и прямая сложности

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

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

Требования для лабораторной работы «Climatechange». Для корректного запуска программы необходимо указать значение параметра sun-brightness,который отвечает за яркость солнца. Указать значение параметра albedo, который отвечает за отражающую способность поверхности, чем он выше, тем больше лучей отражаются от земли.

Ограничения для лабораторной работы «Climatechange». Значение параметра sun-brightnessдолжно быть в диапазоне от 0 до 5, и изменяться с шагом 0,1. Значение параметра albedoдолжно быть в диапазоне от 0 до 1, и изменяться с шагом 0,05. Также стоит иметь в виду, что температура в данной модели не может принимать отрицательные значения.

Вторая лабораторная работа называется «ElFarol». В данной лабораторной работе моделируется посещение бара ElFarol в NewMexico. Каждый четверг посетители данного бара решают идти им сегодня в бар или остаться дома. Данная модель входит в категорию SociealScience (социальная наука). Эта лабораторная работа служит для укрепления знаний в использовании инструментов NetLogo.

Требования для лабораторной работы «ElFarol». Для корректного запуска программы необходимо указать значение параметра memory-size, отвечающего за объем памяти посетителей. Также необходимо указать значение параметра number-strategies, отвечающего за количество стратегий. Следует указать значение параметра overcrowding-threshold, а также параметров qualityи the-number-of-police-visits.

Ограничения для лабораторной работы «ElFarol».Значение параметра memory-sizeдолжно быть в диапазоне от 1 до 10, и изменяться с шагом 1. Значение параметра number-strategiesдолжно быть в диапазоне от 1 до 20, и изменяться с шагом 1. Значение параметра overcrowding-thresholdдолжно быть в диапазоне от 0 до 100 и изменяться с шагом 1. Значение параметра qualityдолжно быть в диапазоне от 1 до 5, и изменяться с шагом 1.Значение параметра the-number-of-police-visits должно быть в диапазоне от 0 до 5 и изменяться с шагом 1. Также необходимо знать, что посещаемость в баре не может быть отрицательной. Значения, получаемые с помощью функции prediction-attendance, не должны быть равны тем числам, с которыми они сравниваются, иначе посетители не смогу решить, идти им в бар или же остаться дома.

Третья лабораторная работа называется «Pagerank». Данная лабораторная работа демонстрирует два различных агентно-ориентированных метода для расчета рангов взаимосвязанных веб-страниц. Задача модели - обеспечить более глубокое понимание алгоритма ранжирования и его математики.

Требования для лабораторной работы «Pagerank». Для корректного запуска программы необходимо указать значение параметра damping-factor, который отвечает за коэффициент дэмпфирования. Указать значение параметра number-of-surfers, который отвечает за количество ищущих. Также необходимо указать значения параметра count-pages, который отвечает за количество сайтов и count-links, который отвечает за количество связей между этими сайтами. Необходимо указать нужный метод поиска и иметь в виду, что рычажок number-of-surfersработает только при случайном методе. Также нужно указать, с каким типом сети вы будете работать. Модификации данной модели работают только с типом сети network-management.

Ограничения для лабораторной работы «Pagerank».Значение параметра dampfing-factorдолжно быть в диапазоне от 0 до 1, и изменяться с шагом 0,1. Значение параметра number-of-surfersдолжно быть в диапазоне от 1 до 100, и изменяться с шагом 1. Значение параметра count-pagesдолжно быть в диапазоне от 1 до 50 и изменяться с шагом 1. Значение параметра count-linksдолжно быть в диапазоне от 1 до 5, и изменяться с шагом 1.Значение параметра pr-pageне может быть меньше 0, потому что у страницы не может быть отрицательного рейтинга.

Четвертая лабораторная работа называется «Turingmachine». Данная лабораторная работа представляет собой модель многоголовой машины Тьюринга на двумерной ленте (2D MTM), которая является продолжением оригинальной машины, предложенной Тьюрингом в 1936 году.

Требования для лабораторной работы «Turingmachine». Для корректного запуска программы необходимо указать значение параметраheads, который отвечает за количество головок. На рычажке newheadstate и переключателе newcellstateнеобходимо задать состояния для головоки ячеек. В выпадающих списках turnнеобходимо выбрать направления для агентов.

Ограничения для лабораторной работы «Turingmachine».Значение параметра headsдолжно быть в диапазоне от 1 до 256, и изменяться с шагом 1. Значение параметра exampleдолжно быть в диапазоне от 1 до 5, и изменяться с шагом 1.В списке turnвозможно выбрать только одно из 4 направлений для агента. В рычажках newheadstateсостояние головки изменяется от 0 до 2 с шагом 1. В переключателях newcellstateячейки должны быть в состоянии onили off.

3. Анализ и разработка моделей для выполнения лабораторных работ

Первая модель, которую будем анализировать, называется «Climatechange».

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

Рисунок 3.1 Общий вид модели

В базовой модели представлены следующие кнопки. Кнопка setupсоздает модель, кнопкаgo запускает модель. Кнопки addcloud и removecloud создают и удаляют облака в модели. Кнопки addCO2 и remove CO2 создают и удаляют молекулы СО2. Кнопка watcharay показывает путь от солнечного луча до инфракрасного излучения. Параметр sunbrightness отвечает за яркость солнца, и чем ярче солнце, тем больше солнечных лучей попадает на землю. Albedo- параметр, отвечающий за отражающую способность поверхности земли, и чем он выше, тем больше солнечных лучей отражается от земли.

При нулевом значении параметра sunbrightnessтемпература остается неизменной. Это показано на рисунке 3.2.

Рисунок 3.2 Модель при значении sunbrightness, равном нулю

При максимальном значении albedoтемпература так же остается неизменной. Это обусловлено тем, что поверхность отражает все солнечные лучи, и, следовательно, температура не растет. Это показано на рисунке 3.3.

Рисунок 3.3 Модель при максимальном значении albedo

Добавление облаков в модель влияет на изменение температуры, так как облака не дают части солнечных лучей попасть на поверхность земли или же не дают им покинуть землю. На рисунках 3.4 и 3.5 показано влияние облаков на поведение модели.

Рисунок 3.4 Модель без облаков

Рисунок 3.5 Модель с облаками

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

При добавлении CO2 инфракрасное излучение не покидает поверхность земли, из-за чего температура сильно возрастает. Это показано на рисунке 3.6.

Рисунок 3.6 Модель с высоким содержанием СО2

Температура в данной модели высчитывается по формуле:

где countheats - количество тепла, полученное землей;

temperature - температура.

На параметр countheats влияетalbedo. Значение albedo, умноженное на 100, сравнивается со случайным числом. Если оно меньше, то солнечный луч оставляет инфракрасное излучение, а если больше, то отражается от поверхности земли. Если солнечных лучей много, то heatsсоздается при попадании луча в одну точку дважды.

Создание солнечных лучей происходит по формуле:

где sunbritness - яркость солнца.

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

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

Рисунок 3.7 Общий вид модифицированной модели

Следующая модель для анализа называется «ElFarol».

El Farol -- это модель, которая моделирует посещение бара ElFarol в NewMexico. Бар пользуется популярностью - особенно в четверг вечером, когда они предлагают ирландскую музыку, но иногда становится переполненным и неприятным.Каждый четверг посетители данного бара решают идти им сегодня в бар или остаться дома[10]. Данная модель входит в категорию SociealScience (социальная наука).

Данный выбор они делают на основе своего предыдущего опыта. Их выбор зависит от количества посетителей бара, которое было в предыдущие разы его посещения.

Общий вид базовой модели представлен на рисунке 3.8.

Рисунок 3.8 Общий вид базовой модели «ElFarol»

В базовой модели имеется несколько видов рычажков.

Рычажок memory-sizeотвечает за размер памяти посетителей, которая представляется массивом чисел, где каждый элемент - это количество посетителей в баре в определённый раз посещения. Размер памяти равен количеству элементов массива.

Рычажок number-strategiesопределяет количество стратегий, которыми руководствуются посетители бара, когда выбирают, идти им в бар или нет. Если это число меньше или равно параметру overcrowding-threshold, то человек идет в бар.

Overcrowding-threshold - параметр, который является ограничением. Как было сказано ранее, если число, полученное в результате выполнения стратегии меньше или равно данному параметру, то человек идёт в бар

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

Для модификации модели добавим ещё два параметра: «Качество» и «Полиция».

В параметре «Качество» учитывается качество обслуживания в баре, качество алкоголя и еды. Данный фактор является одним из ключевых в принятии решения идти в бар или нет. Представим данный параметр в виде рычажка quality, значения в котором будут меняться в диапазоне от 1 до 5 с шагом 1. Рычажок quality представлен на рисунке 3.9.

Рисунок 3.9 Рычажок quality

У каждого бара есть свой определенный стандарт качества. Данный стандарт сравнивается с качеством заведения ElFarol. Если данное качество не удовлетворяет стандарту клиента, то он остается дома.

Параметр «Полиция» представляет из себя значение, равное количеству визитов полицейскими данного заведения. Представим этот параметр так же в виде рычажка the-number-of-police-visits, значения в котором будут меняться в диапазоне от 1 до 5 с шагом 1. Рычажок the-number-of-police-visits представлен на рисунке 3.10.

Рисунок 3.10 Рычажокthe-number-of-police-visits

Для визуализации влияния факторов на выбор клиента добавим график. На этом графике будет отображаться, какое количество клиентов потеряно в результате влияния параметров «Качество» и «Полиция». Данный график представлен на рисунке 3.11.

Рисунок 3.11 График quanlityprediction

Общий вид модернизированной модели представлен на рисунке 3.12.

Рисунок 3.12 Общий вид модернизированной модели

Третья модель, которую будем анализировать, называется «Pagerank».

Эта модель демонстрирует два различных агентно-ориентированных метода для расчета рангов взаимосвязанных веб-страниц. Задача модели - обеспечить более глубокое понимание алгоритма ранжирования и его математики. Общий вид модели представлен на рисунке 3.13.

Рисунок 3.13 Общий вид модели

В базовой модели имеется несколько видов переключателей и рычажков. Переключатель network-choiceпозволяет выбрать сеть, которую можно будет использовать для моделирования. Рычажок damping-factorпоказывает, как значения ранга влияют на ссылочную структуру. Рычажок number-of-surfersотвечает за количество пользователей, которые будут осуществлять переходы между сайтами по ссылкам. Работает только при случайном методе поиска. Переключатель watch-surfersпозволяет включить или выключить наблюдение за перемещениями пользователей. Переключатель show-page-ranksпозволяет включить или выключить показ числового ранга в модели. Переключатель calculation-methodпозволяет выбрать один из двух методов поиска: случайный или диффузионный.

Вычисление ранга страницы происходит по формуле:

где PR - ранг рассматриваемой страницы;

d-коэффициент затухания (означает вероятность того, что пользователь, зашедший на страницу, перейдет по одной из ссылок, содержащейся на этой странице, а не прекратит путешествие по сети);

PR_i-ранг i-ой страницы, ссылающейся на рассматриваемую страницу;

C_i- общее число ссылок на i-ой странице.

Модифицируем данную модель. В базовой модели имеется всего три типа сети. Нас интересует третий тип, именно его и используем для модификации и сделаем ещё один тип. В базовой модели он реализуется с помощью функции create-network-preferential [ nk]. Данная функция принимает два параметра. Первый отвечает за количество создаваемых страниц, а второй за количество ссылок на сайтах, но эти параметры заданы в программе и никак не изменяются. Отсюда можно сделать вывод, что есть возможность реализовать функцию, которая позволит управлять количеством сайтов и связей между ними. Для этого в модель добавим два новых рычажка:count-pages и count-links. Они представлены на рисунке 3.14.

Рисунок 3.14 Count-pagesиcount-links

Также реализуем возможность управлять первоначальным значением рейтинга страниц. Для этого создадим переключатель pr-control, который будет отвечать за возможность управлять рейтингом, а также создадим рычажок pr-page, который будет отвечать за первоначальное значение рейтинга. Если переключатель pr-controlвключен, то ранг устанавливается в зависимости от значения рычажка pr-page, в противном случае ранг страниц определяется по стандартной формуле. Эти элементы представлены на рисунке 3.15.

Рисунок 3.15 Pr-controlиpr-page

Общий вид модифицированной модели представлен на рисунке 3.16.

Рисунок 3.16 Общий вид модифицированной модели

Следующая модель для анализа называется «TuringMachine».

Это модель многоголовой машины Тьюринга на двумерной ленте (2D MTM), которая является продолжением оригинальной машины, предложенной Тьюрингом в 1936 году.

Машина Тьюринга - простая вычислительная машина, способная делать все, что может сделать современный компьютер. Традиционная машина Тьюринга имеет один процессор или «головку» с ограниченным числом внутренних состояний, которые изменяются в зависимости от данных, которые считывает голова. Когда машина Тьюринга вычисляет, голова движется вперед и назад по ленте, меняя ее внутреннее состояние и значение текущей ячейки [11].

Многоголовую машину Тьюринга на двумерной ленте (2D MTM) можно эмулировать на одноглавой одномерной машине Тьюринга (TM), но правила 2D MTM могут быть значительно проще, чем правила традиционной ТМ, имитирующей 2D MTM. В модели может быть до 256 «головок», которые следуют одному и тому же набору основных правил. В этом двухмерном 2D MTM голова может изменять свое состояние, значение его текущей ячейки и перемещаться либо на север, на восток, на запад, либо на юг, в зависимости от того, включена или выключена текущая ячейка и ее текущее состояние.

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

Общий вид базовой модели представлен на рисунке 3.17.

Рисунок 3.17 Общий вид базовой модели

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

Рычажок headsпозволяет выбрать количество головок машины Тьюринга.

Переключатель color-pathsпозволяет выбрать, будут ли агенты белыми или разноцветными.

Рычажок newheadstateзадает новое состояние головки машины Тьюринга. Переключатель newcellstateзадает новое состояние ячейки. В выпадающем списке turnвыбирается в каком направлении повернется агент.

Кнопка setupexampleустанавливает параметры модели, заданные в различных примерах, которые можно выбрать, передвигая ползунок example. В модели всего пять примеров.Также специально для модифицированной модели были разработаны две модели, которые были заданы вместо предустановленных примеров 1 и 2.

Общий вид модернизированной модели представлен на рисунке 3.18.

Рисунок 3.18 Общий вид модернизированной модели

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

В лабораторной работе «Climatechange» используются различные алгоритмы движения объектов в пространстве. Главным является алгоритм движения солнечного луча. Его поведение зависит от выбранных начальных параметров модели, а также от объектов, размещенных в этой модели. Блок-схема для алгоритма движения солнечного луча представлена на рисунке 4.1.

Рисунок 4.1 Алгоритм движения луча солнца

Также важным является алгоритм движения инфракрасного излучения. На его поведение влияют те же объекты, что и на движение солнечного луча. Блок-схема для алгоритма движения инфракрасного излучения представлена на рисунке 4.2.

Рисунок 4.2 Алгоритм движения инфракрасного излучения

В лабораторной работе «ElFarol» главным является алгоритм решения о посещении бара. На это решение влияют значенияустановленных внешних параметров. Решение производится на основе сравнения случайных чисел с числами, установленными на внешних параметрах. Блок-схема для алгоритма решения о посещении бара представлена на рисунке 4.3.



Рисунок 4.3 Алгоритм решения о посещении бара

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

Рисунок 4.3 Алгоритм решения о посещении бара

5. Разработка и реализация программных модулей

5.1 Процедуры и функции для «Climatechange»

Рассмотрим процедуры и функции, используемые в модели для лабораторной работы «Climatechange».

В при помощи оператора globalsопределяются глобальные переменные. Рассмотрим объявленные переменные и их значения.

Sky-top - определяет координату верхней точки неба. Earth-top - определяет координату верхней точки земли. Temperature - общая температура.

Далее с помощью оператора breed задается несколько подмножеств. Breed [ raysray ] - множество солнечных лучей, breed [ IRsIR ] - множество инфракрасного излучения, breed [heats heat] - множество тепловой энергии, breed [CO2s CO2] - множество углекислого газа, breed [trees tree] - множество деревьев, breed [factories factory] - множество фабрик, breed [clouds cloud] - множество облаков. Фрагмент кода с объявлением переменных представлен ниже.

globals [

sky-top

earth-top

temperature

]

breed [rays ray]

breed [IRs IR]

breed [heats heat]

breed [CO2s CO2]

breed [trees tree]

breed [factories factory]

breed [clouds cloud]

clouds-own [cloud-speed cloud-id]

Далее идут процедуры setup и setup-world. В этих процедурах устанавливается цвет ландшафта в зависимости от координаты на плоскости. Также здесь задаются изображения различных объектов модели, и указывается начальное значение температуры. Коды процедур setupи setup-worldпредставлены ниже.

to setup

clear-all

set-default-shape rays "ray"

set-default-shape IRs "ray"

set-default-shape clouds "cloud"

set-default-shape heats "dot"

set-default-shape CO2s "CO2-molecule"

set-default-shape factories "factory"

set-default-shape trees "tree"

setup-world

set temperature 12

reset-ticks

end

to setup-world

set sky-top max-pycor - 5

setearth-top 0

askpatches [ ;; установление цветов для разных разделов мира

if pycor > sky-top [

set pcolor scale-color white pycor 22 15

]

if pycor <= sky-top and pycor > earth-top [ ;; небо

set pcolor scale-color blue pycor -20 20

]

if pycor < earth-top

[ set pcolor red + 3 ] ;; земля

if pycor = earth-top ;; поверхностьземли

[ update-albedo ]

]

End

Затем идет процедура go, в которой выполняется модель. В ней определяется, какой из элементов модели должен появиться в данный момент времени. Код процедуры go с пояснениями представлен ниже.

togo

askclouds [ fdcloud-speed ] ; облакаперемещаютсявдоль

run-sunshine ;; луч выходит

;; если альбедо изменил цвет пятен земляной поверхности

ask patches with [pycor = earth-top]

[ update-albedo ]

run-heat ;; выделениетепла

run-IR ;; выделение инфракрасного излучения

run-CO2 ;; движение молекул СО2

tick

end

Далее идет процедура add-cloud. В это процедуре описывается появление облаков в модели. Здесь определяется то, в какой точке пространства появится облако, его размер, скорость и цвет. Ниже представлен код процедуры add-cloud с пояснениями.

toadd-cloud ;; стирает облака, а затем создаются новые

let sky-height sky-top - earth-top

;; находится случайная высота облака в области неба

let y earth-top + (random-float (sky-height - 4)) + 2

;; скорость облака не может быть нулем

let speed (random-float 0.1) + 0.01

let x random-xcor

let id 0

if any? clouds

[ set id max [cloud-id] of clouds + 1 ]

create-clouds 3 + random 20

[

set cloud-speed speed

set cloud-id id

setxyx + random 9 - 4

;; облака группируются вокруг центра

y + 2.5 + random-float 2 - random-float 2

setcolorwhite

;; разный размер облаков

set size 2 + random 2

set heading 90

]

End

Затем идут процедуры run-sunshine, create-sunshine, reflect-rays-from-clouds иencounter-earth. В этих процедурах создается луч солнца, описывается его поведение во время соприкосновения с препятствиями. Коды этих процедур с пояснениями представлены ниже.

torun-sunshine

askrays [

if not can-move? 0.3 [ die ]

fd 0.3

]

create-sunshine ;; созданиелуча

reflect-rays-from-clouds ;; проверка соприкосновения с облаками

encounter-earth ;; проверка соприкосновения с землей

end

tocreate-sunshine

;; увеличение яркости увеличивает количество лучей

if 10 * sun-brightness>random 50 [

create-rays 1 [

set heading 160

set color yellow

setxy (random 10) + min-pxcor max-pycor

]

]

end

to reflect-rays-from-clouds

ask rays with [any? clouds-here] [ ;; еслилучкасаетсяоблака

set heading 180 - heading ;; лучразворачивается

]

end

to encounter-earth

ask rays with [ycor <= earth-top] [

;; в зависимости от альбедо земля поглощает или отражает тепло

ifelse 100 * albedo > random 100

[ set heading 180 - heading ] ;; отражение

[ rt random 45 - random 45 ;; поглощение

set color red - 2 + random 4

setbreedheats ]

]

End

Следующей идет процедуры run-heat и run-IR, в которых идет расчет показателей температуры, описываются движения лучей и инфракрасного излучения. Коды этих процедур представлены ниже.

to run-heat ;; advances the heat energy turtles

set temperature 0.99 * temperature + 0.01 * (12 + 0.1 * count heats)

ask heats

[

let dist 0.5 * random-float 1

ifelse can-move? dist

[ fd dist ]

[ set heading 180 - heading ]

if ycor >= earth-top [ ;; отражениелучалуча

ifelse temperature > 20 + random 40

and xcor > 0 and xcor < max-pxcor - 8

[ set breed IRs

set heading 20

set color magenta ]

[ set heading 100 + random 160 ]

]

]

end

to run-IR

ask IRs [

if not can-move? 0.3 [ die ]

fd 0.3

if ycor <= earth-top [

set breed heats

rt random 45

lt random 45

set color red - 2 + random 4

]

ifany? CO2s-here ;; проверяется соприкосновение с СО2

[ set heading 180 - heading ]

]

End

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

5.2 Процедуры и функции для «ElFarol»

Процедуры и функции, используемые в модели для лабораторной работы «ElFarol».

В начале кода при помощи оператора globalsопределяются глобальные переменные. Рассмотрим объявленные переменные и их значения.

Attendance - текущее количество посетителей бара. History - история посетителей бара или список значений параметра attendance. Home-patches - это пятна, обозначающие дома посетителей бара. Bar-patches - это пятна, показывающие бар. Crowded-patch - пятна, где идет отображение того, что бар переполнен.

При помощи оператора turtles-own задаются атрибуты или переменные только для черепах. Рассмотрим эти переменные.

Strategies - список стратегий. Beststrategy - индекс текущей стратегии. Attend - означает положительный или отрицательный ответ на решение пойти в бар. Переменная может принимать значение trueили false. Prediction - предсказание о текущем количестве человек в баре. Ниже представлен фрагмент кода с объявлением переменных.

globals [

attendance

history

home-patches

bar-patches

crowded-patch

quality-prediction

police-prediction

]

turtles-own [

strategies

best-strategy

attend?

quality-attend?

opponent-attend?

prediction

quality-counter

police-number

police-attend?

]

Далее в модели идет процедур аsetup. Она вызывается кнопкой setup. Данная процедура отображает и выбирает пятна для бара(barpatches) и пятна для домов (home-patches) в зависимости от места, занимаемого пятном на координатной плоскости. Также здесь генерируется начальная история (переменная history) и происходит создание и размещение черепах. У каждой черепахи генерируется стратегия и выбирается текущая стратегия, как первый элемент массива стратегии. Ниже представлен код для процедуры setup с пояснениями.

tosetup

clear-all

set-default-shape turtles "person"

;; создание «домов»

set home-patches patches with [(pycor < -8 or pxcor < -8) or (pycor > 11) or pxcor > 11]

ask home-patches [ set pcolor green ]

;; создание «бара»

set bar-patches patches with [pxcor > -8 and pycor > -8 and pxcor < 11 and pycor < 11]

ask bar-patches [ set pcolor magenta ]

;; инициализацияпредыдущейпосещаемостислучайнымспособом

set history n-values (memory-size * 2) [random 100]

;; помнить, что история в два раза больше памяти

setattendancefirsthistory

;; Используется одна из меток, чтобы визуально указать, является ли панель «переполненной»

ask patch (0.75 * max-pxcor) (0.5 * max-pycor) [

set crowded-patch self

set plabel-color red

]

;; создание агентов и присваивание им случайных стратегий

create-turtles 100 [

set color white

move-to-empty-one-of home-patches

set strategies n-values number-strategies [random-strategy]

set best-strategy first strategies

set quality-counter random 6

set police-number random 6

update-strategies

]

reset-ticks

end

Далее идет процедура go. Она вызывается кнопкой go. В данной процедуре при помощи функции prediction-attendance получаем числа prediction, quality-counterиpolice-number. Значение prediction сравнивается со значением overcrowding-threshold, quality-counter сравнивается с quality, аpolice-number сравнивается с the-number-of-police-visits. Если значения меньше, то количеству посетителей прибавляется один. Ниже представлен код для процедуры go с пояснениями.

to go

ask crowded-patch [ set plabel "" ]

;; каждый агент предсказывает посещаемость в баре и решает, идти или нет

ask turtles [

set prediction predict-attendance best-strategy sublist history 0 memory-size

set attend? (prediction <= overcrowding-threshold) ;; true или false

set quality-attend? (quality-counter <= quality)

set police-attend? (police-number >= the-number-of-police-visits)

]

;; в зависимости от их решения, агенты отправляются в бар или остаются дома

set quality-prediction 0

set police-prediction 0

ask turtles [

ifelse (attend? and quality-attend? and police-attend?)

[ move-to-empty-one-of bar-patches

set attendance attendance + 1

]

[ move-to-empty-one-of home-patches ]

ifelse (attend?) [

ifelse(quality-attend?) []

[ set quality-prediction quality-prediction + 1 ]

ifelse(police-attend?) []

[ set police-prediction police-prediction + 1 ]

] []

]

;; если бар переполнен, то это показывается

set attendance count turtles-on bar-patches

;; обновляется история посещаемости, удаляется старая посещаемость и приводится последняя посещаемость

set history fput attendance but-last history

;; агент определяет лучшую стратегию для себя

ask turtles [ update-strategies ]

tick

end

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

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

to update-strategies

let best-score memory-size * 100 + 1

foreach strategies [

let score 0

let week 1

repeat memory-size [

set prediction predict-attendance ? sublist history week (week + memory-size)

set score score + abs (item (week - 1) history - prediction)

set week week + 1

]

if (score <= best-score) [

set best-score score

setbest-strategy ?

]

]

End

Функция random-strategy сообщает о случайной стратегии. Стратегия - это всего лишь набор весов от -2,0 до 1,0, который определяет, сколько внимания уделяется каждому предыдущему периоду времени при прогнозировании посещаемости на следующий период времени. Ниже представлен код функции.

to-report random-strategy

report n-values (memory-size + 1) [1.0 - random-float 2.0]

end

Функция predict-attendance сообщает прогноз агента о текущей посещаемости, используя определенную стратегию и часть истории посещаемости.

Затем описывается формулой:

где P(t) - предсказание в момент времени t;

x(t) - посещаемость бара в момент времени t;

A(t) - вес для времени t;

c - константа;

memorysize - внешний параметр.

Ниже представлен код функции.

to-report predict-attendance [strategy subhistory]

report 100 * first strategy + sum (map [?1 * ?2] butfirst strategy subhistory)

end

Функцияmove-to-empty-one-ofиспользуется для того, чтобы у нас была только одна черепаха на пятно. Ниже представлен код функции.

to move-to-empty-one-of [locations] ;; turtle procedure

move-to one-of locations

while [any? other turtles-here] [

move-to one-of locations

]

End

5.3 Процедуры и функции для «Pagerank»

Процедуры и функции, используемые в модели для лабораторной работы «Pagerank».

В начале кода с помощью оператора breed задается два подмножества: breed [ pages page ] - множество страниц, breed [ surferssurfer ] - множество ищущих.

Далее идет процедура setup. В ней происходит определение того, какой тип структуры сети был выбран, установка ранга сайтам, и размещение сайтов на экране.

Код для выбора типа сети.

to setup

clear-all

set-default-shape pages "circle"

ifelse network-choice = "Example 1"

[ create-network-example-1 ][

ifelse network-choice = "Example 2"

[ create-network-example-2 ][

ifelse network-choice = "Preferential Attachment"

[ create-network-preferential 100 2 ] [

ifelse network-choice = "Network management"

[ pr-man count-pages count-links ];

Также в процедуру setupбыло внесено дополнение, а именно в управление страницами. Изменение представлено ниже.

ask pages

[ ifelse pr-control [ set rank pr-page] [set rank 1 / count pages] ]

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

Далее идут функции create-network-example-1, create-network-example-2, create-network-preferential [ n k ] и pr-man [ n k ]. С помощью этих функций строится модель сети. Функции create-network-preferential [ nk ] иpr-man [ nk ] принимают два параметра. Первый отвечает за количество создаваемых страниц, а второй за количество ссылок на сайтах. Отличие этих двух функций в том, что параметры для create-network-preferential [ nk ] заданы в программе, а для pr-man [ nk ] эти параметры можно изменять в самой модели. Ниже представлен коды этих функций.

to create-network-example-1

create-pages 11

ask page 0 [ set color blue create-link-from page 3 ]

ask page 1 [ set color red create-links-from (turtle-set page 2 page 3 page 4 page 5 page 6 page 7 page 8 ) ]

ask page 2 [ set color orange create-link-from page 1 ]

ask page 3 [ set color green create-link-from page 4 ]

ask page 4 [ set color yellow create-links-from (turtle-set page 5 page 6 page 7 page 8 page 9 page 10) ]

ask page 5 [ set color green create-link-from page 4 ]

ask pages with [who > 5] [ set color violet ]

end

to create-network-example-2

create-pages 8

ask page 0 [ die ]

ask page 1 [ create-links-from (turtle-set page 2 page 3 page 5 page 6) ]

ask page 2 [ create-links-from (turtle-set page 1 page 3 page 4) ]

ask page 3 [ create-links-from (turtle-set page 1 page 4 page 5) ]

ask page 4 [ create-links-from (turtle-set page 1 page 5) ]

ask page 5 [ create-links-from (turtle-set page 1 page 4 page 6 page 7) ]

ask page 6 [ create-links-from (turtle-set page 5) ]

ask page 7 [ create-links-from (turtle-set page 1) ]

end

to create-network-preferential [ n k ]

create-pages n [ set color sky ]

link-preferentially pages k

end

to pr-man [ n k ]

create-pages n [ set color sky ]

ifelse k >= n [ link-preferentially pages n - 1 ] [ link-preferentially pages k ]

end

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

Код для диффузионного типа.

ifelse calculation-method = "diffusion"

[ifany? surfers [ asksurfers [ die ] ] ;; удаляетпользователей, есливыбранданныйметод

ask links [ set color gray set thickness 0 ]

ask pages [ set new-rank 0 ]

ask pages

[

ifelse any? out-link-neighbors

[

let rank-increment rank / count out-link-neighbors

ask out-link-neighbors [

set new-rank new-rank + rank-increment

]

]

[

let rank-increment rank / count pages

ask pages [

set new-rank new-rank + rank-increment

]

]

]

ask pages

[

set rank (1 - damping-factor) / count pages + damping-factor * new-rank

;; устанавливает текущий ранг в новый ранг, используя данную формулу

]

Код для случайного типа.

[

if count surfers < number-of-surfers

[

create-surfers number-of-surfers - count surfers

[

set current-page one-of pages

ifelse watch-surfers?

[ move-surfer ]

[ hide-turtle ]

]

]

if count surfers > number-of-surfers

[

ask n-of (count surfers - number-of-surfers) surfers

[ die ]

]

;; возвращает связи в их начальное положение

ask links [ set color gray set thickness 0 ]

ask surfers [

let old-page current-page

askcurrent-page [ setvisitsvisits + 1 ] ;; увеличивает количество посещений на странице, на которой находимся

ifelse random-float 1.0 <= damping-factor and any? [my-out-links] ofcurrent-page;;с вероятностью, зависящей от коэффициента затухания, либо перейти на случайную страницу или случайную страницу, с которой эта страница связана

[ set current-page one-of [out-link-neighbors] of current-page ]

[ set current-page one-of pages ]

;; обновляемвизуализацию

ifelse watch-surfers?

[

show-turtle

move-surfer

let surfer-color color

ask old-page [

let traveled-link out-link-to [current-page] of myself

if traveled-link != nobody [

ask traveled-link [ set color surfer-color set thickness 0.08 ]]]

]

[ hide-turtle ]

]

;; обновляемрангстраниц

let total-visits sum [visits] of pages

ask pages [

set rank visits / total-visits

]

]

5.4 Процедуры и функции для «Turingmachine»

Рассмотрим процедуры и функции, используемые в модели для лабораторной работы «Turingmachine».

Сначала идет процедура setup. В этой процедуре определяется начальное состояние модели в соответствии с заданными параметрами. Код данной процедуры с пояснениями представлен ниже.

tosetup

clear-all

create-turtles heads [

setsize 5

setstate 0 ;; инициализация всех головок в состоянии 0

setheading 0

fdwho ;; выставление головок в вертикальное состояние

set bg black

ifelse color-paths? ;; цветчерепах

[ set fg color ]

[ set fg white ]

]

ask patches [ set on? false ] ;; очищениезначенияячейки

reset-ticks

end

Далее идет процедура go, в которой происходит запуск модели.

Затем идет процедура find-rule. В данной процедуре происходит нахождение правила использования для текущего состояния головки и ячейки. Ниже представлен код этой процедуры.

to-reportfind-rule

ifelseon? ;; проверка состояния пят на

[

if state = 0 [ report fput on-0-state list (direction-to-number on-0-turn) on-0-on? ]

if state = 1 [ report fput on-1-state list (direction-to-number on-1-turn) on-1-on? ]

if state = 2 [ report fput on-2-state list (direction-to-number on-2-turn) on-2-on? ]

]

[

if state = 0 [ report fput off-0-state list (direction-to-number off-0-turn) off-0-on? ]

if state = 1 [ report fput off-1-state list (direction-to-number off-1-turn) off-1-on? ]

if state = 2 [ report fput off-2-state list (direction-to-number off-2-turn) off-2-on? ]

]

End

В процедуре apply-rulesизменение текущей конфигурации по правилам, приведенным в списке.

В процедурах direction-to-numberиnumber-to-direction происходит изменение параметров модели в зависимости от выбранного пункта в списке turn. Ниже представлен код этих процедур.

to-report direction-to-number [direction]

if direction = "--"

[ report 0 ]

if direction = "Right"

[ report 90 ]

if direction = "Backwards"

[ report 180 ]

if direction = "Left"

[ report 270 ]

end

to-report number-to-direction [number]

if number = 0

[ report "--" ]

if number = 90

[ report "Right" ]

if number = 180

[ report "Backwards" ]

if number = 270

[ report "Left" ]

end

6. Экспериментальное тестирование и отладка программного комплекса

6.1 Описание проводимого тестирования

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

6.2 Тестирование лабораторной работы «Climatechange»

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

Для проведения первого теста запустим модель два раза. В первый раз не будем добавлять фабрики, а во второй раз запустим модель с теми же параметрами, но добавим пять фабрик. Результат тестирования представлен на рисунках 6.1 и 6.2.



Рисунок 6.1 Модель без фабрик

Рисунок 6.2 Модель с фабриками

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

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



Рисунок 6.3 Добавление деревьев

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

Для третьего теста создадим модель облачного дня, когда часть солнечных лучей будет задерживаться в атмосфере облаками. Проведем три опыта. Сначала создадим модель облачного дня без фабрик и деревьев, затем добавим в модель фабрики. В последнем опыте добавим ко всему этому деревья. Результат тестирования представлен на рисунках 6.4, 6.5 и 6.6.