巡回セールスマン問題を深層強化学習で解いてみる

この記事は BrainPad Advent Calendar 2018 8日目の記事です。
昨年のAdvent Calendarでは、数理最適化（巡回セールスマン問題から始まる数理最適化）と強化学習（Keras-RLを用いた深層強化学習コト始め）を取り上げました。今年はそれらを組合せたアプローチをご紹介しようと思います。

数理最適化と強化学習

ビジネス課題の解決アプローチとして落とし込まれることも多い（離散）数理最適化問題ですが、具体的な解法としては、大きく分けると

• ヒューリスティクス解法
• 厳密数値解法
  の２つがあるかと思います。ヒューリスティクス解法は、問題特性に関するドメイン知識を活用しながら良い近似解を得ることを目指します。巡回セールスマン問題ではローカルサーチの一種である2-opt法などが有名かと思います。一方、厳密数値解法は、前回ご紹介したような汎用的なソルバーを用いて、探索空間や探索方法に工夫を加えながら数値的に厳密解を得ようとするものです。

それぞれの解法には、以下のような表裏一体でトレードオフとなっている長所、短所があり、実際の課題においては、それらを組合せて用いることが多くなっています。

解法	長所	短所
ヒューリスティクス解法	- 解を得るまでの計算時間（推定時間）が短い	- 問題固有のドメイン知識が必要　 - 基本的には近似解
厳密数値解法	- 問題汎用的なアプローチ - 最適解が期待できる	- 解を得るまでの計算時間（推定時間）が長い

今回ご紹介する機械学習や強化学習によるアプローチは、これらのトレードオフを解決しようというアプローチです。
敢えて図示するとこんな感じ。

このアプローチについては、2017年にGoogle Brainから組合せ最適化問題に対する強化学習アプローチについての論文「Neural Combinatorial Optimization with Reinforcement Learning」が出ており、今回はその概要を（前回同様）「巡回セールスマン問題、TSP」に沿って紹介させていただきます。

組合せ最適化問題とPointer Network

上記論文では、Seq2Seq（下図）などの文章系列生成からの類推に基づいて、解きたい問題のパターン（TSPの場合は地点座標の集合、ないし列）を入力し、その入力の特徴に基づいて、希望の組合せのパターン列（巡回する地点の順列）を生成するネットワークを学習することを考えています。

ただし、文章生成と異なる点は、組合せ最適化の場合、入力集合の中から（重複なく）選択しながら出力パターン列を生成する必要がある点です。これを可能にするため、論文では下図のようなPointer Network¹というネットワークを利用しています。

Seq2Seqと同様Encoder、Decoderから構成され、青い部分がEncoder、赤い部分がDecoderです。Pointer NetworkのDecoder部分は、文章系列生成で導入されたAttention機構²と同じような参照機構（Pointing機構）を持ち、各出力からEncoderの出力列への参照を行い、尤もらしい参照先をDecoderの次の入力として出力系列を順次生成していきます。

再帰ネットワークと共に、このPointing機構の参照ネットワークをデータから学習することで、より良い組合せのパターン列を出力できるようになることを期待します。

強化学習の利用

論文では、上記Pointer Networkの学習に強化学習を用いています。一方、実はPointer Networkの提案論文¹では、既存ソルバーの解を教師として用意し、教師あり学習を行っています。

強化学習の詳細は昨年の記事を参照いただくとして、２つの学習アルゴリズムの大きな違いは、正解教師データをsupervisionによって外部から与える必要がある（教師あり学習）か、もしくは、学習データを自ら探索して取得していく（強化学習）か、にあります。その特徴に伴って２つの学習アルゴリズムには、以下のような代表的な長所、短所があります。

学習手法	長所	短所
教師あり学習	- 達成精度に対するデータ効率が良い	- 事前に教師データを準備する必要がある
強化学習	- 自らデータを探索し自律的に学習する	- 試行錯誤を伴うためデータ効率が悪い

強化学習はデータ探索の試行錯誤を伴うため、達成精度に対する必要データ量の効率は悪くなる傾向にあります。一方、性質の良くない系列（不正解）も含めて様々な詳細パターンを経験するため、最終的にはより豊富な表現が得られる可能性も秘めています。実際、参照論文では、元の教師ありの結果と比較し、より良い性能を発揮したことが報告されています。

一方、強化学習の大きなメリットは、ルールや達成したい目的のみから、supervisionやドメイン知識無しで自律的に学習を進めることができる点です。この論文のアプローチは、AlphaGo Zero³のように、ヒューリスティクスに準ずる（もしくは置き換わる）ような組合せ生成パターンを、ルールのみからスクラッチ学習しようという精力的な試みとなっています。

以上から推察される通り、本アプローチの適用ケースとしては

• ヒューリスティクスが与えにくいような条件が複雑な難しい問題を解く必要があるケース
• 最適化の専門家が不在の中、尤もらしい解を（適用業務制約上）短時間で得る必要があるケース
  などが挙げられるかと思います。

実装例

実装例の全体は Github（もしくは他の方の実装）を参照いただくとして、実装の基礎となる内容のみ簡単に記載します。

