Pointer networkを用いたトラップドア付きKnapsack問題の解法

• Item type: Symposium(1)
• 公開日: 2022-10-17
• タイトル: Pointer networkを用いたトラップドア付きKnapsack問題の解法
• タイトル / 言語: en
• タイトル: Solution of Knapsack problem with trapdoor using Pointer network
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 深層強化学習，NP完全，Knapsack問題，KnapSack暗号，トラップドア
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 情報セキュリティ大学院大学
• 著者所属: 情報セキュリティ大学院大学
• 著者所属(英): en
• 著者所属(英): Institute of Information Security
• 著者所属(英): en
• 著者所属(英): Institute of Information Security
• 著者名: 末吉, 璃子; 有田, 正剛
• 著者名(英): Riko, Sueyoshi; Seiko, Arita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Knapsack 問題は古くからから考えられてきた NP 完全問題である．近年，深層強化学習を用いて最適化問題へ応用する研究が増えている．2016 年には，Pointer network を用いた TSP の解法も提案され，更に Knapsack 問題の解法も検討．本研究では，深層強化学習ベースの解法がトラップドア付の Knapsack 問題に対してどこまで解く事ができるのか検証する．手法としては Pointer network と強化学習を使用して Knapsack 問題の最適解を近似する．トラップドアは村上らの研究による超増加性と偶奇性を組み合わせた複合トラップドア，さらにそれらにモジュラ変換を施したものそしてランダム性と超増加性と偶奇性単体でも比較した．本論文では，その提案手法アーキテクチャ及び実験結果を示し，今後の展望について考察する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Knapsack problem is an NP-complete problem that has been considered for a long time. In 2016, a method for solving the TSP using a pointer network was proposed, and a method for solving the Knapsack problem was also studied. In this study, we verify to what extent deep reinforcement learning-based solution methods can solve the Knapsack problem with trapdoors. The method uses a pointer network and reinforcement learning to approximate the optimal solution of the Knapsack problem. The trapdoor is a composite trapdoor combining hyper-increasing and even-oddness, which was studied by Murakami et al. and then modulo transformed, and randomness, hyper-increasing, and even-oddness alone. In this paper, we present the proposed method architecture and experimental results, and discuss future prospects.
• 書誌情報: コンピュータセキュリティシンポジウム2022論文集; p. 1012-1019, 発行日 2022-10-17
• 出版者 / 言語: ja
• 出版者: 情報処理学会