научная статья по теме МОДИФИКАЦИИ МЕТОДА МУРАВЬИНЫХ КОЛОНИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗРАБОТКИ АВИАЦИОННЫХ МАРШРУТОВ Автоматика. Вычислительная техника

Текст научной статьи на тему «МОДИФИКАЦИИ МЕТОДА МУРАВЬИНЫХ КОЛОНИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗРАБОТКИ АВИАЦИОННЫХ МАРШРУТОВ»

Автоматика и телемеханика, № 3, 2015

Системный анализ и исследование

операций

© 2015 г. Ю.П. ТИТОВ (kalengul@mail.ru) (Московский авиационный институт)

МОДИФИКАЦИИ МЕТОДА МУРАВЬИНЫХ КОЛОНИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ РАЗРАБОТКИ АВИАЦИОННЫХ МАРШРУТОВ

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

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

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

1. Введение

Большинство задач маршрутизации решаются на графах. Графы для задач маршрутизации авиационных средств являются сильносвязанными или полносвязанными. Время перемещения между пунктами определяется в основном расстоянием между ними. Количество дуг в полном графе очень велико поэтому применение жадного алгоритма не представляется возможным.

В последнее время при решении задач комбинаторной оптимизации широко используются методы метаэвристики, в основе которых лежат процедуры случайного поиска, позволяющие находить решения, близкие к оптимальному. Метаэвристически (от англ. metaheuristic, meta — "за пределами" и heuristic — "найти") представляют собой алгоритмы, не имеющие в большинстве случаев строгого доказательства сходимости, но опирающиеся на естественные правила выбора, существующие в объектах живой и неживой природы.

Среди широкого класса метаэвристических методов особое место занимает метод оптимизации муравьиными колониями (ant colony optimization, ACO), предложенный итальянским исследователем Марко Дориго (Marco Dorigo) в 1992 г. [1].

Алгоритм муравьиных колоний можно отнести к многоагентным алгоритмам. Муравьи в данном случае являются агентами, так как они отвечают характеристикам агентов:

1) автономность: агенты, хотя бы частично, независимы;

2) ограниченность представления: ни у одного из агентов нет представления о всей системе или система слишком сложна, чтобы знание о ней имело практическое применение для агента;

3) децентрализация: нет агентов, управляющих всей системой.

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

Ряд исследователей отмечает [2, 3], что на сегодняшний день муравьиные алгоритмы весьма конкурентоспособны по сравнению с другими метаэври-стиками и для некоторых задач дают наилучшие результаты.

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

2. Описание алгоритма муравьиных колоний для задачи коммивояжера

Перемещения муравьев (агентов) по графу описывается правилом: чем больше феромона на дуге графа, тем больше вероятность агента выбрать этот путь [1].

Вероятность выбора агентом дуги г-] считается по формуле

(1)

Рц,к(г) =

та № ■ & (*)

£ (та(г)■ Ш''

] € ^г,к

Рц,к (*) =0, ] /

г,к,

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

0 < Рг],к (г) < 1.

Количество феромона на дугах постоянно меняется. Агенты, определив решение, оставляют на всех дугах, по которым прошли, количество феромона, которое вычисляется по формуле

=-Ат'

(2) Ьк(г)

Атгз,к(Ь) = 0, (г,])/Тк (г),

где Дт^-Д^ - изменение феромона на дуге г-]; ( - общее количество феромона у муравья; Ьк(¿) - длина пройденного к-м агентом пути; Тк(¿) - набор дуг, пройденных к-м агентом.

После окончания итерации (т.е. после того, как все агенты завершили проход по графу) определяется количества феромона, которые оставят на своих путях агенты. Количество феромона на дуге i-j вычисляется по формуле

где Тгу(¿) - текущее количество феромона на дуге г-]; р - коэффициент испарения феромона (0 ^ р ^ 1); ХДт.у)к(£) - общее количество феромона, которое добавили агенты на дугу г-] на текущей итерации.

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

