计算机科学与探索2025，Vol.19Issue(6)：1494-1507,14.DOI:10.3778/j.issn.1673-9418.2407017
基于离散麻雀搜索优化的X结构绕障Steiner最小树算法
Discrete Sparrow Search Optimization-Based Obstacle-Avoiding X-architecture Steiner Minimum Tree Algorithm
摘要
Abstract
The Steiner minimum tree is the optimal connection model for solving the routing problem of very large-scale integration.However,modern chips often contain various obstacles,such as macro cells and IP blocks,making the con-struction of Steiner minimum trees more challenging.Moreover,considering the excellent wirelength optimization capa-bilities of X-architecture routing and the promising application of the sparrow search algorithm in solving NP-hard problems,this paper proposes a discrete sparrow search optimization-based X-architecture obstacle-avoiding Steiner minimal tree algorithm(DSSA_OAXSMT).Firstly,a sparrow representation method based on edge-point pairs and an efficient fitness calculation method are proposed,coupled with a sparrow population update mechanism based on discrete mutation and crossover operations,which address the discrete X-architecture obstacle-avoiding Steiner minimum tree problem.Secondly,a preprocessing strategy is proposed to avoid redundant calculations.Thirdly,a hybrid initialization strategy is introduced,which combines the greedy approach and the roulette wheel selection method to enhance the diversity of the initial popula-tion.Fourthly,an adjustment strategy based on detours is developed to meet obstacle constraints.Finally,a mixed refine-ment strategy is proposed,which incorporates a local refinement strategy based on shared edges and an optimization strat-egy based on crossover detection and handling,enabling further optimization of the wirelength cost.Experimental results show that the proposed algorithm achieves superior wirelength optimization compared with similar works.关键词
Steiner最小树/X结构/绕障/离散麻雀搜索优化/超大规模集成电路Key words
Steiner minimum tree/X-architecture/obstacle-avoiding/discrete sparrow search optimization/very large-scale integration分类
计算机与自动化引用本文复制引用
郑瀚,周茹平,刘耿耿..基于离散麻雀搜索优化的X结构绕障Steiner最小树算法[J].计算机科学与探索,2025,19(6):1494-1507,14.基金项目
国家自然科学基金(62372109) （62372109）
福建省自然科学基金(2023J06017). This work was supported by the National Natural Science Foundation of China(62372109),and the Natural Science Foundation of Fujian Province(2023J06017). （2023J06017）