構築ネットワークについて

まず、構築ネットワークであるPointer Networkについてです。
上記の様に、Pointer NetworkはEncoderとDecoderから構成されます。Encoderとしては、例えば単純なLSTM Cell（Layer）を活用して構成することができます。

Encoder

import tf
from tf.keras.layers import LSTMCell

class Encoder(object):

    def __init__(self, config):
        ...
        # 入力地点データのテンソル定義
        self.inputs = tf.placeholder(tf.float32, [self.batch_size, self.seq_length, self.input_dim])

        # 再帰セル定義など
        self.enc_rec_cell = LSTMCell(self.num_neurons)


    # ネットワーク定義
    # Decoderとの対比から、（LSTMレイヤでなく）敢えて明示的にLoopで記載
    def build_model(self, inputs):

        input_list = self.transpose_input(inputs)

        enc_outputs, enc_states = [], []
        state = self.get_initial_state()

        for input in input_list:
            # 再帰ネットワークへの入出力
            output, state = self.enc_rec_cell(input, state)

            enc_outputs.append(output)
            enc_states.append(state)

        return enc_outputs, enc_states

一方、Decoder側はPointing機構を持つ以下のようなネットワークを構成します。

Decoder

import tf
from tf.keras.layers import LSTMCell
from tf.distributions import Categorical

class Decoder(object):

    def __init__(self, config):
        ...
        self.infty = 1.0E+08

        # 初期入力値のパラメタ変数（Encoderセルの出力次元、[batch_size, n_neuron]）
        first_input = tf.get_variable("GO", [1, self.num_neurons])
        self.dec_first_input = tf.tile(first_input, [self.batch_size, 1])

        # Pointing機構のパラメタ変数
        self.W_ref = tf.get_variable("W_ref", [1, self.num_neurons, self.num_neurons])
        self.W_out = tf.get_variable("W_out", [self.num_neurons, self.num_neurons])
        self.v = tf.get_variable("v", [self.num_neurons])

        # 再帰セル定義など
        self.dec_rec_cell = LSTMCell(self.num_neurons)
        self.mask = 0


    # ネットワーク定義
    # Pointing機構による出力列（ネットワーク）の構成と、対応対数尤度の算出
    def build_model(self, enc_outputs, enc_states):

        output_list = self.transpose_input(enc_outputs)

        dec_logp = []

        input, state = self.dec_first_input, enc_state
        for step in range(self.seq_length):

            # 再帰ネットワークへの入出力
            output, state = self.dec_rec_cell(input, state)

            # Pointing機構への入出力
            masked_scores = self._pointing(enc_output, output)

            # 各入力地点の選択(logit)スコアを持った多項分布の定義
            prob = distr.Categorical(logits=masked_scores)

            # 確率に応じた次地点の選択と、該当対数尤度の定義
            position = prob.sample()
            dec_logp.append(prob.log_prob(position))

            # 既訪問地点マスクと次入力の更新
            self.mask = self.mask + tf.one_hot(position, self.seq_length)
            input = tf.gather(output_list, position)[0]

        return dec_logp


    # Pointing機構定義
    # Encoder出力群（のEmbedding）の情報＋Decoder出力の逐次情報から、参照先別の(logit)スコアを算出
    def _pointing(self, enc_output, dec_output):

        # Encoder出力項（[batch_size, seq_length, n_neuron]）
        enc_term = tf.nn.conv1d(enc_output, self.W_ref, 1, "VALID")

        # Decoder出力項（[batch_size, 1, n_neuron]）
        dec_term = tf.expand_dims(tf.matmul(dec_output, self.W_out), 1)

        # 参照先別のスコアの算出（[batch_size, seq_length]）
        scores = tf.reduce_sum(self.v * tf.tanh(enc_term + dec_term), [-1])

        # 既訪問地点（batch毎に異なる）のスコアに-inftyを付与
        masked_scores = scores - self.infty * self.mask

        return masked_scores

ここで、重複選択を避けるため、既選択地点に対して都度動的にmaskを掛けネットワークを構成していることにご注意ください。また、（選択可能な地点集合に関するMulti-Nominalな分布を仮定し）Pointing機構が与える各地点の次訪問確率値に基づき、生成系列の尤もらしさ（尤度）を算出しています。この尤度は、教師あり学習の損失関数の算出や、強化学習の方策関数として活用されるものです。

強化学習アルゴリズムについて

次に、強化学習のアルゴリズムについてです。
こちらについては、詳細な記載を避け、論文にある疑似コードのみを以下に転記してアルゴリズムの概要をご紹介するに留めます。ご興味のある方は実装ソースや脚注参考文献などをご参照ください。

この学習アルゴリズムは、Actor-Critic、ないしREINFORCE with Baseline⁴と呼ばれている典型的な方策勾配ベースの手法となっています。この擬似コードに現れる p_{\theta} が方策関数（Actor）、b_{\theta_v} が価値関数（Critic、もしくはBaseline）と呼ばれる関数で、これらを上記のEncoder、Decoderのネットワークを用いて構成します。

具体的にはそれぞれ、

