最小全域木を生成した遺伝的アルゴリズムによる直線スタイナー問題 (<特集>機能論理設計, アーキテクチャ設計支援と一般)

スポンサーリンク

概要

論文の詳細を見る
VLSI回路において配線のレイアウトを行う際に効率的になるように求める問題が考えられる。そこで、概略配線に使用されやすい直線スタイナー木を用いて、その効率的なレイアウトを求めた。しかし、この問題はNP-完全であるので最適解を得るのが困難である。そこで、本研究では遣伝的アルゴリズム (GA) を適用してこの解の近似値を求めた。また、今までの多くの研究はその評価基準に長さを用いているが、本研究では通信遅延で評価し、エルモアー遅延と呼ばれるものを用いた。更に、初期集団を生成する際にその一部として最小全域木を含ませることによって、最小全域木のない場合と比較して、最小値を最大で45%、平均値を最大で52%に削減することができた。その際、ノード数が多ければ多いほど解の改善率が大きくなる結果を導いた。
1997-12-11

著者

関連論文

もっと見る

スポンサーリンク