[5H3-OS-18b] OS-18

2:15 PM - 2:30 PM JST(5:15 AM - 5:30 AM UTC)

[5H3-OS-18b-02] Solving the Traveling Salesman Problem via Multiple Utilization of Dynamic Programming by Reservoir Computing

〇Sora Todaka¹, Nozomi Akashi¹, Akihiro Yamamoto¹ (1. Kyoto University)

Keywords:

Combinatorial Optimization,Reservoir Computing,Linear Regression,Dynamic Programming,Traveling Salesman Problem

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