生物システムの適応性に基づく確率的最適化法によるVLSI配置線手法の開発

基于生物系统适应性的随机优化方法开发VLSI贴装线方法

• 批准号: 06750411
• 负责人: 小圷 成一
• 金额: $ 0.58万
• 依托单位: Chiba University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06750411/
• 关键词: 組み合わせ最適化; VLSIレイアウト; フロアプラン; 遺伝的アルゴリズム; 免疫システム

本研究では、VLSIの配置配線問題のように解の品質と求解の高速性が要求される問題に対応するために,遺伝的アルゴリズムを高速化する新たな近似計算法を開発した。具体的には以下の点について研究した。(1)これまでに開発を進めてきた遺伝的アルゴリズムを用いたCADシステムを利用して、比較的小規模な問題における最適解への収束性と計算時間の関係を、計算機シミュレーションを通して求めた。(2)生物システムの進化における個体間の競争・淘汰が局所的分散的に行われる点に着目して、個体間の相互作用を隣接する要素に限定することにより、評価関数の計算を簡略化する近似計算手法に関して研究を進めた。(3)遺伝・進化と同様に生物系の適応システムのひとつである免疫システムについて、工学的システムの最適化手法に導入すべく、基礎的研究を行った。具体的には免疫システムの持つ速やかな適応性を導入した最適化手法を新たに構築し、求解の高速化をはかった。(4)開発手法を比較的大規模なフロアプラン設計問題に応用し、開発手法と既存の手法を解の品質と計算時間に関して比較して、開発手法の有効性を検証した。

In this paper, a new approximation method for solving the problem of VLSI routing is developed. The specific points are as follows: (1)This is the first time that a computer system has been developed and used to compare the optimal solution of a small-scale problem with the relationship between convergence and computation time. (2)The evolution of biological systems involves the simplification of the calculation of inter-individual competition, elimination, dispersion, and interaction between individuals. (3)The research of genetic evolution and biological systems is carried out in the fields of immune systems, optimization methods of engineering systems, and basic research. Specific immune system, speed, adaptability, optimization methods, new construction, speed of solution, etc. (4)Development method comparison large-scale design problems, development method, existing method solution quality, calculation time, development method effectiveness verification

项目成果

Seiichi Koakutsu: "Genetic Simulated Annealing for Floorplan Design" Control and Information Sciences. 197. 268-277 (1994)

Seiichi Koakutsu：“平面设计的遗传模拟退火”控制和信息科学。

田澤 功: "免疫機構を取り入れた遺伝的アルゴリズムのVLSIフロアプラン設計への応用" 計測自動制御学会論文誌. (掲載予定). (1995)

Isao Tazawa：“结合免疫系统的遗传算法在 VLSI 平面图设计中的应用”，仪器与控制工程师学会会刊（待出版）。