[1Q3-J-2] 機械学習: 構造的モデリング

[1Q3-J-2-04] グラフ上の問題に対する難しいインスタンスの自動生成

〇佐藤 竜馬¹、山田 誠^1,2,3、鹿島 久嗣^1,2 (1. 京都大学、2. 理化学研究所 革新知能統合研究センター、3. JST さきがけ)

キーワード：難しいインスタンス、グラフ、アルゴリズム、強化学習

解決に長い時間がかかるインスタンス（難しいインスタンス）の発見は，アルゴリズムの高速化につながる重要なタスクであるが，現状は専門家が問題ごとに規則を発見することによりなされている。
本研究ではグラフ問題に焦点をあて，グラフ問題の難しいインスタンスを自動でかつ効率よく発見するアルゴリズムの開発を目指す。
自動で難しいインスタンスを発見できれば，専門家が問題ごとに難しいインスタンスの生成方法を分析する必要がなくなり，グラフアルゴリズムの研究を加速させることができる。
本研究では，グラフ問題の難しいインスタンスを生成する問題を最適化問題として定式化し，最適化問題を解くことで難しいインスタンスを生成する手法を提案する。
三彩色問題や最大クリーク問題など，理論上・応用上重要なグラフ問題を用いた実験では，提案手法が一貫してランダムベースの手法よりも数倍から数桁難しいインスタンスを生成できた。
特に，提案手法は三彩色問題において，専門家の考案した規則ベースの生成方法より優れた性能を示した。