ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2010, № 1, с. 32-45
== КОМПЬЮТЕРНЫЕ МЕТОДЫ
УДК 007(075)
МУРАВЬИНЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ*
© 2010 г. А. А. Кажаров, В. М. Курейчик
Таганрог, ТТИ ЮФУ Поступила в редакцию 19.05.09 г.
Посвящена решению транспортных задач муравьиными алгоритмами. В основе идеи этого алгоритма лежит моделирование поведения муравьев. Разработаны несколько модификаций муравьиного алгоритма.
Введение. В настоящее время проблема маршрутизации автотранспорта становится все более актуальной. В условиях современной экономики уже невозможно удовлетворять требованиям клиентов без автоматизации решения задач транспортной логистики. От решения этой проблемы напрямую зависит цена на товар, а в некоторых областях рынка затраты на доставку товара соизмеримы с его стоимостью [1].
В работе обсуждается возможность применения муравьиных алгоритмов к различным транспортным задачам и их модификациям. Данный класс алгоритмов разрабатывался в рамках научного направления, которое можно назвать "природные вычисления" [2]. Исследования в этой области начались в середине 90-х годов XX в., автором идеи является Марко Дориго [3—5], который предложил использовать моделирование поведения колонии муравьев.
Рассмотрены задача коммивояжера (ЗК) и маршрутизация автотранспорта с учетом грузоподъемности. Для каждой задачи разработана и реализована математическая модель поведения муравьиной колонии.
В ходе проделанной работы были использованы и исследованы несколько модификаций в муравьиных алгоритмах. Полученные результаты позволяют судить об оптимальном выборе параметров при решении транспортных задач с различными начальными данными. Проведены экспериментальные сравнения с методами поиска оптимального маршрута: метод ветвей и границ, метод "ближайшего соседа", модифицированный генетический алгоритм, стандартный муравьиный алгоритм. Экспериментальные исследования доказали эффективность муравьиных алгоритмов с модификациями по сравнению со стандартным муравьиным алгоритмом и генетическими алгоритмами. Для описания общих
* Работа выполнена при частичной финансовой поддержке РФФИ (грант № 09-01-00492) и федеральной целевой программы РНП 2.1.2/1652, 2.1.2/4595.
принципов и математической модели муравьиных алгоритмов рассмотрим ЗК.
1. Постановка задачи коммивояжера. Задача о коммивояжере, в английской интерпретации TSP (Traveling Salesman Problem), относится к NP-трудным. Она заключается в нахождении кратчайшего гамильтонова цикла в графе [6]. Без каких-либо изменений в постановке она используется для проектирования разводки коммуникаций, разработки архитектуры вычислительных сетей, маршрутизации авто- и авиатранспорта и др.
В неформальной форме ЗК трактуется следующим образом: коммивояжеру необходимо посетить W городов, не заезжая в один и тот же город дважды, и вернуться в исходный пункт по маршруту с минимальной стоимостью. Более строго имеем: дан граф G = (X, U), где |X| = n — множество вершин (города), IU = m — множество ребер (возможные пути между городами). Дана матрица чисел D(i, j), где i, j е 1, 2, ..., n, представляющих собой стоимость переезда из вершины Xj в xxj.
Требуется найти перестановку ф из элементов множества X, такую, что значение целевой функции равно
Fitness(y) = Д(ф(1),
ф(«)) + £{D(ф(i),Ф(i + 1))} ^ min.
i
Если граф неполносвязный, то в матрице D, в ячейках, соответствующих отсутствующим ребрам в графе, ставится бесконечность, в результате чего проход по данному ребру будет исключен.
2. Муравьиный алгоритм. 2.1. Общие положения. Как было сказано выше, основной идеей данного алгоритма является моделирование поведения муравьев, коллективной адаптации. Колония представляет собой систему с очень простыми правилами автономного поведения особей. Однако, несмотря на примитивность деятельности каждого отдельного муравья, поведение всей колонии оказывается достаточно разумным [7]. Основой существования муравьиной
□ Р(1, 2) = 28%
□ Р(1, 3) = 15%
□ Р(1, 4) = 33%
□ Р(1, 5) = 24%
Рис. 1. Распределение вероятностей из одной вершины
колонии служит низкоуровневое взаимодействие, благодаря которому, в целом, колония представляет собоИ разумную многоагентную систему. ВзаимодеИствие определяется через специальное химическое вещество — феромон, откладываемый муравьями на пройденном пути. При выборе направления движения муравей исходит не только из желания пройти кратчайший путь, но и из опыта других муравьев, информацию о котором получает непосредственно через уровень феромонов на каждом пути. Итак, концентрация феромона определяет желание особи выбрать тот или иной путь.
Однако при таком подходе неизбежно попадание в локальный оптимум, так как на начальном этапе выбор агентами направления движения носит случайный характер. Эта проблема решается благодаря испарению феромонов, которое является отрицательной обратной связью. Испарение происходит равномерно по всему ареалу, ограничивая тем самым уровень концентрации феромонов и обратную связь. Таким образом, путь, на который было потрачено меньше времени, менее подвержен испарению, а значит, концентрация феромонов на оптимальном маршруте будет дольше сохраняться [7].
2.2. Простой муравьиный алгоритм для задачи коммивояжера. Для начала сформулируем свойства муравья.
1. Каждый муравей обладает собственной "памятью", хранящей список городов 1,к (табу-лист), которые необходимо посетить муравью к, находящемуся в городе /.
2. Муравьи обладают "зрением", обратно пропорциональным длине ребра
П = 1/яг
"Зрение" определяет "жадность" выбора муравья. Чем ближе находится вершина графа, тем он лучше "виден" и тем больше агент стремится попасть в нее.
3. Любой муравей способен улавливать след феромона, что стимулирует желание муравья пройти по данному ребру. Уровень феромона в момент времени I на ребре Б, будет соответствовать Т-ДО.
4. Вероятность перехода муравья из вершины I в вершину] устанавливается следующим соотношением:
=
X КХОЙп«]13'
I е I,,
У е , к
(2.1)
Р,к(П = 0, 7 * 1,к,
где а, в — параметры, задающие веса следа феромона, коэффициенты эвристики. Параметры а и в отражают относительную значимость двух параметров, а также их влияние на уравнение [8]. Они определяют "жадность" муравья. При а = 0 муравей стремится выбирать кратчайшее ребро, при в = 0 — ребро с наибольшим количеством феромона. Нетрудно заметить, что данное выражение имеет эффект "колеса рулетки".
На рис. 1 слева показан граф, справа — распределение вероятностей перехода из первой вершины в другие. Здесь а = 1 и в = 1, толщина ребер показывает уровень феромонов на этом ребре. С увеличением а вырастут и вероятности выбора ребер, на которых больше концентрация феромонов. С увеличением в вероятность выбора более коротких ребер возрастает, а более длинных — уменьшается. На рис. 2 показано, как меняются вероятности для нескольких ребер с течением времени. Здесь рассмотрен граф из четырех вершин. Для наглядности решается задача поиска минимального пути в графе от х0 к х3. Толщина линий отражает интенсивность прохождения муравьев на этом участке, р01 и р02 — вероятности выбора агентом (муравьем) ребер (х0, хх) и (х0, х2) соответственно. Изначально вероятности перехода из вершины х0 в х1 и х2 равны. На рис. 3 показан пример поведения муравья.
Как видно из рис. 3, муравей прошел путь по вершинам 1—6—5—4 и, находясь в вершине 4, выбирает между вершинами 7 и 3 для последующего путешествия. С течением времени вероятность выбора кратчайшего пути увеличивается, поскольку количество откладываемого феромона обратно пропорционально длине маршрута и задается в следующем виде:
О
V, У) 6 Тк(!),
Дт., = 114!)' ч" кЧ'" (2.2)
,0, (/, у) е Т(),
где Q — параметр, имеющий значение порядка длины оптимального пути, Ьк(() — длина маршрута Т(). Испарение феромона описывается следующим выражением:
Ту(! + 1) = (1 - р)ту(!) + £ Дт.
(2.3)
к = 1
где т — количество муравьев, р — коэффициент испарения (0 < р < 1).
В рассматриваемом простом муравьином алгоритме начальное расположение колонии муравьев задается следующим образом: количество агентов равно числу вершин в графе, и каждому агенту соответствует вершина, с которой он начинает свое путешествие.
Приведем псевдокод простого муравьиного алгоритма для задачи коммивояжера [7], обеди-няющий следующие шаги.
Шаг 1. Ввод матрицы расстояний Б.
Шаг 2. Инициализация параметров алгоритма — а, в, Q.
Шаг 3. Инициализация ребер — присвоение видимости Цу и начальной концентрации феромона.
Ш а г 4. Размещение муравьев в случайно выбранные города без совпадений.
Шаг 5. Выбор начального кратчайшего маршрута и определение Ь*.
Ш а г 6. Цикл по времени жизни колонии I = 1,
^шах.
Ш а г 7. Цикл по всем муравьям к = 1, т.
Шаг 8. Построить маршрут Тк({) на основе распределения вероятности по ребрам (2.1) и рассчитать длину Ьк(1).
Ш а г 9. Конец цикла по муравьям.
Шаг 10. Проверка всех Ьк(() на лучшее решение по сравнению с Ь*.
Шаг 11. В случае, если решение Ьк(1) предпочтительнее, обновить Ь* и Т*.
Ш а г 12. Цикл по всем ребрам графа.
Шаг 13. Обновить следы феромона на ребре на основе (2.3).
Ш а г 14. Конец цикла по ребрам.
Ш а г 15. Конец цикла по времени.
Шаг 16. Вывести кратчайший маршрут Т* и его длину Ь*.
Временная сложность данного алгоритма зависит от времени жизни колонии, количества вершин графа и числа муравьев — 0(1 х т х и2), где I — количество итераций (время жизни колонии), т — число муравьев, и — число вершин [7].
3. Модификации муравьиного алгоритма. 3.1. "Элитные" муравьи. "Элитой" называются муравьи, чьи маршруты лучше остальных. Разработана следующая модификация, основанная на знаниях об "элитных" муравьях [9]. Данная модификация не учитывает количества "элитных" муравьев. Выражение (2.2) для элиты принимает следующий вид:
Дте(0 = Ле-^~, (3.1)
Ь*Ц)
где Ае — "авторитет" "элитных" муравьев.
Таким образом, мы можем регулировать влияние "элитных" муравьев с помощью коэффициента Ае. Оптимальное значение Ае в основном будет зависеть от размерности графа, численности колонии, времени жизни. Отметим несколько вариантов ра
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.