[2N6-GS-1] 基礎・理論: 制約充足と最適化

[2N6-GS-1-04] 群知能による制約充足アルゴリズムにおける動的パラメータ調整

〇戸谷 太亮¹、水野 一徳¹、増金 拓弥¹ (1. 拓殖大学)

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

現実的な時間内に制約充足問題(CSP)の解を発見する手法として，蟻コロニー最適化(ACO)という群知能を用いたアルゴリズムの有効性が実験的に示されている．ACOには複数のパラメータが存在し，これらは任意の値を設定する必要がある．ACOのパラメータを問題に適した値に設定することができれば，高い確率で解を発見することができる可能性が高い．しかし，そのためには，多くの実験と経験によってパラメータの値を調整していく必要があり，これには多くの手間と時間がかかってしまう．本研究では，ACOのパラメータ調整を自動化し，パラメータ調整の手間の削減を目標とする．パラメータ調整を自動化したアルゴリズムに，PSOACOというアルゴリズムが提案されている．このアルゴリズムはACOによる解探索中に，粒子群最適化という群知能を用いて動的にパラメータを調整するアルゴリズムである．本研究では，PSOACOをCSPに適用し，大規模なCSPに対してより高い確率で解を発見するための改良を加えた手法を提案する．また，本研究では，CSPの一つであるグラフ彩色問題を用いて，提案手法の有効性を実験的に示す．