Статья:

НЕЙРОСЕТЕВЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

Журнал: Научный журнал «Студенческий форум» выпуск №39(306)

Рубрика: Технические науки

Выходные данные

Демченко В.С. НЕЙРОСЕТЕВЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА // Студенческий форум: электрон. научн. журн. 2024. № 39(306). URL: https://nauchforum.ru/journal/stud/306/155714 (дата обращения: 26.12.2024).

К условиям публикации Скачать журнал

Журнал опубликован

Мне нравится

Научный журнал «Студенческий форум» выпуск №39(306)

на печатьскачать .pdf поделиться

НЕЙРОСЕТЕВЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

Демченко Владимир Сергеевич

магистрант, Донской государственный технический университет, РФ, г. Ростов-на-Дону

Литвинов Владимир Николаевич

научный руководитель, канд. техн. наук, доцент кафедры Математика и информатика Донской Государственный Технический Университет, РФ, г. Ростов-на-Дону

Аннотация. Задача коммивояжера или (Travelling Salesman Problem) является NP-полной задачей в области комбинаторной оптимизации. Для задачи TSP не существует алгоритма способного найти оптимальное решение за полиномиальное время. В данной статье рассматриваются нейросетевые методы решения задачи коммивояжера, включая нейронную сеть Хопфилда, графовую нейронную сеть и нейронную сеть с подкреплением.

Ключевые слова: задача коммивояжера; нейронная сеть Хопфилда; графовая нейронная сеть; нейронная сеть с подкреплением.

Hopfield neural network

Сеть Хопфилда является рекуррентной нейронной сетью, где каждый нейрон связан с каждым другим. Пусть N — количество нейронов в сети, а $\begin{equation} v=(v1,v2,…,vN) \end{equation}$ — вектор состояния нейронов, где $\begin{equation} v_i∈[{−1,1}] \end{equation}$ . Матрица весов связей между нейронами обозначается как $\begin{equation} W \end{equation}$ , где $\begin{equation} W_{ij} \end{equation}$ — вес связи между нейронами i и j.

Состояние нейрона $\begin{equation} v_i \end{equation}$ обновляется по следующему правилу: $\begin{equation} v_i^{(t+1)} = \text{sign}\left(\sum_{j \neq i} W_{ij} v_j(t)\right) \end{equation}$

где $\begin{equation} sign(x) \end{equation}$ — функция знака, возвращает 1, если $\begin{equation} x>0 \end{equation}$ , и −1, если $\begin{equation} x<0 \end{equation}$ .

Матрица весов $\begin{equation} W \end{equation}$ определяется на основе сохраненных паттернов. Если $\begin{equation} \mathbf{p}^k \end{equation}$ — k-й паттерн, то:

$\begin{equation} W_{ij} = \frac{1}{N} \sum_{k=1}^{P} p_i^k p_j^k \end{equation}$

где P — количество паттернов.

Сеть Хопфилда действует как ассоциативная память, восстанавливая сохраненные паттерны из неполных или искаженных данных.

Neural network with reinforcement learning

В нейронных сетях с подкреплением используется концепция

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

Основное уравнение оптимальности – уравнение Беллмана:

$Q(s,a)=E[R(s,a)+γ\max_ {a′}Q(s′,a′)],$

где – функция ценности действия a в состоянии s, γ – коэффициент дисконтирования.

Нейронная сеть может использоваться для аппроксимации функции ценности QQQ, и обучается с использованием градиентного спуска, чтобы минимизировать ошибку между предсказанными и реальными значениями

$Loss=E[(Q(s,a)−(R(s,a)+γmax_ {a ′} Q(s ′ ,a ′ ))) ^2 ]$

Graph neural network

Графовые нейронные сети обрабатывают данные в виде графов $\begin{equation} G=(V,E) \end{equation}$ , где $\begin{equation} E \end{equation}$ , $\begin{equation} V \end{equation}$ . Пусть $\begin{equation} \mathbf{h}_i \end{equation}$ — вектор признаков узла i, а $\begin{equation} A \end{equation}$ — матрица смежности графа. Для агрегации информации из соседних узлов используется следующая формула обновления:

$\begin{equation} h_ i (t+1) =Aggregation({h_ j (t) ∣j∈N(i)}), \end{equation}$ где $\begin{equation} N(i) \end{equation}$ множество соседей узла i, а Aggregation может быть любой функцией агрегации. После агрегации применяется функция обновления весов.

$\begin{equation} h_ i (t+1) =Update(h_ i (t) ,Aggregation({h_j (t) ∣j∈N(i)})). \end{equation}$

Для графа G=(V,E)G = (V, E)G=(V,E), где {V} — множество вершин, а {E} — множество рёбер, задача коммивояжёра заключается в нахождении кратчайшего замкнутого пути, который проходит через каждую вершину ровно один раз и возвращается в исходную вершину. Формулировка задачи включает следующие элементы:

$\begin{equation} \min \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij} \end{equation} $ (1)

$\begin{equation} \sum_{j=1}^{n} x_{ij} = 1 \quad \forall \, i \in \{1, 2, \ldots, n\} \end{equation} $ (2)

$\begin{equation} \sum_{i=1}^{n} x_{ij} = 1 \quad \forall \, j \in \{1, 2, \ldots, n\} \end{equation} $ (3)

