Решение задачи коммивояжера с помощью SBM (моделируемая машина бифуркации)

Введение

«В предыдущей статье мы попытались запустить задачу MAX-CUT с помощью SBM.

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

Задача коммивояжера (TSP)

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

Если количество городов равно N, существует N! маршрутов-кандидатов, и по мере увеличения N количество комбинаций увеличивается экспоненциально, чтобы найти оптимальное решение путем перебора всех комбинаций.

Мы выразим эту проблему в формате QUBO и попытаемся решить ее с помощью SBM.

Целевая функция

Создайте целевую функцию TSP в формате QUBO.

В методе, который мы будем использовать на этот раз, «какой номер» и «какой город» посетить будут одной переменной QUBO.

Например, в случае N=4 рассмотрите комбинацию переменных QUBO, которая будет маршрутом B→A→C→D. В следующей таблице показано сочетание переменных QUBO: «какой номер посетить» в виде строки и «какой город посетить» в виде столбца.

Переменных N² требуется для количества городов N.

Если расстояние между городами (i,j) равно dᵢ,ⱼ, а переменная QUBO nα,ᵢ используется для выражения того, или не посещать город i для αth, целевая функция выглядит следующим образом.

Первый член представляет собой общее расстояние, которое вы хотите минимизировать, второй и третий члены — ограничения, а k₁, k₂ — весовые коэффициенты, отражающие силу ограничений.

При обычном моделированном отжиге (SA), если полученное решение удовлетворяет ограничениям, вес в условиях ограничения лучше сделать как можно меньшим. Это связано с тем, что при переходе от одного локального решения к другому простота переноса может быть дополнительно улучшена.

В этой статье в качестве значения веса используется 1/2max⁡(dᵢ,ⱼ).

Хотя алгоритм SBM существенно отличается от SA, такая схема может быть эффективной, поскольку использует ту же формулировку. Когда мы на самом деле попробовали это, мы подтвердили, что регулировка веса влияет на качество решения.

ЦПЛИБ

TSPLIB — один из эталонных наборов для задачи коммивояжера. Данные о задаче можно скачать по ссылке.

На этот раз мы оценили следующие два вопроса. Это задача коммивояжера в 14 и 24 городах соответственно.

Бирма14
gr24

Исполнение с СБМ

ИСИНГ решатель

На этот раз для решения TSP мы используем решатель SBM ISING. Решатель ISING решает общие проблемы модели QUBO. Данные задачи, предоставленные решателем ISING, представлены в виде текстовых данных, которые следуют формату, называемому форматом MatrixMarket для коэффициентов полинома QUBO.

%%MatrixMarket matrix coordinate real symmetric
N N E
i0 j0 w_i0j0
i1 j1 w_i1j1
i2 j2 w_i2j2

Первая строка объявляет, что данная матрица является вещественной симметричной матрицей.

Вторая строка описывает размерность матрицы NNN и количество элементов EEE. Другими словами, это соответствует количеству переменных QUBO и их коэффициентов взаимодействия (ненулевых матричных элементов) на машине Изинга.

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

В качестве примера данные, полученные путем преобразования случайно сгенерированного QUBO-полинома задачи 6 городов в MatrixMarket, выглядят так.

'%%MatrixMarket matrix coordinate real symmetric
36 36 396
1 1 -1.526
2 1 1.526
2 2 -1.526
3 1 1.526
3 2 1.526
3 3 -1.526
4 1 1.526
4 2 1.526
4 3 1.526
4 4 -1.526
5 1 1.526
5 2 1.526
(Omitted)

Команда выполнения

Отправьте данные о проблеме, созданные в указанном выше формате, с помощью команды curl и попробуйте получить результат расчета. Перепишите 192.168.0.1 пункта назначения соединения в соответствии со средой.

curl -i -H "Content-Type: application/octet-stream" -X POST "http://192.168.0.1:8000/solver/ising?steps=500&loops=0&timeout=10&dt=0.2" --data-binary @problem.data

Параметры SBM (новое дополнение к параметрам)

Выпущена новая версия SBM PoC edition, в которой можно установить следующие параметры машины.

dt：Интервал времени при решении дифференциальных уравнений симплектическим методом Эйлера.
Δt формулы (12) и (13) в SBM paper.
C：Константы, составляющие гамильтониан SBM.
ξ₀ формулы (2) в SBM paper.

Значение по умолчанию для dt равно 1,0, а C автоматически корректируется по умолчанию, но, в зависимости от проблемы, правильная установка этих значений может упростить получение лучшего решения. На этот раз мы попытались найти оптимальное значение настройки dt и C.

Я также попробовал несколько настроек для steps.

Результат выполнения

Настройка параметра `dt`

Мы изменили dt в диапазоне от 0,01 до 1,0 и по полученному значению переменной QUBO рассчитали расстояние пути TSP.

Другие настройки параметров машины следующие:

-steps: 100, 1000, 10000 -loops: 0 (автоматическая настройка) -target: известное оптимальное значение -timeout: 10 (burma14), 20 (gr24) -C: 0 (автоматическая настройка)

Бирма14

Рисунок выше представляет собой график с горизонтальной осью, обозначенной как dt, и вертикальной осью как расстояние. Нижний конец вертикальной оси является оптимальным значением (3323).

В задаче 14 городов burma14 нам удалось найти оптимальное решение в диапазоне исполнения. В частности, это показывает, что оптимальное решение легко получается в области 0.1<dt<0.3.

gr24

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

В gr24 мы попробовали по 10 раз для каждого dt и проверили его среднее значение и стандартное отклонение. На рисунке показано среднее значение расстояния решения TSP со стандартным отклонением в качестве планки ошибок. Нижний конец вертикальной оси также является оптимальным значением (1272).

В области dt> 0.5 не было получено допустимого решения для TSP.

По сравнению с результатами для каждого steps в районе 0.1<dt<0.3 отличие от оптимального решения меньше в steps=10000. Для steps наблюдалась тенденция к получению лучших решений, если было установлено относительно большое значение.

Когда ограничение времени выполнения фиксировано, steps и runs находятся в компромиссном соотношении, поэтому установка оптимального steps может упростить получение точного решения.

Настройка параметра `C`

Мы пробовали различные значения настройки для C, в новой версии добавлен еще один параметр.

Сначала проверьте значение автоматической настройки C в предыдущем экспериментеdt.

На рисунке среднее значение автоматически установленного значения C вычисляется и строится по результатам выполнения 10 раз для каждого dt. Оказалось, что значение 0,0020~0,0022 было хорошо установлено в районе 0,00175 до dt=0.3 и ниже.

Поэтому я взял значение с шагом 0,00025 в диапазоне 0,00025~0,005 и выполнил его 10 раз, как и раньше. Для параметров, отличных от C, устанавливаются значения настройки (steps=10000, dt=0.26), которые получили среднее хорошее решение в предыдущем разделе.

Результат C=0.00150, который немного меньше, чем значение настройки в автоматической настройке, является хорошим как для среднего значения, так и для минимального значения и достиг оптимального решения. Также не было получено ни одного исполняемого решения с C=0.003 или выше.

Оказывается, корректировка C тоже может способствовать улучшению решения.

Резюме

Задача TSP и полученный наилучший результат показаны ниже.

Оказалось, что решение, близкое к оптимальному решению TSP, можно получить, настраивая различные машинные параметры steps, dt и C. Кроме того, в рассматриваемой на этот раз задаче наблюдалась тенденция к тому, что относительно хорошее решение было легко получено путем подстройки в диапазоне 0.2<dt<0.4.