スタイナ木生成問題に対する遺伝的アルゴリズムを統合的に開発するフレームワーク

• Item type: SIG Technical Reports(1)
• 公開日: 2002-11-27
• タイトル: スタイナ木生成問題に対する遺伝的アルゴリズムを統合的に開発するフレームワーク
• タイトル / 言語: en
• タイトル: A Generic Framework to Solve Steiner Tree Problems in Graphs using a Genetic Algorithm
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学大学院工学研究科
• 著者所属: 広島大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者名: 秦, 純一; 若林, 真一
• 著者名(英): Jun-Ichi, Hata; Shin-Ichi, Wakabayashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では、VLSIレイアウト設計における概略配線に対し、遺伝的アルゴリズム（GA)を用いてグラフでスタイナ木問題を解くためのフレームワークを提案する。提案手法ではGAが目的関数に対してブラインド探索であることを利用し、ユーザが評価値関数を設定することにより多くの配線問題を統一的に圧公庫とを可能にする。また、GA実行中に各オペレータのパフォーマンスに応じて適応的に交差手法等の適用確立を変更する。提案手法により種々のスタイナ木問題に大して個別にGAを開発する必要がなくなり、また、与えられた問題に適したGAを効率良く開発することが可能になる。本稿では、提案手法の有効性をしめすためにVLSIレイアウト設計におけるグラフスタイナ木問題に対して提案フレームワークを適用した結果を示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a generic framework to solve Steier tree problems in graphs using an adaptive genetic algorithm in VLSI layout design. The proposed method is based on the fact that a genetic algorithm adopts a blind search strategy for objective functions. By preparing evaluation functions by users, this proposed framework can solve many routing problems in a unified manner. With the proposed method, one can easily obtain an efficient GA for a given routing problem without developing a GA for that particular problem. In this paper, to show the effectiveness of the proposed framework, experimental results for the Steiner problem in a graph are presented.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 2002, 号 113(2002-SLDM-107), p. 109-114, 発行日 2002-11-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会