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

Discrete Particle Swarm Optimization Algorithm for the Routing of VLSI Circuit

最小矩形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.