確率的制約充足アルゴリズムにおける局所最適構造

スポンサーリンク

概要

論文の詳細を見る
制約充足問題を解くために, 近年, 反復改良型の確率的探索アルゴリズムが盛んに研究されている.しかし, これらのアルゴリズムには, 解探索の途中で局所最適解に捕捉されてしまうという問題点がある.本論文では, 制約充足問題の確率的探索アルゴリズムに関して, 局所最適な状態に陥ってしまう原因について, 問題の制約構造に注目して解析する.具体的な対象問題としてグラフ色塗り問題, 探索アルゴリズムとして反復山登り法を用いる.また, 反復山登り法において, 制約違反を解消することができない構造を示し, 局所最適となる状態を生成する可能性がある構造である, LM pairを提示する.さらに, このLM pairが反復山登り法の探索効率と強く関連していることを実験で確認する.
人工知能学会の論文
2001-01-01

著者

関連論文

もっと見る

スポンサーリンク