计算机科学与探索

作者：郑瀚, 周茹平, 刘耿耿

单位：1. 福州大学 计算机与大数据学院，福州 3501162. 大数据智能教育部工程研究中心，福州 3501163. 福建省网络计算与智能信息处理重点实验室，福州 350116

关键词：Steiner最小树,X结构,绕障,离散麻雀搜索优化,超大规模集成电路

基金：国家自然科学基金（62372109）；福建省自然科学基金（2023J06017）。

Steiner最小树是求解超大规模集成电路布线问题的最佳连接模型。然而，现代芯片中往往存在各种障碍, 如宏单元、IP块等，这些障碍使得Steiner最小树的构建更为困难。同时，考虑到X结构布线具有的良好线长优化能力以及麻雀搜索算法在求解NP难问题上展现出良好的应用前景，提出了一种基于离散麻雀搜索优化的X结构绕障Steiner最小树算法（DSSA_OAXSMT）。设计了基于边点对编码的麻雀表示方法与有效的适应度计算方法，以及一种基于离散化变异与交叉运算的麻雀种群更新机制，能够有效解决离散化的X结构绕障Steiner最小树问题。提出了一种预处理策略，避免了障碍信息的重复计算，提高了算法的运行效率。提出了一种混合初始化策略，通过结合贪心思想和轮盘赌思想提高初始种群的多样性。提出了一种基于绕行的调整策略以满足障碍约束。提出了一种混合精炼策略，其中包含基于公共边的局部精炼策略与基于交叉检测与处理的优化策略，能够进一步优化线长代价。实验结果表明，所提算法相比于同类工作取得了更佳的线长优化能力。

来源：2025年第6期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2025年第6期