結合模擬退火與規則約簡的模糊系統優化方法

童文林，陳德旺，黃允滸，呂宜生

1.福州大學 數學與計算機科學學院，福州350108

2.福州大學 智慧地鐵福建省高校重點實驗室，福州350108

3.中國科學院 自動化研究所 復雜系統管理與控制國家重點實驗室，北京100190

模糊理論自誕生之日起，就一直處在各派的激烈競爭中，經歷了跌宕起伏的2次興起和3次衰落的發展歷程[1]，但其理論研究仍然不夠成熟[2-3]。它是一種可解釋性很強的人工智能方法。對于神經網絡而言，即使是專家也難以解釋和理解參數的意義[4]。而模糊系統由一系列模糊IF-THEN規則構成，其結構和參數可以用該規則來解釋，具備快速、靈活性強、易于理解的特點，但其缺點是自學習能力差，模型精度不高。

王立新與Mendel提出了經典的模糊算法WM[5]。該算法從樣本數據中通過自學習構建模糊系統，具有簡單實用的特點，并且在領域內被廣泛地應用。但WM方法中一條規則僅由一條數據產生，使得通過WM方法構造的模糊系統缺乏良好的完備性以及魯棒性。因此，王立新對WM方法進行改進[6]，定義了沖突規則以及相鄰規則。通過多條數據選舉產生一條規則，對于完備規則庫中無法從數據中提取的規則，通過相鄰規則外推得到，改善了其完備性不足的問題。但WM方法主要關注于如何從數據中學習模糊系統，對學習后的模糊系統關注不足，導致其魯棒性問題仍然沒有得到很好的解決。

針對這些問題，一些研究者提出了基于神經網絡的方法[7]、模糊聚類[8]、基于全局優化的模糊系統[9]、基于神經網絡、模糊系統和遺傳算法[10]三者相結合的方法以及許多改進的模糊算法以及模糊優化算法，例如Garg等[11]、Wu等[12]以及Shi等[13]提出的優化方法。上述算法在一些應用中取得了較好的效果，但是對于模糊集合的劃分個數、隸屬度函數參數的選取缺乏有效的指導[14]，可解釋性仍然有待提高。

因此，如何在模糊建模過程中避免算法效率下降以及兼顧完備性、魯棒性的同時，提高模糊系統的可解釋性仍然是亟待解決的問題。基于以上分析，本文從模糊規則提取與約簡以及模糊系統結構優化即隸屬函數參數優化三方面進行考慮，同時結合模擬退火（Simulated Annealing，SA）優化算法及模糊支持度（Degree of Support，SD）的特點，提出基于模擬退火與支持度規則約簡的模糊系統優化方法SSF。

1 模糊系統理論分析

Mamdani模糊系統（也稱為Zadeh模糊系統）規則表示形式如式（1）所示：前件IF部分及后件THEN部分均使用模糊集合表示。

其中U1,U2,…,Un與V1分別為輸入與輸出空間上的模糊集合。

圖1 展示了由模糊化、模糊規則庫、推理機和去模糊化四部分組成為的Mamdani模糊系統。其中模糊化把每個輸入映射成模糊集，推理機基于規則庫進行推理來得到一個新的模糊集，通過去模糊化把模糊集映射成一個數值化輸出。模糊規則庫作為模糊系統的核心部分，其組成除了模糊規則表示形式，還包括模糊集合的隸屬度函數表示形式[15]。

圖1 Mamdani模糊系統示意圖Fig.1 Schematic diagram of Mamdani fuzzy system

本文隸屬度函數使用三角形隸屬度函數，其定義如式（2）所示：

其中，σ表示三角形隸屬函數的偏差，yc表示三角形隸屬函數的中心值，y表示輸入值。

2 本文算法

2.1 模糊規則提取

對于模糊規則的提取，本文采用以完備的模糊規則庫為基礎，分別確定規則前件與后件的方式，以保證模糊規則的完備性。首先對輸入空間進行劃分，在劃分且為每一維輸入空間分別分配mi個（i為數據維度）模糊集合后，則可以確定一個完備的模糊規則庫所包含的模糊規則數目為∏mi,以及每一條規則的前件部分均由每一維上的模糊集合組合而成，具有式（1）前件的形式。對于規則后件的確定，利用所有輸入數據，根據數據對規則的貢獻程度來確定。

