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

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

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

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

第1章 緒論

1.1 引言

1.2 基本粒子群優化算法

1.2.1 粒子群優化算法的基本原理

1.2.2 基本粒子群優化算法模型

1.2.3 基本粒子群優化算法流程

1.2.4 參數分析與設置

1.3 粒子群優化算法的改進綜述

1.3.1 基于慣性權值的改進

1.3.2 基于加速因子的改進

1.3.3 基于鄰近群拓撲的改進

1.3.4 基于種群規模的改進

1.3.5 混合粒子群優化算法

1.4 粒子群優化算法的機理研究

1.5 粒子群優化算法的應用研究

1.6 離散粒子群優化算法

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

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

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

1.7 DPSO算法應用

1.8 DPSO算法研究展望

參考文獻

第2章 在P問題中的應用

2.1 引言

2.2 求解TSF問題的自適應粒子群優化算法

2.2.1 離散.PSO算法

2.2.2 求解TSP問題的PSO算法設計

2.2.3 慣性權值在離散PSO算法中的作用

2.2.4 實驗結果與分析

2.3 求解TSP問題的動態領域PSO算法

2.3.1 相關概念

2.3.2 TSP問題的PSO操作

2.3.3 動態領域PSO算法的設計

2.3.4 實驗結果及分析

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

2.4.1 模擬進化的蟻群算法

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

2.4.3 實驗結果與分析

參考文獻

第3章 在多工作流調度中的應用

3.1 引言

3.2 問題描述

3.2.1 多目標優化問題

3.2.2 求解多目標優化問題的基本方法

3.3 多目標工作流調度問題

3.4 基于表現型共享的多目標粒子群優化算法

3.4.1 基于表現型共享的適應度函數

3.4.2 算法的基本模型

3.4.3 算法步驟

3.4.4 算例測試與結果分析

3.5 求解多目標工作流調度問題的離散粒子群優化算法

3.5.1 算法基本模型

3.5.2 算法主要步驟

3.5.3 實驗結果

參考文獻

第4章 在多目標最小生成樹問題中的應用

4.1 引言

4.2 問題模型

4.2.1 MST問題

4.2.2 mc-MST問題

4.3 改進的計數算法

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

4.4.1 粒子的編碼機制

4.4.2 粒子的適應度函數

4.4.3 粒子的更新公式

4.4.4 算法描述

4.4.5 收斂性分析

4.5 實驗結果與分析

4.5.1 測試問題

4.5.2 結果與分析

參考文獻

第5章 在入侵檢測數據特征選擇中的應用

5.1 引言

5.2 特征選擇

5.3 基于PSO和相關性分析的特征選擇算法

5.3.1 粒子編碼模式

5.3.2 適應度函數

5.3.3 參數設置

5.3.4 算法描述

5.3.5 實驗結果與分析

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

5.4.1 鄰域粗糙集

5.4.2 算法的具體設計

5.4.3 仿真實驗

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

5.5.1 云的概念

5.5.2 云的對象隸屬度計算

5.5.3 算法的具體設計

5.5.4 實驗結果與分析

參考文獻

第6章 在入侵檢測系統中的應用

6.1 引言

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

6.2.1 目前入侵檢測產品存在的缺陷

6.2.2 分類算法

6.2.3 基于連續粒子群的分類算法

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

6.3.1 基于異常的入侵檢測系統的缺陷

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

6.3.3 修改的否定選擇算法

6.4 混合的網絡入侵檢測引擎

6.4.1 引入混合方式的目的

6.4.2 混合方式

6.4.3 混合的入侵檢測引擎的整體結構

6.4.4 仿真實驗

參考文獻

第7章 在網絡安全態勢感知中的應用

7.1 引言

7.2 基于PSO-FNN的安全態勢感知要素提取算法

7.2.1 相關算法

7.2.2 基于PSO-FNN的安全態勢要素提取模型

7.2.3 基于PSO-FNN的安全態勢要素提取方法

7.2.4 仿真實驗與結果分析

7.3 基于PSO-BPNN的安全態勢預測算法

7.3.1 基于PSO-BPNN的網絡安全態勢預測模型

