複数解の展開と枝刈りを用いる分散制約最適化手法

松井 俊浩  松尾 啓志  

誌名
電子情報通信学会論文誌 D   Vol.J97-D   No.8   pp.1273-1283
発行日: 2014/08/01
Online ISSN: 1881-0225
DOI: 
論文種別: 論文
専門分野: 情報ネットワーク
キーワード: 
マルチエージェントシステム,  分散制約最適化問題,  協調問題解決,  探索,  

本文: PDF(1.2MB)>>
論文を購入




あらまし: 
分散制約最適化問題(DCOP)は,マルチエージェントシステムにおける協調問題解決を各エージェントに分散して配置された離散最適化問題として扱う,基礎的な研究分野である.DCOPの厳密解法として,木探索や動的計画法にもとづく分散アルゴリズムが提案されている.木探索に基づく解法は,メッセージ通信を介する反復的な処理を伴うため,通信にオーバヘッドがあれば,その影響を多く受ける.純粋な動的計画法に基づく解法には反復的な探索はないが,必要とする記憶とメッセージのサイズは,制約網に対する疑似木のinduced-widthに対して指数関数的である.記憶のサイズの制限のもとで,両者を併用する手法は提案されているが,探索点が単一であるか,大域的なコスト値に基づく枝刈りが考慮されていない.メッセージの交換を介する探索処理の反復回数を削減するために,木探索において複数の探索点を同時に展開し,それらに対応する複数の解を同一のメッセージにより送受信することは合理的である.本研究では,記憶とメッセージのサイズの制限のもとで,複数の解を同時に展開する木探索と動的計画法を併用する解法を示し,その効果を実験により評価する.