Доброго времени суток . Спасибо всем заинтересовавшимся моей статьей. Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации. Её суть заключается в поиске самого выгодного маршрута, который проходит через указанные города по одному разу с последующим возвратом в исходный город. Уже при небольшом числе городов >20 задача не может быть решена методом перебора вариантов за приемлемое время.
Для решения задачи коммивояжёра существует большое количество методов и алгоритмов, самые распространённые — поисковые алгоритмы. Лидеры среди них — генетические алгоритмы и алгоритмы колонии муравьёв.
Я придумал свой вариант.
В статье «Сравнение производительности генетических алгоритмов и муравьиных алгоритмов применительно к задаче коммивояжера Авторы: Sabry Ahmed Haroun, Benhra Jamal, El Hassani Hicham Лаборатория LISER, ENSEM, UH2C Касабланка, Марокко.» от May 2015. Приводятся результаты тестов. Генетический алгоритм был разработан на C++. Муравьиный алгоритм оптимизации был написан на C#.
Генетический алгоритм
Первый экземпляр для тестирования ГА — Berlin52 с 52 локациями в Берлине (Groetschel). Генетический алгоритм находит оптимальный тур за 3,4 секунды. Второй экземпляр — Eil76 с 76 городами это считается тест большой размерности. ГА дает неплохие результаты, но не находит оптимального решения. ГА возвращает лучший тур за 13,4 секунды. С приблизительной ошибкой 6%. Самый большой пример в этой статье имеет 280 городов. Из‑за своей сложности этот экземпляр требует больше вычислительного времени и точной настройки (точной настройки? Уже не простая задача! ). ГА обрабатывает этот случай за 517 секунд. С ошибкой 24,7% (так себе точность мягко говоря).
Муравьиный алгоритм
Тест Berlin52 — 52 точки находит тур за 17,7 секунд. Для теста Eil76 76 точек 4,8 сек с ошибкой 9,3% (это не очень хорошо, хотя точек не много). 73,9 секунд с погрешностью 2,4%. Тест A280, то есть 280 точек. Этот экземпляр считается большим. Результат получен за 767,7 сек с ошибкой 19,9% (20% это плохо, я так считаю).
Результаты моего алгоритма
25 точек 0.0003 секунд, погрешность 0%. 750 точек 5 секунд, погрешность примерно 35–40% (да, очень плохо, но это на первом шаге, для 750 точек и за 5 секунд), 2500 точек 200 секунд. Для реализации алгоритма мною за 20 минут написана простенькая программа на Python. Результаты ее работы я пересчитываю с С++ с коэффициентом 25.
Предлагаемый мной алгоритм
Алгоритм заключается в следующем. Имеется набор точек на плоскости с координатами х, у. Задача построить кратчайший путь. Создадим список [[x1, y1], [x2, y2]…[xn, yn]] — это условие задачи. Далее создаем второй список и будем использовать его в качестве скелета. Пока упрощенно занесем в скелет 3 точки находящиеся на краях диапазона. Структура скелета критически важна, но и упрощенный вариант очень не плохо работает. Далее берем первую точку из списка‑условия и подставляем в список — скелет, на первом шаге получаем 4 варианта. Для всех вариантов считаем Евклидовы расстояния суммируем и получаем 4 длины пути. Выбираем вариант с кратчайшим путем и назначаем его новым скелетом. Затем подставляем все точки из условия. Совсем не обязательно подставлять точки из условия по одной можно подставлять группы точек сформированные по критериям.
Реализация алгоритма на Python.
#list1 это точки на плоскости т.е. исходное задание list1=([[5, 3], [4, 2], [2, 4], [7, 3], [5, 5], [3, 1], [3, 3], [1, 6], [1, 2], [6, 0], [7, 4], [4, 3], [3, 4], [4, 0], [6, 7], [0, 3], [3, 7], [6, 3], [1, 4], [5, 0], [1, 0], [2, 6], [6, 2], [2, 7], [3, 2], [7, 2], [4, 1], [3, 0], [6, 5], [3, 5], [1, 1], [7, 7], [5, 2], [1, 7], [0, 5], [0, 2], [2, 3], [6, 1], [0, 0], [7, 6], [5, 6], [7, 1], [4, 7], [0, 4], [0, 6], [1, 5], [0, 7], [2, 0], [2, 2], [3, 6], [5, 4], [6, 4], [5, 1], [4, 5], [7, 0], [2, 5], [0, 1], [4, 6], [5, 7], [1, 3], [2, 1], [6, 6], [7, 5], [4, 4]] ) #list скелет list = ([[0,0],[4,7],[7,4]]) # start1 критерий оценки и выбора скелета и как следствие # пути ,ожидание длины скелета - бесконечность (99999) start1 = 99999 rasst = 0#тот же start1 только текущее значение расстояния #в цикле подставляем 64 точки задания в скелет for i in range (64): #подставляем точки из задания list1[i] в возможные позиции скелета j #получаем j вариантов нового скелета #обратите внимание скаждым новым i цикл j увеличивается for j in range (i + 4 ) : list.insert(j, list1[i]) #для каждого кандидата на новый скелет вычисляем Эвклидово расстояние for k in range( i+3 ) : km = ((list[k+1][ 0]-list[k][ 0])**2 + (list[k+1][ 1]-list[k][ 1])**2)**0.5 rasst =rasst + km #по условию переназначаем start1 и обнуляем rasst и получаем новый скелет if rasst < start1 : start1 = rasst rasst = 0 list2 = list.copy()#глубокое копирование #list.insert капризная штука #list2 кандитат в скелет но только временно #в цикле вычисления расстояний list.pop(j)#очищаем скелет от текущего list1[j] #для проверки следующего варианта else : #иначе просто очищаем скелет от текущего list1[j] list.pop(j) rasst = 0 #обнуляем расстояние list = list2#а вот это уже не кандидат а скелет , но #толькодля текущего list1[j] start1 = 99999#возвращаем start1 !важно #а здесь в конце цикла list1 64 раза ,list2 это и окончательный скелет # и результат , но по хорошему из него нужно изъять тот скелет который #был в начале print("marsh",list2) import matplotlib.pyplot as plt x = [0]*67 y = [0]*67 for j in range (67) : x[j] = list2[j][0] y[j] = list2[j][1] plt.scatter(x, y) plt.plot(x, y) plt.show()
Оптимизация результата
Берем полученный результат и назначаем его новым условием задачи, скелет значительно уменьшаем, то есть это уже не края диапазона, а область скажем 0.25 на 0.25. Затем вновь переназначаем условия и увеличиваем скелет. На каждом шаге отслеживаем уменьшение пути. Далее можно оптимизировать отдельные части общего маршрута. Заметим так же что обработка отрезка длиной 33% от всего списка в 10 раз быстрее, а отрезок в 10% обрабатывается в 100! раз быстрее. Так же еще на начальном этапе по критерию центра тяжести можно выявлять группы точек и со страшной скоростью строить для них локальные пути затем эти пути назначать одной точкой и возвращать уже только в конечный путь. Приведенные методы дают очень хорошие результаты, но ухудшают время для большого сета точек в 15–20 раз.
Заключение
Быстрое решение задачи коммивояжера важно для организации перевозок, чтобы строить оптимальные маршруты по времени, объёму груза и топливу; в системах принятия решений, когда нужно найти оптимальную цепочку действий; при организации конвейера, чтобы сократить время простоя и сделать сборку деталей максимально эффективной; при составлении туристических маршрутов;в экономике для анализа эффективности финансовых инструментов.
