超大規(guī)模集成電路物理設(shè)計中布圖規(guī)劃和線長估計問題是集成電路設(shè)計的重要環(huán)節(jié)，布圖規(guī)劃和線長估計問題是高度復(fù)雜的。我們已對其做了比較深入的研究，分析布圖規(guī)劃和線長估計問題的圖論性質(zhì)，給出問題解的構(gòu)造方法，構(gòu)造了一個多目標(biāo)粒子群優(yōu)化算法框架，繼而研究求解布圖規(guī)劃和線長估計問題的有效多目標(biāo)粒子群優(yōu)化算法。本課題研究在非曼哈頓結(jié)構(gòu)下帶粒子群優(yōu)化的高效總體布線器的構(gòu)建，我們深入研究非曼哈頓結(jié)構(gòu)下總體布線問題的相關(guān)性質(zhì)，選取X結(jié)構(gòu)作為非曼哈頓結(jié)構(gòu)開展研究，取得的主要研究成果如下：（1）針對X結(jié)構(gòu)Steiner最小樹問題，分析非曼哈頓結(jié)構(gòu)Steiner樹性質(zhì)，重新構(gòu)造非曼哈頓結(jié)構(gòu) Steiner 樹的編解碼方式，提出來一種改進的離散粒子群優(yōu)化算法用以求解X結(jié)構(gòu)Steiner最小樹；（2）定義擁擠度估算函數(shù)確定處于擁擠區(qū)域的線網(wǎng)和引入最小化線長最小半徑的性能驅(qū)動布線樹模型，構(gòu)造不同目標(biāo)和不同約束下的非曼哈頓結(jié)構(gòu)布線樹模型，從而構(gòu)建其相應(yīng)的粒子群優(yōu)化算法，繼而從適應(yīng)度函數(shù)的構(gòu)造、算法參數(shù)模型調(diào)整策略和性能提高策略三個方面來研究算法；（3）針對非曼哈頓結(jié)構(gòu)下層分配問題，通過定義線網(wǎng)關(guān)鍵性評價函數(shù)以獲得基于啟發(fā)式策略的初始層分配方案，繼而以最小化擁擠度、通孔數(shù)和串?dāng)_為目標(biāo)給出對初始方案進一步優(yōu)化的非曼哈頓結(jié)構(gòu)層分配算法，分析算法的收斂性并檢驗這些算法的有效性和可行性。本項目的研究成果將為粒子群優(yōu)化算法的進一步應(yīng)用打下基礎(chǔ)，并進一步提高我國關(guān)于超大規(guī)模集成電路設(shè)計基礎(chǔ)理論研究水平。 2100433B

VLSI總體布線的結(jié)果對詳細布線的成功與否和芯片的性能影響極大，其本質(zhì)是典型的NP困難多目標(biāo)組合優(yōu)化問題。非曼哈頓結(jié)構(gòu)的引入使物理設(shè)計的諸多性能得到提高，但目前研究主要集中在通道布線，缺乏一個該結(jié)構(gòu)下有效完整的總體布線方案。本課題研究在非曼哈頓結(jié)構(gòu)下帶粒子群優(yōu)化的高效總體布線器的構(gòu)建，其分為三個階段：（1）構(gòu)建各線網(wǎng)的非曼哈頓結(jié)構(gòu)Steiner最小樹集，定義擁擠度估算函數(shù)確定處于擁擠區(qū)域的線網(wǎng)，并對其構(gòu)造擁擠度驅(qū)動的非曼哈頓結(jié)構(gòu)Steiner樹集；（2）引入能克服線網(wǎng)順序依賴性的整數(shù)線性規(guī)劃模型，并同時采用優(yōu)化時延和功耗目標(biāo)的緩沖器插入技術(shù)，構(gòu)建非曼哈頓結(jié)構(gòu)下基于整數(shù)線性規(guī)劃的總體布線多目標(biāo)優(yōu)化模型，給出其相應(yīng)的多目標(biāo)粒子群優(yōu)化算法；（3）通過定義線網(wǎng)關(guān)鍵性評價函數(shù)以獲得基于啟發(fā)式策略的初始層分配方案，繼而以最小化擁擠度、通孔數(shù)和串?dāng)_為目標(biāo)給出對初始方案進一步優(yōu)化的非曼哈頓結(jié)構(gòu)層分配算法。

