Это совместная работа с Винсентом Стеттлером. Полный код доступен здесь.

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

Мы будем строить решение итеративно на протяжении всей статьи, используя Python и PyTorch.

Коммивояжеры и обходы пабов

Задача коммивояжера (TSP) заключается в нахождении кратчайшего маршрута, соединяющего список городов с учетом матрицы расстояний между этими городами. Вот пример решения (из статьи Wikipedia TSP [1]):

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

Известно, что найти оптимальное решение - это NP-трудная задача - и существует N! различные возможные способы составления тура по N городам. Несмотря на эти мрачные перспективы, проблема имеет очень богатую историю и является одной из наиболее изученных проблем вычислительных наук. Сейчас существует множество различных методов - как точных, так и эвристических - для эффективного поиска хороших решений. Подходы варьируются от имитации эвристики колоний муравьев до чрезвычайно эффективных решателей (таких как Concorde [2]), в которых сложные методы целочисленного линейного программирования используются для поиска точных решений.

Такие решатели, как Concorde, могут найти оптимальные туры для проблем нескольких десятков тысяч городов и туры, близкие к оптимальным (в пределах 1% или меньше), для проблем с миллионами городов. На момент написания один из самых больших примеров проблем был решен с помощью Concorde в 2006 году, и он включал 85 900 межсоединений («городов») в приложении СБИС, что в то время занимало 136 процессорных лет [1]. Этот пример проблемы был евклидовым - это означало, что все расстояния между городами - это евклидовы расстояния между ними. Также были решены большие неевклидовы проблемы (например, рассмотрение времени ходьбы между городами вместо евклидовых расстояний), хотя в целом это намного сложнее.

Возможно, самый важный из когда-либо решенных случаев - это тур по 49 687 пабам в Великобритании с наименьшим расстоянием пешей прогулки (45 495 239 метров). Он был рассчитан в марте 2018 г. [3]:

В целом, мы рекомендуем заинтересованным читателям обратиться к [4] для получения дополнительной информации и интересных анекдотов о проблеме TSP, ее истории и о том, как она сегодня решается на практике.

Почему обучение с подкреплением?

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

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

Пожалуй, самая распространенная мечта компьютерных ученых - заставить компьютер самостоятельно вычислять хорошую эвристику.

Кроме того, у этого подхода есть еще пара преимуществ:

  • В эту структуру можно легко подключить довольно произвольные функции вознаграждения, чтобы можно было использовать один и тот же алгоритм для разных вариантов TSP, особенно для вариантов, которые значительно отличаются от евклидовости. Подумайте, например, о минимизации продолжительности тура, проводя некоторое время в каждом городе или со случайными задержками, привязанными к ссылкам и в зависимости от определенных динамических функций.
  • Скорость вывода и использование в сети: после того, как мы научим нашу нейронную сеть выводить следующий лучший город для посещения, это означает, что для принятия решения, куда идти дальше, требуется только прямой проход через нашу сеть, что обычно очень быстро. Таким образом, он лучше подходит для динамических и онлайн-вариантов использования, чем некоторые более медленные подходы.
  • Мы можем применить машинное обучение к еще одной проблеме. В конце концов, 2020 год!

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

(Очень) краткое руководство по обучению с подкреплением

Обучение с подкреплением (RL) касается того, что агент выполняет последовательность действий, чтобы максимизировать свою (совокупную) награду с течением времени. Агент поддерживает собственное внутреннее состояние и взаимодействует со своим окружением. В общем, эти взаимодействия часто изображаются на таких диаграммах:

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

Есть разные варианты этой установки RL. Например, в некоторых версиях среда поддерживает собственное состояние, которое агент не может полностью наблюдать. Однако для TSP мы будем работать в более простом случае, когда агент имеет полную информацию, а его состояние соответствует состоянию среды.

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

Теперь, когда у нас есть определение состояния, мы уже можем начать писать код, ура!

Здесь мы просто определили именованный кортеж, представляющий состояние. Он содержит матрицу W, которая представляет собой матрицу N x N, содержащую расстояния между всеми N городами. Он также содержит координаты узлов, а также текущее частичное решение, которое будет списком посещенных городов. Это представление кортежа будет нашим «удобным» представлением состояния.

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

