Реализация алгоритмов решения задачи коммивояжёра


Статья для IX Всероссийской молодежной научной конференции «Мавлютовские чтения», УГАТУ, Уфа-2015


Полный текст статьи в сборнике [PDF]

УДК 004

Т. И. ФАБАРИСОВ

З. И. ФАБАРИСОВ

Науч. руковод. – к.т.н., доц. Т.Д. ТАРАСОВА

Уфимский государственный авиационный технический университет

 РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЁРА

Одна из самых известных и важных задач транспортной логистики (и класса задач оптимизации в целом) – задача коммивояжера. Суть задачи сводится к поиску оптимального, то есть кратчайшего пути проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути.

Целью данной работы является сравнение двух алгоритмов решения задачи коммивояжёра: генетического алгоритма (ГА) и метода ветвей и границ (МВГ).

 

Постановка задачи.

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

  • Маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение
  • В каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.

Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице диагональ заполнена нулями). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат [1].

Математическая модель задачи исследования.

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица , где  – длинна (или цена) дуги (i, j),  . Под маршрутом коммивояжера z будем понимать цикл  точек . Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера, длина маршрута l(z) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i1 – фиксирована. Требуется найти маршрут z∈Z, такой, что (z_0 )=min ⁡l(z),z∈Z.

 

Генетический алгоритм.

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

Генетические  алгоритмы  отличаются от других оптимизационных и поисковых процедур тем, что

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

Для применения генетического алгоритма необходимо определить основные структурные элементы: вид элемента популяции, процесс скрещивания, мутации и вид фитнесс-функции [2].

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

В качестве фитнесс-функции мы принимаем функцию вида:

S=∑(i,j∈P)S(gi,gj)

где Р – множество всех связей в маршруте.

Данная функция определяет минимизируемый параметр и позволяет оценивать получаемые решения.

Оператор мутации реализуется следующим образом. Из вектора маршрута случайным образом выбираются 2 элемента (города), которые меняются друг с другом позициями в векторе.

Оператор скрещивания реализуется следующим образом. Пусть S1, S2 — два решения, задаваемые векторами. Выбираем случайным образом две позиции . Новый вектор X¢ получает точки на позициях  от вектора X1, остальные точки получает от вектора X 2 в порядке их появления в векторе.

 

Метод ветвей и границ.

В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия “разделяй и властвуй”).

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

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

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

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы равные нулю. Найдем степени нулевых элементов этой матрицы. Степень нулевого элемента  равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов  – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля [3].

Для получения платежной матрицы маршрутов, включающей дугу , вычеркиваем в матрице строку i и столбец j, а чтобы не допустить образования цикла в маршруте, заменяем элемент, замыкающий текущую цепочку, на бесконечность.

Множество маршрутов, не включающих дугу , получаем путем замены элемента  на бесконечность.

Программная реализация.

Данный алгоритм реализован в виде программы на языке C++ и исследован на достаточно большом количестве примеров.

Интерфейс программы представлен на рисунке 1.

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

Чтобы отменить расстановку городов и отчистить матрицу весов, нужно щелкнуть по кнопке «Очистить граф». Нажав кнопку «Следующий тест», мы получим результат: города графически соединены минимальным путем, его длина дана в окне информации, также выведен сам наименьший маршрут, состоящий из городов, входящих в полученный путь. Также выводится информация о времени выполнения алгоритма.

st11

Рисунок 1 – Интерфейс программы

С помощью данной программы было просчитано порядка 100 примеров. Результаты отражены на рисунке 2.

st12

Рисунок 2 – Эффективность алгоритмов

Заключение.

  • Изучены эвристические и точные алгоритмы решения задачи коммивояжера.
  • Программно реализованы два алгоритма решения задачи коммивояжёра: МВГ и ГА.
  • Проведено сравнение эффективности работы алгоритмов с помощью разработанной программы.
  • Результаты сравнения. При количестве городов меньше 10 МВГ решает задачу коммивояжёра быстрее ГА. При количестве городов от 10 до 15 ГА решает задачу коммивояжёра быстрее МВГ. При количестве городов большем чем 15 МВГ не может решить задачу из-за возросшего времени решения задачи.

Список литературы.

  1. В.И. Мудров Задача о коммивояжере. — 2-е изд. — М.: «УРСС», 2013. — 64 с, ISBN 978-5-397-04106-5
  2. Johnson, D.S., McGeoch, L.A. The traveling salesman problem: a case study. Local search in combinatorial optimization / D.S. Johnson, L.A. McGeoch. – Chichester: Wiley. – Р. 215-310.
  3. Костевич Л. С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л. С. Костевич. — Мн.: Новое знание, 2003. ил., стр. 150, ISBN 985-6516-83-8

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *