生物系の適応性・柔軟性に基づく確率的最適化法の開発とVLSI配置配線問題への応用

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

本研究は,VLSIの配置配線問題のように解の品質と求解の高速性が要求される問題に対するために,評価関数の構造に基づいて解の探索過程を自律的・適応的に最適化する機能を有する,最適化手法を開発することも目的とし,具体的には,以下の点について研究した.1.これまでの研究で開発を進めてきた遺伝的アルゴリズムおよび免疫的アルゴリズムに評価関数の構造に関する情報を蓄積する機能を付加した最適化手法を構築し,まず試験的に比較的小規模な問題に対して評価関数曲面の大局的および局所的構造の有無を調べた.2.開発手法を改善するために,遺伝的アルゴリズムにおいて評価関数の構造を効率的に遺伝子にコーディングする方法,および蓄積された情報の有用性に応じて必要な情報を適応的に取捨選択し遺伝情報として集積するための遺伝子組み替え法を検討し,また免疫的アルゴリズムの特徴のひとつである速やかな適応性を導入することにより,求解の高速化をはった.3.開発手法の実際的な問題への応用としてVLSIレイアウト設計におけるフロアプラン設計問題,および標準セル配置問題を取り上げ,開発手法と既存の手法による結果を解の最適性と計算時間に関して比較検討した.