7.3.2 基于PSO-BPNN網絡安全態勢預測方法

7.3.3 仿真實驗

7.4 網絡安全系統中的組態勢感知研究

7.4.1 個體態勢感知與組態勢感知

7.4.2 基于PSO的聚類分析實驗設計

7.4.3 算法流程

7.4.4 仿真實驗

參考文獻

第8章 在異構集群數據流分配中的應用

8.1 引言

8.2 數據流分配算法

8.3 基于PSO的異構集群數據流自適應分配策略

8.3.1 問題建模

8.3.2 帶動態反饋機制的數據流自適應分配模型

8.3.3 改進的粒子群優化算法

8.3.4 仿真實驗結果與分析

8.4 動態聯盟思想的引入

8.4.1 動態聯盟思想

8.4.2 問題建模

8.4.3 算法描述

8.4.4 算法仿真與結果分析

參考文獻

第9.章 在WSN拓撲控制中的應用

9.1 引言

9.2 基于度約束最小生成樹的wSN分布式拓撲控制

9.2.1 網絡模型與問題描述

9.2.2 求解dc—MsT問題的DPSO

9.2.3 分布式拓撲控制方案

9.2.4 仿真實驗

9.3 基于二連通的WSN拓撲控制方案

9.3.1 網絡模型及問題描述

9.3.2 求解wSN二連通拓撲結構的DPSO算法

9.3.3 仿真實驗

9.4 基于K一連通問題的wSN拓撲控制方案

9.4.1 相關工作

9.4.2 相關定義

9.4.3 集中式的KTCPSO算法描述

9.4.4 分布式KLPSO算法描述

9.4.5 算法的時間復雜度分析

9.4.6 仿真實驗

參考文獻

第10章 在WSN任務調度中的應用

10.1 引言

10.2 任務調度相關概念

10.3 WSN任務分配動態聯盟模型及其算法

10.3.1 問題描述

10.3.2 任務分配動態聯盟模型的構建

10.3.3 求解動態聯盟模型的PSO算法

10.3.4 實驗結果與分析

10.4 帶多Agent的wSN自適應任務調度策略

10.4.1 多Agent系統

10.4.2 基于多Agent的無線傳感器網絡體系結構及系統模型

10.4.3 基于多Agent的無線傳感器網絡自適應任務調度策略

10.4.4 仿真實驗與結果分析

10.5 基于串行聯盟的動態任務分配算法

10.5.1 串行聯盟思想的引入

10.5.2 基于DPSO的聯盟形成算法

10.5.3 基于串行聯盟的任務分配體系結構

10.5.4 仿真實驗

10.6 基于并行聯盟的動態任務分配算法

10.6.1 引言

10.6.2 并行聯盟概述

10.6.3 基于并行聯盟的任務分配算法

10.6.4 基于并行聯盟的任務分配體系結構

10.6.5 仿真實驗

參考文獻

第1l章 在VLSI物理設計中的應用

11.1 引言

11.2 VLSI設計概述

11.2.1 VLSI設計流程

11.2.2 物理設計過程

11.3 單目標電路劃分的離散PSO算法

11.3.1 相關工作

11.3.2 問題模型

11.3.3 算法描述

11.3.4 實驗結果分析

11.4 單目標電路劃分的混合PSO算法

11.4.1 算法的具體設計過程

11.4.2 實驗結果與分析

11.5 多目標電路劃分的離散：PSO算法

11.5.1 相關工作

11.5.2 多目標劃分問題模型

11.5.3 基于DPSO框架下的多目標劃分算法

11.5.4 實驗結果與分析

11.6 解決布圖規劃的DPSO算法

11.6.1 VLSI布圖模式與相關工作

11.6.2 問題描述

11.6.3 算法描述

11.6.4 實驗結果與分析

11.7 解決布圖規劃的多目標PSO算法

11.7.1 采用整數序列編碼的布圖規劃算法

11.7.2 采用序列對編碼的布圖規劃算法

11.8 解決布圖規劃的協同多目標PSO算法

11.8.1 協同多目標算法概述

11.8.2 解決布圖規劃問題的協同多目標PSO算法

11.8.3 實驗結果分析

參考文獻