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

最小矩形Steiner树问题是VLSI布线的一个关键问题,且是一个典型的NP完全问题。为了有效地解决VLSI布线中考虑障碍物的最小矩形Steiner树问题,提出了一种改进的离散粒子群优化算法。考虑到存在障碍物,设计了一个基于惩罚的适应度函数。引入了遗传算法的变异和交叉算子,增加了种群的多样性并适当地扩展了粒子的寻优范围。实验结果表明,算法是有效的,实现简单,且相对遗传算法能更有效迅速地收敛。