Q-обучение

Q-обучение относится к алгоритму для обучения агентов, так что они (надеюсь) сходятся к выбору оптимальных действий. Было показано, что он эффективен в различных контекстах - например, это метод, который использовали Mnih et al. в [5], чтобы научиться играть в игры Atari. Мы и здесь будем придерживаться этого подхода.

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

На высоком уровне, чтобы изучить функцию Q (), идея состоит в том, чтобы запустить много эпизодов с нашим агентом и итеративно улучшить функцию. Во время каждого эпизода, находясь в состоянии s, агент может применять жадную политику, где он выполняет действие a, максимизируя Q (s , a) - а также он может время от времени совершать совершенно случайные действия (чтобы продолжить исследование). В течение многих эпизодов мы можем хранить кумулятивные награды, которые в конечном итоге были получены как «следствие» некоторых пар состояния / действия (s, a). Если наша функция Q () дифференцируема (например, если это нейронная сеть), мы можем затем вычислить градиент ошибки относительно параметров Q ( ), и используйте это для выполнения градиентного спуска и постепенного уточнения параметров. Когда все идет хорошо, это позволяет нам изучить функцию Q ().

Мы упустили здесь много очень важных фактов. Например, на практике нет необходимости ждать до конца эпизода, чтобы оценить целевую совокупную отдачу. Вместо этого мы можем просто подождать один или несколько шагов, а затем «рекурсивно» вызвать функцию Q (), чтобы получить оценку ожидаемого совокупного вознаграждения до конца эпизода. Это действительно изящный и ключевой аспект в обеспечении масштабируемости Q-обучения, но он также может вызвать проблемы со стабильностью, поскольку Q () сам используется для вычисления целей, используемых для его обучения. Для получения дополнительной информации по этой теме мы отсылаем заинтересованных читателей к отличному классу обучения с подкреплением Дэвида Сильвера [6].

Теперь, зафиксированное в коде, Q-обучение для TSP будет выглядеть следующим образом:

Сначала мы создаем объект с именем Q_func, который будет представлять нашу нейронную сеть функции Q () (мы реализуем ее в следующем разделе). Мы также создаем память, которую будем использовать для хранения опыта состояния / действия / вознаграждения. Затем для каждого эпизода мы выбираем новый случайный и полносвязный граф (в идеале из распределения, близкого к распределению нашей последней задачи). Пока наше решение не представляет собой полный тур, мы выбираем следующий узел в соответствии с ε-жадной политикой: с вероятностью ε мы выбираем новый узел случайным образом, а с вероятностью (1-ε) мы выбираем узел (действие a), который максимизирует Q (s, a). Мы будем уменьшать ε в процессе обучения (в строке 16), пока не достигнем некоторой минимальной вероятности исследования, чтобы сделать алгоритм все более и более жадным по мере того, как Q () становится более точным.

Затем мы наблюдаем фактическое вознаграждение, полученное сразу после выполнения этого действия, которое представляет собой просто дополнительное пройденное расстояние до следующего узла (строка 31). Мы сохраняем кортеж опыта в нашей памяти и обновляем наше состояние. Здесь набор опыта определяется как:

Этот опыт - то, что нам понадобится для обучения нашей функции Q (). Они содержат состояние, действие, выполненное, пока агент находился в этом состоянии, полученное совокупное вознаграждение (после определенного количества n шагов) и следующее состояние, в котором агент оказывается после выполнения этого действия. . Нам нужно сохранить это следующее состояние, потому что мы будем использовать его для рекурсивного вызова Q () при оценке совокупных вознаграждений до конца эпизода. В приведенном выше фрагменте мы просто показываем более простую версию n -шагового Q-обучения, где количество шагов n установлено равным 1.

Фактическое обучение Q () начинается в строке 46. Здесь мы выбираем случайный набор событий из нашей памяти. Мы извлекаем пары состояние / действие (входные данные Q ()) из памяти и вычисляем цели, вызывая Q () для следующих состояний. Наконец, в строке 60 мы можем использовать эти цели, как и в любой контролируемой задаче машинного обучения - например, вычисляя потери MSE и выполняя шаг градиентного спуска для обновления Q ().

