【サーベイ編】深層強化学習を使ってTSPを解く

深層強化学習を用いたTSP・VRPの解法について調査する機会があったのでまとめます。
TSP(巡回セールスマン問題)やVRP(配送経路問題)がどういう問題か、ということは知っている前提で話を進めます。

対象とする手法・問題

対象の問題

今回対象となる問題は、2次元のユークリッドTSP、つまり、2次元座標を入力として、2点間の距離をユークリッド距離で計算するような問題です。

調査した論文で提案されている手法はいずれも2次元座標を入力とするモデルですが、入力を工夫すれば一般のTSPに対しても適用可能ではないか、と個人的には考えています。

対象の手法

深層学習を用いた離散最適化手法には、以下のようなものがあります。

• GNNや強化学習を用いて、汎用ソルバー(GUROBI, CPLEX, CBC, など)の近似 or サブルーチンとしての利用を目指す手法
• GNNや強化学習を用いて、0から解を求める手法
• GNNや強化学習を用いて、既知の実行可能解の改善を目指す手法
• 既存のヒューリスティックの適切な組み合わせ方やベストパラメーターの推定を行う手法

この中で、今回は2番目の、「GNNや強化学習を用いて0から解を求める手法」の中で主要なものだと考えられる手法のみを紹介します。

その他の手法について関心のある方は、以下のようなサーベイ論文がありますので参考にされてください。

• Machine learning for combinatorial optimization: A methodological tour d’horizon

また、分枝限定法と機械学習を組み合わせた手法には以下のようなものがあります。

• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies

強化学習とは

強化学習は、「状態の観測→報酬の計算→次の行動の決定」というサイクルを繰り返しながら、最終的に獲得できる報酬を最大化するような行動方針を習得していく手法です。

TSPやVRPにおいては総移動距離の最小化が報酬および強化学習の目的の一例になります。

強化学習を行うにあたって、以下の2つの方針があります。

1. 行動方針そのものを学習する ( 方策勾配法 )
2. 行動の価値を決定する、価値関数を学習する ( Q学習 )

Q学習についてはこのブログでも解説していますので、詳細はこちらをご覧ください。

強化学習の基礎　マルコフ決定過程とQ-Learningについて

深層強化学習を用いてTSPを解くモデルについて

このセクションでは、深層強化学習を用いてTSPなどの離散最適化問題を解く手法について、時系列で紹介していきます。

Hopfield Network (1982年)

連想記憶を可能にしたネットワークです。こちらについてはあまり詳しく調査していないので、wikipediaに説明を任せます。

Pointer Networks (2015年, 2016年)

Pointer Networksは2015年にGoogleが発表した手法で、最近の手法はPointer Networksの思想を継承してデザインされたものが多くなっています。また、自然言語処理で使われている手法を取り込んだ(恐らく)最初の手法です。

2015年の論文で、ネットワークの構造と教師あり学習による結果を提示し、2016年に、強化学習(Actor-Critic)を用いた結果と、Active Searchと呼ばれる改善手法を発表しています。

Pointer Networkの構造

Pointer Networkは、

• 入力グラフ情報から特徴抽出を行うencoder
• encoderの出力を利用して答えとなる経路を出力するdecoder

によって構成されており、encoderとdecoderにはLSTMが用いられています。

decoderは、encoderの入力を元に、次にどの都市を訪れるか確率的に求めます。ビームサーチなどを使って、求めた確率に対して貪欲に経路を決定する方法と、求めた確率に従ってランダムにサンプリングして経路を求める手法があります。

Active Search

Active Searchとは、推論時に各テストインスタンスに対して適切なパラメーターを探索することによって性能向上を狙う手法です。

対象となるインスタンスに特化したパラメーターを使用するので、未知のインスタンスに対する汎化性能も向上しますし、出力される経路長も改善されます。

一方、ここで発表された手法では、モデルの全パラメーターを更新するため、推論時間が膨大になるという弱点もあります。このような経緯から、効果的でありつつもあまり使用されてきませんでした。

Active Searchの改良版として、Efficient Active Search( EAS )2021年, under reviewという手法が発表されています。

こちらの手法では、

1. encoderの1部を除いたほとんど全てのパラメーターを固定した上でActive Searchを行う
2. モデルに2つの線形層を追加し、その層のパラメーターのみを更新対象としてActive Searchを行う
3. 次の地点を選択する際に用いる確率を、ルールベースで作成した表に従って更新することでインスタンスに対するチューニングを行う（モデルパラメーターは更新しない）

の3種類の改善方法を提案しています。

S2V-DQN (2017年)

この手法は、グラフ上の最適化問題を、深層Q学習によって学習した評価関数を用いて貪欲に解くことを目的とした手法です。

問題（＝グラフ）情報から特徴量を抽出するためにStructure2Vecと呼ばれる、グラフ埋め込み分野のネットワークを使用し、Q学習を用いてモデルを最適化することによって評価関数を学習します。

このアプローチによって、学習時の問題インスタンスの大きさに対する影響を小さく抑えることに成功しています。

Attention Model (2019年)

Pointer Network同様、EncoderとDecoderを使用するモデルです。この論文では、より適切なモデル構造と、より効率的な学習方法が必要である、との主張の元、新しいアーキテクチャと学習アルゴリズムを提案しています。Pointer Networkとの差分は以下の通りです。

• Encoder・Decoderに言語処理のモデルであるTransformerのMultihead-Attentionを使用し、LSTMは廃止した。
• 勾配の分散を小さくするためのベースラインの計算を、Greedy-rolloutによって行った。これによって、ベースライン計算用のCriticネットワークを学習する必要がなくなりました。

Greedy-rolloutとは

現在までに見つけた最良の方策を用いて経路をサンプリングし、その経路長をベースラインとして使用する方法のこと。

参考文献

• ホップフィールド・ネットワーク
• Pointer Networks
• Neural Combinatorial Optimization with Reinforcement Learning
• Learning Combinatorial Optimization Algorithms over Graphs
• Attention! Learn to Solve Routing Problems
• Efficient Active Search for Combinatorial Optimization Problems
• Machine learning for combinatorial optimization: A methodological tour d’horizon
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies