A Study on ASP-based Integration of Systematic and Stochastic Local Search
A Study on ASP-based Integration of Systematic and Stochastic Local Search
复制标题
基于ASP的系统随机局部搜索集成研究
DOI：
10.11517/pjsai.jsai2021.0_2e1os13a01
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
番原 睦則
中科院分区：
文献类型：
--
作者：
桑原 和也;田村 直之;番原 睦則
本発表では, SAT の発展形の一つである解集合プログラミング (Answer Set Programming; ASP) 技術を用い, 組合せ最適化問題に対して系統的探索と確率的局所探索を統合的に適用する手法を提案する. 提案手法は, 近似解法の一種である巨大近傍探索 (Large Neighborhood Search; LNS) のアイデアをベースにしている. LNS は解に含まれる変数の値割当ての一部をランダムに選んで取り消し, その変数のみに対して再割当てを行うことで解を再構築する反復解法である. 提案手法では, 解の再構築の操作を, 値割当てをなるべく維持したままでの再探索に置き換えることで, 取り消されなかった変数への再割当てを許す. これによって, どの値割当てを取り消すかに依存しすぎない探索を行うことができる. 提案手法を ASP ソルバー clingo 上に実装し, 国際時間割競技会の問題集 (全 21 問) を用いて性能評価を行った. その結果, 提案手法は, 通常の ASP 解法と比較して, 多くの問題に対してより良い解を得ることができた. また, 1 問について, 既知の最良値を更新することに成功した.