分散制約最適化問題における 局所負荷を考慮した探索アルゴリズム 神奈川大学大学院 橋本大樹 能登正人 背景 ・制約充足問題(Constraint Satisfaction Problem) 人工知能分野における様々な問題を定式化する枠組 実際には… 過制約である問題が多い ・制約最適化問題(Constraint Optimization Problem) CSPでは定式化することが困難なものを扱う問題 制約最適化問題 制約充足問題(CSP) ・解は充足可能か充足不可能の２通り 過制約問題 制約最適化問題(COP) ・解は解の質，またはコストによって表される ・組み合わせの中で最も最適な解を探索できる 既存の探索手法 CSPの解法を制約緩和し，制約違反を最小にするなどしてCOPに 適応させたアルゴリズムが多い 非同期分散最適化手法(Adopt) ・DCOPの解法 ・深さ優先探索を基にした非同期分散探索手法 ・既存のアルゴリズムより効率，記憶量等の改善が証明されている Adoptのアルゴリズム 前処理 ・深さ優先探索木の形成 parent x1 x1 x2 x2 x4 x3 制約グラフ x3 x4 深さ優先探索木 child Adoptのメッセージ通信 メッセージの役割 VALUE 値の変更を下位近傍エージェントに伝える COST 下界値，上界値，値の変更等を親エージェントに伝える THRESHOLD 閾値を調整，振り分け子エージェントに伝える TERMINATE 実行終了を子エージェントに伝える メッセージの相互関係 x1 THRESHOLD messages VALUE messages x2 x3 COST messages x4 処理概要 下位エージェントに値の送信 x1 情報からコストを算出，値の決定 X２までの合計コスト 親エージェントに情報の送信 x2 X４までの合計コスト X３までの合計コスト x3 x4 情報から値の決定 全体の最適化 本研究では Adoptの特徴 ・全体の総コストを最適化 ・上位エージェントは下位エージェントとの間のコス トを知らない ・全体の総コストは最適でも局所的に負荷がかかる 可能性がある 新たなメッセージの追加を行い局所負荷を考慮する グラフ色塗り問題 制約違反領域 制約充足領域 全体の最適化の場合 局所を考慮した最適化の場合 提案概要 下位エージェント間とのコスト は考慮しない x1 局所的な負荷がかかる可能性 x2 x3 問題によっては一点に負荷が 集中しないような処理が必要 x4 メッセージの提案 メッセージ相互関係 THRESHOLD messages x1 VALUE messages COST messages ADDITIONAL messages x2 x3 x4 値を上位エージェントに知ら せるメッセージ 評価方法 グラフ色塗り問題における既存の手法と局所制約違反数を比較する Ｘ 制約違反の分布 を比較 Y Ｚ 制約違反コスト Ｘ＜Ｙ＜Ｚ エージェント数が多くリンク密度が大きい場合違いが現れる 今後の課題 ・密な問題でシミュレーション評価を行う ・実際の重みをどのようにすればよいか ・効率にはどの程度の影響がでるか ・ある程度の距離までメッセージを送信できる ようにする
© Copyright 2024 ExpyDoc
