В данной статье рассматривается процесс создания имитационной модели поведения муравьиной колонии (можно почитать в википедии ) в среде имитационного моделирования «AnyLogic». Данная статья носит практический характер. В ней будет рассмотрен вопрос применения муравьиного алгоритма для решения задачи о коммивояжёре (Почитать можно тут).
Суть задачи коммивояжере заключается в том, что коммивояжер (продавец) должен посетить N городов побывав в каждом из них только один раз по наикратчайшему маршруту. Так как данная задача является NP-сложной и количество вариантов всех возможных маршрутов между N городами вычисляется как «N!», то время поиска кратчайшего маршрута будет увеличиваться по экспоненциальному закону с увеличением значения N. Соответственно время поиска кратчайшего маршрута(решения) с использованием алгоритма «полного перебора» (который дает точное решение) при количестве городов N>16 резко увеличивается (носит экспоненциальный характер). Поэтому мы будем искать не самый короткий по протяженности маршрут, а близкий к нему (рациональный) за конечное время с помощью «муравьиного алгоритма».
Немного слов о AnyLogic – это мощный инструмент позволяющий создавать имитационные модели различной сложности. В нем заложены различные подходы имитационного моделирования. Мы с Вами будем разбирать только один из подходов а именно «Агентное» моделирование. Реализован он на языке программирования «Java», который дополняет существующий инструментарий. Главным недостатком «AnyLogic» является ограничения бесплатной версии по количеству создаваемых агентов их количество не может быть более 50000. «Агент» – является базовой единицей системы имитационного моделирования AnyLogic. Более подробную информацию можно прочитать на сайте www.anylogic.ru
1. Anylogic – качаем бесплатную версию вот отсюда www.anylogic.ru/downloads
Первоначальное знакомство AnyLogic:
Интерфейс AnyLogic представлен на рисунке 1. Он в себя включает:
Рис. 1- Рабочее окно AnyLogic
Тут все просто. Жмем на пункт меню «Файл» далее «Создать» и далее «Модель» вводим имя модели и жмем кнопку «Готово» (рис. 2).
Рис. 2- Создание модели
Ну что, приступим. Первое что, мы сделаем так это создадим так называемые города(вершины графа), которые будет посещать муравей посещать. Для чего открываем в палитре вкладку «Агент» и перетаскиваем оттуда красный кружочек с человечком в «Main» агента как это показано на рисунке 3.
Рис. 3- Создание городов
После того как вы отпустите кнопку мыши у Вас появиться диалоговое окно («Шаг 1»), предлагающее Вам создать агента. Где необходимо будет выбрать пункт «Популяция агентов» и нажать на кнопу «Далее».
Рис. 4- Создание городов
Появиться следующее диалоговое окно (Шаг 2) где необходимо будет ввести имя нового типа агента и имя популяции агентов. Вводим тип «MyTown» и имя популяции «myTowns» и жмем на кнопку «Далее».
Рис. 4а — Вводим имя нового агента
Далее появится следующие окно (Шаг 4.). Здесь выбираем «Анимация агента 2D» и иконку с надписью «Завод» и нажимаем кнопку «Готово» (рис. 5).
Рис. 5- Добавляем анимацию для агента
Теперь создадим переменную, которая будет определять начальное количество городов в нашей модели. Для чего из «Палитры» перетаскиваем в агент «Main» иконку с надписью «Переменная» и вводим ее название «numberTown». Далее нажимаем на иконку нашей переменной и во вкладке Свойства вводим ее начальное значение равное, например 10 и выбираем ее тип «int» (рис. 6).
Рис. 6- Создание переменной
Теперь установим начальное значение нашей популяции городов «myTowns», для чего нажмем мышкой на ее иконку и во вкладке «Свойства» в поле «Начальное количество агентов» напишем имя созданной ранее нами переменной (рис. 7).
Рис. 7 – Изменение свойств популяции «myTowns»
Далее сделаем вывод наших городов в агенте «Main» в случайном месте. Место ограничим квадратом 400x400 точек. Для чего во вкладке «Проекты» выбираем мышкой агент «Main» и во вкладке «Свойства» в поле «При запуске» добавляем следующий код на «Java» (рис. 7а):
Где:
Где:
Рис. 7а – Расставляем города
Далее можем уже посмотреть, что у нас с Вами получилось и запустить нашу модель. Для этого используем клавишу «F5», жмем ее и запускается окно для запуска эксперимента как показано на рисунке 8.
Рис. 8 – Запуск эксперимента
Далее нажимаем на кнопку «Запустить» в нижнем левом углу окна и происходит запуск эксперимента. У Вас на экране должно получиться окно с содержимым как показано на рисунке 9.
Рис. 9 – Результат эксперимента
Итак, на данном шаге мы создали 10 городов и разместили их в случайном (стохастическом) месте на нашем экране. Теперь перейдем к созданию наших «муравьев»
Итак, основной боевой единицей нашей модели будет муравей. Мы должны, во-первых, его создать, а потом смоделировать его поведение.
Создание муравья происходит аналогично создания города. В «Палитре» выбираем «Агент» и перетаскиваем его в «Main». Выбираем «Популяция агентов», потом «Я хочу создать новый тип агента» далее вводим «Имя нового типа» и «Имя популяции» «MyAnt» «myAnts» и жмем «Далее». После выбираем «2D» анимация и, например иконку с надписью «Истребитель» жмем «Готово» должно получиться как показано на рисунке 10.
Рис. 10 – Создаем муравьев
Согласитесь, самолетик не похож на муравья, поэтому мы с Вами это исправим. Заходим в поисковик ищем картинку, на которой изображен муравей и меняем самолет на муравья. Для чего выполняем двойное нажатие на красный кружок возле «myAnts». После чего откроется вкладка «myAnt» где нужно удалить самолет и на его место поместить муравья (рис. 11).
Рис. 11 – Вкладка myAnt
Выделяем мышкой самолет и жмем «Del». Далее переходим во вкладку «Презентация» и перетаскиваем оттуда элемент «Изображение». После автоматически откроется диалог для выбора файла. Выбираем файл с нашим муравьем (рис. 12) и жмем «Ок».
Рис. 12 – Вкладка myAnt с муравьем и уже без самолета
Идем дальше. Выполняем масштабирование муравья и перемещаем его на место, где был когда-то самолет. Должно получиться как показано на рисунке 12а. Все эти операции выполняются с помощь мыши.
Рис. 12а – Вкладка myAnt с муравьем
Теперь нужно научить нашего свежеиспеченного муравья ползать между городами. Правда пока без учета математической модели, но все же пускай побегает. И так, открываем в «Палитре» диаграмму «Диаграмма состояний» и приступаем. Переносим следующие блоки и соединяем их между собой:
В итоге должно получиться, что-то типа как показано на рисунке 13.
Рис. 13 – Логика поведения муравья
Теперь давайте пропишем начальную логику работы диаграммы муравья. Выбираем мышкой стрелочку, которая выходит из блока под название «Выбор города» и добавляем во вкладке «Свойства» в поле «Действие» следующий код (рис. 14):
Тут все очень просто идем в цикле по всем городам и подбрасываем монету (генерируем случайную величину с вероятность. 0,5) если ее значение истина (орел), то отправляем муравья к этому городу покидая цикл. Выражение «this.moveTo(main.myTowns.get(i))» — функция, которая отправляет одного агента к другому.
Рис. 14 – Задаем первоначальную логику движения муравья
Далее жмем на стрелочку, которая выходит из блока «Движение» и во вкладке «Свойства» в поле «Происходит» установим значение «При получении сообщения» и выбираем пункт «При получении заданного сообщения» в поле «Происходит» как показано на рисунке 15.
Рис. 15 – Задаем логику для перехода между «Движение» и «Все обошел»
Теперь настроим последнюю стрелочку, которая выходит из блока «Движение». Выбираем ее мышкой и во вкладке «Свойства» в поле переход устанавливаем «По прибытию агента». Конечный вид «Диаграммы состояний» должен быть как показано на рисунке 16.
Рис. 16 – Диаграмма состояний с настроенными переходами между блоками
Итак, давайте разберем как работает «Диаграмма состояний» поведения муравья:
Рис. 17 – Работа диаграммы состояний
Теперь можем нажать «F5» по посмотреть, что получилось (рис. 18).
Рис. 18 – Оживление муравьев
Итак, что же это за критерии(правила):
Эти критерии диктует нам условием задачи о коммивояжере. Каждый муравей будет у нас с Вами своего рода коммивояжером, который путешествует по городам.
Давайте научим муравья соблюдать эти правила. Для чего из «Палитры» вкладка «Агент» перенесем на вкладку «MyAnt» «Коллекцию» и «Переменную» и назовем их первую как «isVisited» а вторую как «distance». В первой будет учитывать города, в которых мы уже побывали, а во второй пройденное расстояние муравьем.
Рис. 19 – Добавляем переменные
Настроим коллекцию «isVisited». Для чего выбираем ее мышкой и во вкладке «Свойства» устанавливаем «Тип» элементов «int» как показано на рисунке 20.
Для переменной «distance» в ее свойствах в поле «Начальное значение» нужно поставить «0», а тип переменной «double».
Рис. 20 – Коллекция типа «int»
Теперь выбираем стрелочку, выходящую из блока «Выбор_города» и меняем код в поле «Действие» на ниже приведенный:
В коде выше мы добавили проверку на города, в которых уже успели побывать и учет городов, которые посетили, а также считаем пройденное расстояние. Код довольно простой я думаю Вам будет не трудно разобраться.
Можете попробовать запустить «F5» нашу модель и посмотреть, что же получилось. Теперь муравьи будут проходить по всем городам только один раз и завершать свое движение в блоке все обошел.
На этом шаге определим для каждого муравья случайным образом выберем город, с которого он начнет свое путешествие. Для чего на вкладке «Проекты» выбираем мышкой агент «Main» после чего во вкладке «Свойства» добавляем в поле «При запуске» следующий код (рис. 20а):
Рис. 20а – Расставляем муравьев по городам
Я применил случайный выбор начального города. Вы же можете изначально определить всех муравьев только в один город.
Внедрим в нашу модель формулу, приведенную ниже:
где Pi — вероятность перехода по пути i-му пути, li — длина i-го перехода, fi — количество феромона на i-ом переходе, q — величина, определяющая «жадность» алгоритма, p — величина, определяющая «стадность» алгоритма, при этом q+p=1.
Данную формула я позаимствовал с сайта.
Говоря простым языком, данная формула позволяет вычислить вероятность, с которой муравей должен будет осуществить переход в тот или иной город.
Теперь нужно добавить несколько переменных без которых нам не обойтись. Для чего возвращаемся обратно во вкладку «Main» рисунок 21.
Рис. 21 – Вкладка «Main»
Итак, добавляем переменную «numberAnt», в которой будем хранить размер муравьиной колонии. Устанавливаем ее тип «int» и начальное значение равное 100.
Рис. 21 – Переменная «numberAnt»
Далее выбираем популяцию «myAnts» и устанавливаем поле «Начальное количество агентов» равным «numberAnt».
Переменную «p», которая будет определять стадность алгоритма. Ее тип «double» и начальное значение равное 0.5.
Переменную «q», которая будет определять жадность алгоритма. Ее тип «double» и начальное значение равное 0.5.
Рис. 22 – Переменные «q и p»
Итак, теперь зададим случайное значение феромона для каждого ребра(дороги) между городами. Для чего создаем переменную (двумерный массив) «matrixF». Установим у нее во вкладке «Свойствах» в поле «Тип» выбираем значение «Другой» и прописываем «double[][]» в поле начальное значение «new double[numberTown][numberTown]» (рис. 23).
Рис. 23 – Создание двумерного массива «matrixF». Матрица феромонов
Далее нам необходимо инициализировать данную матрицу. Другими словами, заполнить ее случайными значениями. Значение феромона возьмём случайным образом в интервале от 0,1 до
1. Для чего на вкладке «Проекты» выбираем мышкой агент «Main» и после во вкладке «Свойства» добавляем в поле «При запуске» следующий код (рис. 23а):
Рис. 23а – Код инициализации матрицы феромонов
Теперь возвращаемся во вкладку «MyAnt» и приступаем к вычислению вероятности перехода в соответствии с вышеприведенной формулой. Выделяем переход между «Выбор_города» и «Движение» и меняем код в поле Действие на следующий (рис. 24):
Рис. 24 – Задаем поведение муравья на основе аналитического выражения приведенного выше
Так теперь немного поясню что к чему:
Далее выбираем мышкой переход между блоками «Движение» и «Все_обошел» и в поле «Происходит» выбираем значение «При выполнении условия» а в поле условие пишем условие остановки муравья «isVisited.size()==main.myTowns.size()» (рис. 25).
Рис. 25 – Определяем условия остановки муравья
Далее можете запустить «F5» модель и посмотреть, что получилось. Муравьи будут путешествовать между городами с вероятностью, рассчитанной согласно приведенному выше аналитическому выражению.
Теперь давайте выполним два действия. Первое действие заключается в увеличении значения феромона на ребре между городами, по которому прошел муравей. Второе в испарении феромона на ребрах между городами, которое заключается в уменьшении значения феромонов относительно времени моделирования.
Итак, для начала к первому действию, будем обновлять значение феромона ребра, между городом в котором находится муравей и в которой ему предстоит отправиться. Величину, на которую будем увеличивать текущее значение феромона ребра между городами будем вычислять очень и очень просто. Берем нашу максимальную начальную величину значения феромона = 1 у.е. и делим ее на расстояние между городом, в котором находится муравей и городом куда он собирается отправится. Соответственно, чем меньше расстояние, между городами тем больше составит значение, на которое будет увеличен уровень феромона ребра. Для чего выбираем во вкладке «Проекты» агент «MyAnt» выбираем мышкой переход между блоками «Выбор_города» и «Движение» и в поле действие добавляем следующий код «main.matrixF[currentPos][i]=main.matrixF[currentPos][i]+1/this.distanceTo(main.myTowns.get(i);». В итоге должно получаться как показано на рисунке 26
Рис. 26 – Обновляем значение уровня феромонов ребер, по которым прошел муравей
Теперь перейдем к действия №2 и создадим событие, которое будет имитировать испарение феромона на ребрах между городами. Для чего во вкладке проекты выбираем агента «Main» и создаем там еще пару переменных. Первая это «intensity» — будет определять скорость(интенсивность) испарения феромона (Начальное значение «0.5» тип «double»). Вторая «Part» — будет характеризовать долю, на которую будет уменьшаться значение феромона на ребре (Начальное значение «0.9» тип «double»).
Рис. 27 – Создаем переменные «intensity» и «Part»
Далее берем из «Палитры» вкладки «Агент» элемент «Событие» и переносим его в агент «Main» и называем его «evaporation» — этот элемент будет имитировать испарение феромона на ребрах. Жмем на него мышкой и в «Свойствах» в поле «Тип события» выбираем значение «С заданной интенсивностью» в поле «Интенсивность» прописываем имя переменной, которая хранит значение интенсивности «intensity». Время срабатывания оставляем секунды. Далее в действие добавляем код, приведенный ниже:
При срабатывании события «evaporation» будут обновляться значения уровня феромона в матрице matrixF. В итоге у Вас должно получаться так как показано на рисунке 28.
Рис. 28 – Создаем событие «evaporation»
На этом шаге допишем код, который будет определять победителя нашего муравьиного марафона. Победителем будет тот из муравьев, который пробежал по протяженности самый короткий маршрут. В дополнение ко всему после окончания марафона начертим этот маршрут на экране. Для достижения этой цели создадим в агенте «Main» три переменные «bestAnt», «bestDistance» и «numberFinish». В переменной «bestAnt» мы будем хранить индекс самого «быстрого» муравья, тип переменной будет «int» а начальное значение установим «-1». В переменной «bestDistance» будем хранить текущее значение наилучшего по протяженности маршрута между городами, тип переменной будет «double» а начальное значение установим равным бесконечности «infinity». В переменной «numberFinish» будем хранить количество муравьев, которые финишировали в нашем марафоне, тип переменной будет «int» а начальное значение равно «0» (рис. 29).
Рис. 29 – Создаем событие переменных
Далее создадим функцию, которая после финиширования всех муравьев будет рисовать линии наилучшего маршрута между городами. Для чего из «Палитры» перетаскиваем в агент «Main» элемент с названием функция. Имя функции устанавливаем drawPath и во вкладке «Свойства» в поле тело функции добавляем следующий код:
В итоге у Вас должно получиться так как показано на рисунке 29а.
Рис. 29а – Создаем функцию «drawPath»
Теперь возвращаемся обратно к нашим муравьям и дописываем код, который будет определять муравья победителя, протяженность наилучшего маршрута и рисовать этот маршрут между городами. Для чего во вкладе «Проекты» выбираем агента «MyAnt» далее выбираем блок «Все_обошел» и добавляем в поле «Действие при входе» нижеприведенный код:
Должно получиться как показано на рисунке 30.
Рис. 30 – Добавление логики в блок «Все_обошел»
После чего можете нажать «F5» и запустить модель. Муравьи будут бегать искать маршруты, а когда финишируют города соединит синяя линия, которая и есть наилучший маршрут.
Для того чтобы модель стала более научной нужно обязательно добавить график. Поэтому мы с Вами добавим не просто график и гистограмму, которая будет показывать нам распределение протяженности маршрутов, которые преодолели муравьи. Для чего во вкладке «Проекты» выбираем агента «Main» и переходим в его пространство. Далее В «Палитре» переходим во вкладку «Статистика» и оттуда в агент «Main» переносим элемент «Данные гистограммы» и непосредственно саму «Гистограмму». Потом выбираем мышкой гистограммы и во вкладке «Свойства» в поле «Данные» прописываем имя наших «Данных гистограммы» т.е. «data».
Должно получиться как показано на рисунке 31
Рис. 31 – Строим график
После чего нам придется опять вернуться к нашему муравью и заставить его наполнять «Гистограмму» значениями протяженности маршрута. Для чего во вкладке проекты выбираем агента «MyAnt» и переходим в его пространство. Далее выбираем блок «Все_обошел» и добавляем в него одну строчку «main.data.add(distance);». Должно получиться как показано на рисунке 32.
Рис. 32 – Строим график
Далее нажимает «F5» и приступаете к исследованию поведения муравьиного алгоритма. Должно получиться что, то вроде как показано на рисунке 33.
Рис. 33 – Моделируем
И в конце рекомендую добавить в модель еще больше непредсказуемости. Для чего во вкладке «Проекты» выбираете мышкой элемент «Simulation: Main» и во вкладке свойства устанавливаете параметр «Случайность» в положение «Случайное начальное число (уникальные прогоны)» — это позволит каждый запуск модели сделать уникальным (рис. 34).
Рис. 34 – Делаем случайными прогоны
Спасибо за внимание! Исходный код можно скачать с GitHub
Кратко о сути
Суть задачи коммивояжере заключается в том, что коммивояжер (продавец) должен посетить N городов побывав в каждом из них только один раз по наикратчайшему маршруту. Так как данная задача является NP-сложной и количество вариантов всех возможных маршрутов между N городами вычисляется как «N!», то время поиска кратчайшего маршрута будет увеличиваться по экспоненциальному закону с увеличением значения N. Соответственно время поиска кратчайшего маршрута(решения) с использованием алгоритма «полного перебора» (который дает точное решение) при количестве городов N>16 резко увеличивается (носит экспоненциальный характер). Поэтому мы будем искать не самый короткий по протяженности маршрут, а близкий к нему (рациональный) за конечное время с помощью «муравьиного алгоритма».
Немного слов о AnyLogic – это мощный инструмент позволяющий создавать имитационные модели различной сложности. В нем заложены различные подходы имитационного моделирования. Мы с Вами будем разбирать только один из подходов а именно «Агентное» моделирование. Реализован он на языке программирования «Java», который дополняет существующий инструментарий. Главным недостатком «AnyLogic» является ограничения бесплатной версии по количеству создаваемых агентов их количество не может быть более 50000. «Агент» – является базовой единицей системы имитационного моделирования AnyLogic. Более подробную информацию можно прочитать на сайте www.anylogic.ru
Инструменты
1. Anylogic – качаем бесплатную версию вот отсюда www.anylogic.ru/downloads
Первоначальное знакомство AnyLogic:
Интерфейс AnyLogic представлен на рисунке 1. Он в себя включает:
- зеленая область – пространство агента, в котором мы как раз и будем творить;
- красная область – свойства объекта, который находится в фокусе;
- палитра – инструменты, которые можете использовать при создании модели;
- проекты – структура разрабатываемой модели.
Рис. 1- Рабочее окно AnyLogic
Создание проекта
Тут все просто. Жмем на пункт меню «Файл» далее «Создать» и далее «Модель» вводим имя модели и жмем кнопку «Готово» (рис. 2).
Рис. 2- Создание модели
Создаем города
Ну что, приступим. Первое что, мы сделаем так это создадим так называемые города(вершины графа), которые будет посещать муравей посещать. Для чего открываем в палитре вкладку «Агент» и перетаскиваем оттуда красный кружочек с человечком в «Main» агента как это показано на рисунке 3.
Рис. 3- Создание городов
После того как вы отпустите кнопку мыши у Вас появиться диалоговое окно («Шаг 1»), предлагающее Вам создать агента. Где необходимо будет выбрать пункт «Популяция агентов» и нажать на кнопу «Далее».
Рис. 4- Создание городов
Появиться следующее диалоговое окно (Шаг 2) где необходимо будет ввести имя нового типа агента и имя популяции агентов. Вводим тип «MyTown» и имя популяции «myTowns» и жмем на кнопку «Далее».
Рис. 4а — Вводим имя нового агента
Далее появится следующие окно (Шаг 4.). Здесь выбираем «Анимация агента 2D» и иконку с надписью «Завод» и нажимаем кнопку «Готово» (рис. 5).
Рис. 5- Добавляем анимацию для агента
Теперь создадим переменную, которая будет определять начальное количество городов в нашей модели. Для чего из «Палитры» перетаскиваем в агент «Main» иконку с надписью «Переменная» и вводим ее название «numberTown». Далее нажимаем на иконку нашей переменной и во вкладке Свойства вводим ее начальное значение равное, например 10 и выбираем ее тип «int» (рис. 6).
Рис. 6- Создание переменной
Теперь установим начальное значение нашей популяции городов «myTowns», для чего нажмем мышкой на ее иконку и во вкладке «Свойства» в поле «Начальное количество агентов» напишем имя созданной ранее нами переменной (рис. 7).
Рис. 7 – Изменение свойств популяции «myTowns»
Далее сделаем вывод наших городов в агенте «Main» в случайном месте. Место ограничим квадратом 400x400 точек. Для чего во вкладке «Проекты» выбираем мышкой агент «Main» и во вкладке «Свойства» в поле «При запуске» добавляем следующий код на «Java» (рис. 7а):
for (int i=0; i<myTowns.size(); i++) {
myTowns.get(i).setXY(uniform(0,400), uniform(0,400));
}
Где:
- myTowns.size() – количество созданных городов;
- myTowns.get(i).setXY(uniform(0,400), uniform(0,400)) – устанавливаем координаты X и Y для i-го города;
- uniform(0,400) – функция, которая возвращает случайное число в диапазоне от 0 до 400 по равновероятному закону распределения случайной величины. В среде AnyLogic заложен обширный инструментарий для работы с различными распределениями случайных величин. Есть встроенный конструктор распределений вероятностей он доступен в панели инструментов.
Где:
- myTowns.size() – количество созданных городов;
- myTowns.get(i).setXY(uniform(0,400), uniform(0,400)) – устанавливаем координаты X и Y для i-го города;
- uniform(0,400) – функция, которая возвращает случайное число в диапазоне от 0 до 400 по равновероятному закону распределения случайной величины. В среде AnyLogic заложен обширный инструментарий для работы с различными распределениями случайных величин. Есть встроенный конструктор распределений вероятностей он доступен в панели инструментов под вот такой иконкой.
Рис. 7а – Расставляем города
Далее можем уже посмотреть, что у нас с Вами получилось и запустить нашу модель. Для этого используем клавишу «F5», жмем ее и запускается окно для запуска эксперимента как показано на рисунке 8.
Рис. 8 – Запуск эксперимента
Далее нажимаем на кнопку «Запустить» в нижнем левом углу окна и происходит запуск эксперимента. У Вас на экране должно получиться окно с содержимым как показано на рисунке 9.
Рис. 9 – Результат эксперимента
Итак, на данном шаге мы создали 10 городов и разместили их в случайном (стохастическом) месте на нашем экране. Теперь перейдем к созданию наших «муравьев»
Создадим муравья
Итак, основной боевой единицей нашей модели будет муравей. Мы должны, во-первых, его создать, а потом смоделировать его поведение.
Создание муравья происходит аналогично создания города. В «Палитре» выбираем «Агент» и перетаскиваем его в «Main». Выбираем «Популяция агентов», потом «Я хочу создать новый тип агента» далее вводим «Имя нового типа» и «Имя популяции» «MyAnt» «myAnts» и жмем «Далее». После выбираем «2D» анимация и, например иконку с надписью «Истребитель» жмем «Готово» должно получиться как показано на рисунке 10.
Рис. 10 – Создаем муравьев
Согласитесь, самолетик не похож на муравья, поэтому мы с Вами это исправим. Заходим в поисковик ищем картинку, на которой изображен муравей и меняем самолет на муравья. Для чего выполняем двойное нажатие на красный кружок возле «myAnts». После чего откроется вкладка «myAnt» где нужно удалить самолет и на его место поместить муравья (рис. 11).
Рис. 11 – Вкладка myAnt
Выделяем мышкой самолет и жмем «Del». Далее переходим во вкладку «Презентация» и перетаскиваем оттуда элемент «Изображение». После автоматически откроется диалог для выбора файла. Выбираем файл с нашим муравьем (рис. 12) и жмем «Ок».
Рис. 12 – Вкладка myAnt с муравьем и уже без самолета
Идем дальше. Выполняем масштабирование муравья и перемещаем его на место, где был когда-то самолет. Должно получиться как показано на рисунке 12а. Все эти операции выполняются с помощь мыши.
Рис. 12а – Вкладка myAnt с муравьем
Оживляем муравья
Теперь нужно научить нашего свежеиспеченного муравья ползать между городами. Правда пока без учета математической модели, но все же пускай побегает. И так, открываем в «Палитре» диаграмму «Диаграмма состояний» и приступаем. Переносим следующие блоки и соединяем их между собой:
- Начало диаграммы состояний – это отправная точка жизненного цикла нашего муравья;
- Состояние – это блок будет характеризовать состояния жизненного цикла нашего муравья. Таких блоков потребуется у штуки.
- Переход – стрелочка, которая будет соединять между собой наши «Состояния» и выполнять переход из одного «Состояния» в другое «Состояние» при выполнении определенных условий.
В итоге должно получиться, что-то типа как показано на рисунке 13.
Рис. 13 – Логика поведения муравья
Теперь давайте пропишем начальную логику работы диаграммы муравья. Выбираем мышкой стрелочку, которая выходит из блока под название «Выбор города» и добавляем во вкладке «Свойства» в поле «Действие» следующий код (рис. 14):
for (int i=0; i<main.myTowns.size(); i++) {
if (randomTrue(0.5)) {
this.moveTo(main.myTowns.get(i));
break;
}
}
Тут все очень просто идем в цикле по всем городам и подбрасываем монету (генерируем случайную величину с вероятность. 0,5) если ее значение истина (орел), то отправляем муравья к этому городу покидая цикл. Выражение «this.moveTo(main.myTowns.get(i))» — функция, которая отправляет одного агента к другому.
Рис. 14 – Задаем первоначальную логику движения муравья
Далее жмем на стрелочку, которая выходит из блока «Движение» и во вкладке «Свойства» в поле «Происходит» установим значение «При получении сообщения» и выбираем пункт «При получении заданного сообщения» в поле «Происходит» как показано на рисунке 15.
Рис. 15 – Задаем логику для перехода между «Движение» и «Все обошел»
Теперь настроим последнюю стрелочку, которая выходит из блока «Движение». Выбираем ее мышкой и во вкладке «Свойства» в поле переход устанавливаем «По прибытию агента». Конечный вид «Диаграммы состояний» должен быть как показано на рисунке 16.
Рис. 16 – Диаграмма состояний с настроенными переходами между блоками
Итак, давайте разберем как работает «Диаграмма состояний» поведения муравья:
- Первое состояние, в которое попадает муравей это «Выбор_города» в нем пока никаких действий не прописано.
- Далее он по переходу идет в следующее состояние. В этом переходе мы добавили код, который запускает цикл по всем горам и заставляет муравьев бегать по городам.
- Блок «Движение» тут муравей находится пока не прибудет в ранее выбранный город.
- Далее у него есть два пути. Первый он возвращается обратно в блок «Выбор_города» и все повторяется заново. По второму пути он должен будет пойти, когда уже побывал во всех городах. Пока второй путь у нас не настроен. Займемся им чуть позже.
Рис. 17 – Работа диаграммы состояний
Теперь можем нажать «F5» по посмотреть, что получилось (рис. 18).
Рис. 18 – Оживление муравьев
Зададим критерии
Итак, что же это за критерии(правила):
- Муравей должен побывать в каждом городе только один раз.
- Муравей, когда побывал во всех городах завершает свое движение в последнем городе.
Эти критерии диктует нам условием задачи о коммивояжере. Каждый муравей будет у нас с Вами своего рода коммивояжером, который путешествует по городам.
Давайте научим муравья соблюдать эти правила. Для чего из «Палитры» вкладка «Агент» перенесем на вкладку «MyAnt» «Коллекцию» и «Переменную» и назовем их первую как «isVisited» а вторую как «distance». В первой будет учитывать города, в которых мы уже побывали, а во второй пройденное расстояние муравьем.
Рис. 19 – Добавляем переменные
Настроим коллекцию «isVisited». Для чего выбираем ее мышкой и во вкладке «Свойства» устанавливаем «Тип» элементов «int» как показано на рисунке 20.
Для переменной «distance» в ее свойствах в поле «Начальное значение» нужно поставить «0», а тип переменной «double».
Рис. 20 – Коллекция типа «int»
Теперь выбираем стрелочку, выходящую из блока «Выбор_города» и меняем код в поле «Действие» на ниже приведенный:
for (int i=0; i<main.myTowns.size(); i++) {
if (randomTrue(0.9) && isVisited.indexOf(i)==-1) {
this.moveTo(main.myTowns.get(i));
distance=distance+this.distanceTo(main.myTowns.get(i));
isVisited.add(i);
break;
}
}
В коде выше мы добавили проверку на города, в которых уже успели побывать и учет городов, которые посетили, а также считаем пройденное расстояние. Код довольно простой я думаю Вам будет не трудно разобраться.
Можете попробовать запустить «F5» нашу модель и посмотреть, что же получилось. Теперь муравьи будут проходить по всем городам только один раз и завершать свое движение в блоке все обошел.
Меняем первоначальное размещение муравьев
На этом шаге определим для каждого муравья случайным образом выберем город, с которого он начнет свое путешествие. Для чего на вкладке «Проекты» выбираем мышкой агент «Main» после чего во вкладке «Свойства» добавляем в поле «При запуске» следующий код (рис. 20а):
for (int i=0; i<myAnts.size(); i++) {
// Случайным образом выбираем город от куда начнем путешествие
int startTown = uniform_discr(0,myTowns-1);
// Перемещаем муравья в выбранный город
myAnts.get(i).setPosition(myTowns.get(startTown));
// Добавляем выбранный город в список посещенных
myAnts.get(i).isVisited.add(startTown);
}
Рис. 20а – Расставляем муравьев по городам
Я применил случайный выбор начального города. Вы же можете изначально определить всех муравьев только в один город.
Делаем муравьев непредсказуемыми
Внедрим в нашу модель формулу, приведенную ниже:
где Pi — вероятность перехода по пути i-му пути, li — длина i-го перехода, fi — количество феромона на i-ом переходе, q — величина, определяющая «жадность» алгоритма, p — величина, определяющая «стадность» алгоритма, при этом q+p=1.
Данную формула я позаимствовал с сайта.
Говоря простым языком, данная формула позволяет вычислить вероятность, с которой муравей должен будет осуществить переход в тот или иной город.
Теперь нужно добавить несколько переменных без которых нам не обойтись. Для чего возвращаемся обратно во вкладку «Main» рисунок 21.
Рис. 21 – Вкладка «Main»
Итак, добавляем переменную «numberAnt», в которой будем хранить размер муравьиной колонии. Устанавливаем ее тип «int» и начальное значение равное 100.
Рис. 21 – Переменная «numberAnt»
Далее выбираем популяцию «myAnts» и устанавливаем поле «Начальное количество агентов» равным «numberAnt».
Переменную «p», которая будет определять стадность алгоритма. Ее тип «double» и начальное значение равное 0.5.
Переменную «q», которая будет определять жадность алгоритма. Ее тип «double» и начальное значение равное 0.5.
Рис. 22 – Переменные «q и p»
Итак, теперь зададим случайное значение феромона для каждого ребра(дороги) между городами. Для чего создаем переменную (двумерный массив) «matrixF». Установим у нее во вкладке «Свойствах» в поле «Тип» выбираем значение «Другой» и прописываем «double[][]» в поле начальное значение «new double[numberTown][numberTown]» (рис. 23).
Рис. 23 – Создание двумерного массива «matrixF». Матрица феромонов
Далее нам необходимо инициализировать данную матрицу. Другими словами, заполнить ее случайными значениями. Значение феромона возьмём случайным образом в интервале от 0,1 до
1. Для чего на вкладке «Проекты» выбираем мышкой агент «Main» и после во вкладке «Свойства» добавляем в поле «При запуске» следующий код (рис. 23а):
for (int i=0; i<myTowns.size(); i++) {
for (int j=0; j<myTowns.size(); j++) {
matrixF[i][j]=uniform(0.1,1);
}
}
Рис. 23а – Код инициализации матрицы феромонов
Теперь возвращаемся во вкладку «MyAnt» и приступаем к вычислению вероятности перехода в соответствии с вышеприведенной формулой. Выделяем переход между «Выбор_города» и «Движение» и меняем код в поле Действие на следующий (рис. 24):
// Объявляем переменную где будем хранить значение знаменателя
double denominator=0;
// Рассчитываем значение знаменателя для городов где муравей еще не был
for (int i=0; i<main.myTowns.size(); i++) {
if (isVisited.indexOf(i)==-1) { // Если города нет в списке
// Вычисляем i значение значение знаменателя
denominator=denominator+(Math.pow(this.distanceTo(main.myTowns.get(i)), main.q)*Math.pow(main.myTowns.get(i).f, main.p));
}
}
// Объявляем переменную для расчета значение i перехода
double Pi=0;
// Рассчитываем текущее значение вероятности
double probility=uniform(0,1);
for (int i=0; i<main.myTowns.size(); i++) {
// Если города нет в списке рассчитываем вероятность Pi
if (isVisited.indexOf(i)==-1) {
// Рассчитываем текущее значение для i-го перехода и суммируем с предыдущими значениями
Pi=Pi+(Math.pow(this.distanceTo(main.myTowns.get(i)), main.q)*Math.pow(main.myTowns.get(i).f, main.p))/denominator;
}
// Проверяем попало ли расчетное значение Pi в диапазон текущего значения вероятности probility
if (probility<Pi && isVisited.indexOf(i)==-1) {
// Если да то отправляем муравья к i му городу
this.moveTo(main.myTowns.get(i));
// Обновляем значение протяженности пройденного маршрута
distance=distance+this.distanceTo(main.myTowns.get(i));
// Добавляем город в список городов в которых муравей уже успел побывать
isVisited.add(i);
break;
}
}
Рис. 24 – Задаем поведение муравья на основе аналитического выражения приведенного выше
Так теперь немного поясню что к чему:
- li — this.distanceTo(main.myTowns.get(i)), значение протяженности между текущем положением муравья и «i» городом;
- fi — main.matrixF[currentPos][i], значение уровня феромона между текущем городом и городом «i»;
- denominator – denominator+(Math.pow(this.distanceTo(main.myTowns.get(i)), main.q)*Math.pow(main.matrixF[currentPos][i], main.p));, значение знаменателя Pi;
- Pi — Pi+(Math.pow(this.distanceTo(main.myTowns.get(i)), main.q)*Math.pow(main.myTowns.get(i).f, main.p))/denominator, вероятность перехода муравья из текущего города в город «i».
Далее выбираем мышкой переход между блоками «Движение» и «Все_обошел» и в поле «Происходит» выбираем значение «При выполнении условия» а в поле условие пишем условие остановки муравья «isVisited.size()==main.myTowns.size()» (рис. 25).
Рис. 25 – Определяем условия остановки муравья
Далее можете запустить «F5» модель и посмотреть, что получилось. Муравьи будут путешествовать между городами с вероятностью, рассчитанной согласно приведенному выше аналитическому выражению.
Обновляем значение феромона
Теперь давайте выполним два действия. Первое действие заключается в увеличении значения феромона на ребре между городами, по которому прошел муравей. Второе в испарении феромона на ребрах между городами, которое заключается в уменьшении значения феромонов относительно времени моделирования.
Итак, для начала к первому действию, будем обновлять значение феромона ребра, между городом в котором находится муравей и в которой ему предстоит отправиться. Величину, на которую будем увеличивать текущее значение феромона ребра между городами будем вычислять очень и очень просто. Берем нашу максимальную начальную величину значения феромона = 1 у.е. и делим ее на расстояние между городом, в котором находится муравей и городом куда он собирается отправится. Соответственно, чем меньше расстояние, между городами тем больше составит значение, на которое будет увеличен уровень феромона ребра. Для чего выбираем во вкладке «Проекты» агент «MyAnt» выбираем мышкой переход между блоками «Выбор_города» и «Движение» и в поле действие добавляем следующий код «main.matrixF[currentPos][i]=main.matrixF[currentPos][i]+1/this.distanceTo(main.myTowns.get(i);». В итоге должно получаться как показано на рисунке 26
Рис. 26 – Обновляем значение уровня феромонов ребер, по которым прошел муравей
Теперь перейдем к действия №2 и создадим событие, которое будет имитировать испарение феромона на ребрах между городами. Для чего во вкладке проекты выбираем агента «Main» и создаем там еще пару переменных. Первая это «intensity» — будет определять скорость(интенсивность) испарения феромона (Начальное значение «0.5» тип «double»). Вторая «Part» — будет характеризовать долю, на которую будет уменьшаться значение феромона на ребре (Начальное значение «0.9» тип «double»).
Рис. 27 – Создаем переменные «intensity» и «Part»
Далее берем из «Палитры» вкладки «Агент» элемент «Событие» и переносим его в агент «Main» и называем его «evaporation» — этот элемент будет имитировать испарение феромона на ребрах. Жмем на него мышкой и в «Свойствах» в поле «Тип события» выбираем значение «С заданной интенсивностью» в поле «Интенсивность» прописываем имя переменной, которая хранит значение интенсивности «intensity». Время срабатывания оставляем секунды. Далее в действие добавляем код, приведенный ниже:
for (int i=0; i<myTowns.size(); i++) {
for (int j=0; j<myTowns.size(); j++) {
matrixF[i][j]=matrixF[i][j]*Part;
if (matrixF[i][j]<0.1) matrixF[i][j]=0.1;
}
}
При срабатывании события «evaporation» будут обновляться значения уровня феромона в матрице matrixF. В итоге у Вас должно получаться так как показано на рисунке 28.
Рис. 28 – Создаем событие «evaporation»
Определим победителя
На этом шаге допишем код, который будет определять победителя нашего муравьиного марафона. Победителем будет тот из муравьев, который пробежал по протяженности самый короткий маршрут. В дополнение ко всему после окончания марафона начертим этот маршрут на экране. Для достижения этой цели создадим в агенте «Main» три переменные «bestAnt», «bestDistance» и «numberFinish». В переменной «bestAnt» мы будем хранить индекс самого «быстрого» муравья, тип переменной будет «int» а начальное значение установим «-1». В переменной «bestDistance» будем хранить текущее значение наилучшего по протяженности маршрута между городами, тип переменной будет «double» а начальное значение установим равным бесконечности «infinity». В переменной «numberFinish» будем хранить количество муравьев, которые финишировали в нашем марафоне, тип переменной будет «int» а начальное значение равно «0» (рис. 29).
Рис. 29 – Создаем событие переменных
Далее создадим функцию, которая после финиширования всех муравьев будет рисовать линии наилучшего маршрута между городами. Для чего из «Палитры» перетаскиваем в агент «Main» элемент с названием функция. Имя функции устанавливаем drawPath и во вкладке «Свойства» в поле тело функции добавляем следующий код:
// Цикл по порядку следования по городам муравья победителя
for (int i=0; i<myAnts.get(bestAnt).isVisited.size()-1; i++) {
// Создаем динамическую фигуру Линия
ShapeLine myLine = new ShapeLine();
// Устанавливаем начальные координаты линии равные значению горда в маршруте под индексом i
myLine.setX(myTowns.get(myAnts.get(bestAnt).isVisited.get(i)).getX());
myLine.setY(myTowns.get(myAnts.get(bestAnt).isVisited.get(i)).getY());
// Устанавливаем конечные координаты линии равные значению горда в маршруте под индексом i+1
myLine.setEndX(myTowns.get(myAnts.get(bestAnt).isVisited.get(i+1)).getX());
myLine.setEndY(myTowns.get(myAnts.get(bestAnt).isVisited.get(i+1)).getY());
// Устанавливаем цвет линии "синий"
myLine.setColor(blue);
// Устанавливаем стиль линии
myLine.setLineStyle(LINE_STYLE_SOLID );
// Устанавливаем толщину линии
myLine.setLineWidth(1);
// Добавляем линию в презентацию
presentation.add(myLine);
}
// Добавляем замыкающую линию между начальным городом и конечным городом в маршруте
ShapeLine myLine = new ShapeLine();
myLine.setX(myTowns.get(myAnts.get(bestAnt).isVisited.get(myAnts.get(bestAnt).isVisited.size()-1)).getX());
myLine.setY(myTowns.get(myAnts.get(bestAnt).isVisited.get(myAnts.get(bestAnt).isVisited.size()-1)).getY());
myLine.setEndX(myTowns.get(myAnts.get(bestAnt).isVisited.get(0)).getX());
myLine.setEndY(myTowns.get(myAnts.get(bestAnt).isVisited.get(0)).getY());
myLine.setColor(blue);
myLine.setLineStyle(LINE_STYLE_SOLID );
myLine.setLineWidth(1);
presentation.add(myLine);
В итоге у Вас должно получиться так как показано на рисунке 29а.
Рис. 29а – Создаем функцию «drawPath»
Теперь возвращаемся обратно к нашим муравьям и дописываем код, который будет определять муравья победителя, протяженность наилучшего маршрута и рисовать этот маршрут между городами. Для чего во вкладе «Проекты» выбираем агента «MyAnt» далее выбираем блок «Все_обошел» и добавляем в поле «Действие при входе» нижеприведенный код:
// Добавляем единичку после финиша
main.numberFinish++;
// Определяем показатели победил муравей или нет
if (main.bestDistance>distance) {
// Если он прошел расстояние меньше глобального значения наилучшего расстояния протяженности марута
// то мы делаем это расстояние наилучшим
main.bestDistance=distance;
// Запоминаем номер муравья победителя
main.bestAnt = this.getIndex();
}
// Если все муравьи финишировали вызываем функцию з агента Main для отрисовки маршрута
if (main.numberFinish==main.myAnts.size()) main.drawPath();
Должно получиться как показано на рисунке 30.
Рис. 30 – Добавление логики в блок «Все_обошел»
После чего можете нажать «F5» и запустить модель. Муравьи будут бегать искать маршруты, а когда финишируют города соединит синяя линия, которая и есть наилучший маршрут.
Добавим гистограмму в модель
Для того чтобы модель стала более научной нужно обязательно добавить график. Поэтому мы с Вами добавим не просто график и гистограмму, которая будет показывать нам распределение протяженности маршрутов, которые преодолели муравьи. Для чего во вкладке «Проекты» выбираем агента «Main» и переходим в его пространство. Далее В «Палитре» переходим во вкладку «Статистика» и оттуда в агент «Main» переносим элемент «Данные гистограммы» и непосредственно саму «Гистограмму». Потом выбираем мышкой гистограммы и во вкладке «Свойства» в поле «Данные» прописываем имя наших «Данных гистограммы» т.е. «data».
Должно получиться как показано на рисунке 31
Рис. 31 – Строим график
После чего нам придется опять вернуться к нашему муравью и заставить его наполнять «Гистограмму» значениями протяженности маршрута. Для чего во вкладке проекты выбираем агента «MyAnt» и переходим в его пространство. Далее выбираем блок «Все_обошел» и добавляем в него одну строчку «main.data.add(distance);». Должно получиться как показано на рисунке 32.
Рис. 32 – Строим график
Далее нажимает «F5» и приступаете к исследованию поведения муравьиного алгоритма. Должно получиться что, то вроде как показано на рисунке 33.
Рис. 33 – Моделируем
Заключение
И в конце рекомендую добавить в модель еще больше непредсказуемости. Для чего во вкладке «Проекты» выбираете мышкой элемент «Simulation: Main» и во вкладке свойства устанавливаете параметр «Случайность» в положение «Случайное начальное число (уникальные прогоны)» — это позволит каждый запуск модели сделать уникальным (рис. 34).
Рис. 34 – Делаем случайными прогоны
Спасибо за внимание! Исходный код можно скачать с GitHub
toyban
Это не влияет на суть Вашего повествования, но все же задача, которую Вы решаете не NP-полная, а NP-сложная.
kocmoc-dev Автор
Упс. Увлёкся.