巡回セールスマン問題 - Shinichi0713/Reinforce-Learning-Study GitHub Wiki
深層強化学習を用いて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とは、推論時に各テストインスタンスに対して適切なパラメーターを探索することによって性能向上を狙う手法です。
対象となるインスタンスに特化したパラメーターを使用するので、未知のインスタンスに対する汎化性能も向上しますし、出力される経路長も改善されます。