Arxiv/Solve routing problems with a residual edge-graph attention neural network 2021 2105.02730

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

«

Для NP-сложных задач комбинаторной оптимизации обычно сложно находить качественные решения за полиномиальное время. Дизайн либо точный алгоритм или приближенный алгоритм для этих задач часто требует существенно специализированные знания. В последнее время методы глубокого обучения позволяют новые направления решения подобных проблем. В этой статье предлагается структура сквозное глубокое обучения с подкреплением для решения комбинаторных задач оптимизации этого типа.

Этот фреймворк можно применять к разным проблемы только с небольшими изменениями ввода (например, для путешествий задача продавца (TSP), на входе - двумерные координаты узлов; в то время как для задачи маршрутизации с ограниченной пропускной способностью (CVRP) входом является просто заменены на трехмерные векторы, включая двумерные координаты и требования клиентов узлов), маски и контекст декодера векторов. Предлагаемая структура направлена ​​на улучшение моделей грамотности в термины модели нейронной сети и алгоритма обучения. Решение качество TSP и CVRP до 100 узлов значительно улучшено благодаря нашему рамки.

В частности, средний разрыв оптимальности сокращен с 4,53% до 6,68% для CVRP со 100 узлами при использовании жадная стратегия декодирования.

Кроме того, наш фреймворк использует около 1/3 ∼ 3/4 обучающие образцы по сравнению с другими существующими методами обучения при достижении лучшие результаты. Результаты, полученные на случайно сгенерированных экземплярах, и экземпляры тестов из TSPLIB и CVRPLIB подтверждают, что наша структура имеет линейное время работы от размера задачи (количества узлов) в процессе тестирования фаза, и имеет хорошую производительность обобщения от обучения случайным экземплярам к тестированию реальных экземпляров.

…»

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

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

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