Study on Constrained Spanning Tree Problems with Genetic Algorithms
スポンサーリンク
概要
- 論文の詳細を見る
本研究では, データ通信ネットワークの基本構造である最小木問題(Minimum Spanning Tree problem:MST)に関して, 4種類の問題を取り上げ, それらの遺伝的アルゴリズム(GA)に基づく効率的な解法に関する研究を行っている.2次の目的関数を伴う最小木問題(q-MST), 多目的関数を伴う最小木問題(mo-MST), ノード次数(degree)の制約を伴う最小木問題(dc-MST), 及びターミナル(最小木の葉ノード)数の制約を伴う最小木問題(lc-MST)などは, ノードの数が多くなるほど計算時間が指数的に増加してしまうNP完全問題となるため, 従来の最適化手法の適用が困難であるという問題点が指摘されている.本研究では, 制約を伴う4種類の最小木問題を対象として, 問題の木構造特性と進化計算法の特長を結びつけた効率的な遺伝的アルゴリズムをそれぞれ提案しており, NP完全な組合せ最適化問題に対する進化計算法の有効性を明らかにしている.また, 現実のデータ通信ネットワークを構築するための効果的な基本設計法を明らかにしている.すなわち, 本論文は4種類の最小木問題のGAによる解法に関する理論と手法を確立している。
- 1999-06-15