八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题，提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点，采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法，对八角形斯坦纳树的结构进行优化，从而进一步缩减线长. 使用Prim算法预处理取得初始种群，并重新修改了原本的文化基因的编码以及相关操作，以便可以处理八角形斯坦纳树构建这一离散问题，利用八角形结构，使其能在全局范围内，快速收敛并全局寻优. 实验结果表明，所提算法能获得较好拓扑的八角形斯坦纳树，快速得到多端线网最优或者较优的布线结果，缩减布线的线长.

Research on octagonal steiner tree algorithm based on memetic

The scale of integrated circuits has increased dramatically. In view of the problem of multi-terminal network interconnection, it is proposed to use the Steiner tree with more application in the routing stage of VLSI physical design as a starting point, combining a population-based global search and individual-based local enlightenment. The memetic algorithm of the combination of search searches optimizes the structure of the octagonal Steiner tree, thereby further reducing the line length of the routing. In this paper, the Prim algorithm is used to pre-process the original individual, and the original memetic algorithm coding and related operations are re-modified, and the octagonal structure is used to enable rapid convergence and global optimization in the global scope. Finally, the proposed algorithm can be used to solve the discrete octagonal Steiner tree construction problem. The experimental results show that the proposed algorithm can obtain a better topology of the octagonal Steiner tree topology, and quickly obtain the optimal or better routing results of the multi-end line network, reducing the line length of the routing.