從數據挖掘的角度看，每一個樣本數據對完備的模糊規則庫中的每一條規則都是有貢獻的，本文用數據在模糊規則前件上的隸屬度來描述數據對規則的貢獻程度。假設有n條樣本數據且完備的模糊規則庫中包含N條模糊規則，那么C(i,j)表示數據i對規則j的貢獻度(i≤n,j≤N)，如表1所示。

表1 數據貢獻度Table 1 Data contribution

將規則前件看作規則包含的n個模糊集合的笛卡兒積，例如有一條規則具有如下前件形式：

其中，?表示一種t范數。愛因斯坦積與代數積均具有有界性、交換性、非減性以及結合性。同時代數積具有計算及應用簡單的特點，而愛因斯坦積通過一個與自變量相關的因子在一定程度上對輸出值進行修正。因此本文選擇這兩種t范數：

（1）愛因斯坦積

（2）代數積

假設一個二維輸入單輸出且滿足y=X1+X2的模擬樣本數據，如表2所示。

表2 模擬樣本數據Table 2 Simulation sample data

將每一維輸入空間(X1:[0,10],X2:[0,8])劃分并分別分配3個模糊集合，X1空間上的模糊集合為X2空間上的模糊集合為，如圖2所示。

圖2 輸入空間劃分示意圖Fig.2 Schematic diagram of input space division

因此，根據式（2）可以得到每一個模糊集合上隸屬度的計算公式，如式（6）~式（11）所示：

那么就可以確定一個完備的模糊規則庫將包含9（3×3）條規則，其規則形式如下所示：

其中B1,B2,…,B9為規則后件待確定的模糊集合。根據式（3）、式（4）和式（5），可以計算得到樣本數據在規則上的隸屬度。以數據1對規則1的貢獻度C(1,1)計算為例，根據式（3），首先計算出數據1（0，2）在規則1上的隸屬度：

其中?運算以代數積為例，則：

同樣的，可求得數據1對規則1至規則9的貢獻度C(1,j)；數據2對規則1至規則9的貢獻度C(2,j)；數據3對規則1至規則9的貢獻度C(3,j)；數據4對規則1至規則9的貢獻度C(4,j)；其中j=1,2,…,9。經過計算，表2對應的數據貢獻度表如表3所示。

表3 樣本數據貢獻度Table 3 Sample data contribution

得到每一條數據對每一條規則的貢獻度后，以此作為權重，計算規則j輸出部分模糊集合的中心值及偏差σj，從而確定所有的規則，如式（12）和式（13）所示：

2.2 模糊規則約簡

當前的研究主要集中在如何提高模糊系統的精度，而對于學習后的模糊系統的規則數關注不足，影響了模糊系統的可解釋性。因此，適當約簡系統規則對提高模糊系統的可解釋性顯得尤為重要。完備的模糊規則庫中的一些規則相對訓練數據而言是冗余的，本文通過支持度來描述規則是否冗余。支持度SD定義如下：

其中，S(i,j)表示數據i在規則j上的指示函數值，m為樣本數，SDj為第j條規則的支持度。當規則j的支持度SDj小于規則約簡閾值時，規則j被認為是冗余的，將規則j從完備的模糊規則庫中刪除；反之，當規則j具有足夠的支持度時，將其保留。

在2.1節例子的基礎上，對表3根據指示函數公式（14）以及支持度計算公式（15）進行處理，可以得到規則1至規則9的支持度，如表4所示。

表4 規則支持度Table 4 Rule support

設定規則約簡閾值為0.3，那么規則1、規則3以及規則9的支持度低于該閾值，則將這些規則從完備的模糊規則庫中刪除。因此從樣本數據中獲取的模糊規則庫中包含規則2、規則4、規則5、規則6、規則7以及規則8。

2.3 模糊系統結構優化

在提取并約簡規則后，初始的模糊系統已經構建完畢。但是由于模糊集合的分配與輸入空間的劃分往往是根據經驗進行的，帶有很強的主觀性，這樣的模糊系統結構往往難以滿足數據的要求。因此根據模擬退火算法對初始的模糊系統結構進行調整，使模糊系統的結構更加適應數據。

