[2E1-OS-13a] AIと制約プログラミング(1/3)

[2E1-OS-13a-02] フェロモン蓄積を動的に変更する蟻の集団による制約充足アルゴリズム

〇戸谷 太亮¹、水野 一徳¹、小池 祥太朗¹ (1. 拓殖大学)

キーワード：蟻コロニー最適化、群知能、制約充足問題

制約充足問題（CSP）とは，離散値をとるいくつかの変数に対して，与えられたすべての制約を満たす値の割り当てを発見する問題である．CSPの解探索手法として，蟻コロニー最適化（ACO）を用いたアルゴリズムの有効性が実験的に示されている． ACOは，蟻の採餌行動を参考にしたメタヒューリスティクスである．ACOでは，解探索において生成した評価が高い解候補の情報を，フェロモンマップ上にフェロモン蓄積量として記録する．このフェロモンの情報を次の解候補の生成に利用して解探索を行う．しかし，フェロモンの溜まり方によっては局所最適解に陥ってしまう可能性がある．本研究では，複数のフェロモン蓄積を備えたACOによる制約充足問題の解法を提案する．本手法は，蟻を複数のグループに分け，グループごとに対応したフェロモンマップに対して，それぞれ異なる方法でフェロモンを蓄積するものである．また，解探索の途中でグループサイズを調整することにより，フェロモン蓄積にバリエーションを持たせることで効率よく解を発見することを目指す．提案手法をCSPの例題の一つであるグラフ彩色問題に適用し，その有効性を実験的に確認する．