了得網工業技術_多目標粒度支持向量機理論及其應用

內容簡介

《多目標粒度支持向量機理論及其應用》對多目標優化的多樣性保持策略、粒計算基礎理論、支持向量機的基本理論、粒度支持向量機的構造方法及應用進行了深入的研究。內容涉及多目標演化算法、多目標演化算法的多樣性保持策略、粒計算理論與方法、基於模糊格的超盒粒計算分類算法、基於模糊格的超球粒計算分類算法、粒度支持向量機的構造方法、粒計算在無線傳感器網絡節點定位問題中的應用等方面。

目錄
枟信息科學技術學術著作叢書枠序
前言
第1章多目標演化算法 1
1.1 多目標優化問題描述 2
1.2 多目標優化問題的一般求解方法 3 1.2.1 多目標演化算法的多樣性保持策略 6 1.2.2 多目標演化算法的收斂性度量 8 1.2.3 多目標演化算法的多樣性度量 8
參考文獻 9
第2章基於層次聚類的多目標演化算法 14
2.1 個體的適應值 15
2.2 個體間的相似度 15
2.3 層次聚類模型 17
2.4 子種群之間的個體遷移策略 20
2.5 基於層次聚類的多目標演化算法 23
2.6 數值實驗分析 30目錄

枟信息科學技術學術著作叢書枠序

前言

第1章多目標演化算法 1

1.1 多目標優化問題描述 2

1.2 多目標優化問題的一般求解方法 3 1.2.1 多目標演化算法的多樣性保持策略 6 1.2.2 多目標演化算法的收斂性度量 8 1.2.3 多目標演化算法的多樣性度量 8

參考文獻 9

第2章基於層次聚類的多目標演化算法 14

2.1 個體的適應值 15

2.2 個體間的相似度 15

2.3 層次聚類模型 17

2.4 子種群之間的個體遷移策略 20

2.5 基於層次聚類的多目標演化算法 23

2.6 數值實驗分析 30

參考文獻 56

第3章多目標演化算法的自適應多樣性保持策略 57

3.1 傳統多目標演化算法的多樣性保持策略 57 3.1.1 NSGAII算法的多樣性保持策略 57 3.1.2 SPEA算法的多樣性保持策略 59 3.1.3 SPEA2算法的多樣性保持策略 59

3.2 自適應多樣性保持策略 60 3.2.1 分階段多樣性保持策略 61 3.2.2 基於插值的多樣性保持策略 62 3.2.3 基於精度搜索的混合精英保持策略 70

3.3 數值實驗分析 73 3.3.1 結果分析 74 3.3.2 統計分析 83 3.3.3 總結分析 84

參考文獻 84

第4章模糊集 86

4.1 模糊集的表述方法 87

4.2 隸屬度函數的確定方法 91 4.2.1 確定隸屬度函數的注意事項 91 4.2.2 確定隸屬度函數的幾種主要方法 92 4.2.3 常見的模糊分布 96

4.3 模糊集合的運算 105

4.4 貼近度與模式識別 108

4.5 模糊集合的模糊性度量 108 4.5.1 海明距離 109 4.5.2 歐幾裡得距離 110 4.5.3 其他的距離 110

4.6 關繫與映射 110 4.6.1 關繫及其性質 111 4.6.2 關繫的合成 113 4.6.3 關繫的閉包運算 116 4.6.4 映射的定義 118

4.7 模糊關繫與模糊關繫矩陣 119 4.7.1 模糊關繫 119 4.7.2 模糊關繫矩陣 120

參考文獻 121

第5章粒計算代數繫統 123

5.1 引言 123

5.2 向量空間的代數繫統 124

5.3 超盒粒空間的代數繫統 125 5.3.1 超盒粒的兩點表示法 125 5.3.2 超盒粒之間的運算 125 5.3.3 超盒粒之間的模糊包含關繫 127 5.3.4 超盒粒代數繫統的性質 127

5.4 超盒粒的模糊格代數繫統 128 5.4.1 構造超盒粒集 128 5.4.2 設計超盒粒之間的算子 129 5.4.3 建立超盒粒之間的模糊包含關繫 131 5.4.4 構造超盒粒的模糊格代數繫統 133

5.5 基於模糊格的超盒粒計算分類器 134 5.5.1 超盒粒之間的有條件合並 134 5.5.2 基於模糊格的超盒粒計算分類器 136 5.5.3 數值實驗 137

5.6 本章小結 142

參考文獻 142

第6章基於模糊格的粒計算 144

6.1 格計算 146

6.2 模糊格 149

6.3 高維空間上的格 150

6.4 區間格 151

