WEKO3
-
RootNode
アイテム
分散制約最適化問題の解法Max-Sumにおける評価関数の動的な変更手法
https://ipsj.ixsq.nii.ac.jp/records/87053
https://ipsj.ixsq.nii.ac.jp/records/87053e5c36767-1f85-41bf-8e40-3ca0be88e948
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL5311008.pdf (981.8 kB)
|
Copyright (c) 2012 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-11-15 | |||||||
| タイトル | ||||||||
| タイトル | 分散制約最適化問題の解法Max-Sumにおける評価関数の動的な変更手法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Dynamically Changing Utility-functions in Max-Sum Algorithm | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | [特集：エージェントの理論とその応用] Max-Sum，分散制約最適化問題，分散協調問題解決，マルチエージェント | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 名古屋工業大学 | ||||||||
| 著者所属 | ||||||||
| 名古屋工業大学 | ||||||||
| 著者所属 | ||||||||
| 名古屋工業大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nagoya Institute of Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nagoya Institute of Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Nagoya Institute of Technology | ||||||||
| 著者名 |
川東, 勇輝
松井, 俊浩
松尾, 啓志
× 川東, 勇輝 松井, 俊浩 松尾, 啓志
|
|||||||
| 著者名(英) |
Yuuki, Kawahigashi
Toshihiro, Matui
Hiroshi, Matuo
× Yuuki, Kawahigashi Toshihiro, Matui Hiroshi, Matuo
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 分散制約最適化問題（DCOP）はマルチエージェントシステムにおける分散協調問題解決の基礎的な表現として研究されている．本研究では，近年提案されたDCOPの解法であるMax-Sumアルゴリズムに注目する．Max-Sumは，問題を表現するfactorグラフに含まれるサイクルの数が少なければ比較的精度が高い解を得る傾向があるが，より多くのサイクルを含み，辺の密度が高い部分がある場合には解の精度が低下する．その解の精度の低下は，制約網において隣接する変数間の制約も含める評価関数MS-Stableにより改善されるが，各エージェントが評価する部分問題の規模は拡大する．そこで，解の精度と計算量のトレードオフを利用するために，解法の実行中に2つの評価関数を適応的に切り替える手法Z-MSSを提案する．Z-MSSでは各エージェントの利得の推定値に基づいて，評価関数を動的に変更する．利得の推定値により，詳細な評価が必要な部分に対してMS-Stableが割り当てられるため，計算量の増加を抑えつつ，比較的高い解の精度を得ることが期待される．また，Z-MSSはパラメータによって，ある程度は解の精度と計算量を調整でき，その適切な設定値は問題の種類やグラフの構造に依存する．頂点彩色問題および重み付きの二項制約からなる問題において，Z-MSSおよびそのパラメータの効果を実験により評価する． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Distributed Constraint Optimization Problems (DCOPs) have been studied as a fundamental model of multi-agents cooperation. We address the Max-Sum algorithm that has been proposed as a solution method for DCOPs. The Max-Sum algorithm generates relatively better approximate solutions when it is applied to less cyclic factor graphs. However, in the case that the graph contains many cycles and dense parts, the quality of the solution decreases. The solution quality can be improved by using extended utility function MS-Stable that additionally evaluates constraints among neighborhood nodes. On the other hand, the MS-Stable increases the size of the local problem that is computed in each agent. To employ this trade off, we propose Z-MSS that suitably switches the both types of utility-functions while the solution method is running. In Z-MSS, each agent switches utility functions based on the estimation values of its utilities. As a result, MS-Stable is applied to the parts of the problem that need detailed evaluation. The effects of Z-MSS and its parameters are experimentally evaluated applying it to graph coloring problems and weighted binary constraint problems. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 53, 号 11, p. 2419-2431, 発行日 2012-11-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
