Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Предсказатель научили сразу строить полезные решения для NP-трудных задач, не вызывая математический решатель при обучении и запуске. Команда Monash University показала, что DFLNOL обошёл обучение по среднеквадратичной ошибке во всех проверенных режимах, хотя препринт не рецензирован и числа получили сами авторы. Для систем маршрутизации это способ заменить долгую оптимизацию нейронным слоем, если допустимо получать хорошее, но не гарантированно оптимальное решение.
Почему точного прогноза недостаточно для хорошего маршрута
В задачах маршрутизации сначала приходится предсказывать неизвестные параметры: время проезда, стоимость ребра, доступный бюджет или награду за посещение точки. Затем математический решатель выбирает маршрут по этим прогнозам. Обычный предсказатель минимизирует среднеквадратичную ошибку MSE, но она не учитывает, как ошибка изменит итоговое решение.
Небольшое отклонение рядом с границей допустимого бюджета может полностью перестроить маршрут. Более крупная ошибка на неиспользуемом ребре, напротив, ничего не изменит. Поэтому два прогноза с одинаковой MSE могут привести к решениям разного качества.
Обучение с учётом решений исправляет этот разрыв: модель получает обратную связь не за точность параметров как таковую, а за качество выбранного маршрута. Качество измеряют относительным сожалением — насколько результат после необходимых исправлений хуже оптимального решения при уже известных фактических параметрах.
Проблема прежних подходов в вычислительной цене. Одни многократно запускают решатель во время обучения, другие требуют заранее найти оптимальные маршруты и использовать их как эталоны. Если неизвестные параметры входят ещё и в ограничения, модель должна учитывать не только стоимость решения, но и риск получить недопустимый маршрут.
Как нейронный слой заменяет вызовы решателя
DFLNOL разделяет обучение на два этапа. Сначала нейронный слой оптимизации учится выбирать рёбра по уже известным параметрам задачи. Ему не показывают готовые маршруты: вместо этого функция потерь сочетает целевую стоимость, штрафы за нарушение ограничений и структурные требования к связности.
Слой выдаёт не готовый набор рёбер, а непрерывные оценки их полезности. Он учитывает устройство графа и уже выбранные рёбра, а затем несколько раз уточняет оценки. Это помогает представить конкуренцию между соседними переходами и получить результат, который проще превратить в допустимый маршрут.
После предварительного обучения слой замораживают. Предсказатель получает контекст, оценивает неизвестные параметры и передаёт их в этот слой. Получившийся непрерывный маршрут оценивают уже по фактическим параметрам из истории: модель видит стоимость решения и штрафы за возможные нарушения ограничений. Градиент проходит через замороженный слой обратно в предсказатель, поэтому исходную комбинаторную задачу решать при каждом обновлении не требуется.
При запуске система соединяет предсказатель, нейронный слой и специализированный модуль сборки дискретного маршрута. Если фактические ограничения отличаются от предсказанных, заданное для задачи правило исправляет маршрут до допустимого состояния. Такой подход сохраняет явный прогноз параметров: при необходимости его можно передать обычному решателю вместо нейронного модуля.
Когда результат меняет архитектурный план
DFLNOL снизил сожаление относительно MSE во всех 12 проверенных режимах. На ATSP с неопределённой стоимостью рёбер среднее сожаление упало с 52,53% до 14,83%. Нейронная сборка решения занимала около 15 миллисекунд на экземпляр против примерно 6 секунд при передаче того же прогноза в Gurobi.
Система также обучалась быстрее рассмотренных методов, которые учитывают решения и вызывают оптимизацию в цикле. При этом выигрыш дал не только быстрый модуль сборки: вариант с Gurobi на этапе запуска тоже превосходил MSE, то есть предсказатель действительно научился выдавать параметры, полезные для последующего решения задачи.
Менять план имеет смысл, если продукт многократно решает однотипную задачу выбора рёбер, располагает историей контекстов и фактических параметров, а задержка решателя мешает обучению или работе сервиса. DFLNOL особенно уместен там, где неопределённость влияет одновременно на стоимость и допустимость решения.
Это не универсальная замена математической оптимизации. Для каждой задачи нужны собственные целевая функция, штрафы, модуль сборки маршрута и правило исправления. Кроме того, нейронный результат не даёт гарантии оптимальности, поэтому для редких и дорогих решений с обязательным доказательством качества решатель остаётся частью архитектуры.
Эксперименты охватывают asymmetric traveling salesperson и endpoint-free orienteering с неопределённостью в цели, ограничениях или сразу в обоих местах; в ATSP-замерах графы доходили до 200 узлов. Эти стенды показывают работу подхода на двух задачах выбора рёбер, но пока не подтверждают тот же выигрыш на производственных данных и других классах оптимизации.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