總體布線是VLSI物理設(shè)計中極為重要的一個環(huán)節(jié)。非曼哈頓結(jié)構(gòu)的提出為物理設(shè)計帶來諸多性能的提高，但該結(jié)構(gòu)的引入和多層工藝的普及，使得總體布線問題更為復(fù)雜，且目前研究工作只就某些局部目標(biāo)展開，缺乏一種該結(jié)構(gòu)下有效完整的總體布線方案。正是在這樣的背景下，本項目對非曼哈頓結(jié)構(gòu)VLSI總體布線相關(guān)問題展開一些研究工作，選取X結(jié)構(gòu)作為非曼哈頓結(jié)構(gòu)的代表，完成的主要工作如下：（1）基于多目標(biāo)PSO和Elmore時延模型提出了一種構(gòu)建時延驅(qū)動X結(jié)構(gòu)Steiner樹的有效算法，從而有助于性能驅(qū)動X結(jié)構(gòu)總體布線問題的研究。（2）繞障Steiner最小樹的構(gòu)建是VLSI物理設(shè)計中一個極為重要問題，為此，提出一種基于粒子群優(yōu)化的有效算法用于求解X結(jié)構(gòu)下的繞障Steiner最小樹問題。考慮到粒子群優(yōu)化算法存在收斂速度慢的不足，進一步設(shè)計一種四步驟的高效啟發(fā)式算法用于求解該問題。（3）針對ML-OAXSMT問題，以最小化布線總代價為目標(biāo)，并同時考慮到通孔數(shù)的優(yōu)化，提出了一種基于PSO算法和懲罰機制的ML-OAXSMT構(gòu)建算法。為了進一步提高求解多ML-OAXSMT問題的算法質(zhì)量，基于查找表的思想，提出了一種高效的繞障策略，可以準(zhǔn)確獲得多層環(huán)境下的Steiner點位置，從而構(gòu)建一棵高質(zhì)量的ML-OAXSMT。(4) 針對X結(jié)構(gòu)下的總體布線問題，提出一種基于ILP模型、劃分策略及PSO等技術(shù)的高質(zhì)量X結(jié)構(gòu)總體布線算法。 本項目進一步擴寬研究思路，針對曼哈頓結(jié)構(gòu)下繞障Steiner樹構(gòu)建問題并且將PSO擴展應(yīng)用于VLSI電路劃分階段，主要完成以下工作：（1）研究了電壓轉(zhuǎn)換速率的計算模型和RSMT-RERR問題中的電壓轉(zhuǎn)換速率約束，基于SPCF算法框架提出考慮電壓轉(zhuǎn)換速率約束的直角Steiner樹構(gòu)造算法。（2）研究了ML-OARSMT問題的特征，提出了該問題布線圖的構(gòu)造方法。考慮避開障礙和連通相鄰層，選擇了三種類型候選通孔位置。 （3）電路劃分作為VLSI物理設(shè)計中的首個關(guān)鍵環(huán)節(jié)，通過附加考慮時延因素，構(gòu)造了電路劃分的多目標(biāo)問題模型，引入局部搜索策略以及基于小生境技術(shù)的表現(xiàn)型共享粒子評價機制，設(shè)計了一個求解多目標(biāo)電路劃分問題的混合DPSO。 2100433B

