| 講演名 | 2002/11/21 スタイナ木生成問題に対する遺伝的アルゴリズムを統合的に開発するフレームワーク 秦 純一, 若林 真一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,VLSIレイアウト設計における概略配線に対し,遺伝的アルゴリズム(GA)を用いてグラフ上でスタイナ木問題を解くためのフレームワークを提案する.提案手法ではGAが目的関数に対してブラインド探索であることを利用し、ユーザが評価値関数を設定することにより多くの配線問題を統一的に扱うことを可能にする.また,GA実行中に各オペレータのパフォーマンスに応じて適応的に交差手法等の適用確率を変更する.提案手法により種々のスタイナ木問題に対して個別にGAを開発する必要がなくなり,また,与えられた問題に適したGAを効率よく開発することが可能になる.本稿では,提案手法の有効性を示すためにVLSIレイアウト設計におけるグラフスタイナ木問題に対して提案フレームワークを適用した結果を示す. |
| 抄録(英) | 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. |
| キーワード(和) | VLSIレイアウト設計 / 遺伝的アルゴリズム(GA) / スタイナ木問題 |
| キーワード(英) | VLSI layout design / Genetic Algorithm / Steiner tree problem |
| 資料番号 | CPSY2002-69 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CPSY |
|---|---|
| 開催期間 | 2002/11/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Computer Systems (CPSY) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | スタイナ木生成問題に対する遺伝的アルゴリズムを統合的に開発するフレームワーク |
| サブタイトル（和） | |
| タイトル（英） | A Generic Framework to Solve Steiner Tree Problems in Graphs using a Genetic Algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | VLSIレイアウト設計 / VLSI layout design |
| キーワード(2)（和/英） | 遺伝的アルゴリズム(GA) / Genetic Algorithm |
| キーワード(3)（和/英） | スタイナ木問題 / Steiner tree problem |
| 第 1 著者 氏名（和/英） | 秦 純一 / Jun'ichi HATA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 若林 真一 / Shin'ichi WAKABAYASHI |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2002/11/21 |
| 資料番号 | CPSY2002-69 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 478 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |