情報処理学会 第76回全国大会講演要旨

Particle Swarm Optimization（PSO）を拡張して制約充足問題へ適応する手法を提案する。
PSOとは魚や鳥の群れなどの行動からヒントを得て提案された多点探索手法であり、探索個体自身の最良解と群れ全体の最良解をもとに探索する。
PSOは関数最適化問題に適した手法であるが、制約充足問題へ適用する場合には離散変数の扱いが問題となる。
本研究では最良解からのハミング距離に応じて遷移確率を求める。それをもとに探索個体を移動させることによってPSOを制約充足問題へ適用した。また三色グラフ色塗り問題を対象とした評価実験により、本手法の有効性を確認した。