Модернизация программы агентно-ориентированного моделирования 'Лабиринт агентов'
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
. АНАЛИЗ АЛГОРИТМОВ И ПРОГРАММНЫХ
РЕАЛИЗАЦИЙ ПОВДЕНИЯ АГЕНТОВ В ДВУМЕРНОЙ СРЕДЕ
1.1 Анализ алгоритмов и программных
реализаций
2. РАЗРАБОТКА АРХИТЕКТУРЫ ПРОГРАММНОГО КОМПЛЕКСА “ЛАБИРИНТ
АГЕНТОВ”
3. РАЗРАБОТКА СТРУКТУР ДАННЫХ И ЗНАНИЙ ДЛЯ “ЛАБИРИНТ АГЕНТОВ”
. РАЗРАБОТКА АЛГОРИТМОВ
4.1 Вертикальный поиск
.2 Горизонтальный поиск
.3 Диагональный поиск
.4 Поиск по спирали (одновременно)
.5 Поиск по спирали (последовательно)
.6 Алгоритм индивидуальной базы
знаний
5. РАЗРАБОТКА И РЕАЛИЗАЦИЯ ПРОГРАММНЫХ МОДУЛЕЙ
5.1 Болото
.2 Горы
.3 Интерфейс
.4 Карта лабиринта
6. ЭКСПЕРИМЕНТАЛЬНОЕ ТЕСТИРОВАНИЕ И ОТЛАДКА ПРОГРАММНЫХ МОДУЛЕЙ
6.1 Оценка надежности ПС
.2 Экспериментальное тестирование ПС
.3 Руководство пользователя
7. ОЦЕНКА КАЧЕСТВА РАЗРАБАТЫВАЕМОГО ПРОДУКТА
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ВВЕДЕНИЕ
В настоящее время существует большое количество информации, по различным
темам, среди которой пользователь ищет необходимую ему информацию, и с каждым
днем количество информации растет и растет. Уже сейчас современный человек за
месяц получает столько информации, сколько человек 17 века за всю жизнь. Каждый
день появляются все новые источники информации. Пользователю приходится одному
перерабатывать огромное количество информации, которой порой такое количество,
что в одиночку он не справляется. Здесь нам на помощь и приходят агенты,
которые помогают, пользователям в обработке информации.
Агент - это программа, самостоятельно выполняющая задание, которое
пользователь указал для выполнения, в период длительного промежутка времени,
они помогают пользователю с поиском или же сбором информации, анализом данных.
К интеллектуальным агентам могут относиться боты, компьютерные вирусы,
поисковые системы - это все относиться к интеллектуальным агентам. Агенты могут
выполнять различные действия и добиваться различных целей, в зависимости от
требования пользователя. Они могут искать нужную информацию или же собирать ее
и передавать пользователю для отчетности, или же проводить анализ данных.
Простой пример, это агент, который помогает пользователю найти самый дешевый
номер в отеле, пользователь указывает агенту страну, и нужный ему отель, а все
последующие функции выполняет сам агент, он прочесывает сайты в поиске самого
дешевого номера в отеле, всю информацию которую агент найдет, он предоставит
пользователю в виде отчета об успехах поиска.
В выпускной квалификационной работе, была модернизирована программа для 4
курса в рамках лабораторной работы “Лабиринт Агентов”. Эта программа использует
агентно-ориентированное моделирование. Есть некий лабиринт, в котором агенту
необходимо найти золото, следуя одному из видов поисков, которые включают в
себя (вертикальный поиск, горизонтальный поиск, диагональный поиск, поиск по
спирали одновременный, поиск по спирали последовательный), но лабиринт заполнен
препятствиями, которые мешают агенту найти золото, поэтому в зависимости от
поиска и занятости поля препятствиями, агент тратит различное время на поиски
золота. После выполнения всех экспериментов, данные собранные агентом выводятся
в виде отчета.
Выпускная квалификационная работа состоит из семи пунктов. В первом
разделе описаны алгоритмы и программные реализации программы “Лабиринт
агентов”. Во втором разделе описана архитектура программного комплекса. В
третьем разделе описаны структуры данных программы. В четвертом разделе описаны
алгоритмы программы “Лабиринт агентов”. В пятом разделе описаны разработанные
модули для программы. В шестом разделе описано экспериментальное тестирование.
В седьмом разделе описана оценка качества разработанного продукта.
1. АНАЛИЗ АЛГОРИТМОВ И ПРОГРАММНЫХ РЕАЛИЗАЦИЙ ПОВДЕНИЯ АГЕНТОВ В ДВУМЕРНОЙ
СРЕДЕ
Помощь агентов для решения каких-либо задач используется давно, суть
задач всегда остается одной и той же, меняется только ее формулировка и среда,
в которой агент должен решить стоящую перед ним задачу.
Задачи по исследованию поведения агентов в двумерной среде известны давно
и имеют множество интерпретаций. К примеру, таких как “Охота на индейку” или
“Обезьяна и банан”. Эти задачи описал в своей книге “Системы искусственного
интеллекта” Девятков В.В. [1]
Задача “Охота на индейку”
Суть задачи звучит следующим образом: есть поле в котором находятся
индейки и есть охотник, которому необходимо выстрелить в индейку, но, чтобы
сделать выстрел ему сначала необходимо зарядить ружье, при зарядке ружья затвор
издает звук, который могут услышать индейки и спрятаться от охотника. Индейки
бывают двух типов глухие, которые не слышат затвора ружья, и не глухие, которые
при звуке затвора прячутся. Цель проста, если охотник сначала пройдет по полю,
зарядит ружье и совершит выстрел, то попадет в глухую индейку, но если индейка
не будет глухая, останется ли она в живых?
Задача “Обезьяна и банан”
В комнате находится обезьяна, так же в комнате подвешен банан, до
которого обезьяна не может дотянуться. У окна в комнате всегда стоит ящик,
пододвинув который под банан, обезьяна может схватить банан. Точка появления
обезьяны различна, она может находиться у окна, рядом с ящиком, у двери, под
бананом и на ящике. Обезьяна может двигать ящик, к банану, к окну или от окна,
к двери, так же обезьяна может залезать на ящик и слезать, вопрос данной задачи
следующий, будет ли банан схвачен?
Агентов так же используют и в современных играх. Они представляют собой
искусственный интеллект, который либо помогает пользователю, либо мешает
проходить уровни. В зависимости от действий пользователя в окружающей его
среде, агенты начинают себя вести по-разному, в зависимости от того как
пользователь влияет на окружающую среду или же самих агентов.
Как пример можно привести игру шахматы, где пользователь играет против
компьютера или же агента. Агент знает множество ходов и комбинаций, и в
зависимости от действий пользователя, то есть от его ходов, агент будет
по-разному реагировать, увидев ходы пользователя, агент будет ходить
основываясь на них или же выявит закономерность ходов и сходит наперед.
Так же агентов используют в симуляции каких-либо процессов. В зависимости
от описанной среды, в которой находятся агенты и их поведения можно создать
симуляцию почти чего угодно. Каких-либо физических законов, лишь описав среду и
приписав агентам поведение частиц в этой среде в зависимости от того, что
происходит в окружающей их среде. Так же агентов можно использовать для
социальных экспериментов.
Программа NetLogo программа
мульти-агентного моделирования. Данная программа позволяет работать с
разнообразными моделями, в которых используются агенты. В библиотеках данной
программы содержаться тысячи моделей на основе поведения агентов в окружающей
среде. Данные модели позволяют лучше понять те или иные аспекты реальных
моделей, используя только поведение агентов. Как уже было сказано программа
содержит огромное количество готовых моделей для изучения, и во всех них
используются агенты, для решения тех или иных задач.
Данная модель давно известна и представляет собой модель Хищник-Жертва.
На поле находятся овцы, которые свободно перемещаются по полю и едят травку,
так же на поле находится несколько волков, которые ищут овец и едят их, если
волк не находит овцу за определенное количество ходов, то он умирает, если же
находит, то у него появляются силы и он размножается. Данная модель позволяет
изучить при каком количестве овец и волков возможно совместное сосуществование,
и при каких полная гибель того или иного вида, так же есть вариант гибели сразу
двух видов.
“Обедающие философы”
Агенты представляют философов, сидящих за одним столом и обедающих. В
зависимости от количества философов будет разное количество столовых приборов,
изначально их по 6. Когда философ проголодается то берет два столовых прибора и
ест, пока он не наестся, он не положит приборы на стол. Так же философ может
взять только один столовый прибор, если не успел взять второй, и будет
находиться в состоянии очереди, либо ждать пока освободиться другой прибор,
либо положит его на стол. Задача данной модели заключается в следующем, найти
тот момент, когда философы смогут договориться и не будут голодать.
Помощь агентов в решении определенных задач признана уже давно, благодаря
агентам мы можем симулировать различные модели и проводить с помощью этих
моделей эксперименты, не прибегая к настоящей модели. Если правильно описать
среду в которой будут находится агенты и их поведение в этой среде, то можно
построить модель практически чего угодно.
В нашем случае стоит задача “Лабиринт агентов”. В лабиринте спрятано
золото, которое необходимо найти агенту или агентам, по пути встречаются
препятствия, которые мешают агенту или же агентам найти золото, так как золото
может находится в любой точке лабиринта, включая препятствия. Для поиска золота
можно использовать несколько агентов, которые вместе будут искать золото, так
же можно менять вид поиска, который используют агенты для поиска золота. Цель
задачи проста, в зависимости от количества агентов и видов поиска, какой вид
поиска в конкретной ситуации окажется быстрее и какой вид поиска окажется самым
точны, при котором будет больше количество удачный экспериментов.
1.1 Анализ
алгоритмов и программных реализаций
В программе “Лабиринт агентов” используется несколько алгоритмов поиска
агентом золота в лабиринте. Это вертикальный поиск, горизонтальный поиск,
диагональный поиск, поиск по спирали (одновременно), поиск по спирали
(последовательно).
Вертикальный поиск. Один из возможных поисков, которые могут использовать
агенты для нахождения золота. Особенность вертикального поиска заключается в
том, что агент движется по вертикали вверх или вниз, делая шаг в сторону
(вправо или влево) лишь в том случае, когда дошел до верхнего или нижнего
предела поля, наткнулся на препятствие в виде сквозняка от ямы или от вони от
чудовища, или склона горы или же болота, или находится в тупике. Пример
вертикального поиск представлен на рисунке 1.1
Рисунок 1.1 - Вертикальный поиск
Вертикальный поиск так же известный как поиск в ширину, довольно
популярный поиск информации. Вертикальный поиск используют в своих системах
такие компании как Google, Yahoo, MSN. Конечно компании Google, Yahoo, MSN не
являются вертикальными поисковыми системами, а используют горизонтальный поиск
с включением методов вертикального поиска. Вертикальный поиск позволяет найти
не углубленную информацию, а общую, то есть ту информацию которая включает в
себя картинки, видео записи, продукты компаний и просто общую информацию по
теме, если же необходима более глубокая информация по какой-либо теме
используют горизонтальный поиск.
Горизонтальный поиск. Поиск, который агент использует для поиска золота в
лабиринте. Особенность горизонтального алгоритма поиска заключается в том, что
агент движется по горизонтали вправо или влево, делая шаг в верх или вниз в том
случае, когда дошел до левого или правого предела поля, наткнулся на
препятствие в виде сквозняка от ямы, или вони от чудовища, или склона горы, или
болота, или же находится в тупике. Пример горизонтального поиска представлен на
рисунке 1.2
Рисунок 1.2 - Горизонтальный поиск
Горизонтальный поиск или же поиск в глубину, используется для нахождения
более углубленной информации по какой-либо теме. Является основным способом
поиска информации с помощью поисковых систем, так как находит всю информацию по
заданному вопросу, не только общую, но и углубленную.
Диагональный поиск. Поиск, который агент использует для поиска золота в
лабиринте. Данный алгоритм поиска существенно отличается способом передвижения
агента, так как движение осуществляется по диагонали и реализовано дискретным
шагом по диагонали. Диагональ перемещения проходит из левого нижнего угла поля
в правый верхний угол. Поэтому для движения используются два шага-степа: вправо
- вверх (до предела - правый верхний угол поля, т.е. max по горизонтали и
потолок) и влево - вниз (max по вертикали и предел по горизонтали слева). В
остальном алгоритм похож на предыдущие, т.е. агент так же оглядывается в
поисках золота и блеска. При обнаружении препятствия пытается сделать шаг в
противоположном направлении, если это у него не получается, то включается
алгоритм вывода агента из тупика. Пример диагонального поиска представлен на
рисунке 1.3
Рисунок 1.3 - Диагональный поиск
Поиск по спирали (одновременно). В данном алгоритме введены специальные
параметры для синхронизации поиска между агентами, когда в настройках
количество агентов более одного. Также они позволяют отслеживать продвижение
агента в определенном направлении. Таким образом, агент поменяет направление
движения, только если встретит препятствие, в том числе и границы поля, или уже
исследованное поле. Это позволяет организовать общее продвижение агентов по
спирали одновременно. Пример поиска по спирали (одновременно) представлен на
рисунке 1.4
Рисунок 1.4 - Поиск по спирали (одновременно)
Поиск по спирали (последовательно). В отличие от предыдущего алгоритма здесь
не используются дополнительные параметры, но из-за этого продвигаться по полю
может лишь один из агентов (если их больше одного), другой начинает своё
движение только когда первый окажется в тупике, из которого невозможно
выбраться. Хотя этот алгоритм, в общем, и затрачивает больше времени для
поиска, чем предыдущий, но является более экономичным при использовании
ресурсов. Если, например, агенты были бы реализованы аппаратно, то имелись бы в
виду энергетические ресурсы. Пример поиска по спирали (последовательно)
представлен на рисунке 1.5
Рисунок 1.5 - Поиск по спирали (последовательно)
В лабиринте агент следует следующим задачам. Ему необходимо найти золото,
если золото было найдено, то в окне сообщений выведется информация об успехе,
если же нет, то информация о провале. При поиске золота и хождению по лабиринту
агент встречает препятствия по пути, среди которых ямы со сквозняком, горы со
склоном, чудовища с вонью и болото. В отличии от всех других препятствий болото
замедляет движение агента по лабиринту пока он находится в зоне действия
болота.
База знаний агентов. Представляет собой два вида базы знаний, первая
общая база знаний агентов, вторая личная база знаний агентов.
Общая база знаний агентов. Если на поле присутствует несколько агентов и
пользователь, выбрал в настройках программы, общую базу знаний, то агенты будут
работать сообща, то есть каждый агент будет знать о перемещениях других агентов
по полю и не будет ходить в уже посещенные ячейки. Эта база знаний представляет
собой общий разум агентов, где они идут только туда где еще не был никто из
них. С общей базой знаний поиск проходит быстрее так как агенты знают где они
уже были, и не пытаются идти в уже посещенные ячейки.
Рисунок 1.6 - Общение агентов
Личная база знаний. Так же пользователь может выбрать личную базу знаний
агентов, в настройках программы. Личная база знаний подразумевает, что у
каждого агента она своя и каждый агент знает только о своем передвижении, агент
не знает куда уже ходили другие агенты до него, поэтому чтобы не ходить в одну
и ту же ячейку дважды, агенты общаются друг с другом. Пример общения агентов
представлен на рисунке 1.6. Перед тем как сходить в ячейку они спрашивают у
других агентов были ли они в ней, если ответ положительный, то агент выбирает
другую клетку для посещения.
Выход из лабиринта. Агенты могут покинуть лабиринт если найдут выход или
же остаться в лабиринте и продолжить поиски золота. Но не всегда, есть шанс
найти золото оставшись в лабиринте.
2. РАЗРАБОТКА АРХИТЕКТУРЫ ПРОГРАММНОГО
КОМПЛЕКСА “ЛАБИРИНТ АГЕНТОВ”
Требования программного комплекса “Лабиринт Агентов”. При запуске
программы необходимо указать имя пользователя, а также выбрать, что будет с
файлами предыдущей работы, сохранить их или же перезаписать. При настройке поля
компьютером необходимо указать все настройки, которые могут понадобиться
компьютеру для подготовки поля к экспериментам. В эти настройки входят такие
как, процент заполнения поля ямами и горами, количество агентов, настройки
агентов, будут ли они постоянными или же изменяться после каждого эксперимента,
количество испытаний, которое хочет провести пользователь, так же время
задержки, необходимое пользователю, базу знаний агентов, будет ли она индивидуальной
или совместной.
Если же поле будет настроено пользователем для проведения экспериментов
самостоятельно, то он должен расположить на поле ямы, горы, чудовище, золото и
болота. Выбрать необходимое количество испытаний и время задержки. После чего может
смело приступать к выполнению экспериментов.
Ограничения программного комплекса “Лабиринт Агентов”. Число агентов,
зависит от размера поля заданного пользователем, при минимальном поле 10 на 10
клеток, всего можно поставить 96 агентов, это связанно с тем, что 96 клеток из
100 будет заняты агентами, а оставшиеся 4 клетки будут включать в себя золото,
болото, чудовище и яму. Максимальное количество агентов составляет 396 на поле
20 на 20 клеток, ограничения на количество агентов ставиться автоматически в
зависимости от размера поля заданного пользователем. Время задержи не должно
быть меньше 20мс из-за того, что если время задержки будет меньше 20мс
пользователь не увидит движения агента, а увидит лишь его путь, по которому
будет сложно понять как двигался агент, особенно если не знать алгоритмов
поиска агента, поэтому было принято, что минимально время задержки составит
20мс, максимально 100мс, так как при задержки 100мс агент будет двигаться
достаточно медленно, чтобы пользователь смог разобрать его траекторию движения.
Агентов никогда не может быть меньше 1, так как суть экспериментов заключается
в поиске золота агентами, а при их отсутствии все эксперименты закончатся
провалом. Процент заполнения поля, это настройка лабиринта включает сюда, горы
и ямы, в зависимости от процента гор и ям будет больше или же меньше, в каждом
эксперименте поле должно быть заполнено ямами и горами, минимальное значение
это 1 яма и 1 гора, при заполнении поля на 1%. Так как ямы и горы обязательны
для экспериментов, то процент заполнения поля равный 0 мы поставить не можем.
Рассмотрим ограничения, которые появляются если поле заполняет сам
пользователь. При расстановке агентов, пользователь все так же зависит от
размеров поля, в зависимости от размеров поля зависит количество агентов,
которое пользователь может поставить. Для правильной работы программы,
пользователь обязательно должен поставить хотя бы одного агента на поле, в
противном случае, программа сообщит ему об этом. Так же поле должно в себя
включать ямы, горы, золото, чудовище и болота. Для работы программы
пользователь обязан расставить все эти предметы на поле в количестве равному 1.
Заполнение поля ямами и горами пользователь решает сам, по-своему желанию или
же требованиям лабораторной работы. А вот количество золота и чудовища не
должно превышать 1. А количество болото всегда должно быть равно 2. Так как при
попадании в болото, агент замедляется и какое-то время стоит на месте, при
большом количестве болот, один эксперимент бы занимал большое количество
времени, не говоря уже о 100 экспериментах.
Представим для программы агентно-ориентированного моделирования “Лабиринт
агентов” структурную схему приложения.
Структурная схема представлена на рисунке 2.1
Рисунок 2.1-Структурная схема
3. РАЗРАБОТКА СТРУКТУР ДАННЫХ И ЗНАНИЙ
ДЛЯ “ЛАБИРИНТ АГЕНТОВ”
В программе агентно-ориентированного программирования “Лабиринт агентов”
агенты для исследования лабиринта используют данные и знания. Перемещаясь по
лабиринту агентам необходимо знать в каких частях лабиринта они уже были, в
какие ячейки они должны сходить и уметь определять, что перед ними находится
золото или же чудовище.
У каждого агента есть база знаний, с помощью которой агент свободно
передвигается по лабиринту в поисках золота, и не ходит по одним и тем же
местам. База знаний агентов. Представляет
собой два вида базы знаний, первая общая база знаний агентов, вторая личная
база знаний агентов.
Общая база знаний агентов. Если на поле присутствует несколько агентов и
пользователь, выбрал в настройках программы, общую базу знаний, то агенты будут
работать сообща, то есть каждый агент будет знать о перемещениях других агентов
по полю и не будет ходить в уже посещенные ячейки. Эта база знаний представляет
собой общий разум агентов, где они идут только туда где еще не был никто из
них. С общей базой знаний поиск проходит быстрее так как агенты знают где они
уже были, и не пытаются идти в уже посещенные ячейки.
Личная база знаний. Так же пользователь может выбрать личную базу знаний
агентов, в настройках программы. Личная база знаний подразумевает, что у
каждого агента она своя и каждый агент знает только о своем передвижении, агент
не знает куда уже ходили другие агенты до него, поэтому чтобы не ходить в одну
и ту же ячейку дважды, агенты общаются друг с другом. Перед тем как сходить в
ячейку они спрашивают у других агентов были ли они в ней, если ответ
положительный, то агент выбирает другую клетку для посещения. Пример общения
агентов представлен на рисунке 3.1
Рисунок 3.1 - Общение агентов
Для выбора той или иной базы знаний у агента, пользователь может
воспользоваться настройками программы агентно-ориентированного программирования
“Лабиринт агентов”. Пример выбора базы знаний агентов представлен на рисунке
3.2
Рисунок 3.2 - Выбор базы знаний
Лабиринт представлен в виде двумерного массива, каждая ячейка лабиринта
имеет свой номер, отличный от всех других ячеек. В каждой ячейке может
находиться золото, или болото, или чудовище, или горы, или ямы, независимо от
ее расположения. При поиске золота агент проверяет каждую ячейку, в которую он
собирается идти, и если там находится препятствие, то агент его обходит. [7]
В программе агентно-ориентированного моделирования “Лабиринт агентов”
имеется множество данных, включая данные исследований, которые проводит
пользователь. Для сохранения этих данных и для более удобной работы с ними, все
данные исследований и ключевые данные настроек, сохраняются в специальном
текстовом файле, в корне программы. При запуске программы пользователь может
либо удалить результаты предыдущих экспериментов, либо же продолжить сохранять
результаты в том же файле. Пример выбора представлен на рисунке 3.3
Рисунок 3.3 - Выбор сохранения результатов работы
Рисунок 3.4 - Результаты экспериментов в программе
Данные и результаты экспериментов записываются в специальном поле в
программе, где их можно изучить, при каждом новом эксперименте эти данные
удаляются с формы, но сохраняются в файле. Пример вывода данных результата в
программе, представлен на рисунке 3.4
Всего программа создает два файла с результатами экспериментов, один из
них называется result, а второй short. Их отличия в том, что result записывает, всю информацию по
экспериментам, копируя информацию из результатов представленных в программе в
отдельный файл, а short представляет
результаты экспериментов в специальном виде, укороченном по сравнению с файлом result, где все данные записаны в строки.
Пример результатов в файле result,
представлен на рисунке 3.5
Рисунок 3.5 - Результаты экспериментов в файле result
Пример сохранения данных экспериментов в файле short, представлен на рисунке 3.6
Рисунок 3.6 - Результаты экспериментов в файле short
Сформируем таблицу с результатами экспериментов, для более удобного
восприятия, результаты тестирования представлены в таблице 3.1
Таблица 3.1 - Результаты тестирования
|
№
|
Алгоритм
|
Время
|
Плотность
|
Агенты
|
Вид экспер
|
Результат
|
|
1
|
Вертикальный
|
26
|
8
|
1
|
Фикс. чис. ям,
аген.
|
Зол. найдено
|
|
2
|
Вертикальны
|
60
|
8
|
1
|
Фикс. чис. ям,
аген
|
Зол. найдено
|
|
3
|
Вертикальный
|
19
|
8
|
1
|
Фикс. чис. ям,
аген
|
Зол. найдено
|
Поле программы агентно-ориентированного моделирования “Лабиринт агентов”
реализуется с помощью двумерного массива. При прохождении агентом этого
массива, номер каждой ячейки записывается в памяти агентов, поэтому они не
будут ходить по одному и тому же маршруту, а все объекты в лабиринте, такие как
горы, золото и т.д., расставляются в лабиринте случайным образом. Поэтому
каждый эксперимент, каждое прохождение агентом лабиринта является
исключительным.
4. РАЗРАБОТКА АЛГОРИТМОВ
В программе “Лабиринт агентов” используются различные алгоритмы поиска
агентом золото, каждый из этих алгоритмов уникальный и по-своему хорош. Для
проведения экспериментов мы используем такие виды поиска как вертикальный
поиск, горизонтальный поиск, диагональный поиск, поиск по спирали
(одновременно), поиск по спирали (последовательно). Разберем несколько примеров
поиска и приведем их блок-схемы. [5]
4.1
Вертикальный поиск
Вертикальный поиск. Один из простых поисков, но в то же время
эффективных. Алгоритм вертикального поиска заключается в следующем: агент, всегда
движется только вертикально, изначально он движется вниз, проверяя свободно ли
нижняя клетка (нет ли там болота, ямы, горы, чудовища, золота или стены
лабиринта), при нахождении золота эксперимент заканчивается, агент движется
вниз до тех пор пока не встретит одно из препятствий, если он не сможет сходить
в нижнею клетку, то агент свернет влево или вправо и продолжит движение вниз,
если же и после поворота движение вниз не возможно, то агент начнет двигаться
вверх, до следующего препятствия, после которого он опять свернет и начнет
двигаться вниз. Пример блок-схемы алгоритма вертикального поиска представлен на
рисунке 4.1
4.2
Горизонтальный поиск
Горизонтальный поиск. Данный поиск почти идентичен вертикальному поиску,
различия лишь в том, что агент движется уже по горизонтали.
Рисунок 4.1 - Алгоритм вертикального поиска
Рисунок 4.2 - Алгоритм горизонтального поиска
Алгоритм
горизонтального поиска заключается в том, что агент всегда движется по
горизонтали, первый свой шаг он делает влево, в зависимости от состояния данной
клетки, если она не содержит каких-либо препятствий, то агент переходит в нее,
если же он не может сходить в нее, то агент поворачивает, то есть идет на один
уровень вверх или вниз, а далее опять влево, пока не дойдет до края лабиринта,
затем он опуститься или поднимется на один уровень и начнет движение вправо, и
так до тех пор пока агент не найдет золото, или же не попадет в тупик из
которого он не сможет выбраться, так же возможно что агент просто не сможет
найти золото и эксперимент закончится. Пример блок-схемы алгоритма
горизонтального поиска представлен на рисунке 4.2 и рисунке 4.3
4.3
Диагональный поиск
Диагональный поиск. По сравнению с вертикальным и горизонтальным поиском
диагональный поиск занимает больше времени. Суть поиска заключается в том, что
он идет по диагонали, если это возможно, то есть агент всегда старается
двигаться по диагонали или ищет подходящее место откуда он сможет начать
двигаться по диагонали. Алгоритм диагональное поиска заключается в следующем.
Агент начинает двигаться по диагонали, в сторону которую это возможно, в
приоритете начать движение в правую сторону, но если это будет невозможно, то
движение начнётся в лево. Само движение на поле представляет собой движение
вперед-вверх-вперед или же вперед-вниз-вперед, в зависимости от того куда
направляется агент в верх поля или же спускается вниз поля. Благодаря
диагональному поиску большинство препятствий агент обходит, используя этот
поиск, но если же препятствие появилось на пути в виде болота, горы, чудовища,
ямы, границ лабиринта, то агент начинает двигаться в противоположном
направлении в зависимости от того куда он шел на поиски. Если движение по
диагонали становится невозможно, то агент начинает двигаться, используя метод
горизонтального поиска, до тех пор, пока не появится возможность начать
движение опять по диагонали или же агент не найдет золото. Пример блок-схемы
алгоритма диагонального поиска представлен на рисунке 4.3
Рисунок 4.3 - Алгоритм диагонального поиска
4.4 Поиск
по спирали (одновременно)
По спирали (одновременно). Используя метод поиска по спирали
(одновременно), агент движется по спирали и ищет золото, но полнота этого поиска
открывается тогда, когда мы используем больше чем 1 агента при поиске золота в
лабиринте. Два агента одновременно движутся по лабиринту используя метод поиска
по спирали, в этом и заключается главная особенность данного вида поиска.
Начинает свое движение агент, используя поиск по спирали, всегда с движения
вверх, если же по какой-либо причине он не может двигаться вверх, то он начнет
движение влево, если же и в лево он не сможет сходить, то пойдет вниз. Движение
агента продолжается либо до первого препятствия в виде болота, чудовища, ямы
или до границы лабиринта, далее агент продолжает движение в другую сторону,
рисуя тем самым спираль, агент движется от внешнего круга спирали к ее центру,
дойдя до центра и не найдя золото, агент возвращается на изначальную позицию и
начинает движение в другую сторону, по тому же алгоритму какой он уже
использовал. Но главная идея этого поиска заключается в одновременном поиске
золота агентами. Поэтому в независимости, сколько агентов у нас будет на поле,
все они будут использовать один и тот же метод, поиск по спирали, они поделят
между собой территорию лабиринта и будут одновременно двигаться в поисках
золото, не пересекаясь друг с другом. Пример блок-схемы алгоритма поиска по
спирали (одновременно), представлен на рисунке 4.4
Рисунок 4.4 - Алгоритм поиска по спирали (одновременно)
4.5 Поиск
по спирали (последовательно)
По спирали (последовательно). Данный метод поиска использует тот же самый
алгоритм, что и поиск по спирали. Агент начинает свое движение вверх, если же
оно невозможно, то он идет влево, если же и влево нет возможности сходить, то
агент начинает движение вниз лабиринта, идя до границы лабиринта и поворачивая,
тем самым рисуя своими движениями спираль, от внешнего круга к центру спирали.
Если по пути агенту встретятся препятствия в виде болота, ям, чудовища или гор,
то агент обойдет препятствие и продолжит движение в том направлении в каком он
шел, если это будет возможность. Главная особенность этого вида поиска и его главное
отличие от поиска по спирали (одновременно) в том, что изначально движется
только один агент и при его попадании в тупик, он останавливается и начинает
двигаться второй агент и так далее пока золото не будет найдено или все агенты
не окажутся в тупиках.
Рисунок 4.5 - Алгоритм поиска по спирали (последовательно)
Этот вид
поиска занимает больше всего времени, особенно если задано большое поле
лабиринта (20 клеток на 20). Весь потенциал данного поиска можно получить,
используя только больше 1 агента, так как он рассчитан на поиск с
использованием нескольких агентов.
4.6
Алгоритм индивидуальной базы знаний
Так же не стоит забывать о функции, которую могут использовать агенты, а
именно личная база знаний агентов. Эта функция позволяет агентам знать лишь о
своем перемещении по лабиринту, и для дальнейшего движения им необходимо
работать сообща. При движении агент всегда говорит о своих намерениях сходить в
ту или иную ячейку, если в ней уже побывал кто-то из агентов, то ему ответят,
что в данной ячейке уже были и тогда агент пойдет в другую ячейку. Используя
эту функцию каждый, агент является отдельным элементом со своим разумом, а не
частью целого, как это будет при общей базе знаний. Пример блок-схемы алгоритма
поиска с личной базой знаний, представлен на рисунке 4.6
Рисунок 4.6 - Алгоритм поиска с личной базой знаний
5. РАЗРАБОТКА И РЕАЛИЗАЦИЯ ПРОГРАММНЫХ
МОДУЛЕЙ
Для программы агентно-ориентированного программирования “Лабиринт
агентов” было разработано несколько модулей, которые не только влияют на
проведение экспериментов, но также преображают программу, меняя ее интерфейс на
более удобный пользователю.
5.1 Болото
Специальный объект на поле, при попадании в который агент останавливается
на короткий промежуток времени и потом опять продолжает движение. Было решено
ввести всего 2 болота на поле из-за того, что при большой концентрации болота
на поле агент просто не сможет нормально искать золото, а больше всего простоит
в болоте, это не только повредит проводимому нами эксперименту, но также и
увеличит количество времени его проведения. Ниже представлено описание кода
болота. [10]
Код болота.
procedure boloto(x,y:integer);
beginnot(mas[x-1,y] div 102=1)
then[x-1,y]:=mas[x-1,y]+1000;not(mas[x+1,y] div 102=1) then[x+1,y]:=mas[x+1,y]+1000;not(mas[x,y-1]
div 102=1) then[x,y-1]:=mas[x,y-1]+1000;not(mas[x,y+1] div 102=1)
then[x,y+1]:=mas[x,y+1]+1000;
end;
Данный код создает новую процедуру болото. Данная процедура создает
вокруг ячейки с болотом (клетки с буквой Б) создает обозначение слякоти, то
есть расставляет букву “с”.
for i:=1 to gor do beginj:=1 to vert do begin'Б'=StringGrid1.Cells[i,j] then
boloto(i,j);
end;
Данный цикл ищет по горизонтали и вертикале в лабиринте букву “Б”, и при
ее нахождении выполняется процедура болото, которая расставляет вокруг
найденной буквы “Б”, буквы “с”. [12](sum6<2) do
begin:=random(gork);:=random(vertk);(FLabir.StringGrid1.Cells[ranXz+1,ranYz+1]='')
then begin:=sum6+1;.StringGrid1.Cells[ranXz+1,ranYz+1]:='Б' ; end;
end;
В данном цикле описано размещение болота на поле. При каждом эксперименте
местоположение всех элементов, включая болото различны и задаются тандемным
число по горизонтали и вертикали, далее проверяется, если случайная точка поля
пустая, то она занимается болотом, после расстановки 1 болота, к сумме
прибавляется 1, и цикл выполняется до тех пор, пока сумма не будет больше 2,
следовательно, на поле будет всегда только 2 болото, не больше и не меньше.
Пример объекта болото, представлен на рисунке 5.1
Рисунок 5.1 - Болото
5.2 Горы
Еще одно дополнительное препятствие для агента в поисках золота. Горы
являются обычными объектами, которые будут препятствовать агенту в поисках
золота, количество гор на поле может быть различно и зависит от процента
заполнения поля который выберет пользователь. Так же, как и ямы, горы могут
вообще отсутствовать на поле или же быть в огромном количестве. Ниже
представлено описание кода создания гор.
procedure Gora(x,y:integer) ;
beginnot((mas[x-1,y]mod 100) div 10=1) then[x-1,y]:=mas[x-1,y]+10;not((mas[x+1,y]mod
100) div 10=1) then[x+1,y]:=mas[x+1,y]+10;not((mas[x,y-1]mod 100) div 10=1)
then[x,y-1]:=mas[x,y-1]+10;not((mas[x,y+1]mod 100) div 10=1)
then[x,y+1]:=mas[x,y+1]+10;
end;
В данной части кода создается процедура гора, которая будет располагать
крестом буквы “c” вокруг той
точки поля к которой будет применяться данная процедура.
while (sum7)<(ssg) do
begin:=random(gork);:=random(vertk);(FLabir.StringGrid1.Cells[ranX+1,ranY+1]='')
then begin:=sum7+1;.StringGrid1.Cells[ranX+1,ranY+1]:='г' ;
End
Цикл в верху описывает заполнение поля горами. Ячейка поля для горы
выбирается случайным образом по горизонтали и вертикали, далее идет проверка,
является ли ячейка, которую мы получили случайным образом пустой, если нет, то
выбирается новая ячейка, если же она пустая, то в нее записывается буква “г”
обозначающая гору. Далее к общему числу гор прибавляется единица и идет
проверка, не больше ли число гор чем специальное число, полученное из процента
заполнения поля. [8]i:=1 to gor do beginj:=1 to vert do begin'г'=StringGrid1.Cells[i,j] then
Gora(i,j);
end;
В данном цикле выполняется поиск буквы “г”, то есть ячеек в которых
расположены горы, при нахождении такой ячейки выполняется, специальная
процедура “Gora”, которая располагает вокруг ячейки
с горой буквы “c”, обозначающие
склон горы
Пример объекта гора, представлен на рисунке 5.2
Рисунок 5.2 - Гора
5.3
Интерфейс
Так же было решено сделать интерфейс более удобным и поменять цвета,
основных форм, на более приятный. Так же кнопки были заменены на кнопки с
рисунками, что делает интерфейс приложения более приятным для работы
пользователю. Пример изменённого интерфейса представлен на рисунке 5.3, рисунке
5.4 и рисунке 5.5
Рисунок 5.3 - Форма “Анкета”
Рисунок 5.4 - Форма “Настройки”
Рисунок 5.5 - Форма “О программе”
5.4 Карта
лабиринта
Изначально карта поля представляла собой ячейки в которых были написаны
соответствующие буквы, обозначающие тот или иной объект: я-яма, г-гора,
ч-чудовище, б-болото, з-золото, а-агент. А рядом с каждым объектом
располагались их составляющие, например, у ямы это сквозняк, у чудовища вонь, а
у золота это блеск. Пример представлен на рисунке 5.6
Рисунок 5.6 - Карта лабиринта
После создания новых объектов, таких как горы и болота, карта лабиринта
маленького размера (10 клеток на 10) была почти вся усеяна буквами, а пустых
ячеек оставалась мало, поэтому было принято заменить буквенное обозначение
объектов, соответствующими картинками, по которым пользователь будет понимать,
что это за объект. Пример представлен на рисунке 5.7
Рисунок 5.7 - Карта лабиринта
Так же был заменен агент, теперь он тоже имеет не буквенное обозначение и
картинку, показывающую его местоположение. Пример представлен на рисунке 5.8
Рисунок 5.8 - Карта агента
Для того чтобы не сбить пользователя с толку, в приложении была выведена
подсказа, показывающая пользователю как изображается тот или иной объект на
карте. Пример представлен на рисунке 5.9
Рисунок 5.9 - Подсказка пользователю
Ниже представлен пример кода, который заменяет буквенное изображение на
картинки. Пример кода для горы. [9]:=0; W:=0;j:=1 to gor do
for i:=1 to vert do beginStringGrid1.Cells[j,i]='г' then:=j; W:=i;;(ACol=H) and
(ARow=W) then StringGrid1.Canvas.StretchDraw(Rect, Image2.Picture.Graphic);
end;
Сначала по горизонтали и вертикали идет поиск ячейки в которой стоит
буквенное обозначение горы, то есть буква “г”. Запоминается местоположение этой
ячейки и записывается в память, далее для данной ячейки используется заливка
ячейки изображением, для этого необходимо заранее поместить изображение на
форму в компоненте Image.
Для добавления других изображений, используется тот же метод, который
описан выше, пример кода представлен ниже.
for j:=1 to gor do
for i:=1 to vert do begin(StringGrid1.Cells[j,i]='Б') or (StringGrid1.Cells[j,i]='Бс') or (StringGrid1.Cells[j,i]='Бб') then:=j; W:=i;;(ACol=H) and
(ARow=W) then StringGrid1.Canvas.StretchDraw(Rect, Image1.Picture.Graphic);;
Выше приведен код для обозначения болота картинкой. Картинка размещается
в объекте StringGrid.
H:=0; W:=0;j:=1 to gor do
for i:=1 to vert do beginStringGrid1.Cells[j,i]='г' then:=j; W:=i;;(ACol=H) and
(ARow=W) then StringGrid1.Canvas.StretchDraw(Rect, Image2.Picture.Graphic);
end;
Выше приведен код для обозначения гор картинкой. Картинка размещается в
объекте StringGrid.
H:=0; W:=0;j:=1 to gor do
for i:=1 to vert do beginStringGrid1.Cells[j,i]='з' then:=j; W:=i;;(ACol=H) and
(ARow=W) then StringGrid1.Canvas.StretchDraw(Rect, Image3.Picture.Graphic);;
Выше приведен код для обозначения золота картинкой. Картинка размещается
в объекте StringGrid.
H:=0; W:=0;j:=1 to gor do
for i:=1 to vert do beginStringGrid1.Cells[j,i]='ч' then:=j; W:=i;;(ACol=H) and
(ARow=W) then StringGrid1.Canvas.StretchDraw(Rect, Image4.Picture.Graphic);;
Выше приведен код для обозначения чудовища картинкой. Картинка
размещается в объекте StringGrid.
H:=0; W:=0;j:=1 to gor do
for i:=1 to vert do beginStringGrid1.Cells[j,i]='я' then:=j; W:=i;;(ACol=H) and
(ARow=W) then StringGrid1.Canvas.StretchDraw(Rect, Image5.Picture.Graphic);;
Выше приведен код для обозначения ямы картинкой. Картинка размещается в
объекте StringGrid.
H:=0; W:=0;j:=1 to gor do
for i:=1 to vert do beginStringGrid2.Cells[j,i]='а' then:=j; W:=i;;(ACol=H) and
(ARow=W) then StringGrid2.Canvas.StretchDraw(Rect, Image11.Picture.Graphic);;
Выше приведен код для обозначения агента картинкой. Картинка размещается
в объекте StringGrid.
if (ACol=0) and (ARow=0) then
StringGrid1.Canvas.FillRect(Rect);(ACol=0) and (ARow=0) then
StringGrid2.Canvas.FillRect(Rect);
end;
Так же разработан выход из лабиринта. Добавлен новый объект лабиринта,
такой как выход, при нахождении выхода агент может с вероятностью 50% покинуть
лабиринт или же остаться в лабиринте и продолжить искать золото, данный объект
позволяет по-другому взглянуть на поиски агентом золота. Пример выхода агента
из лабиринта представлен на рисунке 5.10. программный данный
интерфейс отладка
Рисунок 5.10 - Пример выхода из лабиринта
Так же агент может остаться в лабиринте и найти золото, пример
представлен на рисунке 5.11
Рисунок 5.11 - Пример выхода из лабиринта
Так же если агент останется в лабиринте, он может не найти золото, пример
представлен на рисунке 5.12
Рисунок 5.12 - Пример выхода из лабиринта
Выход из лабиринта реализуется в модуле поиска агентом золота. Во время
нахождения выхода, генерируется случайное число 0 или 1, от которого зависит
покинет ли агент лабиринт или продолжит искать золото. При выпадение 0 агент
покидает лабиринт, если же выпадает 1, то агент остается в лабиринте и
продолжает искать золото.
6. ЭКСПЕРИМЕНТАЛЬНОЕ ТЕСТИРОВАНИЕ И
ОТЛАДКА ПРОГРАММНЫХ МОДУЛЕЙ
6.1 Оценка
надежности ПС
Проведем оценку надежности модернизированного программного средства
агентно-ориентированного моделирования “Лабиринт агентов”. Для проверки
надежности существует несколько моделей таких как: модель Миллса, модель
Шумана, модель Ла Падула, модель Джелинского-Моранды, модель Муса, модель
Липова, простая интуитивная модель, модель Каркорена, модель Нельсона [4]. Для
проведения оценки надежности были выбраны модель Миллса и модель Нельсона.
Модель Нельсона.
Проведем оценку надежности программного средства на основе модели
надежности Нельсона
При расчете надежности модель учитывает вероятность выбора определенного
тестового набора для очередного выполнения программы.
Предполагается, что область данных, необходимых для выполнения тестов
разделена на К взаимоисключающих подобластей Zi, i=1, 2,.., K.
Пусть Pi - вероятность того, что для очередного выполнения программы
будет выбран набор данных из области Zi. Значения Pi определяются по статистике
входных данных в реальных условиях работы программного средства.
Предполагается, что к моменту оценки надежности было выполнено Ni прогонов программы на наборе данных Zi и из них ni прогонов закончились отказом. Тогда надежность определяется
по формуле:
,
,
После оценки надежности на основе модели Нельсона получили значение
надежности равное 0.8, что говорит о достаточно высокой надежности
разработанного программного средства.
Модель Миллса.
Проведем оценку надежности разработанного программного средства по модели
Миллса. Данная модель предполагает необходимость, перед началом тестирования,
искусственно вносить в программу некоторое количество ошибок.
Ошибки вносятся случайным образом. Специалист, проводящий тестирование не
знает ни количества, ни характера внесенных ошибок, до момента оценки показателя
надежности.
Предполагается, что все ошибки имеют равную вероятность обнаружения в
процессе тестирования. Первоначальное число ошибок в программе определяется по
формуле:
𝑁= 𝑆·𝑛𝑉,
где S - количество искусственно внесенных ошибок;- число найденных
собственных ошибок; - число обнаруженных, к моменту оценки внесенных ошибок.
Предположим, в нашем случае в программу было специально внесено 20
ошибок, к некоторому моменту времени, было обнаружено 6 собственных ошибок и 15
внесенных. Тогда проведя расчеты получим, что первоначальное число ошибок в
программе равно 8.
Второй частью модели Миллса, является проверка гипотезы об оценке
первоначального числа ошибок в программе. А именно если допустить, что в
программе имеется k собственных ошибок и S искусственно внесенных, то
вероятность с которой можно утверждать, что в программе первоначально было N =
n ошибок рассчитывается по формуле:
С= {1, если 𝑛>𝑘𝑆𝑠+𝑘+1,если 𝑛≤𝑘,
Если допустить что в разработанном программном средстве не выявлено
собственных ошибок и все искусственно внесенные ошибки были обнаружены, то
вероятность того, что в программе нет ошибок равна 0,95. Теперь если учесть,
что в программе есть 6 собственных ошибок, получим, что вероятность равна 0,74.
6.2
Экспериментальное тестирование ПС
Проведем экспериментальное тестирование программного средства
агентно-ориентированного моделирования “Лабиринт агентов”. Тестирование было
решено провести в два этапа, первое тестирование проводить программист
модернизирующих программное средства и ставит свою оценку модернизированной
программе, выделяет ее плюсы и минусы. Вторая часть тестирования заключается в
проведении тестирования группой экспертов, которыми выступят люди, работавшие
со старой версией программного средства, так как им уже известна данная
программа агентно-ориентированного моделирования “Лабиринт агентов”, то они
смогут поставить справедливую оценку программе, рассказать о ее плюсах и
минусах, а также объяснить ее отличие от старой версии данной программы.
Первый
этап тестирования
Первый этап тестирования заключается в тестировании программного средства
программистом, производившим модернизацию программного средства. Проводилась
модернизация программы агентно-ориентированного программирования “Лабиринт
агентов”, были разработаны новые модули для программы, которые бы расширяли
область проводимых экспериментов, так же программа была модернизирована внешне,
был изменен интерфейс.
Для проведения тестирования возьмем следующие настройки программного
средства, приведённые в таблице 6.1
Таблица 6.1 - Настройки программы
|
Алгоритм
|
Размеры поля
|
Заполнение поля
|
База знаний
|
Агенты
|
Экспер.
|
Вид
|
Время
|
|
Вертикальный
поиск
|
10 на 10
|
2%
|
Совместная
|
1
|
10
|
Фикс
|
100мс
|
Пояснения таблицы 6.1. Алгоритмом поиска является вертикальный поиск,
размеры поля выбраны 10 клеток на 10, заполнение поля ямами и горами 2%, база
знаний агентов выбрана совместная, количество агентов равно 1, количество
экспериментов равно 10, вид эксперимента - фиксированное число ям и агентов,
время задержки равняется 100мс. Вид формы с настройками программы представлен
на рисунке 6.1.
Рисунок 6.1 - Настройки программы
Приступим к проведению экспериментов. Было проведено 10 экспериментов с
настройками, представленными на рисунке 6.1 и таблице 6.1. Во время проведения
экспериментов не возникло не одной ошибке, включая программные ошибки и ошибки
вычисления самой программы. Все 10 экспериментов были выполнены и представлены
результаты по этим экспериментам. Приведем пример результатов экспериментов в
виде таблицы 6.2
Таблица 6.2 - Результаты экспериментов
|
№
|
Вид поиска
|
Время
|
% Заполнения
|
Агенты
|
Вид эксп.
|
Результат
|
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
1
|
Вертикальный
|
78
|
9
|
1
|
Фикс.
|
Зол.найдено
|
|
2
|
Вертикальный
|
1
|
9
|
1
|
Фикс.
|
Зол.не найдено
|
|
3
|
Вертикальный
|
13
|
9
|
1
|
Фикс.
|
Зол.найдено
|
|
4
|
Вертикальный
|
26
|
9
|
1
|
Фикс.
|
Зол.найдено
|
|
5
|
Вертикальный
|
10
|
9
|
1
|
Фикс.
|
Зол.не найдено
|
|
6
|
Вертикальный
|
26
|
9
|
1
|
Фикс.
|
Зол.найдено
|
|
7
|
Вертикальный
|
14
|
9
|
1
|
Фикс.
|
Зол.не найдено
|
|
8
|
Вертикальный
|
2
|
9
|
1
|
Фикс.
|
Зол.не найдено
|
|
9
|
Вертикальный
|
16
|
9
|
1
|
Фикс.
|
Зол.найдено
|
|
10
|
Вертикальный
|
67
|
9
|
1
|
Фикс.
|
Зол.найдено
|
|
|
|
|
|
|
|
|
|
|
На рисунке 6.2 представлены результаты экспериментов, выведенные в
программе агентно-ориентированного моделирования “Лабиринт агентов”.
Рисунок 6.2 - Результаты экспериментов
Так же ниже представлены результаты экспериментов в двух сохраненных
текстовых файлах, short и result, на рисунках 6.3 и 6.4.
Рисунок 6.3 - Результаты экспериментов в фале short
Рисунок 6.4 - Результаты экспериментов в фале result
По результатам первой части тестирования было выявлено, что программа
справляется с поставленными задачами, во время выполнения экспериментов не
возникло никаких сбоев или же программных ошибок, все эксперименты, проводимые
нами, были закончены и по окончанию были сформированы результаты наших
экспериментов в двух текстовых файлах. Так же работать с программой стало более
удобно из-за ее измененного интерфейса, который более приятен пользователю, в
особенности замены буквенных обозначений на картинки, что делает работу с
данной программой более удобной.
Второй
этап тестирования
Для второго этапа тестирования, необходимо дистрибутив программного
средства передать экспертам для дальнейшего тестирования. Суть заключается в
том, что эксперты будут проводить один и тот же эксперимент и выявлять как
работает данное программное средство, удобно ли им пользоваться, какие ошибки
возникают во время работы программы, и многое другое. Так же данный этап
тестирования покажет, как работает программное средство на различных
компьютерах с различным ПО и возникают ли какие-либо проблемы между
взаимодействием программы и ПО компьютера.
Таблица 6.3 - Настройки программы
|
Алгоритм
|
Размеры поля
|
Заполнение поля
|
База знаний
|
Агенты
|
Экспер.
|
Вид
|
Время
|
|
Вертикальный поиск
|
10 на 10
|
2%
|
Совместная
|
1
|
10
|
Фикс
|
100мс
|
Для тестирования было выбрано пять экспертов, которые проведут
тестирование программного средства, напишут свой отзыв и приведут плюсы и
минусы данного программного средства. Вид формы с настройками программы
представлен на рисунке 6.5.
Рисунок 6.5 - Настройки программы.
Первый эксперт.
При проведении тестирования, не было выявлено никаких программных ошибок
или сбоев, программное средство работало хорошо с установленным ПО, все
результаты тестирования успешно сохранились в отдельных файлах в корне
программы. Так же интерфейс стал более приятен и отзывчив пользователю, а
замена буквенных обозначений на изображения положительно сказал на работе с
программой, так как разбираться с буквами на маленьком поле намного сложнее чем
с изображениями, по которым сразу понятно какой именно это объект. Результаты
эксперимента представлены на рисунке 6.6.
Рисунок 6.6 - Результаты экспериментов эксперта 1
Второй эксперт.
Во время проведения тестирования не возникло никаких программных ошибок.
Программа отвечала всем целям для которых проводился эксперимент. Во время
использования программы не возникло сложности с пониманием интерфейса
программы. Результаты эксперимента представлены на рисунке 6.7.
Рисунок 6.7 - Результаты экспериментов эксперта 2
Третий эксперт.
Программа показала себя надлежащим образом. По сравнению со старой
версией программы, новая версия обзавелась более приятным интерфейсом, который
сразу располагает пользователя, изучения данного интерфейса не займет много
времени у пользователей плохо знакомыми с компьютерами. Программа стабильно
работала, не смотря на различные ПО запущенные фоновым процессом. Все
эксперименты необходимые для тестирования программы были выполнены без проблем.
Результаты эксперимента представлены на рисунке 6.8.
Рисунок 6.8 - Результаты экспериментов эксперта 3
Четвертый эксперт.
Для проведения тестирования требовалось провести 10 экспериментов с
определенными настройками, все эксперименты были выполнены удачно, без
возникновения каких-либо ошибок. По завершению экспериментов, результаты были
записаны в отдельном файле, что не вызвало проблем с изучением результатов работы
программы. Результаты эксперимента представлены на рисунке 6.9.
Рисунок 6.9 - Результаты экспериментов эксперта 4
Пятый эксперт.
При запуске программы, сразу же был замечен новый интерфейс, который стал
более ярким и приветливым к пользователю, в дальнейшем использовании программы,
интерфейс приятно удивил, когда вместо буквенных обозначений на поле появились
картинки объектов. Так же понравились новые объекты, которых не было в старой
версии программы, такие как болото, горы и выход. Эти новые объекты расширили
рамки проводимых экспериментов, добавив новые возможности, которые влияют на
каждый проведенный эксперимент, а, следовательно, на его результат. Результаты
эксперимента представлены на рисунке 6.10.
В таблице 6.4 покажем мнение каждого эксперта относительно отдельных
модулей программы, как они считают важны ли новые добавленные модули и
исправленные старые или же, по их мнению, работа со старой версии программного
средства было более удобна и практична.
Рисунок 6.10 - Результаты экспериментов эксперта 5
Таблица 6.4 - Мнение экспертов
|
Эксперт 1
|
Эксперт 2
|
Эксперт 3
|
Эксперт 4
|
Эксперт 5
|
|
1
|
2
|
3
|
4
|
5
|
6
|
|
Интерфейс
|
+
|
+
|
+
|
+
|
+
|
|
Модуль “Болото”
|
+
|
+
|
-
|
+
|
+
|
|
Модуль “Гора”
|
+
|
-
|
+
|
+
|
-
|
|
Модуль “Выход”
|
+
|
+
|
+
|
+
|
+
|
|
Анимация
движения
|
+
|
+
|
+
|
-
|
+
|
|
Изображение
картинками
|
+
|
+
|
+
|
+
|
+
|
Как видно по результатам проведенного тестирования и опроса, результаты
тестирования программного средства, агентно-ориентированного моделирования
“Лабиринт агентов” можно считать успешными. Все тестовые эксперименты
закончились успехом и показали отличный результат работы программного средства.
По результатам опроса видно, что большинство разработанных модулей были
встречены хорошо, пользователями уже работавших с данным программным средством.
Оценки экспертов по каждому модулю превышают средние показатели, что
свидетельствует о хорошо разработанных модулях и их внедрении в программу
агентно-ориентированного моделирования “Лабиринт агентов”.
6.3
Руководство пользователя
Руководство пользователя является важнейшей частью разработки
программного средства, так как программой будут пользоваться не только
пользователи, которые уже знакомы с программой или же люди, хорошо владеющие
компьютером, а также люди у которых могут возникнуть трудности в понятии
интерфейса программного средства или самой программы.
Для запуска программы агентно-ориентированного моделирования “Лабиринт
агентов”, необходимо запустить специальный файл формата exe, который запустит программу. Файл
называется labirint.exe и представлен на рисунке 6.11
Рисунок 6.11 - Файл labirint.exe
После запуска файла labirint.exe открывается приветствующая форма
“Анкета”. На этой форме предлагается ввести имя пользователя или его псевдоним,
и выбрать будут ли сохранены результаты прошлых исследований или же они будут
удалены и в фалах будут сохранены только новые результаты. Кнопка “ОК” на форме
“Анкета” является изначально неактивной, только после выбора пользователя
сохранить результаты предыдущих экспериментов или не сохранять она становиться
активной, и пользователь сможет продолжить работу с программой. Пример формы
представлен на рисунке 6.12
Рисунок 6.12 - Форма “Анкета”
После формы “Анкета” пользователь попадает на главную форму программы
агентно-ориентированного моделирования “Лабиринт агентов”. На главной форме
приложения нас встречают два поля, на первом поле располагаются объекты
лабиринта, на втором поле располагаются агенты, которые ищут золото в
лабиринте, пример показан на рисунке 6.13. Так же на этой форме располагается
подсказка пользователю, если он будет расставлять объекты вручную, а не с
помощью компьютера, пример представлен на рисунке 6.14. Так же здесь находятся
такие кнопки как “Поиск”, “Очистить”, “Настройки”, “Статистика”, “Печать” и
“Выход”. Все кнопки за исключением “Печать”, “Выход” и “Настройки” неактивны,
они станут активны после того как мы настроим программу. Кнопка “Печать” печатает форму программы.
После настройки программы, пользователь вновь возвращается на главную
форму приложения “Лабиринт”. Здесь уже неактивные кнопки стали активными, а
также произошло заполнения поля объектами, если пользователь указал заполнения
поля компьютером. Пример заполненных полей представлен на рисунке 6.16. Теперь
пользователь может приступать к проведению экспериментов, для этого он должен
нажать кнопку “Поиск”. После нажатия кнопки поиск программа приступит к
выполнению поставленной задачи, а справа от поля будет можно увидеть результат
выполнения экспериментов. Пример представлен на рисунке 6.17. После проведения
экспериментов, пользователь может закрыть программы и исследовать файлы с
результатами экспериментов, которые сохраняются в корне программы в фалах short.txt и result.txt или же продолжить дальше проводить
эксперимент, для этого ему всего лишь необходимо нажать на кнопку “Возвращение
к исходному интерфейсу”.
Рисунок 6.13 - Поля программы
Рисунок 6.14 - Подсказка пользователю
При нажатии кнопки “Настройки” пользователь попадает на форму
“Настройки”, где он может настроить эксперименты так как пожелает. Выбрать
алгоритм поиска, заполнение поля, количество экспериментов и многое другое.
Пример формы “Настройки” представлен на рисунке 6.15
Рисунок 6.15 - Форма “Настройки”
Рисунок 6.16 - Заполненные поля лабиринта
Рисунок 6.17 - Результаты эксперимента
7. ОЦЕНКА КАЧЕСТВА РАЗРАБАТЫВАЕМОГО
ПРОДУКТА
Для программы агентного-моделирования “Лабиринт агентов” проведем оценку
качественных показателей. Для этого необходимо составить таблицу описания
оценок программного средства. Описание оценок программного средства
представлено в таблице 7.1
Таблица 7.1 - Описание оценок программного средства
|
Значение оценки
|
Описание
|
|
0 - 0,49
|
Свойство в
программном средстве присутствует, но его качество неприемлемо
|
|
0,5 - 0,9
|
Свойство в
программном средстве присутствует, обладает приемлемым качеством
|
|
0,91 - 1
|
Свойство в
программном средстве присутствует, обладает высоким качеством
|
Характеристика показателей качества программного средства представлена в
таблице 7.2.
Таблица 7.2 - Характеристика показателей программного средства
|
Показатели
качества
|
Сущность
показателя
|
Экспертная
оценка
|
Экспериментальная
оценка
|
|
1
|
2
|
3
|
4
|
|
Надежность
|
Свойство
программы непрерывно сохранять работоспособность
|
0,17
|
0,97
|
|
Эффективность
|
Характеризует
эффективность использования ПС
|
0,15
|
0,99
|
|
Время ответа
|
Характеризует
то, насколько быстро программа отвечает на воздействие
|
0,03
|
0,9
|
|
Рациональность
|
Свойство ПС,
характеризующее затрачиваемые им ресурсы ПК
|
0,09
|
0,94
|
Определим качество разработанного программного средства.
,
где Wi - вес показателя качества;
ri -
экспериментальная оценка;
n -
число показателей.
На основе данных таблицы 7.2 построим гистограмму распределения оценок по
интервалам. Гистограмма представлена на рисунке 7.1
Рисунок 7.1 - Гистограмма распределения оценок по интервалам
Оценим трудоемкость модернизации программы агентно-ориентированного
моделирования “Лабиринт агентов”. Для определения трудоемкости разработки
процесса просматриваются следующие этапы «Определение весовых показателей
действующих лиц», «Определение весовых показателей вариантов использования»,
«Определение технической сложности проекта», «Определение уровня квалификации
разработчиков», «Оценка трудоемкости проекта». Весовые коэффициенты действующих
лиц представлены в таблице 7.3
Таблица 7.3 - Весовые коэффициенты действующих лиц
|
Тип лица
|
Весовой
коэффициент
|
|
Простое
|
1
|
|
Среднее
|
2
|
|
Сложное
|
3
|
Типы действующих лиц программы агентно-ориентированного моделирования
“Лабиринт агентов” представлены в таблице 7.4
Таблица 7.4 - Типы действующих лиц для разрабатываемой системы
|
Действующие
лицо
|
Тип
|
|
Пользователь
|
Сложное
|
|
Агент
|
Сложное
|
|
Среда
|
Простое
|
Вычислим общий весовой показатель, умножая количество действующих лиц
каждого типа на соответствующий весовой коэффициент.
,
Весовые коэффициенты представлены в таблице 7.5
Таблица 7.5 - Весовые коэффициенты вариантов использования
|
Тип Варианта
использования
|
Описание
|
Весовой
коэффициент
|
|
Простой
|
3 или менее
транзакций
|
5
|
|
Средний
|
От 4 до 7 транзакций
|
10
|
|
Сложный
|
Более 7
транзакций
|
15
|
Сложность вариантов использования для программы агентно-ориентированного
моделирования “Лабиринт агентов” представлена в таблице 7.6.
Таблица 7.6 - Сложность вариантов использования для разработанной системы
|
Вариант
использования
|
Тип
|
|
Добавить
клиента
|
Средний
|
|
Редактировать
клиента
|
Средний
|
|
Удалить клиента
|
Простой
|
|
Поиск по
клиентам
|
Простой
|
|
Создать отчет
|
Простой
|
Общий весовой показатель вычисляется умножением количества вариантов
использования каждого типа на соответствующий весовой коэффициент. Общий
весовой показатель равен:
Рассчитаем показатель UUCP,
формула:
Техническая сложность проекта вычисляется с учетом показателей
технической сложности. Показатели технической сложности представлены в таблице
7.7
Таблица 7.7 - Показатели технической сложности
|
Показатель
|
Описание
|
Вес
|
|
T1
|
Распределенная
система
|
2
|
|
T2
|
Высокая
пропуск. способность
|
1
|
|
T3
|
Работа кон.
пол. в режиме on-line
|
1
|
|
T4
|
Сложная
обработка данных
|
1
|
|
T5
|
Повторное
использование кода
|
1
|
|
T6
|
Простота
установки
|
0,5
|
|
T7
|
Простота
использования
|
0,5
|
|
T8
|
Переносимость
|
2
|
|
T9
|
Простота
внесения изменений
|
1
|
|
T10
|
Параллелизм
|
1
|
|
T11
|
Специальные
требования к безопасности
|
1
|
|
T12
|
Непосредственный
доступ в систему со стороны внешних пользователей
|
1
|
|
T13
|
Специальные
требования к обучению пользователей
|
1
|
Показатели технической сложности для программы агентно-ориентированного
моделирования “Лабиринт агентов” представлены в таблице 7.8
Таблица 7.8 - Показатели технической сложности для рассматриваемой
системы
|
Показатель
|
Вес
|
Значение
|
Значение с
учетом веса
|
|
1
|
2
|
3
|
4
|
|
T1
|
2
|
2
|
4
|
|
T2
|
1
|
2
|
2
|
|
T3
|
1
|
3
|
3
|
|
T4
|
1
|
3
|
3
|
|
T5
|
1
|
4
|
4
|
|
T6
|
0.5
|
5
|
2,5
|
|
T7
|
0.5
|
5
|
2,5
|
|
T8
|
2
|
5
|
10
|
Продолжение таблицы 7.8 - Показатели технической сложности для
рассматриваемой системы
|
T9
|
1
|
3
|
3
|
|
T10
|
1
|
2
|
2
|
|
T11
|
1
|
2
|
2
|
|
T12
|
1
|
5
|
5
|
|
T13
|
1
|
1
|
1
|
|
Сумма
|
|
|
44
|
Техническая сложность проекта вычисляется по формуле:
Показатели уровня квалификации разработчиков представлены в таблице 7.9
Таблица 7.9 - Показатели уровня квалификации разработчика
|
Показатель
|
Описание
|
Вес
|
|
F1
|
Знакомство с
технологией
|
0.15
|
|
F2
|
Опыт разработки
приложений
|
0.5
|
|
F3
|
Опыт
использования объектно-ориентированного подхода
|
1
|
|
F4
|
Наличие
ведущего аналитика
|
0.5
|
|
F5
|
Мотивации
|
1
|
|
F6
|
Стабильность
требований
|
2
|
|
F7
|
Частичная
занятость
|
-1
|
|
F8
|
-1
|
Показатели уровня квалификации разработчиков для информационной системы
обслуживание клиентов книжного издательства представлены в таблице 7.10
Таблица 7.10 - Показатели уровня квалификации разработчика для
разрабатываемой системы
|
Показатель
|
Вес
|
Значение
|
Значение с
учетом веса
|
|
F1
|
1.5
|
3
|
4.5
|
|
F2
|
0.5
|
2
|
1
|
|
F3
|
1
|
2
|
2
|
|
F4
|
0.5
|
1
|
0.5
|
|
F5
|
1
|
5
|
5
|
|
F6
|
2
|
3
|
6
|
|
F7
|
-1
|
1
|
-1
|
|
F8
|
-1
|
2
|
-2
|
|
Сумма
|
|
|
16
|
Рассчитаем уровень квалификации разработчиков по формуле:
В результате получили показатель, формула:
Определим трудоемкость проекта. В качестве начального показателя возьмем
10 человека-часов. При рассмотрении показателей получаем 28 человека-часов.
Общее количество человека-часов на создание информационной системы равно 278,6,
это приблизительно 11-12 рабочих дней, если над проектом работает один человек.
ЗАКЛЮЧЕНИЕ
В выпускной квалификационной работе была проведена модернизация программы
агентно-ориентированного моделирования “Лабиринт агентов”.
Данная программа позволяет проводить эксперименты на основе
агентно-ориентированного моделирования, где агенты взаимодействуют со внешней
средой и друг с другом. Так как каждый построенный лабиринт индивидуален, то
вероятности повторения эксперимента практически нет, даже если будут
использоваться одинаковые настройки программы.
В пункте “Анализ алгоритмов и программных реализаций поведения агентов в
двумерной среде” описаны кто-же такие агенты, типовые задачи, связанные с
агентно-ориентированным моделированием и приведены примеры использования
агентов в различных сферах и программах. Так же проанализированы алгоритмы и
реализации поведения агентов в программе агентно-ориентированного моделирования
“Лабиринт агентов”.
В пункте “Разработка архитектуры программного комплекса “Лабиринт
агентов”” приведены требования и ограничения к программе
агентно-ориентированного моделирования “Лабиринт агентов”, так же приведена
структурная схема программы.
В пункте “Разработка структур данных и знаний для “Лабиринт агентов””
представлены данные программы и описаны действия над этими данными, так же
представлена база знаний программы.
В пункте “Разработка алгоритмов” представлены различные алгоритмы поиска,
их словесное описание и приведены рисунки блок-схем алгоритмов поиска.
В пункте “Разработка и реализация программных модулей” описаны все
программные модули, которые мы разработали, приведено их описание с
изображением работы данных модулей в программе, включая пример кода с
комментариями по каждому разработанному нами модулю.
В пункте “Экспериментальное тестирование и отладка программных модулей”
описаны модели надежности программного обеспечения, выбрана пара моделей для
проверки надежности нашей модернизированной программы, так же проведено
тестирования программы в два этапа и описано руководство пользователя.
В пункте “Оценка качества разрабатываемого продукта” проведена оценка
качественных показателей и оценка трудоемкости модернизации программы
агентно-ориентированного моделирования “Лабиринт агентов”.
Модернизированную программу можно внедрить в учебный процесс, для более
полного понимания агентов и агентно-ориентированного моделирования. В
дальнейшем данную программу можно доработать, добавив движение чудовища,
которое ищет агентов в то время как агенты ищут золото или выход из лабиринта.
Так же можно переписать данную программу на более популярные языки
программирования такие как C# или
Java. Используя нейронную сеть можно
попытаться разработать обучающихся агентов, которые в зависимости от количества
экспериментов, буду улучшать свой результат поиска золота, обучаясь после
каждого пройденного лабиринта.
СПИСОК
ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Девятков,
В.В. Системы искусственного интеллекта: пособие для вузов / В.В. Девятков.
-Москва: МГТУ, 2001. -352 с.
. Швецов,
А.Н. Мультиагентные системы: учебное пособие / А.Н. Швецов -Вологда: ВоГТУ,
2012. -110 с.
. Швецов,
А.Н. Агентно-ориентированные системы: основные модели монография / А.Н. Швецов
-Вологда: ВоГТУ, 2012. -190 с.
. Василенко
Н.В. Модель оценки надежности программного обеспечения / Н.В. Василенко, В.А.
Макаров. // Вестник Новгородского государственного университета им. Ярослава
Мудрого. 2004. -№28. -С. 126-132.
. Тарасов
В.Б. От многоагентных систем к интеллектуальным организациям: монография / В.Б.
Тарасов. - Москва: Эдиториал УРСС, 2002 - 352 с.
. Еременко
И.Ю. Интеллектуальные системы принятия решений и управления: монография / И.Ю.
Еременко. - Белгород: ТНТ, 2015. - 404 с.
. Гаврилова
Т.А. Базы знаний интеллектуальных систем: учебник для технических вузов / Т.А.
Гаврилова, В.Ф. Хорошевский.- Санкт-Петербург: Питер, 2000. - 384 с.
.
Архангельский, А.Я. Программирование в Delphi для Windows
А.Я. Архангельский. - Санкт-Петербург: Бином-Пресс, 2007. - 1248 с.
. Фленов,
М.А. Библия Delphi, 3-е издание / М.А. Фленов. -
Санкт-Петербург: БХВ-Петербург, 2011. - 300 с.
. Культин,
Н.В. Основы программирования в Embarcadero Delphi / Н.В.
Культин. - Москва: Интернет-издание, 2015. - 232 с.
. Коталевский
Д.Ю. Основы имитационного моделирования и системного анализа в управлении:
учебное пособие / Д.Ю. Коталевский. - Москва: МГУ, 2011. - 304 с.
. Осипов Д.Л.
Delphi. Профессиональное моделирование:
монография / Д.Л. Осипов. - Москва: Символ-плюс, 2006. - 1056 с.