2006.07.28

Research

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

A Comparison of Encodings and Algorithms for Multiobjective Minimum Spanning Tree Problems

MOCKの提案者による論文。97年なので、MOCKはこの研究成果の影響をうけている可能性が高い。



Abstract

与えられたグラフから最小全域木を求める問題は、古くからネットワークデザインの領域の重要な課題である。基本的なMST問題は効果的な解法が存在するが、Degree-constrainedや多目的である問題はNP困難である。昨今のDegree-constrained単目的MST問題の解法としては、Raidlの進化的アプローチやKnowlesとCornneのPrimのアルゴリズムの改良版が上げられる。多目的MST問題には、ZhouとGneのPruferベースエンコーディングを用いた進化的アルゴリズムの他にも、最適化分野の種々の近似構成的なテクニックが持ちいられる。本論では(Degree-constrained)単目的MST問題に最も高い性能を示す最新の手法を多目的MST問題に適用し、ZhouとGenの手法をベースにした手法と比較する。さらにその後我々が以前提案したPAESの改良型アルゴリズムを提案する。研究により、ダイレクトエンコーディング、および多目的MST用に再設計されたPrimのアルゴリズムベースの単純な繰り返し処理が、明確にPruferエンコーディングより良い性能を示すことが分かった。