總體布線是物理設(shè)計中極為重要的一個環(huán)節(jié)。非曼哈頓結(jié)構(gòu)帶來物理設(shè)計諸多性能的提高，該結(jié)構(gòu)的引入和多層工藝的普及，使得總體布線算法更為復(fù)雜，且目前研究工作只就某些局部目標(biāo)展開，缺乏一個該結(jié)構(gòu)下有效完整的多層總體布線方案。為此，本課題研究在非曼哈頓結(jié)構(gòu)下高效的VLSI多層總體布線器的構(gòu)建：（1）利用X結(jié)構(gòu)Steiner樹的幾何性質(zhì)，定義其編解碼方式和操作算子，繼而構(gòu)造X結(jié)構(gòu)Steiner最小樹；（2）定義不同程度的擁擠區(qū)域為權(quán)重各異的障礙物，融入懲罰機制，構(gòu)建X結(jié)構(gòu)繞障Steiner樹，并利用分治思想和整數(shù)規(guī)劃模型，構(gòu)建擁擠線網(wǎng)的重布方法；（3）將緩沖器插入問題轉(zhuǎn)換成求解最小半徑最小代價生成樹，構(gòu)造求解該問題的多目標(biāo)粒子群優(yōu)化算法，以期優(yōu)化時延；（4）定義線網(wǎng)順序的評價函數(shù)，分析串?dāng)_的計算方法，構(gòu)造同時優(yōu)化串?dāng)_和通孔數(shù)的X結(jié)構(gòu)層分配多目標(biāo)粒子群優(yōu)化算法，以還原之前映射到平面上的多層總體布線資源。

第1章 緒論

1.1 引言

1.2 基本粒子群優(yōu)化算法

1.2.1 粒子群優(yōu)化算法的基本原理

1.2.2 基本粒子群優(yōu)化算法模型

1.2.3 基本粒子群優(yōu)化算法流程

1.2.4 參數(shù)分析與設(shè)置

1.3 粒子群優(yōu)化算法的改進綜述

1.3.1 基于慣性權(quán)值的改進

1.3.2 基于加速因子的改進

1.3.3 基于鄰近群拓?fù)涞母倪M

1.3.4 基于種群規(guī)模的改進

1.3.5 混合粒子群優(yōu)化算法

1.4 粒子群優(yōu)化算法的機理研究

1.5 粒子群優(yōu)化算法的應(yīng)用研究

1.6 離散粒子群優(yōu)化算法

1.6.1 將速度作為位置變化的概率

1.6.2 直接將連續(xù)PSO用于離散問題的求解

1.6.3 重新定義PSO算法操作算子

1.7 DPSO算法應(yīng)用

1.8 DPSO算法研究展望

參考文獻

第2章 在P問題中的應(yīng)用

2.1 引言

2.2 求解TSF問題的自適應(yīng)粒子群優(yōu)化算法

2.2.1 離散.PSO算法

2.2.2 求解TSP問題的PSO算法設(shè)計

2.2.3 慣性權(quán)值在離散PSO算法中的作用

2.2.4 實驗結(jié)果與分析

2.3 求解TSP問題的動態(tài)領(lǐng)域PSO算法

2.3.1 相關(guān)概念

2.3.2 TSP問題的PSO操作

2.3.3 動態(tài)領(lǐng)域PSO算法的設(shè)計

2.3.4 實驗結(jié)果及分析

2.4 求解TSP問題的PSO一ACO算法

2.4.1 模擬進化的蟻群算法

2.4.2 PSO-ACO算法的設(shè)計思想及總體框架

2.4.3 實驗結(jié)果與分析

參考文獻

第3章 在多工作流調(diào)度中的應(yīng)用

3.1 引言

3.2 問題描述

3.2.1 多目標(biāo)優(yōu)化問題

3.2.2 求解多目標(biāo)優(yōu)化問題的基本方法

3.3 多目標(biāo)工作流調(diào)度問題

3.4 基于表現(xiàn)型共享的多目標(biāo)粒子群優(yōu)化算法

3.4.1 基于表現(xiàn)型共享的適應(yīng)度函數(shù)

3.4.2 算法的基本模型

3.4.3 算法步驟

3.4.4 算例測試與結(jié)果分析

3.5 求解多目標(biāo)工作流調(diào)度問題的離散粒子群優(yōu)化算法

3.5.1 算法基本模型

3.5.2 算法主要步驟

3.5.3 實驗結(jié)果

參考文獻

第4章 在多目標(biāo)最小生成樹問題中的應(yīng)用

4.1 引言

4.2 問題模型

4.2.1 MST問題

4.2.2 mc-MST問題

4.3 改進的計數(shù)算法

4.4 求解mc-MST問題的NDPSO算法