Существуют модификации алгоритма муравьиных колоний. Они основаны на увеличении количества оставляемого феромона у агентов, которые нашли самые короткие пути. Если увеличивается феромон только у одного агента, такой алгоритм называется элитным, в случае, когда агентов несколько, ранжированным [4, 5].

3. Алгоритм муравьиных колоний для задачи коммивояжера в псевдокоде

Агентов представим в виде объектов исходя из терминологии объектно-ориентированного программирования. У каждого муравья будем хранить список пройденных им вершин. Отдельно будет храниться указатель на вершину, в которой находится агент.

Тогда алгоритм можно реализовать следующим образом.

Строка № 01. Начало

Строка № 02. Цикл № 1: Пока не нашли оптимальный путь, выполнить

Строка № 03. Создание популяции агентов

Строка № 04. Установка агента в начальную вершину

Строка № 05. Цикл № 2: по всем агентам

Строка № 06. Цикл № 3: Пока агент не закончит перемещение, выполнить Строка № 07. Процедура: передвинуть агента на следующую вершину Строка № 08. Конец Цикла № 3 Строка № 09. Конец Цикла № 2

Строка № 10. Если агент прошел не по всем вершинам, то Строка № 11. Удалить агента

(3)

Основная программа:

Строка № 12. Конец Если

Строка № 13. Цикл № 4 по всем агентам

Строка № 14. Добавление феромона на дуги графа

Строка № 15. Конец Цикла № 4

Строка № 16. Испарение феромона со всех дуг графа

Строка № 17. Конец Цикла № 1

Строка № 18. Вывод оптимального пути

Строка № 19. Конец

Процедура перемещения агента на следующую вершину Строка № 01. Начало процедуры

Строка № 02. Получение списка вершин, в которые агент может попасть из той, в которой он находится

Строка № 03. Удаление вершин, в которых уже побывал агент Строка № 04. Если список вершин не пустой, то

Строка № 05. Вычисляем общее количество феромонов на дугах возможных переходов

Строка № 06. Распределяем вероятности по дугам Строка № 07. Выбираем переход

Строка № 08. Перемещаем агента на данную вершину Строка № 09. Увеличиваем общую длину пройденного агентом пути на величину перехода

Строка № 10. Конец Если Строка № 11. Конец процедуры

4. Применение метода муравьиных колоний

Метод муравьиных колоний можно применять не только для решения задачи коммивояжера, но и для других прикладных задач маршрутизации авиационных средств [6]. Для того чтобы алгоритм муравьиных колоний решал другие задачи маршрутизации, необходимы изменения алгоритма. Разделим весь алгоритм муравьиных колоний на две части: в первой части определяется целевая функция - количество феромонов, а во второй определяются ограничения - набор вершин, куда агент может переходить из той, в которой находится. Изменение этих двух частей позволяет применять алгоритм муравьиных колоний к другим задачам.

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

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

M - Min

4 —тт:- <0,1,

Min

где M - среднее количество собранных ресурсов на итерации; Min - минимальное количество несобранных ресурсов на итерации.

5. Задача сбора ресурсов

Рассмотрим задачу следующего вида: Существует множество городов с аэропортами. Каждый город производит некоторое количество ресурсов. Авиационное средство перевозит ресурсы. При доставке ресурсов из определенного города авиакомпания получает прибыль. Для каждого города выгода от доставки ресурсов различна. У авиационного средства есть запас топлива, который ограничивает его перемещения между аэропортами. Будем считать, что единица топлива расходуется на единицу пройденного расстояния. Целевая функция:

(5) К = шах(Кг),

ограничения:

(6) Ьг < Ь,

где К - прибыль, которую получит компания; Кг - величина прибыли, которую собрал агент г; Ьг - длина пути, который прошел агент г; Ь - ограничение на длину пути агента.

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

(7) Аг^) = Дтах-ад)'

Дт^,к(г) = о, (г,з)/Тк (

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком