求解VLSI布线问题的离散粒子群优化算法  

Discrete Particle Swarm Optimization Algorithm for the Routing of VLSI Circuit

作　　者：刘耿耿[1] 王小溪[1] 陈国龙[1,2] 郭文忠[1] 王少铃[1] 

机构地区：[1]福州大学数学与计算机科学学院,福州350108 [2]福州大学离散数学及其应用教育部重点实验室,福州350003

出　　处：《计算机科学》2010年第10期197-201,共5页Computer Science

基　　金：国家973重点基础研究发展规划项目(No.2006CB805904);国家自然科学基金项目(No.10871221);福建省科技创新平台计划项目(2009J1007);福州大学大学生科研训练计划资助

摘　　要：最小矩形Steiner树问题是VLSI布线的一个关键问题,且是一个典型的NP完全问题。为了有效地解决VLSI布线中考虑障碍物的最小矩形Steiner树问题,提出了一种改进的离散粒子群优化算法。考虑到存在障碍物,设计了一个基于惩罚的适应度函数。引入了遗传算法的变异和交叉算子,增加了种群的多样性并适当地扩展了粒子的寻优范围。实验结果表明,算法是有效的,实现简单,且相对遗传算法能更有效迅速地收敛。Rectilinear Steiner Minimal Tree is one of the key problems in the routing of Very Large Scare Integration and a typical NP-complete problem.To solve the rectilinear Steiner minimal tree with rectangular obstacles（RSMTRO）problem effectively,an improved discrete particle swarm optimization（IDPSO）algorithm was proposed.Considering exi-stence of obstacles,the penalty-based fitness function was designed.The principles of mutation and crossover operator in genetic algorithm were incorporated into the proposed PSO algorithm to achieve better diversity,and the scope of the particle optimization was appropriately expanded.Simulation results show that IDPSO algorithm can efficiently provide RSMTRO solution with good quality and converges more efficiently and rapidly than genetic algorithm.

关 键 词：超大规模集成电路 布线 粒子群优化 最小矩形Steiner树 障碍物 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]