講演情報
[5H3-OS-18b-02]リザバー計算を用いた動的計画法の多重的活用による巡回セールスマン問題の計算
〇戸高 空1、明石 望洋1、山本 章博1 (1. 京都大学)
キーワード：
組合せ最適化、リザバー計算、線形回帰、動的計画法、巡回セールスマン問題
一度計算した結果を保存し，計算結果を効率的に再利用することは，古くから計算コスト削減のための重要な設計思想である．これらの効率化の多くは，単一の問題を計算する中での中間結果の利用に留まっているが，異なる複数の問題を同時に計算する場合においても，その計算過程を共有し，互いに活用することが可能である．実際に，最大値と最小値の関数では，それらを同時に計算することによる効率化が可能である．しかし，より複雑な問題設定において，人手で問題間の非自明な関係を見出し，計算過程の活用方法を設計するのは困難である．そこで本研究では機械学習により計算過程の活用方法を学習することを目指す．具体的にリザバー計算の手法に基づき，組合せ最適化問題を解く動的計画法で記録された計算結果を線形回帰の特徴量として用い，別の組合せ最適化計算に活用する手法を提案する．さらに，巡回セールスマン問題において本手法の有効性を確かめた．現在の計算の設計とは異なる，複数の計算プロセスが中間結果や状態を有機的に共有・再利用することで計算資源を効率的に活用する計算のあり方を示唆している．