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

Edge-Sets: An Effective Evolutionary Coding of Spanning Trees


タイトルは面白そうなんだけど、40ページもあるのであまり読む気になれない。でも著者のRaidlさんはこの業界で有名な人のようなのでそのうち読むかも。

これで5つ全部のアブストを読み終えた。
どれを読むかはまた今度考えることにして、MOCKの論文を1本読んでしまうことにする。

Abstract

進化的アルゴリズムにおける根本的な設計対象として、解候補の個体表現方法とその個体表現に対するオペレータの設計がある。我々はネットワークデザイン問題に用いられる進化的アルゴリズムのSpanningTree表現としてエッジを直接エンコードする手法を提案する。その後初期化、交叉、突然変異オペレータをその個体表現に適した形で設計する。これらのオペレータは局所性と遺伝力、計算効率を向上させる。初期化と交叉はランダムスパニングツリーアルゴリズムを応用したものであり、このランダムスパニングツリーアルゴリズムには3つの手法、PrimおよびKruskal、ランダムウォークをそれぞれ解析的および実験的に用いた。本論ではエッジセットエンコーディングが進化的アルゴリズムでNP困難なDegree-constrained MST問題にいかに有効に作用するかを示す。提案アルゴリズムのオペレータは、簡単な拡張を行うだけで実行可能なスパニングツリーのみを生成するように設定でき、局所的で問題固有のヒューリスティクスを組み込むことができる。ネットワークランダムキーと重み配列を用いたBlogコード手法でスパニングツリーをエンコードする他手法との比較により、エッジセットエンコーディングの優位性が示された。そしてその差は特に大規模ネットワークで顕著であった。