- CITS: согласованный алгоритм поиска по дереву Изинга для решения комбинаторных задач оптимизации (arXiv)
Автор:Юнуо Цэн, Дебасис Дас, Сюаньяо Фонг
Аннотация:Моделируемый отжиг (SA) привлекает больше внимания среди классических эвристических алгоритмов, потому что решение задачи комбинаторной оптимизации может быть естественным образом отображено в основное состояние гамильтониана Изинга. Однако в практической реализации процесс отжига не может быть сколь угодно медленным и, следовательно, он может отклониться от ожидаемого стационарного распределения Больцмана и попасть в ловушку локального минимума энергии. Чтобы преодолеть эту проблему, в этой статье предлагается эвристический алгоритм поиска путем расширения пространства поиска от цепи Маркова до рекурсивного дерева с ограниченной глубиной, основанного на SA, где родительский и дочерний узлы представляют текущее и будущее спиновые состояния. На каждой итерации алгоритм будет выбирать наилучшее близкое к оптимальному решение в допустимом пространстве поиска, исследуя дерево в смысле «заглядывать вперед». Кроме того, руководствуясь когерентной машиной Изинга (CIM), мы ослабляем дискретное представление спиновых состояний до непрерывного представления с членом регуляризации и используем сокращенную динамику осцилляторов для исследования окрестности выбранных узлов дерева. Мы протестировали наш алгоритм на репрезентативной NP-сложной задаче (MAX-CUT), чтобы проиллюстрировать эффективность этого алгоритма по сравнению с полуопределенным программированием (SDP), SA и имитацией CIM. Наши результаты показывают, что выше простых эвристик SA и CIM наша стратегия поиска по дереву высокого уровня способна предоставить решения за меньшее количество эпох для сформулированных Изингом задач NP-оптимизации.
2. Скрученные гибридные алгоритмы для комбинаторной оптимизации (arXiv)
Автор:Либор Каха, Александр Клиш, Роберт Кениг
Аннотация:Предлагаемые гибридные алгоритмы кодируют комбинаторную функцию стоимости в проблемный гамильтониан и оптимизируют ее энергию, изменяя набор состояний с низкой сложностью схемы. Классическая обработка обычно используется только для выбора вариационных параметров после градиентного спуска. Как следствие, эти подходы ограничены описательной силой ассоциированных состояний. Мы утверждаем, что для некоторых задач комбинаторной оптимизации такие алгоритмы могут быть подвергнуты дальнейшей гибридизации, что позволит использовать возможности эффективной нелокальной классической обработки. В частности, мы рассматриваем объединение квантового вариационного анзаца с жадной классической процедурой постобработки для задачи MaxCut на 3-регулярных графах. Мы показываем, что средний размер разреза, полученный этим методом, может быть определен количественно через энергию модифицированного гамильтониана задачи. Это мотивирует рассмотрение улучшенного алгоритма, вариационно оптимизирующего энергию модифицированного гамильтониана. Мы называем это скрученным гибридным алгоритмом, поскольку дополнительный этап классической обработки сочетается с другим выбором вариационных параметров. Мы иллюстрируем жизнеспособность этого метода с помощью алгоритма квантовой аппроксимации (QAOA), давая аналитические нижние оценки ожидаемых коэффициентов аппроксимации, достигаемые с помощью скрученного QAOA. Они показывают, что необходимая нелокальность квантового анзаца может быть уменьшена по сравнению с исходным QAOA: мы находим, что для уровней p = 2,…, 6 уровень p может быть уменьшен на единицу, грубо сохраняя ожидаемое отношение аппроксимации. Это уменьшает глубину схемы на 4 и количество вариационных параметров на 2.
3. Что не так с глубоким обучением в древовидном поиске для комбинаторной оптимизации (arXiv)
Автор: Максимилиан Бётер, Отто Кисиг, Мартин Тараз, Сарел Коэн, Карен Зайдель, Тобиас Фридрих
Выдержка: Комбинаторная оптимизация лежит в основе многих реальных задач. Особенно с появлением графовых нейронных сетей (GNN) сообщество глубокого обучения разрабатывает решатели, которые получают решения NP-сложных задач, изучая структуру решения для конкретной задачи. Однако воспроизвести результаты этих публикаций оказалось затруднительно. Делаем три взноса. Во-первых, мы представляем набор тестов с открытым исходным кодом для NP-сложной задачи максимального независимого множества как во взвешенном, так и в невзвешенном вариантах. Пакет предлагает унифицированный интерфейс для различных современных традиционных и основанных на машинном обучении решателей. Во-вторых, используя наш набор эталонных тестов, мы проводим углубленный анализ популярного алгоритма управляемого поиска по дереву, разработанного Li et al. [NeurIPS 2018], тестирование различных конфигураций на малых и больших синтетических и реальных графах. Повторно реализуя их алгоритм с упором на качество кода и расширяемость, мы показываем, что сеть свертки графа, используемая при поиске по дереву, не изучает осмысленного представления структуры решения и фактически может быть заменена случайными значениями. Вместо этого поиск по дереву опирается на алгоритмические методы, такие как кернелизация графа, чтобы найти хорошие решения. Таким образом, результаты оригинальной публикации не воспроизводимы. В-третьих, мы расширили анализ, чтобы сравнить реализации поиска по дереву с другими решателями, показав, что классические алгоритмические решатели часто работают быстрее, обеспечивая при этом решения аналогичного качества. Кроме того, мы анализируем недавний решатель, основанный на обучении с подкреплением, и наблюдаем, что для этого решателя GNN отвечает за конкурентоспособное качество решения.
4. Общая основа для оценки надежности комбинаторных оптимизационных решателей на графах (arXiv)
Автор: Хань Лу, Зэнан Ли, Жунчжун Ван, Цибин Рен, Цзюньчи Ян, Сяокан Ян.
Аннотация. Решение комбинаторной оптимизации (КО) на графах является одной из фундаментальных задач для приложений верхнего уровня в интеллектуальном анализе данных, машинном обучении и исследовании операций. Несмотря на присущую СО сложность NP-сложности, эвристические алгоритмы, основанные на методах ветвей и границ, основанные на обучении, разрабатываются для максимально точного решения задач СО с учетом ограниченного бюджета времени. Однако практическая метрика чувствительности решателей CO остается в значительной степени неисследованной. Существующие теоретические метрики требуют оптимального решения, которое невозможно, а метрика состязательной атаки на основе градиента из глубокого обучения несовместима с необучаемыми решателями, которые обычно недифференцируемы. В этой статье мы разрабатываем первую практически достижимую метрику надежности для решателей общей комбинаторной оптимизации. Мы разрабатываем не хуже гарантии оптимальной стоимости, поэтому не требуем оптимальных решений, а недифференцируемую задачу решаем, прибегая к методам состязательной атаки черного ящика. Обширные эксперименты проводятся с 14 уникальными комбинациями решателей и задач CO, и мы демонстрируем, что производительность современных решателей, таких как Gurobi, может ухудшиться более чем на 20% в течение заданного ограничения по времени на сложных экземплярах, обнаруженных нашим метрика надежности, вызывающая опасения по поводу надежности решателей комбинаторной оптимизации.
