免疫系・遺伝系に基づく適応学習型最適化法の構築とVLSIレイアウト設計への応用

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

本研究は,大規模で複雑な評価関数曲面を有する組合せ最適化問題に対応するために,最適化の過程で評価関数の構造に関する情報を遺伝情報として収集・蓄積し,これに基づいて解の探索過程を自律的・適応的に調整する適応的学習型最適化手法の開発を目的とし,具体的には,以下の点について研究した.1.遺伝的アルゴリズムに評価関数の構造に関する情報を蓄積する機能を付加した適応的学習型最適化手法を構築した.評価関数曲面のどのような情報が利用可能かを調べるために,試験的に比較的小規模な配置問題について,評価関数の大局的および局所的構造の有無,問題のサイズおよびレイアウトモデルの相違による影響の有無を調べた.2.開発手法を改善するために,評価関数の構造を効率的に遺伝子コーディングする方法,および蓄積された情報の有用性に応じて必要な情報を適応的に取捨選択するための遺伝子組替え法を検討した.開発手法を比較的大規模な配置配線問題に応用した.具体的にはVLSIレイアウト設計におけるフロアプラン設計問題,および配置問題を取り上げ,種々のレイアウトモデルについて開発手法と既存の最適化法による結果を,解の品質と計算時間に関して比較検討した.