VLSI标准单元布局遗传交叉算子比较研究  

Research on genetic crossover for VLSI standard cell placement by comparing

作　　者：陈雄峰[1] 吴景岚[1,2] 

机构地区：[1]闽江学院计算机科学系,福建福州350121 [2]福州大学离散数学与理论计算机科学研究中心,福建福州350108

出　　处：《闽江学院学报》2013年第5期56-61,共6页Journal of Minjiang University

基　　金：国家自然科学基金项目(61170308)

摘　　要：遗传算法的成功之处在于其交叉、变异等进化机理,交叉算子性能对算法的整体性能有决定性的影响,因而成为了设计大规模问题遗传算法的关键因素.首先简要介绍VLSI标准单元布局问题定义及其染色体编码,给出4种主要交叉算子的基本思想及其算法步骤,并对其中循环交叉算子进行改进.而后使用标准测试例子对这4种交叉算子的性能进行深入的实验比较,分析交叉算子特征与性能的关联性,总结了高性能交叉算子的设计思想.改进型限定长度循环交叉算子的性能实验结果验证了该设计思想的有效性.The success of genetic algorithm is its evolutionary mechanism, including crossover and muta- tion. Crossover has a decisive influence on overall performance of genetic algorithm, so it has become a key factor in the design of genetic algorithm for large-scale problem. We first briefly introduce VLSI stand- ard cell placement problem and its chromosome coding, present basic idea of four major kinds of crossover and their algorithm steps respectively, and improve the cycle crossover. By using standard test examples, we conduct experiments on the performance of these four kinds of crossover for further comparing, analyze the correlation of their characteristics and performance, and then summarize the idea for designing high- performance crossover. Experimental results of the improved method named length-limited cycle crossover verify the validity of this idea.

关 键 词：遗传算法 VLSI标准单元布局 交叉算子 比较 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]