Это все, что касается Q-обучения! Теперь в следующем разделе мы обсудим возможную архитектуру нейронной сети функции Q ().

Изучение вложений графов

Напомним, что нам все еще нужна функция Q (), которая может принимать график, историю посещенных узлов и действие во входных данных и возвращать ожидаемое совокупное вознаграждение. В качестве дополнительного требования мы хотели бы, чтобы эту функцию Q () можно было вызывать с графиками разного размера. Таким образом, нам не нужно обучать отдельную модель для каждого возможного размера графа. Это представляет собой проблему, потому что это означает, что матрицы графиков W, взятые в качестве входных данных, не всегда будут иметь одинаковый размер.

Здесь, чтобы решить эту проблему и найти подходящую архитектуру, мы будем следовать подходу, предложенному в [7]. В этой статье авторы предлагают использовать алгоритм под названием structure2vec [8]. Идея состоит в том, что Q () можно научить представлять каждый узел в графе векторами фиксированного размера, то есть его можно научить находить вложение графа фиксированного размера.

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

Чтобы построить вложения фиксированного размера из графов потенциально переменного размера, structure2vec использует идеи, аналогичные распространению убеждений, когда каждый узел многократно отправляет «сообщения» по краям графа для итеративного построения его представления. Используя уравнения, [7] описывает эту процедуру вложения следующим образом:

где μ обозначают p -мерные вложения узла (например, для узла v), которые строятся итеративно (для определенного количества итераций T) для каждого узла v, учитывая:

  • Состояние x узла v (первый термин выше). Это вектор, который содержит некоторые индикаторные переменные, фиксирующие, например, был ли узел уже посещен или нет, а также его координаты (x, y) на карте. Мы будем использовать наши тензорные представления истории посещенных узлов, упомянутые здесь ранее.
  • Собственные вложения соседей (второй член выше).
  • Вес входящих ребер (третий член выше).

Наконец, чтобы сделать вложение доступным для изучения, все сшивается вместе с помощью некоторых обучаемых линейных отображений θ, а также некоторых нелинейностей ReLU (хотя, конечно, возможны различные архитектурные варианты).

Вычисление этих вложений узлов - это первый шаг для функции Q (). Второй шаг - использовать вложения для вычисления предполагаемых совокупных вознаграждений для каждого узла. Опять же, в уравнениях это выражается в [7] как:

Здесь Q (s, v; Θ) - наша функция Q (), параметризованная Θ ( набор параметров θ), а v обозначает следующую вершину для посещения, которая представляет действие. Само значение вычисляется как нелинейная функция конкатенации как локального вложения v, так и глобальной агрегации всех вложений (суммирование производится по всем узлам графа). Наконец, обратите внимание, что вычисления выполняются с использованием «последних» значений μ, полученных после T -й итерации.

В коде мы можем написать это с помощью PyTorch следующим образом:

При инициализации мы просто объявляем аффинные карты с параметрами θ (хотя, в отличие от приведенных выше уравнений, мы также вводим здесь обучаемые смещения) . Затем прямой проход реализует функция, определяемая двумя приведенными выше уравнениями. Мы реализуем версию, которая принимает пакеты состояний узлов и тензоров графов, и для каждого элемента в пакете она выводит вектор размера N, который содержит предполагаемые совокупные вознаграждения за выбор каждого узла в качестве следующее действие. Обратите внимание, что формально мы реализуем векторную функцию Q (s), которая возвращает одно значение для каждого возможного действия вместо скалярная функция Q (s, a), но две версии эквивалентны с точки зрения вычислений, потому что мы всегда вызываем Q (s, a) для каждого возможного действия a в любом случае. Мы выбрали эту векторную версию, чтобы получить выгоду от векторизации.

В приведенном выше коде мы также предлагаем расширить один из аффинных слоев (первый) дополнительной нелинейностью, за которым следует линейный слой (применяется к строкам 51–52). Это просто для демонстрации того, как описанная выше базовая архитектура может быть тривиально расширена, чтобы сделать сеть глубже.