4.4.1 粒子的編碼機制

4.4.2 粒子的適應(yīng)度函數(shù)

4.4.3 粒子的更新公式

4.4.4 算法描述

4.4.5 收斂性分析

4.5 實驗結(jié)果與分析

4.5.1 測試問題

4.5.2 結(jié)果與分析

參考文獻

第5章 在入侵檢測數(shù)據(jù)特征選擇中的應(yīng)用

5.1 引言

5.2 特征選擇

5.3 基于PSO和相關(guān)性分析的特征選擇算法

5.3.1 粒子編碼模式

5.3.2 適應(yīng)度函數(shù)

5.3.3 參數(shù)設(shè)置

5.3.4 算法描述

5.3.5 實驗結(jié)果與分析

5.4 基于PSo和鄰域約簡模型的特征選擇算法

5.4.1 鄰域粗糙集

5.4.2 算法的具體設(shè)計

5.4.3 仿真實驗

5.5 基于PSO和云模型的特征選擇算法

5.5.1 云的概念

5.5.2 云的對象隸屬度計算

5.5.3 算法的具體設(shè)計

5.5.4 實驗結(jié)果與分析

參考文獻

第6章 在入侵檢測系統(tǒng)中的應(yīng)用

6.1 引言

6.2 基于連續(xù)粒子群分類算法的誤用檢測

6.2.1 目前入侵檢測產(chǎn)品存在的缺陷

6.2.2 分類算法

6.2.3 基于連續(xù)粒子群的分類算法

6.3 基于否定選擇算法的異常檢測

6.3.1 基于異常的入侵檢測系統(tǒng)的缺陷

6.3.2 人工免疫與否定選擇算法

6.3.3 修改的否定選擇算法

6.4 混合的網(wǎng)絡(luò)入侵檢測引擎

6.4.1 引入混合方式的目的

6.4.2 混合方式

6.4.3 混合的入侵檢測引擎的整體結(jié)構(gòu)

6.4.4 仿真實驗

參考文獻

第7章 在網(wǎng)絡(luò)安全態(tài)勢感知中的應(yīng)用

7.1 引言

7.2 基于PSO-FNN的安全態(tài)勢感知要素提取算法

7.2.1 相關(guān)算法

7.2.2 基于PSO-FNN的安全態(tài)勢要素提取模型

7.2.3 基于PSO-FNN的安全態(tài)勢要素提取方法

7.2.4 仿真實驗與結(jié)果分析

7.3 基于PSO-BPNN的安全態(tài)勢預(yù)測算法

7.3.1 基于PSO-BPNN的網(wǎng)絡(luò)安全態(tài)勢預(yù)測模型

7.3.2 基于PSO-BPNN網(wǎng)絡(luò)安全態(tài)勢預(yù)測方法

7.3.3 仿真實驗

7.4 網(wǎng)絡(luò)安全系統(tǒng)中的組態(tài)勢感知研究

7.4.1 個體態(tài)勢感知與組態(tài)勢感知

7.4.2 基于PSO的聚類分析實驗設(shè)計

7.4.3 算法流程

7.4.4 仿真實驗

參考文獻

第8章 在異構(gòu)集群數(shù)據(jù)流分配中的應(yīng)用

8.1 引言

8.2 數(shù)據(jù)流分配算法

8.3 基于PSO的異構(gòu)集群數(shù)據(jù)流自適應(yīng)分配策略

8.3.1 問題建模

8.3.2 帶動態(tài)反饋機制的數(shù)據(jù)流自適應(yīng)分配模型

8.3.3 改進的粒子群優(yōu)化算法

8.3.4 仿真實驗結(jié)果與分析

8.4 動態(tài)聯(lián)盟思想的引入

8.4.1 動態(tài)聯(lián)盟思想

8.4.2 問題建模

8.4.3 算法描述

8.4.4 算法仿真與結(jié)果分析

參考文獻

第9.章 在WSN拓?fù)淇刂浦械膽?yīng)用

9.1 引言

9.2 基于度約束最小生成樹的wSN分布式拓?fù)淇刂?

