Abstract: The paper presents a solution to the traveling salesman problem using various reinforcement learning algorithms and a comparative analysis of the results obtained when learning algorithms by minimizing the length of the final route. The result of the selected algorithm was compared with a random one.
Keywords: reinforcement learning, traveling salesman problem, combinatorial optimization problem, deep learning, heuristic algorithms, route optimization
Введение.
Задача коммивояжера — древнейшая задача комбинаторной оптимизации, заключающаяся в поиске Гамильтонова графа — графа, содержащего гамильтонов цикл. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу, то есть простой цикл, в который входят все вершины графа. Исследование решения задачи коммивояжера имеет богатую историю и обширный инструментарий различных подходов.
Другими словами, Задача коммивояжера (или TSP) заключается в нахождении кратчайшего возможного пути, соединяющего города с учетом матрицы расстояний между этими городами.
Задача имеет множество практических применений в различных областях, в том числе:
- Логистика и транспорт: решение задачи коммивояжера можно использовать для оптимизации маршрутов доставки для курьеров, водителей и грузовых компаний, сокращая расход топлива и время, необходимое для доставки.
- Производство и производство: оптимизация порядка производства в производственном процессе, сокращая время и затраты, необходимые для производства.
- Дизайн сети: оптимизация развертывания сетей связи, например, для размещения вышек сотовой связи.
- Секвенирование ДНК: определение порядка секвенирования фрагментов ДНК, что сокращает общее время и стоимость секвенирования.
- Робототехника и автоматизация: оптимизация пути робота, сокращения времени и энергии, необходимых для выполнения задачи.
- Туристическая индустрия: оптимизация маршрутов путешествий для туристов, снижения затрат и времени, необходимых для поездки.
Это всего лишь несколько возможных примеров применений задачи коммивояжера из множества возможных задач оптимизаций, стоящих перед современным бизнесом и наукой . Известно, что поиск оптимального решения является NP-трудной задачей и существует (N-1)! различных возможных способов собрать решение с посещением N городов.
В настоящее время существует множество различных методов — как точных, так и эвристических — для эффективного поиска хороших решений. Подходы варьируются от эвристических моделей муравьиных колоний до чрезвычайно эффективных решателей (таких как Concorde), использующих сложные методы целочисленного линейного программирования для поиска точных решений.
References
1. Электронный ресур https://www.math.uwaterloo.ca/tsp/pla85900/index.html Дата обращения 05.04.20232. Электронный ресур https://www.math.uwaterloo.ca/tsp/pla85900/compute/cpu.htm Дата обращения 23.04.2023
3. Пантелеев А.В., Метлицкая Д.В., Алешина Е.А. Методы глобальной оптимизации. Метаэвристические стратегии и алгоритмы. М.: Вузовская книга, 2013.
4. Reinforcement Learning: An Introduction. Second edition, in progress. Richard S. Sutton and Andrew G. Barto c 2014, 2015. A Bradford Book. The MIT Press.
5. Vijay R., Konda John N., Actor-Critic Algorithms – 2018. URL: https://arxiv.org/pdf/1801.01290.pdf
6. Электронный ресур https://spinningup.openai.com/en/latest/algorithms/sac.html
Дата обращения 02.05.2023
7. Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, Sergey Levine – 2017. URL: https://arxiv.org/pdf/1702.08165.pdf