基于自适应PSO和混合转换策略的X结构Steiner最小树算法  

Self-adapting PSO Algorithm with Efficient Hybrid Transformation Strategy for X-Architecture Steiner Minimal Tree Construction Algorithm

作　　者：刘耿耿[1,2] 陈志盛[1] 郭文忠[1,2,3] 陈国龙[1] LIU Genggeng;CHEN Zhisheng;GUO Wenzhong;CHEN Guolong(College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116;Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350116;Key Laboratory of Spatial Data Mining and Information Sha- ring, Ministry of Education, Fuzhou University, Fuzhou 350116)

机构地区：[1]福州大学数学与计算机科学学院,福州350116 [2]福州大学福建省网络计算与智能信息处理重点实验室,福州350116 [3]福州大学空间数据挖掘与信息共享教育部重点实验室,福州350116

出　　处：《模式识别与人工智能》2018年第5期398-408,共11页Pattern Recognition and Artificial Intelligence

基　　金：国家重点基础研究发展计划(973计划)项目(No.2011CB808000);国家自然科学基金项目(No.11501114;11271002);福建省科技创新平台项目(No.2014H2005;2009J1007);海西政务大数据应用协同创新中心资助~~

摘　　要：X结构Steiner最小树(XSMT)是非曼哈顿结构总体布线算法中多端线网的最佳连接模型,属于NP难问题.文中基于混合转换策略和自适应粒子群优化算法,提出XSMT构造算法.首先设计有效的混合转换策略,扩大算法寻优空间,提高算法收敛效率.为了满足粒子编码的健全性,算法的更新方式引入带并查集策略的交叉和变异算子,同时采取自适应调整学习因子的策略,加快粒子群优化算法的收敛速度.实验表明,文中算法能得到较好的XSMT求解方案,获得多种不同拓扑的XSMTs,有利于VLSI总体布线阶段的拥挤度优化.X-architecture Steiner minimal tree （XSMT） problem is an NP-hard problem, and it is the best connection model for a multi-terminal net in non-Manhattan global routing problem. An XSMT construction algorithm based on hybrid transformation strategy and self-adapting particle swarm optimization （PSO） is proposed. Firstly, an effective hybrid transformation strategy is designed to enlarge the search space and enhance the convergence of the algorithm. Secondly, the crossover and mutation operators based on union-find sets and a self-adapting strategy to adjust the learning factors are proposed to satisfy the robustness of particle coding and further speed up the convergence of algorithm. The experimental results show that the proposed algorithm efficiently produces a better solution than others. Moreover, it obtains a series of XSMTs with different topology but same length. Thus, it provides a variety of options for global routing and opportunities to reduce congestion.

关 键 词：x结构 STEINER树 粒子群优化 混合转换策略 自适应策略 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]