生態ピラミッド階層を取入れた遺伝的アルゴリズムの研究とVLSIチップ設計への適用

点击翻译按钮获取中文摘要

最適解を求めることが困難な組合せ最適化問題に対する近似解法として生物進化プロセスの概念に基づいた遺伝的アルゴリズムが注目されている。本研究では対象とする問題に対するパラメータ設定を自動的に行う階層遺伝的アルゴリズムを開発すると共に、提案アルゴリズムの有効性を実験的に検証することを目的した。本研究の研究実施結果を以下に示す。1.階層遺伝的アルゴリズムの提案:生物界における生態ピラミッド構造の概念を導入した階層遺伝的アルゴリズムを提案した。提案手法では生物界での生態ピラミッドの生物の捕食関係における強弱を遺伝的アルゴリズムにおける人口数の大小とみなし、パラメータ値の異なる複数の遺伝的アルゴリズムを並列に実行させることより生態ピラミッドを模倣した。また、ピラミッド階層の異なる遺伝的アルゴリズム間で解を通信することで解探索の成熟度を推定し、パラメータ設定を自動的に行う機構を設けた。2.ハイパーグラフ分割問題に対する階層遺伝的アルゴリズムの開発:1.で提案した階層遺伝的アルゴリズムに基づいて、VLSIレイアウト設計等の応用分野で重要な問題であるハイパーグラフ分割問題に対する階層遺伝的アルゴリズムを開発した。提案手法では1.で提案した手法に著者らが既に提案しているハイパーグラフ分割問題に対するヒューリステイックアルゴリズムを組み込んだ。3.提案手法の評価:2.で提案したハイパーグラフ分割手法をC言語を用いて、研究室現有の5台のSPARC-station10等のワークステーションにより構成される分散環境上に実現し、実際の大規模論理回路に基づくデータを入力として、計算機実験により従来手法との比較を行い、提案手法を評価した。ワークステーション上での高速処理と実験精度向上を実現するため、ワークステーションの2台の主記憶を現状の16MBから64MBに増設拡張した。