Беги, муравей. Беги07.05.2020 23:37

В данной статье рассматривается процесс создания имитационной модели поведения муравьиной колонии (можно почитать в википедии) в среде имитационного моделирования «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» в случайном месте. Место ограничим квадратом 400×400 точек. Для чего во вкладке «Проекты» выбираем мышкой агент «Main» и во вкладке «Свойства» в поле «При запуске» добавляем следующий код на «Java» (рис. 7а):

for (int i=0; i

for (int i=0; i

for (int i=0; i

for (int i=0; i

for (int i=0; i

// Объявляем переменную где будем хранить значение знаменателя
double denominator=0; 
// Рассчитываем значение знаменателя для городов где муравей еще не был
for (int i=0; i

for (int i=0; i

// Цикл по порядку следования по городам муравья победителя
for (int i=0; i

// Добавляем единичку после финиша
main.numberFinish++;
// Определяем показатели победил муравей или нет
if (main.bestDistance>distance) {
	// Если он прошел расстояние меньше глобального значения наилучшего расстояния протяженности марута
	// то мы делаем это расстояние наилучшим
	main.bestDistance=distance;
	// Запоминаем номер муравья победителя
	main.bestAnt = this.getIndex();
}
// Если все муравьи финишировали вызываем функцию з агента Main для отрисовки маршрута
if (main.numberFinish==main.myAnts.size()) main.drawPath();