6.5 基於模糊格的超盒粒計算分類算法 152 6.5.1 超盒粒的兩點表示法 153 6.5.2 包含度函數 153 6.5.3 超盒粒之間的有條件合並 156 6.5.4 基於模糊格的超盒粒計算分類算法 158 6.5.5 數值實驗 159

6.6 基於模糊格的超球粒分類算法 164 6.6.1 超球粒的單點表示法 164 6.6.2 超球粒之間的模糊包含度函數 164 6.6.3 超球粒的有條件合並 168 6.6.4 基於模糊格的超球粒計算分類算法 169 6.6.5 數值實驗 170

6.7 本章小結 173

參考文獻 174

第7章多目標粒計算 177

7.1 多目標演化算法 177 7.1.1 NSGAII算法 180 7.1.2 SPEA2算法 181

7.2 基於多目標優化的超盒粒計算 185 7.2.1 多目標超盒粒計算模型 186 7.2.2 種群的初始化 186 7.2.3 個體之間的演化操作 187 7.2.4 基於重要度的個體優劣比較 190 7.2.5 基於多目標優化的超盒粒計算 191

7.2.6 算法的性能評價 193

7.3 數值實驗 193

7.4 本章小結 199

參考文獻 200

第8章粒度支持向量機 202

8.1 統計學習基本理論簡介 203

8.2 支持向量機 206

8.3 模糊支持向量機 212 8.3.1 兩類問題模糊支持向量機 213 8.3.2 多類問題模糊支持向量機 214

8.4 基於數據貢獻度的粒度模糊支持向量機 214 8.4.1 基於貢獻度的兩類問題粒度模糊支持向量機 215 8.4.2 多類問題粒度模糊支持向量機 217 8.4.3 數值實驗 218

8.5 基於粗糙集邊界的粒度模糊支持向量機 220 8.5.1 粗糙集理論簡介 221 8.5.2 訓練集的粒化過程 223 8.5.3 基於粗糙集邊界的粒度模糊支持向量機 225 8.5.4 數值實驗 225

8.6 基於屬性集粒化的粒度模糊支持向量機 227 8.6.1 基於重要度的屬性約簡 228 8.6.2 屬性集的粒化方法 229 8.6.3 基於屬性集粒化的粒度模糊支持向量機 230 8.6.4 數值實驗 231

8.7 本章小結 233

參考文獻 233

第9章粒計算在 WSN節點定位中的應用 236

9.1 節點之間通信量的估計 238 9.1.1 接收信號強度 238 9.1.2 信號到達時間 238

9.2 節點的定位技術 238 9.2.1 映射技術 239 9.2.2 統計定位算法 239

9.3 基於粒計算的傳感器節點定位算法 240 9.3.1 WSN的結構 240

9.3.2 定位區域的網格化 242 9.3.3 粒計算定位算法 242 9.3.4 定位算法的精度分析 243 9.3.5 數值仿真實驗 244

9.4 本章小結 246

參考文獻 246

第10章總結與展望 248

10.1 研究工作總結 248

10.2 研究工作展望 251

媒體評論

在線試讀

第1章多目標演化算法
多目標優化問題(multi-objective optimization problem,MOP)廣泛存在於科學和工程領域,這類問題的子目標通常是相互衝突的,也就是說某個子目標性能的改善可能引起其他子目標性能的降低[1-3]?例如,無線傳感器網絡中成本(與節點個數相關)與覆蓋率就是兩個衝突的目標,對於一個特定的區域,為了得到較高的覆蓋率,人們往往要增加傳感器節點的個數,這就會增加經濟成本和通信的復雜性?因此,使用少的傳感器個數得到的網絡覆蓋範圍就是典型的多目標優化問題?
由於多目標優化問題中多個目標之間的衝突性,使多個目標同時達到是很困難的?因此,常用的多目標優化問題解決方法主要有兩種:一種是將多目標優化問題轉化成單目標優化問題(如通過加權求和的形式),用單目標優化算法求解[4]?這類方法中權重的確定往往依賴於領域知識和問題的復雜性,而且隻能得到的對應權重組合的解,這個解往往不能完全適合決策者的需要,限制了多目標優化問題的應用領域?另一種是借助基於種群搜索的啟發式演化算法和解的偏序關繫(如 Pareto支配關繫)建立的多目標演化算法(MOEA)[5]?演化計算是模擬自然界生物進化的過程與機制,用來求解優化與搜索問題的一類自組織?自適應的仿生優化技術?它具有生物基礎堅實?認知科學意義鮮明?自然並行和對任何函數類可用等突出特點?這類技術自 Holland提出遺傳算法以來,已經得到了迅速的發展,在應用中獲得很大成功?演化算法具有基於種群的全局搜索?對問題的復雜性不敏感和內在並行性等特征,基於 Pareto支配關繫的多目標演化算法能在一次運行得到一組折中的可行解,而且該組解的獲取方法不依賴於領域知識以及對問題的復雜性不敏感,決策者可以根據領域知識和問題特點在這組可行解中選擇合適的決策方案,因此多目標演化算法已經成為研究多目標優化問題的重要方法和手段,廣泛應用於管理決策?工程技術和科學研究等領域?
用演化算法求解多目標優化問題的多目標演化算法隻能在有限的搜索空間上,利用個體之間的支配關繫,通過逐步求精的方法逼近解集?例如,Pareto支配關繫的逐步求精方法得到的解集對應的就是 Pareto前沿?由於種群規模是有限的,多目標演化算法隻能得到有限個離散的解組成的非劣解集,即多目標演化算法得到的是離散的非劣解集,而多目標優化問題的解有可能是連續點組成的曲線?曲面?超曲面等,即多目標優化問題的解集是連續解集?因此,如何保證後得到的非劣解集與解集的逼近程度以及近似 Pareto前沿上對應的非劣解集盡可能地分布均勻是衡量多目標演化算法的兩個重要指標,而且在每次迭代過程中都要度量這兩個指標?非劣解集與解集的逼近程度是通過算法的收斂性來度量的,而非劣解集的分布均勻性是通過種群的多樣性來度量的?第1章多目標演化算法