$\begin{equation} \sum_{i, j \in S} x_{ij} \leq |S| - 1 \quad \forall \, S \subset \{1, 2, \ldots, n\}, \, 2 \leq |S| \leq n - 1 \end{equation} $

$\begin{equation} x_{ij} \in \{0, 1\} \quad \forall \, i, j \in \{1, 2, \ldots, n\} \end{equation} $ (4)

Формально задача может быть представлена как задача целочисленного программирования, где переменные $\begin{equation} x_{ij} \end{equation}$ указывают на то, используется ли ребро (i,j)(i, j)(i,j) в пути.

Уравнения (2) и (3) гарантируют, что в цикле будет только одна вершина графа в качестве начальной и одна в качестве конечной, а уравнение (4) обеспечивает отсутствие решений являющихся замкнутыми циклами, что гарантирует обход всех точек.

В работе Ma и др. [4] был использован графовый указатель, предложенный Vinyals, который обучался с помощью методов подкрепляющего обучения для оптимизации иерархической стратегии и механизма вознаграждения. Bello [5] также обучил графовый указатель с отрицательной длиной пути в качестве сигнала вознаграждения и применил метод градиентного спуска для оптимизации параметров рекуррентной нейронной сети. Deudon и др. [6] заменили LSTM в методе Bello и совместили его с эвристикой 2-opt, что позволило получить более удовлетворительные результаты при применении к задаче коммивояжера.

Кроме использования графовых указателей в сочетании с обучением с подкреплением, предложены и другие сети и системы для решения данной задачи. В частности, Dai и др. [7] применили архитектуру Structure2Vec для встраивания вершин графа в информационные признаки и использовали Q-обучение вместе с жадным методом вставки для размещения каждой новой вершины в локально оптимальную позицию в частично сформированном маршруте, таким образом постепенно формируя тур. Bresson [8] применил фреймворк трансформера для кодирования, обучал его с помощью подкрепляющего обучения и декодировал с помощью поиска по лучу. Решение на основе трансформера показал лучшие результаты по сравнению с ранее предложенными методами решения задачи коммивояжера.

Выводы

Сложность графовых данных представляет собой серьезный вызов для дальнейших исследований, поскольку графовые структуры имеют высокую степень связности и множество параметров, что усложняет задачу их обработки и анализа.

Хотя графовые нейронные сети (GNN) демонстрируют высокую эффективность в решении TSP, необходимо исследовать их способность к решению других комбинаторных задач. Генерализационная способность этих сетей, то есть их возможность справляться с различными задачами оптимизации, остается открытым вопросом и требует дальнейшего изучения. Использование больших языковых моделей (LLM) для решения комбинаторных задач, таких как TSP, также представляет перспективное направление. LLM, такие как GPT-2 и выше, могут эффективно обрабатывать сложные и разнообразные данные, предоставляя мощные инструменты для моделирования и предсказания. Однако, необходимо учитывать высокие требования к вычислительным ресурсам и сложность интерпретации решений, что может быть предметом дальнейших исследований и улучшений.

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

Список литературы:

1. Исследование решения комбинаторных задач с помощью больших языковых моделей: пример решения задачи коммивояжера с использованием GPT-3.5 Turbo Махмуд Масуд, Ахмед Абдельхай и Мохаммед Элхенави, [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2405.01997 (дата обращения 01.12.2024)

2. Методы нейронных сетей для решения задачи коммивояжера Юн Ши, Юаньин Чжан, [Электронный ресурс] – Режим доступа: https://www.researchgate.net/publication/363130090_The_neural_network_methods_for_solving_Traveling_Salesman_Problem (дата обращения 01.12.2024)

3. Опрос по задаче коммивояжера Санчит Гойал [Электронный ресурс] – Режим доступа: https://www.researchgate.net/publication/228708267_A_Survey_on_Travelling_Salesman_Problem (дата обращения 01.12.2024)

4. Ма Кью , Ге С , Хе Д, и др. Комбинаторная оптимизация с помощью сетей указателей графов и иерархического обучения с подкреплением. [Электронный ресурс] – Режим доступа: https://arxiv.org/abs/1911.04936v1 (дата обращения 01.12.2024)

5. Белло И, Пхам Х, Ли Кью В и др. Нейронная комбинаторная оптимизация с подкреплением. [Электронный ресурс] – Режим доступа: https://arxiv.org/abs/1611.09940v3 (дата обращения 01.12.2024)

6. Деудон М, Цоурнут П, Лацосте А и др. Эвристики обучения для TSP с помощью градиентного спуска. Международная конференция по интеграции программирования ограничений, искусственного интеллекта и исследования операций. Springer, 2018 г.

7. Ханьюн Дай, Елиас Б. Кхалил, Ю Жанг, Бистра Дилкина, Ли Сонг. Алгоритмы комбинаторной оптимизации обучения на графах. В трудах 31-й конференции по нейронным системам обработки информации (NeurIPS). 2017, стр. 6348–6358

8. Брессон X, Лоран Т. Трансформер для задачи коммивояжера. [Электронный ресурс] – Режим доступа: https://arxiv.org/abs/2103.03012v1 (дата обращения 01.12.2024)

НЕЙРОСЕТЕВЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

Похожие статьи