9.2.1 網(wǎng)絡(luò)模型與問題描述

9.2.2 求解dc—MsT問題的DPSO

9.2.3 分布式拓?fù)淇刂品桨?

9.2.4 仿真實驗

9.3 基于二連通的WSN拓?fù)淇刂品桨?

9.3.1 網(wǎng)絡(luò)模型及問題描述

9.3.2 求解wSN二連通拓?fù)浣Y(jié)構(gòu)的DPSO算法

9.3.3 仿真實驗

9.4 基于K一連通問題的wSN拓?fù)淇刂品桨?

9.4.1 相關(guān)工作

9.4.2 相關(guān)定義

9.4.3 集中式的KTCPSO算法描述

9.4.4 分布式KLPSO算法描述

9.4.5 算法的時間復(fù)雜度分析

9.4.6 仿真實驗

參考文獻

第10章 在WSN任務(wù)調(diào)度中的應(yīng)用

10.1 引言

10.2 任務(wù)調(diào)度相關(guān)概念

10.3 WSN任務(wù)分配動態(tài)聯(lián)盟模型及其算法

10.3.1 問題描述

10.3.2 任務(wù)分配動態(tài)聯(lián)盟模型的構(gòu)建

10.3.3 求解動態(tài)聯(lián)盟模型的PSO算法

10.3.4 實驗結(jié)果與分析

10.4 帶多Agent的wSN自適應(yīng)任務(wù)調(diào)度策略

10.4.1 多Agent系統(tǒng)

10.4.2 基于多Agent的無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)及系統(tǒng)模型

10.4.3 基于多Agent的無線傳感器網(wǎng)絡(luò)自適應(yīng)任務(wù)調(diào)度策略

10.4.4 仿真實驗與結(jié)果分析

10.5 基于串行聯(lián)盟的動態(tài)任務(wù)分配算法

10.5.1 串行聯(lián)盟思想的引入

10.5.2 基于DPSO的聯(lián)盟形成算法

10.5.3 基于串行聯(lián)盟的任務(wù)分配體系結(jié)構(gòu)

10.5.4 仿真實驗

10.6 基于并行聯(lián)盟的動態(tài)任務(wù)分配算法

10.6.1 引言

10.6.2 并行聯(lián)盟概述

10.6.3 基于并行聯(lián)盟的任務(wù)分配算法

10.6.4 基于并行聯(lián)盟的任務(wù)分配體系結(jié)構(gòu)

10.6.5 仿真實驗

參考文獻

第1l章 在VLSI物理設(shè)計中的應(yīng)用

11.1 引言

11.2 VLSI設(shè)計概述

11.2.1 VLSI設(shè)計流程

11.2.2 物理設(shè)計過程

11.3 單目標(biāo)電路劃分的離散PSO算法

11.3.1 相關(guān)工作

11.3.2 問題模型

11.3.3 算法描述

11.3.4 實驗結(jié)果分析

11.4 單目標(biāo)電路劃分的混合PSO算法

11.4.1 算法的具體設(shè)計過程

11.4.2 實驗結(jié)果與分析

11.5 多目標(biāo)電路劃分的離散：PSO算法

11.5.1 相關(guān)工作

11.5.2 多目標(biāo)劃分問題模型

11.5.3 基于DPSO框架下的多目標(biāo)劃分算法

11.5.4 實驗結(jié)果與分析

11.6 解決布圖規(guī)劃的DPSO算法

11.6.1 VLSI布圖模式與相關(guān)工作

11.6.2 問題描述

11.6.3 算法描述

11.6.4 實驗結(jié)果與分析

11.7 解決布圖規(guī)劃的多目標(biāo)PSO算法

11.7.1 采用整數(shù)序列編碼的布圖規(guī)劃算法

11.7.2 采用序列對編碼的布圖規(guī)劃算法

11.8 解決布圖規(guī)劃的協(xié)同多目標(biāo)PSO算法

11.8.1 協(xié)同多目標(biāo)算法概述

11.8.2 解決布圖規(guī)劃問題的協(xié)同多目標(biāo)PSO算法

11.8.3 實驗結(jié)果分析

參考文獻