最小全域木を生成した遺伝的アルゴリズムによる直線スタイナー問題

• 吉村昌浩

  茨城大学工学部情報工学科

• 渋沢 進

  茨城大学工学部情報工学科

書誌事項

タイトル別名

• A rectilinear Steiner problem using genetic algorithms by the generation of minimum spanning trees

抄録

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

収録刊行物

• 情報処理学会設計自動化研報

  情報処理学会設計自動化研報 86 (3), 17-24, 1997

  一般社団法人情報処理学会

詳細情報

• CRID: 1573668926782829824
• NII論文ID: 110004028414
• NII書誌ID: AN1011091X
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles