Реализация муравьиного алгоритма

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

Рисунок 2.3. Класс AntAlgorithm

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

· alfa и beta – параметры влияющие на жадность алгоритма

· p – коэффициент испарения феромонов

· q – параметр, имеющий значения порядка цены оптимального решения

· t – начальное значение феромонов на ребрах

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

Метод pijkt реализует формулу (1.1) муравьиного алгоритма. Программная реализация данного метода представлена на рисунке 2.4:

Рисунок 2.4. Реализация формулы (1.1)

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

Метод randomizerпринимает массив вероятностей с идентификаторами вершин. На основании полученного массива строит отрезки на интервале, соответствующие вероятностям. И затем возвращает идентификатор той вершины, на отрезок которой выпало случайное число.

Метод локального обновления, реализующий формулу (1.2) устроен следующим образом: на вход методу поступает объект ребра, затем из него по свойству feromonпроисходит расчет нового количества феромонов с помощью формулы (1.2). Программный код этого метода представлен на рисунке 2.5

Рисунок 2.5. Метод локального обновления

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

Рисунок 2.6. Метод глобального обновления

Solveрешает основную задачу муравьиного алгоритма с модификацией муравьиной колонии. Реализацию данного метода удобнее всего представить в виде блок-схемы (рисунок 2.6)

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

Реализация метода Solve заключается в три основных цикла: первый цикл итераций, по окончанию каждой из которых, происходит глобальное обновление феромонов на лучшем пути. Затем вложенный цикл,запускает муравьев на стартовую вершину. И последний цикл с числом повторений равным количеству вершин, выполняет основную логику передвижения муравьяпо ребрам и делает локальное обновление феромонов в конце каждого перехода. После выполнения всех циклов метод Solveвозвращает лучший найденный путь, по которому можно отсортировать адреса пациентов.

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

1. ул. Богданова, 48к1, Москва, Россия, 119620 (Стартовый адрес)

2. ул. Богданова, 10, Москва, Россия, 119618

3. ул. Главмосстроя, 7, Москва, Россия, 119618

4. Солнцевский пр., 13, Москва, Россия, 119620

5. Солнцевский пр., 34, Москва, Россия, 119620

6. ул. Щорса, 8к1, Москва, Россия, 119620

7. Авиаторов ул., 6, Москва, Россия, 119619

8. Авиаторов ул., 14, Москва, Россия, 119620

9. Авиаторов ул., 30, Москва, Россия, 119620

10. Волынская ул., 4, Москва, Россия, 11962

Тогда матрица, полученная с помощью веб-службы «GoogleMapsDistanceMatrixAPI» имеет вид (таблица 2.1):

Таблица 2.1

Матрица стоимостей

Проинициализировав, каждыйэлемент матрицы начальным значением феромонов и применяя к ней реализованный алгоритм,процесс решенияможно представить в виде графика (рисунок 2.8), на котором заметно, как происходила оптимизация маршрута из точки 1 на каждой итерации:

Рисунок 2.8. График итераций

Уже на 24 итерации алгоритма был найденмаршрут{1, 7, 8, 6, 9, 10, 4, 5, 3, 2}, который остался оптимальным на всех последующих итерациях,и его время пути составляет65 минут. Время пути сокращается почти в два раза, в сравнении, если бы врач посещал адреса по порядку из входных данных (в сумме 128 минут). Также время выполнения запроса для 10 точек, за 100 итераций и 10 агентов, вместе с запросом к«GoogleMapsDistanceMatrixAPI» для получения матрицы, в среднем составляет 150мс

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