進化・免疫系に基づく適応学習型最適化法の開発とVLSIレイアウトCADへの応用

本年度は,評価関数曲面の構造に基づいて解の探索過程を自律的・適応的に調整する適応学習型最適化法の開発を目的に,具体的には以下の2点について研究を行った。1.開発手法の検証・改良免疫系でみられるランダム的な遺伝子組み替え交叉法を導入し,その効果として期待される探索領域の拡大および解集団内の遺伝的多様性の維持により,開発手法の解の品質面での性能向上を試みた。解候補の集団を構成して多点探索を行い,交叉法により生成された解候補のうち良好な解候補を集団に残す処理により探索の途中経過を解集団に反映させることで,自律的・適応的な適応学習型最適化を行うことができる。新規開発の交叉法を導入することにより,従来の交叉法を用いる場合に比べて,解の品質の向上,および解の探索時間の短縮といった,最適化手法としての性能向上が達成された。2.実データへの応用開発手法を実際的な配置配線問題に応用し,既存の最適化手法による結果と比較することにより,その優位性を検証した。具体的にはVLSIレイアウト設計における標準的な問題であるフロアプラン設計問題,標準セル配置問題,および概略配線問題などを取り上げた。評価関数としては,チップ面積最小化に加えて高速動作化・低消費電力化に関する項の導入を考えた。また高速動作化のための信号遅延時間の計算,および消費電力の計算において,より精密な値を乗めるために,アナログ回路シミュレータを用いる計算法を導入した。具体的な配置配線問題のデータとして,一般的に用いられている大規模なベンチマークデータを利用することで,既存の他手法との比較を容易にした。シミュレーション実験の結果,従来手法と比較して良好な配置配線結果が得られることを確認した。

本年度は,評価関数曲面の構造に基づいて解の探索過程を自律的・適応的に調整する適応学習型最適化法の開発を目的に,具体的には以下の2点について研究を行った。1.開発手法の検証・改良免疫系でみられるランダム的な遺伝子組み替え交叉法を導入し,その効果として期待される探索領域の拡大および解集団内の遺伝的多様性の維持により,開発手法の解の品質面での性能向上を試みた。解候補の集団を構成して多点探索を行い,交叉法により生成された解候補のうち良好な解候補を集団に残す処理により探索の途中経過を解集団に反映させることで,自律的・適応的な適応学習型最適化を行うことができる。新規開発の交叉法を導入することにより,従来の交叉法を用いる場合に比べて,解の品質の向上,および解の探索時間の短縮といった,最適化手法としての性能向上が達成された。2.実データへの応用開発手法を実際的な配置配線問題に応用し,既存の最適化手法による結果と比較することにより,その優位性を検証した。具体的にはVLSIレイアウト設計における標準的な問題であるフロアプラン設計問題,標準セル配置問題,および概略配線問題などを取り上げた。評価関数としては,チップ面積最小化に加えて高速動作化・低消費電力化に関する項の導入を考えた。また高速動作化のための信号遅延時間の計算,および消費電力の計算において,より精密な値を乗めるために,アナログ回路シミュレータを用いる計算法を導入した。具体的な配置配線問題のデータとして,一般的に用いられている大規模なベンチマークデータを利用することで,既存の他手法との比較を容易にした。シミュレーション実験の結果,従来手法と比較して良好な配置配線結果が得られることを確認した。