[2T1-GS-10] AI応用：一般

[2T1-GS-10-02] 深層強化学習によるナップサック問題の解法に関する研究

〇末吉 璃子¹、有田 正剛¹ (1. 情報セキュリティ大学院大学)

[[オンライン]]

キーワード：Knapsack暗号、Knapsack問題、Pointer Network、深層強化学習、トラップドア

近年、機械学習の発展に伴い深層強化学習を最適化問題へ応用する研究が増えている。その中で本研究では、強化学習（Actor-Critic）とPointer networkを用いて、暗号に用いられるKnapsack問題を解く事を目標とし、強化学習（Actor-Critic）とPointer networkをTSPを解く事に応用したGoogle Brainの研究を元にKnapsack暗号のトラップドア(Knapsack問題)を解く為の手法を提案する。具体的には、ランダムと超増加性及びモジュロ超増加性トラップドアを問題とし、厳密解を求め、LLLアルゴリズムとの比較も行った。結果は、いずれの問題も30次元まで解く事が出来、問題によってはLLLアルゴリズムよりも精度が良かったが、基本的に高次元低密度ではLLLアルゴリズムの方が良い結果となった。