Теперь мы в основном закончили с основными строительными блоками нашего подхода RL к TSP! Нам все еще нужен дополнительный код для выполнения фактической оптимизации (например, с использованием потерь MSE и оптимизатора Адама), для выбора лучшего (жадного) действия из нейронной сети или для генерации случайных графиков. Мы не включаем сюда весь этот код для простоты, но вы можете найти его в прилагаемой записной книжке.

Предварительные результаты

Мы обучили эту модель на небольших случайных графах с 10 узлами. Графики полностью связаны; узлы размещаются равномерно и случайным образом на квадрате [0,1] x [0,1], а веса ребер - это просто все попарные евклидовы расстояния между узлами. Мы обучили его с размерностью встраивания p = 5, пакетами по 16, снижающейся скоростью обучения и минимальным значением ε, равным 0,1. Мы сделали только минимальную оптимизацию гиперпараметров, поэтому к нашим результатам следует относиться с недоверием. Тем не менее, что довольно удивительно, в ходе обучения выяснилось, что агент действительно все чаще принимает решения, которые сокращают время поездки!

Вот несколько примеров туров:

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

Хотя мы, конечно, далеки от производительности решателей TSP (или даже довольно наивной эвристики), мы все же находим эти результаты довольно удивительными. Мы ни разу не кодировали правила о том, как найти хороший тур - однако агент может принимать более правильные решения, только наблюдая за пройденным расстоянием!

Что дальше?

Есть еще много дел:

  • Улучшенные последовательности захвата: для простоты наши тензоры состояния по существу захватывают набор посещенных узлов, а не упорядоченную последовательность посещенных узлов. Это чрезвычайно плохое представление частичных обходов, которые, вероятно, не имеют возможности работать по-настоящему хорошо, даже с идеальным алгоритмом. Более серьезная реализация должна улучшить способ обработки последовательностей.
  • Лучшее использование структуры графа: в этой версии TSP мы на самом деле не использовали структуру графа, потому что мы рассматривали только полносвязные графы, тогда как обычно более разреженные графы могут давать сильные индуктивные смещения [9]. Мы заинтересованы в изучении аналогичных подходов к смежным задачам с более разреженными графами.
  • Больше настроек, инженерии и возможностей: мы сделали только минимальную настройку гиперпараметров, и, вероятно, можно получить лучшие результаты. Мы заметили, что настройка таких моделей RL может быть довольно сложной, с большим разбросом по качеству результатов и большой чувствительностью по многим гиперпараметрам, что может сделать обучение и оценку модели довольно сложными и дорогостоящими. Более того, наша реализация нацелена на простоту понимания, а не на скорость. Например, он не оптимизирован для эффективной работы на графических процессорах (хотя должен работать на графическом процессоре). Более быстрый код может ускорить цикл экспериментов. Наконец, мы играли только с мелкими моделями, имеющими небольшую емкость - модели с большей емкостью могли дать лучшие результаты.

Выводы

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

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

использованная литература

[1]: https://en.wikipedia.org/wiki/Travelling_salesman_problem

[2]: http://www.math.uwaterloo.ca/tsp/concorde/index.html

[3]: http://www.math.uwaterloo.ca/tsp/pubs/

[4]: http://www.math.uwaterloo.ca/tsp/index.html

[5]: Мних, Владимир и др. «Игра в атари с глубоким обучением с подкреплением». Препринт arXiv arXiv: 1312.5602. 2013 г.

[6]: http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html

[7]: Халил, Элиас и др. «Изучение алгоритмов комбинаторной оптимизации по графам». NeurIPS. 2017 г.

[8]: Дай, Ханджун, Бо Дай и Ле Сон. «Дискриминационные внедрения моделей скрытых переменных для структурированных данных». ICML. 2016 г.

[9]: Батталья, Питер В. и др. «Реляционные индуктивные предубеждения, глубокое обучение и сети на графах». Препринт arXiv arXiv: 1806.01261. 2018 г.