Arxiv/Learning Improvement Heuristics for Solving Routing Problems 2020 1912.05784
Недавние исследования использования глубокого обучения для решения проблем маршрутизации сосредоточены на строительная эвристика, решения которой еще далеки от оптимальности. Эвристика улучшения имеет большой потенциал для сокращения этого пробела путем итеративного уточнение решения.
Однако все классические эвристики улучшения основываются на созданные вручную правила, которые могут ограничивать их эффективность. В этой статье мы предлагаем фреймворк глубокого обучения с подкреплением для изучения эвристики улучшения проблемы с маршрутизацией. Мы проектируем глубокую архитектуру, основанную на самовнимании, как сеть политик для руководства выбором следующего решения. Мы применяем наш метод к две важные проблемы маршрутизации, то есть проблема коммивояжера (TSP) и проблема маршрутизации емкостного транспортного средства (CVRP).
Эксперименты показывают, что наш метод превосходит современные подходы, основанные на глубоком обучении. Ученый политики более эффективны, чем традиционные, созданные вручную, и могут быть дальнейшее усиление за счет простых стратегий диверсификации. Более того, политика хорошо обобщать для разных размеров проблем, начальных решений и даже набор данных из реального мира.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.