基于动态粒子群优化的X结构Steiner最小树算法  

X-Architecture Steiner Minimum Tree Algorithm Based on Dynamic Particle Swarm Optimization

作　　者：王景熠 朱予涵 周茹平 刘耿耿[1,2] WANG Jingyi;ZHU Yuhan;ZHOU Ruping;LIU Genggeng(College of Computer and Data Science,Fuzhou University,Fuzhou 350116,Fujian,China;Fujian Key Laboratory of Network Computing and Intelligent Information Processing,Fuzhou University,Fuzhou 350116,Fujian,China)

机构地区：[1]福州大学计算机与大数据学院,福建福州350116 [2]福州大学福建省网络计算与智能信息处理重点实验室,福建福州350116

出　　处：《计算机工程》2024年第9期226-234,共9页Computer Engineering

基　　金：国家自然科学基金(62372109);福建省自然科学基金(2023J06017)。

摘　　要：Steiner最小树(SMT)是总体布线的最佳连接模型,其构造是1个NP-难问题。粒子群优化(PSO)算法在解决NP-难问题中具有良好的表现,而PSO算法中种群的拓扑结构及搜索信息的传递机制对其性能有着很大的影响。1个适用于具体问题的种群拓扑结构对算法性能的提升极为显著。因此,利用PSO求解总体布线问题需要根据具体布线问题的特性来选择合适的粒子拓扑结构策略,以提升PSO的性能。提出基于动态PSO的X结构Steiner最小树(XSMT)算法以解决总体布线问题。首先,设计动态子群与信息交换策略,对种群进行子群划分,引入信息交换的概念,让子群在保持独立性的同时与其他子群进行信息交换,增加子群多样性;其次,设计粒子学习与变异策略,通过设置子群中粒子的学习对象使子群趋向于全局最优,并选择每个子群中适应度值最好的粒子进行变异,使粒子更易于跳出局部最优;最后,设计从多群局部学习过渡到单群全局学习策略,使算法在迭代次数到达阈值之后从局部学习过渡到全局学习,使得粒子在较优拓扑结构的基础上内部连接以获得更好的线长优化率。实验结果表明,与现有的2种R结构SMT(RSMT)算法相比,所提算法在优化线长方面分别优化了10.25%、8.24%;与现有的3种XSMT算法相比,该算法在优化线长方面分别优化了2.44%、1.46%、0.48%,验证了算法的有效性。The Steiner Minimum Tree(SMT)is the best connection model for global routing;its construction is an NP-hard problem.The Particle Swarm Optimization(PSO)algorithm performs well on solving NP-hard problems.The topological structure of the population and the transmission mechanism of search information in the PSO algorithm significantly influence its performance.A population topology structure suitable for specific problems significantly improves the algorithm performance.Therefore,using PSO to solve the overall routing problem requires the selection of an appropriate particle topology strategy based on the characteristics of the specific routing problem to improve PSO performance.Therefore,an X-architecture SMT(XSMT)algorithm based on the dynamic PSO is proposed herein,to solve the overall routing problem.First,a dynamic subgroup and information exchange strategy is designed to divide the population into subgroups,and the information exchange concept is introduced to enable subgroups to exchange information with other subgroups while maintaining their independence,thus increasing subgroup diversity.Second,a particle learning and mutation strategy is designed.By setting the learning objects of particles in the subgroup,the subgroup tends toward the global optimum,and particles with the best adaptation value in each subgroup are selected for mutation such that they can jump out of the local optimum in a more straightforward manner.Finally,a transition strategy from multi-group local learning to single-group global learning is designed to ensure the algorithm transitions from local to global learning after the number of iterations reaches a certain threshold.The particles are internally connected based on an excellent topological structure to obtain an improved routing length optimization rate.Experimental results demonstrate that compared with two existing R-architecture SMT(RSMT)algorithms,the proposed algorithm achieves 10.25%and 8.24%optimization in terms of routing length,respectively.Similarly,compared with thre

关 键 词：动态粒子群优化 信息交换 X结构Steiner最小树 超大规模集成电路布线 粒子群优化离散化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]