分散制約最適化問題:擬似木に基づくハイブリッド型の解法の提案

沖本 天太  山本 将  櫻井 祐子  横尾 真  井上 克巳  

誌名
電子情報通信学会論文誌 D   Vol.J96-D   No.12   pp.2920-2928
発行日: 2013/12/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (ソフトウェアエージェントとその応用論文特集)
専門分野: 理論
キーワード: 
分散制約最適化問題,  探索型の解法,  擬似木,  p-最適性,  

本文: PDF(640.2KB)
>>論文を購入


あらまし: 
分散制約最適化問題はマルチエージェントシステムにおける協調問題解決の基本的な枠組みである.この問題では,擬似木に基づく探索型の厳密解法の開発が重要である.これらの解法におけるメモリ使用量は,変数の数に対して多項式のオーダで抑えられるが,最適解を求めるのに多くの時間を要するという問題点がある.そのため,分散制約最適化問題では,どのようにして,擬似木に基づく探索型の厳密解法の実行時間を短縮するかが重要な課題となっている.本論文では,探索型の代表的な厳密解法と近似解法を組合せたハイブリッド型の解法を提案する.実験では,本解法が既存の探索型の厳密解法と比べ,より高速に求解可能であることを示す.更に,擬似木に基づく近似解法と擬似木に基づく探索型の厳密解法は相性が良いことを実験により検証する.