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

Abstract: Rectilinear Stciner Minimal Trec is one of the key problems in the routing of Very I_argc Scare Integration and a typical NP-complete problem. To solve the rectilinear Steiner minimal tree with rectangular obstacles(RSMTRO)problem effectivcly,an improved discrete particle swarm optimization(IDPSO ) algorithm was proposed Considering existence 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.

Key words: Very large scale integration, Routing, Particle swarm optimization, Rectilinear stciner minimal tree, Obstacles