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

发布时间：2022-01-24 08:26

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

【文章来源】：福州大学学报(自然科学版). 2019,47(06)北大核心

【文章页数】：6 页

【部分图文】：

走线模式图

为了加快算法的收敛速度, 基于文化基因的八角形斯坦纳树算法采用最大并集的策略来实现交叉操作, 选择当前最优的个体和迭代过程中最优的个体进行交叉. 初始阶段是得到两个个体的交集, 第二个阶段是将剩下未连接到斯坦纳树上的引脚, 随机选择前两者中的一种连接方式连接起来, 最终得到交叉操作的结果, 详见图2所示.2) 双重变异操作.

图3 双重变异操作

【参考文献】：
期刊论文
[1]求解边坡最小安全系数的混合文化基因算法[J]. 许晶,陈建利.  福州大学学报(自然科学版). 2017(04)
[2]采用基于遗传算法的文化基因算法求解TSP问题[J]. 谭立状,贠国潇,张家华.  科技视界. 2016(05)
[3]基于图论的VLSI中最小斯坦纳树问题及其改进算法[J]. 陈秀华.  南京师范大学学报(工程技术版). 2015(04)
[4]一种解决VLSI布局问题的文化基因算法[J]. 张亚娟,刘寒冰,靳宗信.  科技通报. 2013(12)
[5]我国集成电路产业发展现状及前景[J]. 徐强.  国际经济合作. 2009(01)
[6]文化基因算法（Memetic Algorithm）研究进展[J]. 刘漫丹.  自动化技术与应用. 2007(11)
[7]国际集成电路产业发展现状与前景[J]. 吴雄.  电子与自动化. 1996(06)



本文编号：3606238