Arxiv/Learning Collaborative Policies to Solve NP-hard Routing Problems 2021 2110.13987

Материал из DISCOPAL
Перейти к: навигация, поиск

«

В последнее время фреймворки глубокого обучения с подкреплением (DRL) продемонстрировали потенциал для решения NP-сложных проблем маршрутизации, таких как задача коммивояжера (TSP), без специальных экспертных знаний. Хотя DRL можно использовать для решения сложных проблем, структурам DRL все еще трудно конкурировать с современными эвристиками, показывающими существенный разрыв в производительности. В этой статье предлагается новая иерархическая стратегия решения проблем, называемая политиками сотрудничества при обучении (LCP), которая может эффективно находить почти оптимальное решение с использованием двух итеративных политик DRL: сеялки и ревизора.

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

С другой стороны, ревизор изменяет каждое решение-кандидат, созданное сеялкой; он разделяет полную траекторию на субтуры и одновременно пересматривает каждый субтур, чтобы минимизировать расстояние прохождения. Таким образом, ревизор обучается повышать качество решения-кандидата, уделяя особое внимание уменьшенному пространству решений (что полезно для эксплуатации). Обширные эксперименты показывают, что предложенная схема сотрудничества с двумя политиками лучше, чем структура DRL с одной политикой, в решении различных NP-трудных проблем маршрутизации, включая TSP, TSP с получением призов (PCTSP) и проблему маршрутизации с ограниченными возможностями (CVRP).

…»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.