多目的分散制約最適化問題における厳密/非厳密解法の提案

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

誌名
電子情報通信学会論文誌 D   Vol.J96-D   No.12   pp.2929-2938
発行日: 2013/12/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (ソフトウェアエージェントとその応用論文特集)
専門分野: 理論
キーワード: 
多目的分散制約最適化問題,  パレート解,  LPノルム,  P-最適性,  

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


あらまし: 
実世界に存在する様々な最適化問題では,異なる評価基準を同時に考慮する場合が存在する.多目的分散制約最適化問題(MO-DCOP)は,異なる評価基準をもつ複数の目的関数が存在する分散制約最適化問題(DCOP)である.DCOPとは,制約最適化問題における変数及び制約が複数のエージェントに分散された問題である.本論文では,MO-DCOPにおける最初の厳密解法を提案する.本解法の特徴を以下に示す.本解法では,(i) パレート解を求める古典的なLpノルム法,(ii) DCOPの解法で広く用いられている擬似木,(iii) 動的計画法を用いる.また(iv) 本解法の計算量は制約グラフの誘導幅の指数オーダーとなる.本解法では,マンハッタンノルムを用いた場合はパレート解を保証するが,ユークリッド/チェビシェフノルムを用いた場合はパレート解を保証しないことを示す.更に,MO-DCOPにおける非厳密解法を提案する.本解法は最適化問題における近似解の評価基準であるp-最適性に基づく解法であり,誤差の上界を事前に与えることができる最初の非厳密解法である.