模擬退火算法[16]在解空間搜索時采用Metropolis準則，以一定的概率接受比當前解更差的解，從而能夠跳出局部最優，得到全局最優。該算法從起始溫度以及初始解開始，在當前溫度下為當前解加入擾動后產生新解以搜索更優的解。當在當前溫度下達到一定搜索次數時，通過降溫系數降低當前溫度繼續搜索。溫度的降低也將導致對更差解的接受概率逐漸降低，直到溫度降低到停止溫度時得到最終解。本文隸屬函數選擇三角形隸屬函數，包括left、center和right三個分段點。將系統中包含的所有模糊集合的中心點center組成初始解向量進行搜索。每一次搜索都為當前解增加擾動以產生新解，也就意味著新解對應的模糊集合的中心點相較于當前解對應的模糊集合的中心點發生了改變，為了保證模糊集合重疊的特性，需要同步地調整新解對應的模糊集合的left和right點：將新解對應的所有模糊集合的left點修改為前一個模糊集合的center點，right點修改為后一個模糊集合的center點。

SA算法使用Metropolis準則時，根據當前解與新解在目標函數上的差值決定是否更新當前解為新解。對模糊系統結構參數優化是為了提高模糊系統的精度，因此本文將訓練集上的均方誤差（MSE）作為搜索過程中的目標函數，如式（16）所示。對于新解而言，用于預測的模糊規則庫有兩種選擇：一種是使用在初始解條件下提取的模糊規則；另一種是利用新解重新提取模糊規則。

其中，y?k、yk分別為預測值和真實值。y?k是在由單值模糊化、乘積運算、加權平均反模糊化得到的模型上預測的結果，如式（17）所示：

在搜索新解的過程中，解向量中每一維的解空間在當前解更新后都會發生變化，而在當前解的基礎上增加一個受溫度參數影響的隨機數來增加擾動也會變得難以控制。因此通過在解向量中每一維的搜索范圍內隨機選取一個值作為新解的每一維實現增加擾動產生新解。同時，解向量中每一維的搜索范圍將受到溫度的影響：隨著溫度的降低，解向量中每一維的搜索范圍以縮減系數β進行收縮。縮減系數的定義如式（18）所示：

那么解向量中每一維的搜索范圍經過縮減后的左、右邊界點分別如式（19）和式（20）所示：

其中，left、center和right分別表示解向量對應模糊集合的左邊界點、中心點和右邊界點，maxT表示初始溫度，T表示當前溫度。

當溫度降低至停止溫度時，搜索結束，將退火過程中的最優解作為最終解，模糊系統的結構參數調優完成，最終的模糊系統構造完畢。

3 算法實現及分析

本文的模糊系統建模及優化流程如圖3所示。

圖3 模糊系統建模及優化流程Fig.3 Fuzzy system modeling and optimization process

3.1 實現步驟

步驟1將導入的數據集進行歸一化處理，并劃分為訓練集Dtrain和測試集Dtest。

步驟2將輸入空間進行等分劃分，并為每一個子空間分配模糊集合。根據分配的模糊集合確定所有規則的前件。

步驟3計算所有樣本數據對完備模糊規則庫中所有規則的貢獻程度。根據式（14）和式（15）計算每條規則的支持度，并設定規則約簡閾值刪除冗余規則。

步驟4根據式（12）和式（13）確定模糊規則庫中規則后件部分的模糊集合。

步驟5設定模擬退火算法超參數：起始溫度maxT、停止溫度minT、每一溫度下的搜索次數n以及降溫系數q。選取初始解，利用SA算法對模糊系統的隸屬函數的參數進行優化，調整模糊系統結構。

步驟6最終的模糊系統構造完畢，將測試集數據Dtest輸入此模糊系統進行預測，得到預測結果。

同樣地，利用表2的模擬數據對本文算法進一步介紹。步驟1是數據預處理的過程，步驟2及步驟3已經分別在前文第2.1節以及第2.2節敘述，因此不在此處贅述。經過步驟3約簡規則后，從樣本數據中確定了模糊規則庫中包含規則2、規則4、規則5、規則6、規則7以及規則8。接著執行步驟4，以規則2為例確定其后件。根據式（12）和式（13），可以分別得到其后件模糊集合的中心點及偏差：

