Улучшенная табу-симулированная бифуркация для комбинаторной оптимизации

Почему более умный поиск имеет значение

От прокладки маршрутов для грузовиков до сопоставления частиц в коллайдере — многие из самых сложных вычислительных задач сводятся к одной проблеме: найти наилучший выбор среди астрономического числа вариантов. Эти так называемые комбинаторные задачи лежат в основе логистики, финансов, биологии и инженерии, но они настолько сложны, что даже суперкомпьютеры испытывают трудности. В этой статье представлен новый алгоритмический приём, называемый Tabu‑Enhanced Simulated Bifurcation (TESB), который помогает компьютерам не застревать в тупиках и находить лучшие решения заметно быстрее.

Тяжёлые решения в ландшафте возможностей

Исследователи часто представляют комбинаторные задачи как неровный ландшафт, полный холмов и впадин. Каждая точка на этом ландшафте представляет возможное решение, а высота соответствует его «энергии» или стоимости; низкие впадины — хорошие решения, а самая глубокая впадина — наилучшее. Многие реальные задачи, такие как разрезание сети на две хорошо отделённые части (задача Max‑Cut) или восстановление треков частиц в детекторе, можно свести к такому энергетическому ландшафту с помощью математической модели, известной как модель Изинга. Загвоздка в том, что таких впадин астрономическое количество, поэтому процедура поиска легко может остановиться в сравнительно неплохой впадине и никогда не обнаружить куда более глубокую в другом месте.

От квантовых идей к классической скорости

Simulated Bifurcation (SB) — относительно новый, вдохновлённый физикой подход к исследованию таких неровных ландшафтов. Вместо перебора дискретных решений SB представляет систему как движущиеся частицы в сглаженной версии ландшафта, описываемые уравнениями, напоминающими классическую механику. По мере медленной смены управляющего параметра система «бифурцирует», и положения частиц наклоняются в сторону низкоэнергетических впадин, кодирующих хорошие решения. SB уже показал высокую эффективность на крупных задачах и хорошо работает на графических процессорах, но у него есть общий с многими методами поиска недостаток: он может застревать в локальных минимумах, особенно на нерегулярных, плотно связанных задачах, где некоторые области ландшафта гораздо запутаннее других.

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

Ключевая идея TESB — наделить SB своего рода кратковременной памятью, вдохновлённой хорошо известной стратегией оптимизации, называемой tabu search. В табу-поиске алгоритм хранит список недавно исследованных плохих решений и временно запрещает возвращаться к ним. TESB переносит эту концепцию в картинку энергетического ландшафта. Сначала «разогревающая» стадия использует исходный SB для быстрой генерации множества приближённых решений. Они соответствуют локальным впадинам, в которых система склонна застревать. Затем TESB модифицирует ландшафт, добавляя мягкое штрафование вокруг этих регионов, фактически повышая дно соответствующих впадин. Во время последующей «проверочной» стадии система снова эволюционирует в этом изменённом ландшафте, теперь побуждаемая обходить старые ловушки и устремляться к более глубоким, ранее неизведанным впадинам.

Поддержание динамики поиска малыми толчками

Практическая проблема — как использовать эту память, не перегибая палку. Если TESB штрафовал бы каждую прошлую впадину одинаково и навсегда, это могло бы так выровнять ландшафт, что полезная ориентация пропала бы. Чтобы избежать этого, метод заимствует ещё одну идею из современного машинного обучения: мини‑пакеты. На каждом шаге проверочной фазы TESB случайно выбирает только небольшое подмножество сохранённых субоптимальных решений для включения в штраф. Это позволяет ландшафту смещаться ровно настолько, чтобы оттолкнуть систему от протоптанных областей, сохраняя при этом общую структуру и разнообразие поиска. Численные тесты показывают, что эта стратегия даёт TESB возможность продолжать улучшать решения долгое время после того, как динамика исходного SB фактически остановилась.

Испытание метода

Авторы протестировали TESB на стандартных тестовых графах Max‑Cut и на сложных задачах из физики высоких энергий, где восстановление путей заряженных частиц одновременно важно и вычислительно затратнo. На тестах Max‑Cut TESB часто достигает оптимальных или близких к оптимальным разрезов гораздо надёжнее, чем исходные варианты SB. В терминах «времени до решения» — сколько времени в среднем требуется, чтобы получить ответ заданного качества — TESB может быть до тысячи раз быстрее на самых сложных примерах. В задачах восстановления треков, содержащих более ста тысяч переменных, TESB последовательно находит конфигурации с более низкой энергией (то есть лучшим соответствием данным), одновременно требуя меньше вычислительных ресурсов по сравнению с базовыми методами, что подчёркивает его масштабируемость для реальных очень больших систем.

Что это значит для будущего

Проще говоря, TESB превращает быстрый, но порой близорукий поисковик в более стратегического исследователя, который помнит, где уже был, и учится избегать плохих районов. Путём изменения энергетического ландшафта вокруг прошлых ошибок, а не полного перезапуска, он значительно повышает шансы достичь качественных решений за разумное время. Это сочетание динамики, навеянной физикой, с классическими табу‑идеями указывает на более общий путь развития: многие нетрадиционные оптимизационные движки, будь то классические или квантово-вдохновлённые, могут получить аналогичный прирост, внедрив умные штрафы, учитывающие историю. Для приложений, которым нужно решать всё более крупные и сложные комбинаторные задачи, TESB предлагает перспективный новый инструмент для преодоления прежних ограничений производительности.

Цитирование: Tao, XZ., Zeng, QG., Huang, ZJ. et al. Tabu-Enhanced Simulated Bifurcation for combinatorial optimization. Commun Phys 9, 100 (2026). https://doi.org/10.1038/s42005-026-02538-2

Ключевые слова: комбинаторная оптимизация, симулированная бифуркация, табу-поиск, Max-Cut, восстановление треков частиц