Задача коммивояжера: обходим 750 точек за 5 сек

Доброго времени суток . Спасибо всем заинтересовавшимся моей статьей. Задача коммивояжёра — одна из самых известных задач комбинаторной оптимизации. Её суть заключается в поиске самого выгодного маршрута, который проходит через указанные города по одному разу с последующим возвратом в исходный город. Уже при небольшом числе городов >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 = 99999rasst = 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 pltx = [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 раз.

Заключение

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