[3J4-J-1] 基礎・理論: 探索問題とその応用

[3J4-J-1-01] フェロモン更新に負のフィードバックを取り入れたACOによる制約充足問題の解法

〇増金 拓弥¹、水野 一徳¹ (1. 拓殖大学大学院工学研究科情報・デザイン工学専攻)

キーワード：制約充足、蟻コロニー最適化、メタヒューリスティクス

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