因此根據式（2）得到規則2后件的模糊集合如下式所示：

同樣地，其余規則的后件部分模糊集合均可確定。所有規則后件部分確定后，即可得到模糊規則庫。

在提取并約簡模糊規則后執行步驟4，假設maxT=100,minT=1,q=0.9,n=20。初始時，模糊集合的中心點分別為0，5，10，0，4，8，因此算法的初始解x0=[0,5,10,0,4,8]。從初始解開始搜索，假設經過第一次搜索后產生的新解為x1=[2,4,8,2,6,7]，表示新解對應的模糊集合的中心點分別為2，4，8，2，6，7，那么需要同步地調整新解中每個模糊集合的左邊界點為前一個模糊集合的中心點，右邊界點為后一個模糊集合的中心點。模糊集合調整前后示意圖如圖4、圖5所示，其中黑色曲線表示當前解x0所對應的模糊集合，藍色曲線表示新解x1所對應的模糊集合。

圖4 X1輸入空間模糊集合調整對比圖Fig.4 Comparison diagram of fuzzy set adjustment in X1 input space

圖5 X2輸入空間模糊集合調整對比圖Fig.5 Comparison diagram of fuzzy set adjustment in X2 input space

接著根據式（17）分別使用x0對應模糊集合以及x1對應模糊集合對測試集進行預測。對于x1而言，若選擇重新提取規則，則執行步驟3、步驟4后再進行預測；否則使用初始解條件下提取的模糊規則進行預測。預測完成后，根據式（16）分別計算當前解的目標函數值f，以及新解的目標函數值f′，即二者在測試集上的均方誤差。根據Metropolis準則決定是否接受新解，當f′

對當前解更新完成后，進行新的搜索。在溫度為100的條件下進行20次搜索后，根據T′=q×T降低當前溫度為90，同時根據式（18）、（19）、（20）縮小當前溫度下新解的搜索范圍。在溫度為100時：

解向量中每一維的搜索范圍為[L,R]，即每一維對應的模糊集合的左右邊界點之間。在溫度為90時：

因此對應的每一維的搜索范圍在[L′,R′]。相較于溫度為100時，搜索范圍縮減了10%，意味著減少了對較差解的搜索，更偏向于較優解。以溫度為100時和溫度為90時，解向量第二維即集合中心點的搜索范圍進行對比，如圖6所示。

圖6 搜索范圍對比圖Fig.6 Comparison of search ranges

如此循環搜索，當溫度降低到停止溫度minT且搜索完成時，選擇退火過程中的最優解作為模糊系統隸屬度函數參數的解，完成系統結構的優化。至此，模糊系統構造完畢，可執行步驟6對輸入數據進行預測。

3.2 算法復雜度分析

在實現過程中，提取與約簡規則時需要遍歷所有樣本數據和模糊規則以及存儲樣本數據對完備模糊規則支持度，因此其時間、空間復雜度均為O(n×N)，其中n為樣本數據量，N為完備模糊規則庫中的規則數。而在優化過程中僅需O(1)復雜度存儲SA算法的超參數，需要O(T×C)時間復雜度，其中T為搜索新解的溫度個數，C表示每個溫度下的搜索次數。整個模糊系統的參數包括輸入部分模糊集合以及輸出部分模糊集合，其復雜度為O(M+K)，其中M為輸入空間上劃分的模糊集合個數，k為提取約簡后的規則量。因為O(1)≤O(M+K)≤O(n×N)，所以該算法的空間復雜度為O(n×N)，時間復雜度為O(n×N+T×C)。從以上分析看，時間復雜度相對較高，這是用模擬退火算法提高精度所付出的代價，因此降低時間復雜度將成為日后的一個研究重點。

4 實驗結果與分析

為了驗證本文算法的有效性，將t范數使用式（4）愛因斯坦積且在SA中對新解重新提取模糊規則庫的算法命名為SSF1；將t范數使用式（4）愛因斯坦積且在SA不對新解重新提取模糊規則庫的算法命名為SSF2；將t范數使用式（5）代數積且在SA中對新解重新提取模糊規則庫的算法命名為SSF3；將t范數使用式（5）代數積且在SA中不對新解重新提取模糊規則庫的算法命名為SSF4。同時引入了BP算法、RBF算法和WM算法進行比較分析。將MSE（式（16））與R2作為客觀評價標準。

