針對(duì)多端線網(wǎng)互連問題,提出以超大規(guī)模集成電路物理設(shè)計(jì)中布線階段應(yīng)用較多的斯坦納樹為切入點(diǎn),采用一種基于種群的全局搜索和基于個(gè)體的局部啟發(fā)式搜索相結(jié)合的文化基因算法,對(duì)八角形斯坦納樹的結(jié)構(gòu)進(jìn)行優(yōu)化,從而進(jìn)一步縮減線長(zhǎng).使用Prim算法預(yù)處理取得初始種群,并重新修改了原本的文化基因的編碼以及相關(guān)操作,以便可以處理八角形斯坦納樹構(gòu)建這一離散問題,利用八角形結(jié)構(gòu),使其能在全局范圍內(nèi),快速收斂并全局尋優(yōu).實(shí)驗(yàn)結(jié)果表明,所提算法能獲得較好拓?fù)涞陌私切嗡固辜{樹,快速得到多端線網(wǎng)最優(yōu)或者較優(yōu)的布線結(jié)果,縮減布線的線長(zhǎng). 

【文章來源】：福州大學(xué)學(xué)報(bào)(自然科學(xué)版). 2019,47(06)北大核心

【文章頁(yè)數(shù)】：6 頁(yè)

【部分圖文】：

走線模式圖

為了加快算法的收斂速度, 基于文化基因的八角形斯坦納樹算法采用最大并集的策略來實(shí)現(xiàn)交叉操作, 選擇當(dāng)前最優(yōu)的個(gè)體和迭代過程中最優(yōu)的個(gè)體進(jìn)行交叉. 初始階段是得到兩個(gè)個(gè)體的交集, 第二個(gè)階段是將剩下未連接到斯坦納樹上的引腳, 隨機(jī)選擇前兩者中的一種連接方式連接起來, 最終得到交叉操作的結(jié)果, 詳見圖2所示.2) 雙重變異操作.

圖3 雙重變異操作

【參考文獻(xiàn)】：
期刊論文
[1]求解邊坡最小安全系數(shù)的混合文化基因算法[J]. 許晶,陳建利.  福州大學(xué)學(xué)報(bào)(自然科學(xué)版). 2017(04)
[2]采用基于遺傳算法的文化基因算法求解TSP問題[J]. 譚立狀,贠國(guó)瀟,張家華.  科技視界. 2016(05)
[3]基于圖論的VLSI中最小斯坦納樹問題及其改進(jìn)算法[J]. 陳秀華.  南京師范大學(xué)學(xué)報(bào)(工程技術(shù)版). 2015(04)
[4]一種解決VLSI布局問題的文化基因算法[J]. 張亞娟,劉寒冰,靳宗信.  科技通報(bào). 2013(12)
[5]我國(guó)集成電路產(chǎn)業(yè)發(fā)展現(xiàn)狀及前景[J]. 徐強(qiáng).  國(guó)際經(jīng)濟(jì)合作. 2009(01)
[6]文化基因算法（Memetic Algorithm）研究進(jìn)展[J]. 劉漫丹.  自動(dòng)化技術(shù)與應(yīng)用. 2007(11)
[7]國(guó)際集成電路產(chǎn)業(yè)發(fā)展現(xiàn)狀與前景[J]. 吳雄.  電子與自動(dòng)化. 1996(06)



本文編號(hào)：3606238