[1Win4] Poster session 1

[1Win4-12] Ant Colony Optimization with Flexible Pheromone Evaporation for Constraint Satisfaction Problems

〇Saqier Wu¹, Koichiro Sato¹, Kazunori Mizuno² (1.Graduate School of Engineering, Takushoku University, 2.Takushoku University)

Keywords: constraint satisfaction problem, search, swarm Intelligence, ant colony optimization

近年，大規模かつ解決困難な制約充足問題(CSP)に対して，アントコロニー最適化(ACO)を用いて解決しようとする研究が盛んに行われている．ACOは人工アリのフェロモンコミュニケーションにより効率的な問題解決が見込めるが，フェロモン蓄積の偏りが適切ではない場合，局所最適に陥ってしまう危険性がある．これに対して，フェロモンの蒸発率を動的に変化させる研究が行われているが，解探索の状況に関わらず変化が単調であり，解決困難な問題に対応することが難しい．本研究では，解探索の状況に応じて柔軟にフェロモン蒸発率を調節する機能を備えたACOを提案する．本手法は，一定世代ごとにアリが構築した解候補の評価値の変化量に応じて蒸発率を変化させるものである．本手法を大規模かつ解決困難なCSPの具体的問題に適用することによりその有効性を実験的に示す．