多目標優化問題(multi-objective optimization problem,MOP)廣泛存在於科學和工程領域,這類問題的子目標通常是相互衝突的,也就是說某個子目標性能的改善可能引起其他子目標性能的降低[1-3]?例如,無線傳感器網絡中成本(與節點個數相關)與覆蓋率就是兩個衝突的目標,對於一個特定的區域,為了得到較高的覆蓋率,人們往往要增加傳感器節點的個數,這就會增加經濟成本和通信的復雜性?因此,使用少的傳感器個數得到的網絡覆蓋範圍就是典型的多目標優化問題?

由於多目標優化問題中多個目標之間的衝突性,使多個目標同時達到是很困難的?因此,常用的多目標優化問題解決方法主要有兩種:一種是將多目標優化問題轉化成單目標優化問題(如通過加權求和的形式),用單目標優化算法求解[4]?這類方法中權重的確定往往依賴於領域知識和問題的復雜性,而且隻能得到的對應權重組合的解,這個解往往不能完全適合決策者的需要,限制了多目標優化問題的應用領域?另一種是借助基於種群搜索的啟發式演化算法和解的偏序關繫(如 Pareto支配關繫)建立的多目標演化算法(MOEA)[5]?演化計算是模擬自然界生物進化的過程與機制,用來求解優化與搜索問題的一類自組織?自適應的仿生優化技術?它具有生物基礎堅實?認知科學意義鮮明?自然並行和對任何函數類可用等突出特點?這類技術自 Holland提出遺傳算法以來,已經得到了迅速的發展,在應用中獲得很大成功?演化算法具有基於種群的全局搜索?對問題的復雜性不敏感和內在並行性等特征,基於 Pareto支配關繫的多目標演化算法能在一次運行得到一組折中的可行解,而且該組解的獲取方法不依賴於領域知識以及對問題的復雜性不敏感,決策者可以根據領域知識和問題特點在這組可行解中選擇合適的決策方案,因此多目標演化算法已經成為研究多目標優化問題的重要方法和手段,廣泛應用於管理決策?工程技術和科學研究等領域?

用演化算法求解多目標優化問題的多目標演化算法隻能在有限的搜索空間上,利用個體之間的支配關繫,通過逐步求精的方法逼近解集?例如,Pareto支配關繫的逐步求精方法得到的解集對應的就是 Pareto前沿?由於種群規模是有限的,多目標演化算法隻能得到有限個離散的解組成的非劣解集,即多目標演化算法得到的是離散的非劣解集,而多目標優化問題的解有可能是連續點組成的曲線?曲面?超曲面等,即多目標優化問題的解集是連續解集?因此,如何保證後得到的非劣解集與解集的逼近程度以及近似 Pareto前沿上對應的非劣解集盡可能地分布均勻是衡量多目標演化算法的兩個重要指標,而且在每次迭代過程中都要度量這兩個指標?非劣解集與解集的逼近程度是通過算法的收斂性來度量的,而非劣解集的分布均勻性是通過種群的多樣性來度量的?

