考虑长度限制的X结构Steiner最小树算法

摘要

长度限制Steiner最小树模型能够充分利用障碍内布线资源以进一步缩短总线长，进一步考虑X结构具有更好的线长优化效果，同时麻雀搜索算法具有良好的优化能力，本文基于动态种群麻雀搜索算法，提出了一种高质量的考虑长度限制的X结构Steiner最小树算法.首先，提出了一种基于动态种群机制改进麻雀搜索机制，通过动态调整种群结构以提高麻雀的多样性，避免算法过早陷入局部最优解.其次，提出了一种混合初始化策略以提高初始种群的多样性，有利于算法找到质量更佳的解.最后，提出了一种考虑角点复用的调整策略，通过在调整期间复用障碍物角点，有效缩短了绕行所需的线长.实验结果表明，相比于同类工作，本文所提出的算法能够取得良好的线长优化效果，证明了该算法的有效性，为电子设计自动化领域的布线优化提供了一种新的方法和思路.

关键词

Steiner最小树 / X结构 / 长度限制 / 超大规模集成电路 / 动态种群 / 麻雀搜索优化

基金资助

国家自然科学基金项目(62372109)资助; 福建省杰出青年科学基金项目(2023J06017)资助