スタディ 01 · 強化学習・グラフニューラルネットワーク

強化学習を用いてTSPの経路を生成するグラフモデル

2018.09–2021.06・学部研究生

都市をグラフで表現し、経路へ追加する都市を強化学習で選ぶ探索プログラムを実装しました。

強化学習の設計

NeurIPS 2017グラフ組み合わせ最適化研究を参考にした実装

Reinforcement learningStructure2VecDeep Q-learningGraph neural networkTensorFlowNumPy

担当した役割と成果

研究目標: 都市が増えるほど組み合わせの数が急激に増えるTSPで、既存のアルゴリズムより速く短い経路を見つけることが目標でした。指導教員とともに強化学習で取り組みました。
担当する役割: 参考文献のグラフ表現とQ学習（Q-learning）のアイデアに基づき、TSP環境、モデル、学習ループ、挿入ルールを統合する実験用コードを実装しました。
成果: 都市の位置、距離、訪問状況をグラフとして入力し、モデルが選んだ都市を挿入ヒューリスティックで経路に追加する探索プログラムを作成しました。公開コードでベースラインと比較する実験を行い、学習がうまく機能しなかった原因も突き止めました。

実験結果と試行錯誤

元の設定で学習させたところ、ポリシーがすべての都市に対して同じQ値を出力し、都市が番号順に選択される結果となりました。

問題都市数ごとに行列のサイズが異なるため、入力サイズが固定されたニューラルネットワークにそのまま入れられませんでした。
解決Structure2Vecで都市ごとに埋め込みを作り、評価ネットワークが未訪問の都市ごとにQ値を付けるようにしました。
問題次の都市を選択するだけでは、経路上のどの位置に配置するかは決まりません。
解決都市の選択は学習モデルが行い、挿入位置は経路長が最も増加しにくい場所を探すヒューリスティックが決定するという組み合わせを採用しました。
問題短い経路が出現しても、それが学習効果によるものなのか、挿入ルールの効果によるものなのかを判別するのは困難です。
分析・検証都市の順序をランダムにした場合でも、同様の挿入ルールを適用して比較を行い、Q値およびTDターゲットの算出過程を追跡しました。ショートカット学習（short-cut learning）においては、学習ポリシーの改善は確認されませんでした。

OR-Tools解に対する平均経路長の比・学習範囲は都市30～400個・3つのseedの学習方策がすべて同じ経路を出しました
都市数（課題数）	学習済みポリシー	ランダム順序 + 挿入	円の挿入	最近傍点	学習済みポリシー vs ランダム（ウィルコクソン検定のp値）
20(100)・学習範囲外	1.11	1.11	1.03	1.18	0.96
50 (50)	1.13	1.14	1.05	1.21	0.24
100 (30)	1.12	1.13	1.06	1.22	0.38

Q値爆症
正規化なしで完全グラフ全体を加算したため、Q値が数百万単位まで増大し、更新時の損失が10¹⁵のオーダーにまで跳ね上がりました。
TD目標値エラー
目標値が「残りの都市」ではなく、常に「開始都市」のQ値に基づいて計算されており、nステップ後の状態も1つずれていました。
エピソードを100回分に短縮
大きなグラフは1エピソードあたり約45秒かかるため、10,000回繰り返すとシード（seed）あたり5日以上かかります。回数のみを減らし、その他の設定はそのままにしました。

次の実験で補完すべき点

最近のプロジェクトに関連する点

初めてニューラルネットワークを自分でコードとして実装した研究でした。グラフの要素や関係性を学習入力として表現した経験が、家具のパネルや面を認識する現在の研究につながっています。