在生物界的演化過程中,僅根據某個特定的度量指標對種群中的個體進行度量以判斷其優劣的方法,並不能真實體現個體後代的優劣?這就是說,僅僅用適應值來度量個體的優劣,優秀個體的後代並不一定都是優秀個體,可能產生差的個體;相反,差個體的後代並不一定是差的,可能產生比較優秀的個體?在傳統的多目標演化算法中,僅僅根據個體的適應值的大小就淘汰差的個體而保留優秀的個體,使差的個體從此失去進一步競爭的機會是不公平的,也是不符合自然規律的?因而,往往會出現算法早熟收斂,得到的非劣解集可能不能更好地逼近 Pareto前沿和種群的多樣性損失,使種群出現同質的現像?在演化過程中盡量保持種群的多樣性既有助於發現潛在的非劣解,加快算法的收斂,又能使得找到的近似Pareto前沿盡可能地逼近 Pareto前沿;保持對應近似 Pareto前沿解集的多樣性能使其具有較好的均勻性?因此,多樣性保持策略的研究成為多目標演化算法的研究熱點之一?

1.1 多目標優化問題描述

不失一般性,本書討論的多目標優化問題都是小化多目標優化問題,可描述為[6]一個多目標優化問題含有 n個自變量,k個目標函數和 m個約束條件,目標函數和約束條件都是自變量的函數,即

min y=(f1(x),f2(x),…,f k(x))(1-1)

s.t. g(x)= g1(x),g2(x),…,g m(x)≤0

其中,x=(x1,x2,…,x n)∈R n;y=(y1,y2,…,y n)∈R k;x組成解空間 R n;y組成目標空間 R k?

多目標優化問題與單目標優化問題有著顯著的差別,單目標優化問題的目標函數是的,解通常也是的?多目標優化問題含有多個目標,而且目標函數之間往往是相互衝突?相互矛盾的,因此多目標優化問題的解是非劣解組成的解集(非劣解集),非劣解集中的解不存在優劣關繫?在多目標優化問題中,解之間的優劣性比較是非常重要的,一般用 Pareto支配關繫來定義解之間的優劣關繫?

定義1-1 對於解空間中的任意兩個近似解 x′和 x″,若同時滿足如下兩個條件,則稱 x′支配 x″,記做 x′吵x″,

① 於所有的目標函數,x′都不比 x″差,即

f i(x′)≤f i(x″), i=1,2,…,k

②至少存在一個目標函數使得 x′比 x″要優,即存在 j(1≤j≤k),使

f i(x′)
定義1-2 對於決策變量 x∈R n,若不存在 x′∈R n,使得 x′吵x,則稱 x為 R n上的 Pareto解?

定義1-3 對於給定的多目標優化問題和 Pareto解集ρ倡,Pareto前沿定義為

PF倡= F(x)= f1(x),f2(x),…,f k(x) x∈ρ倡

定義1-4 非劣解集ρ由解空間 R n中沒有被其他解支配的解構成的集合,即

ρ= x∈R n棎愁x′∈R n,x′吵x

定義1-5 與解空間的非劣解集對應的目標空間的向量集合稱為近似 Pareto前沿,即

PF= F(x)= f1(x),f2(x),…,f k(x) x∈ρ

1.2 多目標優化問題的一般求解方法早在1967年,Rosenberg就建議采用演化機制解決多目標優化問題[7],但直到

1985年Schaffer使用演化算法成功地解決多目標優化問題後,多目標演化算法纔引起研究者的廣泛關注[8]?近10年來,多目標演化算法的研究吸引了越來越多的學者和不同領域專家,國際上有關的學術活動也非常活躍?從2001年以來,每兩年召開一次多目標演化優化(evolutionary multi-criterion optimization,EMO)的國際會議,演化計算領域有影響的兩個國際學術會議 Congress on Evolutionary Computation(CEC)和 Genetic and Evolutionary Computation Conference(GECCO)也將多目標演化的相關研究作為專題研討?IEEE Transaction on Evolutionary Computation?Evolu-tionary Computation和 Genetic Programming and Evolvable Machines等權威期刊以及相關的國內外學術期刊有關多目標演化的論文大量湧現?國內外有大量的科研機構建立了與多目標優化和演化計算相關的網站,收集了大量的研究成果,供相關領域的研究人員學習交流?

多目標演化算法根據不同的需要有多種分類方法,如按不同的決策方式分類[9],可以分為前決策技術?交互決策技術以及後決策技術;按不同的適應值評價方法分類[6],可以分為基於聚類的方法?基於準則的方法以及基於 Pareto的方法?本書按使用不同的多樣性保持策略進行分類,可以分為小生境方法?聚類分析方法及網格方法?下面對一些常用的多目標演化算法,簡單說明它們的多樣性保持策略?適應值評價方法,以及算法的性能等,如表1-1所示?

