基于蟻群算法的類TSP積木塊布局優(yōu)化算法.pdf

1、計(jì)算機(jī)輔助集成電路版圖設(shè)計(jì)技術(shù)又稱布圖設(shè)計(jì)技術(shù)，它是一門涉及計(jì)算機(jī)科學(xué)與半導(dǎo)體技術(shù)的交叉學(xué)科。布圖設(shè)計(jì)自動(dòng)化是整個(gè)集成電路設(shè)計(jì)工程中與產(chǎn)品的研制和生產(chǎn)直接相關(guān)的一個(gè)設(shè)計(jì)過程，并且直接影響到IC電路的設(shè)計(jì)周期、成本、正確性和產(chǎn)品質(zhì)量[1]，其內(nèi)容包括設(shè)計(jì)評(píng)價(jià)和版圖校核、布局設(shè)計(jì)、布線設(shè)計(jì)幾個(gè)方面，其中的積木塊布局設(shè)計(jì)已被證明是集成電路布圖設(shè)計(jì)中的一個(gè)NP完全問題。 蟻群算法(AntcolonyAlgorithm)[2]是一種適合于

2、多變量組合優(yōu)化問題的隨機(jī)型全局搜索算法，它是群體智能系統(tǒng)最成功的例子之一，如今已被廣泛應(yīng)用到諸如經(jīng)典TSP問題以及通信網(wǎng)絡(luò)路由問題等許多類型的問題，受蟻群算法在解決NP問題中所表現(xiàn)出的優(yōu)良性能的啟發(fā)，本文將蟻群算法加以進(jìn)一步改進(jìn)后用于求解積木塊布局設(shè)計(jì)中的布局優(yōu)化這一過程。 本文在深入研究積木塊布局問題的基礎(chǔ)上，針對(duì)將傳統(tǒng)蟻群算法模型用于求解積木塊布局問題時(shí)無法滿足布局過程中積木塊單元位置始終處于移動(dòng)狀態(tài)下這一要求，文章采用了一

3、種類TSP模型的概念，能夠?qū)⒎e木塊初始布局轉(zhuǎn)化為一種類似TSP的積木塊布局形式，從而建立了一種新的類TSP積木塊布局優(yōu)化模型，此外本文還對(duì)傳統(tǒng)蟻群算法模型中的兩個(gè)主要更新公式進(jìn)行了改進(jìn)并運(yùn)用于布局優(yōu)化求解中，并在此基礎(chǔ)上提出了基于蟻群算法的類TSP積木塊布局優(yōu)化算法，從而使每一個(gè)積木塊單元可以在搜索區(qū)域內(nèi)時(shí)時(shí)進(jìn)行移動(dòng)和旋轉(zhuǎn)的同時(shí)采用改進(jìn)后的蟻群算法求解出最優(yōu)布局結(jié)果，并且布局結(jié)果滿足積木塊單元之間所必需的連線關(guān)系。為提高算法運(yùn)算速度，避