多層一般化相互割当問題の定式化とその解法

花田　研太  平山　勝敏  

誌名
電子情報通信学会論文誌 D   Vol.J96-D   No.12   pp.2908-2919
発行日: 2013/12/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (ソフトウェアエージェントとその応用論文特集)
専門分野: 理論
キーワード: 
マルチエージェントシステム,  分散協調問題解決,  分散最適化,  ラグランジュ緩和,  

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



あらまし: 
本論文では，一般化相互割当問題（GMAP）の従来の定式化と過制約な状況を扱う定式化の齟齬を解消する新しい問題として多層一般化相互割当問題（MLGMAP）を提案する．MLGMAPは，割り当てられない財の数を最小化した上で，効用最大，若しくはコスト最小となる財の割当てを求める問題である．また，MLGMAPを解く手法として2段階最適化手法とペナルティコスト最適化手法を提案し，それぞれに対して既存のプロトコルであるDisLRP-DAとDisLRP-IBFを適用した．提案手法を実験的に評価した結果，ペナルティコスト最適化手法におけるDisLRP-DAが最も有効であるが，ペナルティコストの設定によって，割り当てられない財の数を最小化できる問題例の数と得られる実行可能解の質にトレードオフの関係があることが分かった．