2006.07.26

Research

最小全域木の文献(調査候補3/5)

An Efficient Evolutionary Algorithm for the Degree-Constrained Minimum Spanning Tree Prolem

Degree-Constrainedな最小全域木問題って何?効果的な個体表現というのは面白そうなところ。アブスト訳を以下に。

Abstract

解候補の表現と変化オペレータは進化的アルゴリズムにおける基本的設計要素である。本論ではDegree-constrained最小全域木問題に対する新たな表現方法と有効なオペレータを提案する。重み付き無向グラフG(V,E)に対して、この種の問題はノードの次数が上限値d(d>=2)を越えない最小全域木を同定する。進化的アルゴリズムでは解候補は単純にエッジセットで表現され、特別な初期化と交叉、突然変異オペレータにより新たな実行可能解候補を生成される。従来の全域木表現に対して、提案手法ははるかに高い局所性を持ち、 かつ計算効率が高い。子個体は常にO(|V|)時間内に生成される。加えて本論では、どのように問題固有のヒューリスティクスが効果的に初期化や交叉や突然変異に、計算時間を増加させることなく組み込まれるかを示す。最大困難な500子の極値点を持つ困難な問題を用いて実験を行った結果、多くの問題で提案手法はいくつかの他手法よりも優れた解を数秒で同定することができた。この提案手法の基本的アイデアは、他のネットワーク最適化にも適用可能である。