• 方策関数：Encoder-Decorderからなるネットワークが与える生成配列の尤度値
• 価値関数：Encoder+FC層からなるネットワークが与える期待報酬（巡回路長）値
  によって構成されます。

学習用の（入力）地点集合に対して、方策関数のネットワークによって巡回路を生成し、生成巡回路に対してこれらの関数が与える値を上記アルゴリズムによって評価、より高い報酬が得られる様にネットワークパラメタの更新を進めていきます。

試行結果

上記のような実装に基づき、実際に強化学習によってより良い報酬（より短い巡回路長）を与える出力系列が得られるか、実験的に学習を行ってみました。今回は簡単のため、ランダムに発生させた10地点に対して学習を行いました。

128 [パターン/batch] x 1,000 [batch] ~ 150,000 [パターン] 程度のデータを学習させた後、学習された方策関数ネットワークを用いて、テスト地点データに対して最適巡回路を推定してみたものが以下の図です。（最適巡回路の算出には、100個の巡回路を生成し、そのベストを用いています。）

RL Bestが推定された最適巡回路、OR Solverがソルバによって与えられた（最適）巡路となっています。少ないデータ量での学習でしたが、最適巡回路を生成し得るネットワークが学習できていることが分かります。一方RL Sampleは最適経路の推定時に生成した100個の巡回路を単純に重ねたもので、色が濃いほどより多く選ばれている経路になっています。今回学習されたネットワークは必ずしも決定論的に経路を出力している訳ではなく、微妙な地点間（特に近接する地点間）に関してはある程度不定性を持って悩みながら経路生成していることが伺えます。今後、学習データを増やしたり、学習ネットワークを工夫することで、より不定性の少ない出力が可能になっていくであろう、と考えられます。

また、今回の学習ネットワークが、局所的な経路を積み重ねての系列生成であるため、

• 少ない地点で学習したネットワークを用いての多地点巡回路の推定
• 訪問地点の更新に伴う、残り地点に対する最適巡回路の更新
  なども柔軟に行うことができ、これらはより広いビジネス適用ケースが想定可能であることを示唆しています。

前者を試したのが以下の例です。
この例では20地点で学習し、29地点（実際の地図上の地点⁵）の巡回路の推定を行っています。

Solverの結果とは乖離しているものの、ある程度の巡路を得ることができました。近い地点間の訪問順序に不定性が伴うことも同様に伺えます。参照論文でも、このような外挿推定力なども考慮した性能評価を行っています。

下図は後者について試してみたものです。当初計画の10地点の訪問巡路から、実際の訪問地点が（今回はランダム）決まって行った際に、残りの地点を巡回しつつ、緑の最終帰還地点に戻るまでの最適経路を再推定してみたものです。

今回のネットワークであれば入力地点集合を変更するだけでこのような柔軟な推定が容易に可能となります。また、訪問地点が減っていくのに応じて、選択巡路の不定性が（予想通り）減っていっていることも見て取ることができます。

以上、簡単な学習を行った結果を、今回のアプローチの特殊性に関連する事柄を中心にお示ししました。
一方、今回は概念検証のため簡易的な実装を用いて、実験的に試行してみたものです。実際の論文では、補足機構や、探索アルゴリズムの追加によるさらなる生成巡回路の改善を図り、100地点を越えるような問題に対しても、ヒューリスティクスや教師あり、厳密最適解と比較可能なレベルの解の出力を実現しています。ご興味のある方はぜひ実際の論文や関連資料をご参照ください。

まとめ

今回は数理最適化問題を、機械学習、特に強化学習で解くアプローチをご紹介しました。簡易的に試行したのみではありますが、長く研究されてきている数理最適化に対しても、機械学習によるアプローチが検討され得ることをご理解いただければ幸いです。この例のように、機械学習によって、既存のドメイン知識をデータに基づいて再構築し直したり、互いに補うことでより有効なビジネス活用を模索するケースは今後も益々増えてくるのではないかと思います。

今回のアプローチは、系列生成モデルに基づくもので、言語生成にとどまらず動画や音声生成に関連して、より高精度な学習モデル/アルゴリズムの発展が続いています。

• WaveNet:A Generative Model for Raw Audio
• Transformer: A Novel Neural Network Architecture for Language Understanding
  また同様に強化学習に関しても、より効率的な学習モデル/アルゴリズムの模索が続いています。
• Going beyond average for reinforcement learning
• Preserving Outputs Precisely while Adaptively Rescaling Targets

これらの構成技術の発展に伴って、本アプローチについても今後さらなる発展が期待されますので、引き続き注意深く見守っていきたいと思っています。

P.S.
昨日AlphaZeroのフルペーパーがScienceにパブリッシュされたようです。この例もまさに機械学習/強化学習によるドメイン知識の再構築の典型的な例ですね。

• AlphaZero: Shedding new light on the grand games of chess, shogi and Go

1. Pointer Networks ↩ ↩²

2. Neural Machine Translation by Jointly Learning to Align and Translate ↩

3. AlphaGo Zero: Learning from scratch ↩

4. Reinforcement Learning: An Introduction (R. Sutton, A. Barto) ↩

5. National Traveling Salesman Problems ↩