次数制約付き最小生成木問題への 分散協調探索手法の適用

平成 23 年度創成シミュレーション工学専攻修士論文梗概集
計算システム分野
次数制約付き最小生成木問題への
分散協調探索手法の適用
学籍番号 22413508
氏名 伊藤 翼
指導教員 松尾啓示 教授
松井俊浩 准教授
1 はじめに
通信網を介する分散協調システムでは，
通信や競合
ている．
このフィーダ木の構築に類似した形式化と，
DPOP を応用したボトムアップな解法を，より一般的
解決，各ノードの能力を考慮したデータの同期が必
な木の構築問題である d-MST 問題に適用可能である．
要となる．そこで，次数制約付き最小生成木(d-MST:
4 分散 d-MST 問題の形式化
Degree-Constrained Minimum Spanning Tree) が重
d-MST 問題を各エージェントに変数と評価関数が
要な概念として研究されている．d-MST 問題の多く
分散して配置された分散d-MST 問題として形式化す
の集中的な解法が提案されているが，近年，非集中
る．その構成要素と制約は以下の通りである．
型システムが増加傾向にあるため，本研究ではマル
. 𝑛個のエージェント集合𝐴 = {𝑖|𝑖 = 0,1, … , 𝑛 − 1}
チエージェントの分散協調問題の枠組みで d-MST 問
題を形式化し，分散協調探索手法を提案する．
2 次数制約付き最小生成木(d-MST)問題
次数制約付き最小生成木問題では，
入力として重み
付き無向グラフ𝐺 = (𝑉, 𝐸, 𝑐)と，各頂点の次数𝑑(𝑖)
に対し，次数の制限数𝑏𝑖 が与えられる．このとき，
各頂点𝑖の次数を𝑑 𝑇 (𝑖)とするとき，𝑑 𝑇 (𝑖) < 𝑏𝑖 を満
たし，閉路を含まず，かつ，∑(𝑖,𝑗)∈𝐸𝑇 𝑐(𝑖, 𝑗)を最小化
各エージェント𝑖の変数𝑥𝑖 (辺の選択を表す)
. 各エージェント𝑖の隣接エージェント集合𝑁𝑏𝑟𝑖
. 変数𝑥𝑖 の値域𝐷𝑖 (𝐷𝑖 = 𝑁𝑏𝑟𝑖 ⋃{∅})
. 各エージェント𝑖の評価関数fi (𝑖)
𝑐(𝑖, 𝑥𝑖 )
fi (𝑖) = { 0
∞
𝑖 ≠ 𝑥𝑥 𝑖
𝑥𝑖 = ∅
(1)
otherwise(制約違反)
する連結無向成分が d-MST である．
. 木制約: 連結かつ閉路がない生成木である．
. 次数制約: ∀𝑖 ∈ 𝐴に対して，𝑑 𝑇 (𝑖) < 𝑏𝑖 を満たす．
3 関連研究
この形式化においては，各エージェント𝑖の変数𝑥𝑖 の
3.1 d-MST 問題の解法
値域𝐷𝑖 は接続すべき近傍エージェント集合と空集
Prim のアルゴリズムを d-MST 問題の解法として拡
合の和𝑁𝑏𝑟𝑖 ⋃{∅}となる．エージェント𝑖がこの変数
張した d-Prim が提案されている．Prim のように任
𝑥𝑖 の値を決定するとき，d-MSTの辺として辺(𝑖, 𝑥𝑖 )を
意の単一頂点のみを含む部分木からから処理を開始
選択することを表す．𝑥𝑖 = ∅のときエージェント𝑖は
する．部分木に属する頂点と，属さない頂点を繋ぐ
辺を選択しないことを表す．ある1 つのエージェン
辺のコストが最小で，かつ次数制約を満たす頂点を
トが辺を選択せず，それ以外の𝑛 − 1のエージェン
部分木追加していく．最終的に全ての頂点を追加し
トが辺を選択するとき，全てのエージェントの変数
たとき，d-MST の近似解を得る．
値の組み合わせは生成木を表す．木制約と次数制約
を満たし，min{∑𝑖∈𝐴𝑇 𝑓𝑖 (𝑖)}を満たす木を目的とする．
3.2 電力網の経路割り当て問題
分散制約最適化問題を電力網の経路割り当て問題
fi (𝑖)は式(1)のように評価される．
に適用する手法が提案されている．
電力網において，
5 提案手法 --分散協調探索手法--
全ての電力消費に対して配電線の最大容量を違反し
5.1 dd-mst(厳密解法)
ないように電力を供給するために，電力源を根とす
各エージェントがメッセージ交換を伴う協調探索
る生成木であるフィーダ木を構築する．木は有向辺
を行いd-MST 問題の厳密解を求めるdd-mstを提案す
の情報を持つ供給元変数で表現される．また，分散
る．まず，順序木を構築し，各エージェントの計算
制約最適化問題に対する厳密解法である DPOP アル
順序を得る．次に順序木に沿って，部分木集合をボ
ゴリズムに，資源制約の評価を追加した解法を用い
トムアップに集計していく．各エージェントは全て
平成 23 年度創成シミュレーション工学専攻修士論文梗概集
計算システム分野
表1： 解の質とサイクル数
の子のエージェントから受信する部分木集合の部分
木と自身の変数値より決定する辺の候補との組み合
わせを計算し，新たな部分木集合を生成して，親の
エージェントに送信する．根のエージェントは集計
された部分木集合から最適解を計算し，全てのエー
ジェントに最適解を伝播させる．
5.2 dd-mst の探索空間を削減する近似解法
dd-mstは制約による解候補の除去が不十分であれ
ば，最悪の場合，探索すべき組み合わせは｡∏𝑖∈𝐴 |𝐷𝑖 |
表２： 異なる部分木の制限数による探索
となる．従って，各エージェントの記憶容量や計算
量を考慮し，部分解の容量を制限することが望まし
い．そこで，dd-mstの部分木の数に制限数𝑘を設け，
部分木の特徴に基づく優先探索を用いて組み合わせ
の切り捨てを行う近似解法を提案する．
5.2.1 総コスト値に基づく優先探索
各エージェントの計算する部分木の総コストに基
セージを受信し，処理，送信する一連の動作の単位
づく優先探索による組み合わせ削減手法である．あ
である．組み合わせ数とは各エージェントの保持す
る部分木𝑇𝐴 が，別の部分木𝑇𝐵 よりも優先されるとき，
る部分木の平均数である．
総コスト𝑄𝑇𝐴 ，𝑄𝑇𝐵 と辺数|𝐸𝑇𝐴 |，|𝐸𝑇𝐵 | に対し，
表1から，
厳密解法であるdd-mstの誤差は常に0とな
𝑄𝑇𝐴 /𝐸𝑇𝐴 < 𝑄𝑇𝐵 /𝐸𝑇𝐵 のように比較される．
るため，最も解の質が高いことがわかる．しかしな
5.2.2 次数に基づく優先探索
がら，計算量が多いため「-」で示されるように現実
各エージェントの計算する部分木の次数の余剰数
的な時間で解が得られない場合がある．dd-mst-tc
の最小値に基づく優先探索による組み合わせ削減手
と dd-mst-tcmdeg は ， い ず れ の𝑛 に お い て も ，
法である．次数の余剰数とは，頂点𝑖の次数制約𝑏𝑖 と
dd-primよりも小さい誤差を実現できた．従って，探
次数𝑑(𝑖)の差𝑏𝑖 − 𝑑(𝑖)である．ある部分木𝑇𝐴 が，別
索空間の規模を小さく抑えつつ，ある程度の解の質
の部分木𝑇𝐵 よりも優先されるとき，次数の余剰数の
を保つ手法の適用の有効性を示すことができた．そ
集 合 𝑅(𝑇𝐴 )，𝑅(𝑇𝐵 ) に 対 し ， 𝑚𝑖𝑛{𝑅(𝑇𝐴 )} >
𝑚𝑖𝑛{𝑅(𝑇𝐵 )}のように比較される．
の一方で，表2から，𝑘の値を減少させると，誤差と
6 実験・評価
せると，最適値に近付けることが可能である．従っ
各手法を実験により比較、評価した．グラフの辺に
割り当てるコスト値の種類は，一様分布に従う10か
ら100の整数値とする．エージェント数𝑛は10から30，
実行不可能解の数が増加し，反対に𝑘の値を増加さ
て，解く問題の規模や各エージェントの能力に見合
った𝑘の値の設定が非常に重要であると考える．
また，表1から，サイクル数はdd-mstに関する2手法
次数制約は全て3とし，
10個の問題を解いた解に関す
がdd-primよりも常に少ない．
これは順序木に沿った
る各評価指標の平均値を評価する．評価対象は
1往復のメッセージ伝播のみを行うためである．
ただ
d-Primを分散処理化したdd-prim，5.1で述べた
し、なるべく小さいk を用いなければ、1 メッセー
dd-mst，5.2.1で述べたdd-mst-tc，5.2.1と5.2.2の
ジあたりの通信時間は大きくなる．
優先探索を組み合わせたdd-mst-tcmdegである．
解の
7 まとめ
質とサイクル数に関する結果を表1に示す．制限数𝑘
本研究では，分散協調問題の枠組みで，d-MST問題
は実行不可能解の数が0となる30,000に設定する．
ま
を形式化し，分散協調探索手法を提案した．部分木
た，異なる制限数𝑘を用いたときの結果を表2に示す．
の辺の総コストと次数の余剰数に基づく優先探索を
誤差とは，
各手法で得たd-MSTの辺の総コストと最適
用いて部分木の切り捨てる近似解法では，探索空間
値との差である．サイクルとはエージェントがメッ
を削減しつつ，一定の解の質を得ることができた．