表1-1 主要的多目標演化算法

算法多樣性保持策略適應值評價方法性能

VEGA[7]無標準的適應值賦值

實現簡單但容易向目標空間的某些邊界點收斂,並對 Pareto前沿端的非凸部分較為敏感

MOGLS[10]無

對目標函數進行線性加權,權繫數采用隨機的方法生成

容易實現但算法易於向目標空間的某些邊界點收斂,並對 Pareto前沿的非凸部分較敏感

MOGA[11,12]

基於適應值共享機制

的小生境方法

根據 Pareto概念對個體進行分級

效率高且實現相對容易,但收斂速度較慢,算法效率與小生境選擇參數有關

NSGA[13]

基於適應值共享機制的小生境方法

根據 Pareto支配關繫對個體進行分級排序

較好的收斂速度,但算法效率與小生境參數選取有關

NPGA[14]

基於適應值共享機制的小生境方法

基於 Pareto支配關繫的錦標賽選擇方法

實現容易但算法效率依賴於小生境參數與錦標賽參數

NGPA2[15]

基於適應值共享機制的小生境方法

基於確定性 Pareto級別排序比較集的錦標賽選擇

在 NPGA算法的基礎上,引入了精英保持策略,提高了算法的性能,但復雜度較大

NSGAII[16]

基於擁擠機制的小生境方法

根據支配關繫對個體進行分級排序

參數少,易於實現且效率高,但擁擠距離隻針對目標空間

SPEA[17,18]聚類方法

根據外部歸檔集中非劣解集支配個體的數目進行分級

易於實現但聚類算法較為復雜

SPEA2[19,20]

基於擁擠機制的小生境方法

支配強度

改進了 SPEA,保持了近似 Pareto前沿邊界點,但適應值計算和密度計算較為復雜

PAES[21]

網格方法

基於 Pareto支配關繫

隨機變異,爬山法搜索,易於實現,計算效率高,但非基於種群方法,算法性能依賴於網格數

續表

算法多樣性保持策略適應值評價方法性能

PAES2[22]

網格方法

基於 Pareto支配關繫

基於種群,易於實現但網格計算時間消耗較多

PESA[23]

網格方法

對外部歸檔的非劣解集中的個體進行錦標賽選擇

算法強調演化過程中搜索方向和步長的自適應調節,增強了算法局部尋優能力;超網格和擁擠距離的計算消耗太多時間

PESA2[24]

網格方法

對外部歸檔的非劣解集的個體進行錦標賽選擇

改進了 PESA算法的性能但算法在網格上的計算時間消耗較多

MOPSO[25,26]

網格方法

基於自適應網格機制的評價方法

算法收斂速度快,但為了保證解分布的均勻性和寬廣性,需要引入其他策略,使得算法的復雜度比較高

DMOEA[27]

網格方法基於自格密度

采用有格密度更新技術,自適應的設置遺傳算法的參數但比其他算法更難實現

RDGA[28]

網格方法

根據解的等級和密度評價適應值

格更新法,對目標函數個數魯棒性較好但比其他算法更難實現

HE MO[29-31]

網格方法線性加權

公平競爭模型的引入改進了標準遺傳算法的缺陷,不僅能確保種群的多樣性,而且保證了個體間的公平競爭,然而層間閾值?個體遷移的比率和劃分的層數等參數的設置相當繁瑣,嚴重制約著算法的性能

當前,國內外有關多目標演化算法的研究進入了快速發展階段,並取得了許多可喜的成果[32],大概可以分為交互式多目標演化優化,Chaudhuri和 Deb等提出交互式多目標演化算法,算法中交互地引入決策者的偏好信息,使算法搜索到期望區域內的解[33-37];基於集合的多目標演化優化,Fernandeza和 Lopez等提出基於偏序方法學的多目標演化優化解決高維多目標優化問題[5,38,39];基於演化範例的多目標演化優化,為了解決目標維數很大時選擇壓力減小的情況,Gao等提出了基於平衡選擇壓力排序策略的多目標演化算法[40]?

由於種群規模有限,多目標演化算法隻能得到有限個離散的解組成的非劣解集,與其對應的近似 Pareto前沿也是離散集合,而實際多目標優化問題的解有可能是連續的,其對應的 Pareto前沿也是連續的?如何以離散的解集去逼近連續解集和用何種方法去度量離散解集與連續解集的逼近程度是多目標演化算法研究的主要內容?多樣性保持策略是實現多目標演化算法收

商品搜索

商品分类

【醫學】

【各大出版社】