基于位矩阵编码实现模拟集成电路模块布局的遗传算法

A Bit-Matrix Genetic Approach to Analog Module Placement

提出了一种新的实现模拟集成电路模块布局的遗传算法 .其位矩阵编码法提高了算法的搜索效率 ;模块的滑行处理使绝对布局问题转变成相对布局问题 ,极大地减小了搜索状态空间而不降低精度 ;复制过程中个体间的相似性检查避免了算法的早熟收敛 ;目标函数覆盖了模拟集成电路的特殊要求 ;正交实验的方法用来研究算法参数 ,其最优取值由另一个衍化遗传算法确定 .多种电路的测试结果表明 ,该算法性能优于传统的模拟退火算法 ,布局结果与手工布局相仿 。

This paper presents a novel approach to analog module placement with genetic algorithm. The bit matrix encoding is employed to improve search efficiency. It uses the principle of the divide and conquer technique, which allows the genetic algorithm to generate new configurations faster without degrading its search result. The idea of module slide is adopted to transform the absolute placement to the relative placement. It drastically decreases the configuration space without degrading search opportunities. Inspired by natural phenomena, similarity checks between the mating parents and between either parent and offspring are performed to improve the quality of evolution. They prevent the search from premature during the reproduction. The dedicated cost function covers the special requirements of analog integrated circuits. A fractional factorial experiment is conducted using an orthogonal array to study the algorithm parameters. A meta GA is applied to determine the optimal parameter values. The fractional factorial experiment shrinks the configuration space so that the meta GA can complete a search more efficiently. The Algorithm with optimized parameters is tested with several local benchmark circuits. The experimental results show this promising algorithm makes the better performance than the conventional simulated annealing approach with the satisfactory results comparable to manual placement. It considerably improves the design efficiency.