Info

川東 勇輝, 松井 俊浩, 松尾 啓志 : "分散制約最適化問題の解法Max Sumにおける評価関数の緩和手法", 合同エージェントワークショップ&シンポジウム (JAWS2010) ショート発表論文 (Oct. 2010)

Abstract

マルチエージェントシステムにおける協調問題解決を表す基本的な枠組みとして，分散制約最適化問題の研究が行われている．分散制約最適化問題の解法Max Sum は，複雑な制約網の問題に適用した場合に解の精度が低下する．この解の精度の低下は，制約網において自変数と制約がある隣接変数間の制約を評価関数に含める解法MS-Stable により改善される．しかしながら，評価関数で用いる制約が増えることにより各エージェントにおいて評価される部分問題の規模が拡大する問題がある．そこで本研究では，評価関数において隣接変数間の制約の一部を評価から除外する手法，制約網の構造によって使用する評価関数を切り替える手法，周辺関数の値に基づいてサイクル毎に評価関数を切り替える手法の3 つの手法を提案する．また，組み合わせ最適化問題である頂点彩色問題を例題として用いて，これら3 つの手法の解の精度，計算量を比較し，解の精度と計算量のトレードオフが得られることを示す．