[3J4-J-1] Fundamental AI, theory: search and application

[3J4-J-1-01] ACO with Pheromone Update by Negative Feedback Can Solve CSPs

〇Takuya Masukane¹, Kazunori Mizuno¹ (1. Department of Computer Science, Takushoku University)

Keywords:Constraint Satisfaction, Ant Colony Optimization, meta heuristics

近年，大規模な制約充足問題を解くための手法として，蟻コロニー最適化（ACO）が注目されている．ACOでは，評価が高い解候補をフェロモンとして蓄積させ，探索で利用している．本研究ではACOによる探索の更なる効率化を図るために，従来のフェロモンに加えて，評価が低い解候補もフェロモンとして蓄積させるACOモデルを提案する．解候補を生成する際，フェロモンを参考にして評価が高い解候補に近づくだけでなく，評価が低い解候補から遠ざかるようにすることで，より効率的な探索が行なわれることが期待される．ACOアルゴリズムの1つであるcunning Ant Systemに本提案モデルを適用したところ，探索の成功率の向上が見られた．