分散breakout: 反復改善型分散制約充足アルゴリズム
横尾 真, 平山 勝敏
情報処理学会論文誌, Vol.39, No.6. pp. 1889--1897, 1998.


本論文では分散制約充足問題を解くための新しいアルゴリズムである分散 breakoutアルゴリズムを提案する. 本アルゴリズムは集中型の制約充足問題を解くための 反復改善型のアルゴリズムであるbreakoutアルゴリズムに触発されたものであ り,各エージェントは近傍のエージェントと現在の変数の値の割当,可能 な改善方法を交換し,エージェント全体として制約条件違反の個数が減少する ように値の変更を行う. また,エージェント全体として局所最適に陥ったことを検出するのではなく, 近傍との通信のみで検出できる,より弱い条件である準局所最適を検出し, 制約の重みを変更することにより準局所最適から脱出する. 実験的な評価により,本アルゴリズムは グラフの色塗り問題の非常に難しい問題のインスタンス に関して既存のアルゴリズムより効率的であることを示す.