Абстрактный

Используя Simulated Bifurcation Machine (SBM), опубликованную Toshiba Digital Solutions Corporation на AWS Marketplace, мы выполнили тесты для задачи комбинаторной оптимизации MAX-CUT.

Имитационная машина бифуркации

SBM - это программа для решения задач комбинаторной оптимизации, предоставляемая Toshiba Digital Solutions Corporation. Используя методы классической физики, используемые для описания бифуркационных явлений, адиабатических процессов и эргодической (или более поздней теории хаоса), и применяя их к комбинаторной оптимизации, SBM быстро решает большие проблемы.

Пробная версия доступна на торговой площадке AWS.

Проблема MAX-CUT

Мы выбрали задачу MAX-CUT как типичную комбинаторную задачу, которую может решить SBM.

Задача задачи MAX-CUT - разбить граф на два взаимоисключающих подграфа так, чтобы совокупный вес ребер между подграфами был максимальным.

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

Рассмотрим случай, когда мы разбиваем граф V на подграфы S и T.

Мы определяем двоичное значение sᵢ, также называемое переменной Изинга, чтобы выразить, какая вершина подграфа vᵢ ∈ V находится следующим образом.

Используя эту переменную, мы определяем целевую функцию задачи оптимизации следующим образом

где Wᵢ ⱼ - вес ребра между вершинами vᵢ и v ⱼ. Только в том случае, если vᵢ, v ⱼ находятся в противоположных подграфах,

Когда две вершины находятся в одном подграфе, вес соединяющего их ребра будет умножен на 0. Таким образом, максимизация этой функции даст решение задачи MAX-CUT.

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

Кроме того, определение истинного двоичного файла

На основе переменной Изинга мы можем переписать целевую функцию следующим образом

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

Выполнение SBM

Режим MAX-CUT

SBM включает в себя специализированный решатель MAX-CUT (режим MAX-CUT), который вводит текст, описывающий проблему. Для ввода текста SBM поддерживает формат MatrixMarket, а также формат эталонного набора данных MAX-CUT Gset.

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

N E
i0 j0 w_i0j0
i1 j1 w_i1j1
i2 j2 w_i2j2

В первой строке указано количество вершин N и ребер E, а в следующих строках указано количество ребер, по одному ребру в строке. Каждая такая строка содержит вершины конечных точек ребра i и j, а также его вес wᵢ ⱼ.

В качестве примера ниже показана задача MAX-CUT с 5 вершинами и 7 ребрами в формате Gset.

5 7
1 2 1
1 5 1
2 3 -1
2 4 1
2 5 -1
3 4 -1
4 5 1

Визуализация этого в виде графика приводит к следующему рисунку.

Параметры SBM

Следующие параметры могут быть отправлены в SBM.

  • steps: количество шагов в расчете SBM. По умолчанию 0, и в этом случае количество шагов определяется динамически.
  • loops: Сколько раз будет повторяться расчет SBM, чтобы найти лучшее решение. Значение по умолчанию - 1, а значение 0 заставит SBM работать до истечения времени ожидания.
  • timeout: Максимальное время расчета в секундах. Если выполнение следующего цикла, вероятно, приведет к превышению таймаутом SBM, вычисления будут прекращены раньше.
  • target (необязательно): если значение указано, выполнение прекращается, когда целевая функция достигает указанного значения.
  • stats: уровень детализации возвращаемых статистических данных. Статистика собирается по выполнению циклов * шагов. Возможные значения:
  • none: не возвращать статистических данных.
  • summary: возвращает среднее значение, стандартное отклонение и наилучшую частоту.
  • full: возвращает среднее значение, стандартное отклонение и гистограмму.

Выполнение примера с пятью вершинами из приведенного выше с использованием curl выглядит следующим образом