4.1 數據集描述

本文在3個數據集上驗證提出的算法，所有數據集均選自機器學習庫UCI Machine Learning Repository。各數據集的特征總結如表5所示。

表5 數據集特征總結Table 5 Summary of data set characteristics

4.2 Adv數據集應用

圖7 展示了各算法在Adv數據集的訓練集、測試集上的預測效果。表6、表7分別展示了各算法在訓練集和測試集上各項評價指標值。

從表6、表7可以看出，SSF1算法在各項評價指標上都表現得最佳，尤其在MSE與R2指標上，占了絕對優勢。結合圖7和表7，SSF算法對樣本數據的學習能力比BP、RBF以及WM算法都更強。而從圖7（b）和表7可以看出，SSF1、SSF2有更好的泛化能力。與WM算法相比，SSF算法在規則數目上均比WM算法的少，可解釋性得到提高。SSF1的規則數約是WM的一半，可解釋性最好。

表6 各算法在訓練集上的各項評價指標值（Adv數據集）Table 6 Evaluation index values of each algorithm on training set（Adv data set）

表7 各算法在測試集上的各項評價指標值（Adv數據集）Table 7 Evaluation index values of each algorithm on test set（Adv data set）

圖7 各算法在Adv數據集上的預測效果Fig.7 Prediction results of each algorithm on Adv data set

4.3 DJ數據集應用

圖8 展示了各算法在DJ數據集的訓練集及測試集上的預測效果。表8、表9分別展示了各個算法在訓練集和測試集上各項評價指標值。

表8 各算法在訓練集上的各項評價指標值（DJ數據集）Table 8 Evaluation index values of each algorithm on training set（DJ data set）

表9 各算法在測試集上的各項評價指標值（DJ數據集）Table 9 Evaluation index values of each algorithm on test set（DJ data set）

圖8 各算法在DJ數據集上的預測效果Fig.8 Prediction results of each algorithm on DJ data set

在DJ數據集上，SSF1算法在訓練集、測試集中同樣表現出良好的性能，在誤差以及模型的解釋能力上比傳統的BP算法、RBF算法以及WM方法都要更好。在規則數目上，SSF1與SSF3分別占WM算法的29.3%與34.6%，SSF2與SSF4的規則數分別占WM算法的56%。可以明顯看出，基于SSF的四種算法的規則數顯著下降，可解釋性進一步提高。

4.4 Rev數據集應用

圖9 展示了各算法在Rev數據集的訓練集、測試集上的預測效果。表10、表11分別展示了各算法在訓練集和測試集上的各項評價指標值。

表10 各算法在訓練集上的各項評價指標值（Rev數據集）Table 10 Evaluation index values of each algorithm on training set（Rev data set）

表11 各算法在測試集上的各項評價指標值（Rev數據集）Table 11 Evaluation index values of each algorithm on test set（Rev data set）

圖9 各算法在Rev數據集上的預測效果Fig.9 Prediction results of each algorithm on Rev data set

從表10可以看出，SSF算法在各項指標上均表現得比其他算法更好。其中SSF3在訓練集上的各項指標居于首位，表現出明顯的優勢。從表11可以看出，SSF1的誤差最小，精度最高且對模型的解釋能力表現得更好。從規則數目上看，SSF3規則數最少，可解釋性最好。

5 結論與展望

通過實驗可以看出，SSF算法在實際回歸預測問題中具有一定的可行性以及較好的性能。與一些經典算法相比，SSF1及SSF3算法在精度和可解釋性上具有明顯的優勢：

（1）SSF算法以完備的模糊規則庫為基礎，依據所有數據對規則的貢獻程度參與模糊規則庫中規則的生成，并通過模糊規則的支持度對冗余的規則進行約簡，提高了模型的可解釋性。

（2）通過模擬退火算法對模糊集合的結構參數進行調整，克服人工經驗的主觀性，使模糊系統更加適應數據，增強了泛化能力，提高了預測精度。

當前優化的模糊系統在高維數據中的表現還有待提高。在今后的工作中，將把機器學習中的一些技巧應用到模糊系統構造及優化中，并考慮應用于深度模型中，以適應高維數據的要求，進一步提高模糊系統處理實際問題的能力。