$ echo -e "5 7\n1 2 1\n1 5 1\n2 3 -1\n2 4 1\n2 5 -1\n3 4 -1\n4 5 1" | curl -i -H "Content-Type: application/octet-stream" -X POST "http://192.168.0.1:8000/solver/maxcut?steps=0&loops=0&timeout=1&stats=full" --data-binary @-

Обратите внимание, что IP-адрес (здесь 192.168.0.1) зависит от вашей среды.

Мы используем параметры, перечисленные ниже

  • steps = 0
  • loops = 0
  • timeout = 1
  • stats = full

Если выполнение выполнено успешно, SBM отправит следующий ответ.

HTTP/1.1 200 OK
    Content-Type: application/json; charset=utf-8
    Content-Length: 233
    ETag: W/"e9-6jYjTGcvinFBL6/eKnutYNzItOQ"
    Date: Mon, 19 Aug 2019 03:59:29 GMT
    Connection: keep-alive
{"id":"r1477108799","time":1,"wait":0,"runs":396800,"steps":10,"message":"timeout","value":3,"result":[0,1,0,0,1],"stats":{"avg":2.441142,"stddev":1.372172,"histogram":[[-2,24009],[-1,4124],[0,15682],[1,12766],[2,12636],[3,327583]]}}

Центральными частями ответа JSON являются следующие

  • result: найдено лучшее решение
  • value: Значение целевой функции для лучшего решения
  • runs: Количество выполнений (циклы * шаги)

Бенчмаркинг с Gset

Теперь мы выполним тестовый набор данных MAX-CUT Gset, который можно загрузить с сайта http://web.stanford.edu/~yyye/yyye/Gset/.

Gset состоит из задач от G1 до G81 и, из-за некоторых пропущенных чисел, имеет в общей сложности 71 задачу с размером графа от 800 до 20 000 вершин. Существуют графы без взвешенных ребер (все веса равны 1), а также графы с взвешенными ребрами, у которых веса либо +1, либо -1. Геометрически структуру графиков можно разделить на три категории.

  • Случайные графики
  • Планарные графики
  • Тороидальные графы

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

Для простоты использования мы используем curl для публикации набора данных Gset в SBM. Например, чтобы выполнить задачу G1 с параметрами steps=0, loops=0, timeout=10 и target=11624, перейдите в каталог, где хранится набор данных Gset, и выполните следующую команду

$ cat G1 | curl -i -H "Content-Type: application/octet-stream" -X POST "http://192.168.0.1:8000/solver/maxcut?steps=0&loops=0&timeout=10&target=11624" --data-binary @-

Результаты тестов

Ниже перечислены результаты для 69 графиков в Gset. Все исполнения выполнялись с параметрами
steps=0 (автоматически), loops=0 (автоматически), timeout=10 и target=(best-known), где best-known относится к наиболее известным значениям целевой функции для данной задачи, которые были взяты из предыдущего исследования.

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

Для вышеуказанного теста мы позволили системе автоматически определять соответствующее количество steps. Однако мы подозреваем, что более высокой производительности можно достичь, указав величину steps априори. Чтобы проверить эту гипотезу, мы выполнили задачу G65 с ограничением по времени 60 секунд и числом steps на цикл от 10 000 до 1 000 000. На рисунке ниже показано решение проблемы G65.

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

Для проблемы G65 установка количества steps на значения, превышающие 500 000, приводит к более оптимальным решениям, чем запуск многих циклов с меньшим steps.

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

Вывод

Используя SBM, мы смогли найти приблизительные решения проблем MAX-CUT на высокой скорости. В частности, сравнительно небольшие задачи с примерно 2000 вершинами были решены менее чем за секунду.

Среди задач, сформулированных Изингом, задачи MAX-CUT считаются относительно простыми для решения, поскольку они не имеют ограничений. Хотя мы рассмотрели проблемы MAX-CUT из набора данных Gset для этого теста, мы намерены провести аналогичные тесты с более сложными и реалистичными проблемами оптимизации. Путем дальнейшей настройки мы также исследуем, насколько большей скорости и точности можно достичь с помощью SBM.