基于改進(jìn)螢火蟲算法的模糊Petri網(wǎng)學(xué)習(xí)能力研究

顏明

（中國(guó)傳媒大學(xué)計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院，北京 100024）

1 引言

Petri 網(wǎng)(Petri Net, PN)是1962 年德國(guó)博士C. A.Petri 提出的一種用來(lái)模擬一些具有并行或并發(fā)事件的離散事件系統(tǒng)的數(shù)學(xué)模型，近年來(lái)被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)、自動(dòng)化控制、通信等領(lǐng)域的建模和性能分析過(guò)程中。但由于PN 難以描述不確定、模糊的系統(tǒng)，學(xué)者們將Petri網(wǎng)和和模糊數(shù)學(xué)相結(jié)合，擴(kuò)充其模糊處理能力提出模糊Petri 網(wǎng)（Fuzzy Petri Net，F(xiàn)PN[1]）。FPN 在具有PN 的固有優(yōu)點(diǎn)基礎(chǔ)上，還能夠精確描述模糊知識(shí)并兼有模糊系統(tǒng)的推理功能，能夠促進(jìn)知識(shí)分析、推理和決策，被廣泛應(yīng)用在知識(shí)庫(kù)系統(tǒng)的建模和診斷過(guò)程中[2]。但FPN的自適應(yīng)能力較差，其權(quán)值、閾值、確信度往往依賴于人工的經(jīng)驗(yàn)，從而影響推理結(jié)果的精度[3]。國(guó)內(nèi)外目前對(duì)于FPN參數(shù)優(yōu)化研究大多建立在具體的適用范圍的基礎(chǔ)上，如Pedrycz 與Gomide[4]為提高FPN的調(diào)整（學(xué)習(xí)）能力，采用了一種廣義模糊Petri 網(wǎng)（Generalized Fuzzy Petri Net，GFPN），Li 和Lara-Rosano 等[5]提出的在嚴(yán)格條件下FPN的權(quán)值參數(shù)的學(xué)習(xí)，Yang 等通過(guò)遺傳算法與FPN 結(jié)合，提升FPN 的學(xué)習(xí)能力[6]。在加權(quán)模糊Petri 網(wǎng)上，文獻(xiàn)[7]通過(guò)蟻群算法進(jìn)行優(yōu)化FPN的參數(shù)，并將該思路運(yùn)用與故障診斷推理過(guò)程中，取得了較好結(jié)果。LI等在基于FPN 的礦用變壓器故障診斷通過(guò)利用Elman 網(wǎng)絡(luò)算法的自適應(yīng)能力對(duì)FPN 的模型的初始參數(shù)進(jìn)行優(yōu)化[8]。在這些優(yōu)化的例子中，F(xiàn)PN 的模型大都局限在某一特定的領(lǐng)域，并且在優(yōu)化的結(jié)果上，這些算法大都存在精度不夠，易陷入局部最優(yōu)解，且易受初始參數(shù)的影響。本文擬在經(jīng)典螢火蟲算法（Firefly Algorithm，F(xiàn)A）的基礎(chǔ)上，利用經(jīng)典螢火蟲算法的全局搜索能力，通過(guò)優(yōu)化螢火蟲算法的步長(zhǎng)策略，改進(jìn)移動(dòng)策略，優(yōu)化簇間關(guān)系，對(duì)于FPN 的參數(shù)進(jìn)行調(diào)整優(yōu)化，提高FPN的自適應(yīng)能力。

2 FPN的形式化定義

FPN 多種形式的定義方式，但主要有庫(kù)所、變遷、確信度、閥值、權(quán)值這幾個(gè)部分構(gòu)成，因此本文采用一種通用的八元組來(lái)定義FPN[1]：

其中：

P={p1,p2,…,pn}為庫(kù)所的集合；

T={t1,t2,…,tm}表示所有變遷集；

I:P×T→{0,1}是一個(gè)n*m n*m 的輸入矩陣，用于表示庫(kù)所至變遷之間是否存在有向??；

O:P×T→{0,1}是一個(gè)n*mn*m 的輸出矩陣，表示從變遷至庫(kù)所是否存在有向?。?/p>

M=(m1,m2,…,mn)T為標(biāo)識(shí)向量，表示映射的完成度，初始值由M0表示；

て:て→(0,1]為各個(gè)變遷的閾值；

W(i,j)是規(guī)則的權(quán)值集合，表示從庫(kù)所pi到變遷tj的支持度；

U 是確 信 度的 集 合，U={U1,U2,…,Um}，其中Ui∈[0,1]表示由變遷ti(i= 1,2,…,m)至庫(kù)所pi(i=1,2,…,n)的確信度。

在FPN 中，若某庫(kù)所結(jié)點(diǎn)只有連線指向變遷結(jié)點(diǎn)，而無(wú)變遷結(jié)點(diǎn)指向它時(shí)，稱該庫(kù)所節(jié)點(diǎn)為輸入結(jié)點(diǎn)，反之稱該庫(kù)所節(jié)點(diǎn)為輸出結(jié)點(diǎn)[9]。

3 模糊Petri網(wǎng)的推理算法

一般而言，F(xiàn)PN 模型運(yùn)用于工程實(shí)踐中，主要有兩大步驟：根據(jù)特定的問(wèn)題（或者說(shuō)是特定問(wèn)題的知識(shí)庫(kù)）構(gòu)建對(duì)應(yīng)的FPN模型與根據(jù)得到的FPN模型構(gòu)造相應(yīng)的模糊推理算法,再將其運(yùn)用于實(shí)際問(wèn)題[10]。

3.1 變遷點(diǎn)燃函數(shù)

為了將判斷變遷是否使能的問(wèn)題，建立一個(gè)變遷點(diǎn)燃函數(shù)。該函數(shù)的自變量滿足一定要求并具有連續(xù)性，同時(shí)其模糊推理結(jié)果容易求導(dǎo)，建立的變遷點(diǎn)燃函數(shù)如下：

設(shè)y(x)是一個(gè)Sigmoid型函數(shù)，其中b為滿足要求的常量，則y(x)的表達(dá)式為y(x)= 1/( 1+e?b(x?k))

3.2 變遷點(diǎn)燃連續(xù)函數(shù)

3.3 最大運(yùn)算連續(xù)函數(shù)

根據(jù)前面的y(x)函數(shù)，假設(shè)x1,x2,x3為3 個(gè)變遷使能時(shí)的輸出，則當(dāng)b 足夠大時(shí)，下列推導(dǎo)過(guò)程顯然成立：

……，

根據(jù)以上規(guī)則，當(dāng)多個(gè)變遷使能時(shí)，對(duì)應(yīng)的輸出庫(kù)所p 終可得到一個(gè)連續(xù)的最大函數(shù)值Mp。通過(guò)建立模糊推理函數(shù)，接下來(lái)便可以構(gòu)建FPN 模型從而進(jìn)行相應(yīng)推理。

3.4 模糊Petri網(wǎng)建模及推理

本文通過(guò)一個(gè)具體FPN 模型來(lái)研究改進(jìn)螢火蟲算法對(duì)其參數(shù)的優(yōu)化。

已知庫(kù)所p1,p2,p3,p4,p5,p6,p7,p8 各自對(duì)應(yīng)著一個(gè)專家系統(tǒng)中的有關(guān)命題d1,d2,d3,d4,d5,d6,d7,d8,它們之間存在著如下的模糊產(chǎn)生式規(guī)則：

R1:IF d1 THEN d2(u2,て2),

R2: IF d1 or d2 THEN d3(u1,て1,u3,て3),

R3: IF d3 and d4 and d5 THEN d6(w1,w2,w3,u4,て4),

R4: IF d6 and d7 THEN d8(w4,w5,u5,て5).

按照上述模糊產(chǎn)生式規(guī)則，可建立以下FPN 模型，如圖1所示：

圖1 FPN模型實(shí)例

4 改進(jìn)螢火蟲算法

螢火算法作為一種基于群體的隨機(jī)搜索算法，其算法過(guò)程簡(jiǎn)單，對(duì)初始參數(shù)依賴小的特點(diǎn)，被廣泛應(yīng)用于參數(shù)尋優(yōu)中，但是算法的性能是以犧牲大量的時(shí)間來(lái)提升為代價(jià)的。因此，本文在已有螢火蟲算法的基礎(chǔ)上，提出一種基于分簇策略的振蕩螢火蟲改進(jìn)算法（Cluster-Based Oscillate Firefly Algorithm，CBOFA），以期提高了算法的精度的同時(shí)減少不同個(gè)體間的運(yùn)算次數(shù)。

4.1 螢火蟲算法的改進(jìn)思路

本文提出的改進(jìn)螢火蟲算法，具體改進(jìn)思想表現(xiàn)在如下三個(gè)方面。

首先，通過(guò)采用K?means聚類算法對(duì)螢火蟲種群進(jìn)行分簇；

其次，針對(duì)螢火蟲算法中全局最優(yōu)個(gè)體對(duì)于算法尋優(yōu)功能的導(dǎo)向作用，引入Levy飛行[11]策略與邊界約束，為平衡算法的尋優(yōu)速度和精度，引入改進(jìn)的精英鄰居策略，通過(guò)采用不同的進(jìn)化策略，以分而治之的方式，極大的增強(qiáng)了尋優(yōu)速度；

最后，利用全局自適應(yīng)步長(zhǎng)與光強(qiáng)對(duì)螢火算法輸入?yún)?shù)進(jìn)行優(yōu)化，針對(duì)螢火蟲算法在高維時(shí)尋優(yōu)精度不夠，引入振蕩策略，極大的提高了算法精度。

4.2 分簇策略

K?means算法是一種經(jīng)典的基于距離大小的聚類算法，CBOFA算法通過(guò)借鑒的K?means的距離作為分類依據(jù)，同時(shí)采用與標(biāo)準(zhǔn)K?means不同的聚類步驟，將每一代前k 個(gè)適應(yīng)度最高的個(gè)體作為簇內(nèi)中心，按照距離，將其余的個(gè)體劃分到不同的簇間。經(jīng)過(guò)一次迭代，所有個(gè)體重新開始按照適應(yīng)度排序，選擇適應(yīng)度最高的前k個(gè)個(gè)體，再次進(jìn)行簇劃分[12]。

其中，簇間距離采用歐式距離，具體計(jì)算如下：

xi=(xi.1,xi.2,...,...xi.d),xj=(x1.2,xj.2,...xj.d)為兩個(gè)不同的個(gè)體，其中d為數(shù)據(jù)維度，i,j∈[0,n],n為種族大小。

4.3 進(jìn)化策略

針對(duì)螢火蟲算法中全局最優(yōu)個(gè)體對(duì)于算法尋優(yōu)功能的導(dǎo)向作用，通過(guò)引入Levy飛行策略提高最優(yōu)個(gè)體的隨機(jī)擾動(dòng)能力，提升尋優(yōu)的范圍，同時(shí)為控制尋優(yōu)過(guò)程中，隨機(jī)飛行造成的個(gè)體超出問(wèn)題邊界，對(duì)最優(yōu)個(gè)體加入邊界控制，利用最優(yōu)個(gè)體的導(dǎo)向性能，從而控制所有個(gè)體均在問(wèn)題范圍內(nèi)求解。其次，對(duì)于分簇后的簇間最優(yōu)個(gè)體，為防止求解部分問(wèn)題時(shí)，由于缺少信息交流而陷入局部最優(yōu)解，通過(guò)改進(jìn)的精英鄰居策略，防止部分個(gè)體丟失其搜索性能。通過(guò)不同的采用不同的進(jìn)化策略，以分而治之的方式，在不影響螢火蟲搜索能力的同時(shí)，極大的增強(qiáng)了FA 算法的搜索范圍和尋優(yōu)速度，具體實(shí)現(xiàn)如下文所示。

4.4 移動(dòng)策略

對(duì)于分簇后的種群，每一個(gè)種簇因?yàn)榉N群多樣性的減小，局限于局部搜索，為避免分簇后的每一個(gè)進(jìn)化單位陷入局部最優(yōu)，因此引入精英鄰居引導(dǎo)策略，每一個(gè)簇間的最優(yōu)個(gè)體都為其它簇間最優(yōu)個(gè)體的鄰居，通過(guò)比較不同鄰居的適應(yīng)度值，來(lái)確定具體的移動(dòng)方式。

假設(shè)xi,xj為兩個(gè)不同的個(gè)體，若xj的適應(yīng)度大于xi，則xi的移動(dòng)公式為[13]：

其中，Boundmax,Boundmin分別為搜索區(qū)域的上限和下限。

Levy 飛行的隨機(jī)步長(zhǎng)服從Levy分布，Levy分布與高斯分布與柯西分布相比較，其尾翼更加的寬大，具有更強(qiáng)的擾動(dòng)效果[14]，其簡(jiǎn)化形式為：

其中，λ為指數(shù)參數(shù)，s為隨機(jī)步長(zhǎng)，s 的計(jì)算通常采用Mantegna[15]提出的計(jì)算公式：

其中，參數(shù)μ,v服式（5）的正態(tài)分布：

式中的δμ與δv定義為：

結(jié)合Levy飛行策略，將全局最優(yōu)個(gè)體的進(jìn)行改進(jìn)，假設(shè)為第t次迭代下的全局最優(yōu)個(gè)體，則xi的改進(jìn)移動(dòng)公式如下[11]：

其中，Levy(λ)為L(zhǎng)evy飛行產(chǎn)生的步長(zhǎng),α為CBOFA 的步長(zhǎng)，sign(rand)為L(zhǎng)evy飛行的方向，rand為[0,1]上服從均勻分布的隨機(jī)數(shù)：

為防止FA 在隨機(jī)移動(dòng)時(shí)，造成其位置超出問(wèn)題邊界，而引起運(yùn)算速度的降低與精度的損失，在對(duì)最優(yōu)個(gè)體的移動(dòng)上引入邊界控制機(jī)制[16]，其公式表示為：

4.5 全局策略

由FA 算法的描述可知，光吸收系數(shù)γ與α對(duì)于算法的收斂速度與精度有著重要的影響，對(duì)FA 算法中固定步長(zhǎng)α在搜索解的過(guò)程中，算法精度低，易陷入局部最優(yōu)解[17]，算法后期容易在最優(yōu)解附件振蕩的問(wèn)題，引入自適應(yīng)步長(zhǎng)策略，通過(guò)算法的迭代次數(shù)，動(dòng)態(tài)的更新步長(zhǎng)，具體實(shí)現(xiàn)如下：

光吸收系數(shù)的改進(jìn)有利于進(jìn)一步加快算法的尋優(yōu)速度，通過(guò)引入變尺度光強(qiáng)策略，利用文獻(xiàn)[18]的變尺度混沌映射Sinusoidal map，引入尺度變換后，光強(qiáng)吸收系數(shù)簡(jiǎn)化可表示為[19]：

在經(jīng)典的FA 算法中，螢火算對(duì)于高維尋優(yōu)問(wèn)題易陷入局部最優(yōu)，很難從局部的極值中跳出。隨著迭代次數(shù)增加，螢火蟲向聚集在一塊，有著較強(qiáng)的吸引力，從而使得種群多樣性降低。為增加種群多樣性，增打跳出局部最優(yōu)值得概論，在移動(dòng)公式中加入振蕩因子[20]，改進(jìn)后的螢火蟲移動(dòng)公式如下:

1、普通螢火蟲個(gè)體，假設(shè)xj的亮度大于xi，則xi的移動(dòng)公式為：

2、簇間最優(yōu)螢火蟲個(gè)體，假設(shè)xj為亮度大于xi的鄰居，則xi的移動(dòng)公式為：

4.6 基于分簇策略的振蕩FA改進(jìn)算法

綜上所述，具體的算法步驟如下，程序流程見圖2：

圖2 程序流程圖

1.設(shè)置算法最大迭代次數(shù)Tmax，種群大小n，光吸收系數(shù)λ，步長(zhǎng)因子α；

2.隨機(jī)生成n只螢火蟲，計(jì)算其適應(yīng)度；

3.對(duì)所有個(gè)體按適應(yīng)度進(jìn)行排序，選取適應(yīng)度靠前的k 個(gè)個(gè)體作為簇中心，并計(jì)算其余個(gè)體與簇中心個(gè)體的距離，完成分簇；

4.通過(guò)全局自適應(yīng)步長(zhǎng)與變尺度光強(qiáng)策略更新步長(zhǎng)與光強(qiáng)；

5.全局最優(yōu)個(gè)體利用式（11）進(jìn)行擾動(dòng)，除全局最優(yōu)個(gè)體以外的簇間最優(yōu)個(gè)體利用式（17）進(jìn)行位置更新，簇內(nèi)普通個(gè)體利用式（16）進(jìn)行位置更新；

6.對(duì)所有螢火蟲個(gè)體的適應(yīng)度進(jìn)行重新計(jì)算；

7.若算法迭代達(dá)到Tmax，則輸出最優(yōu)解，否則轉(zhuǎn)到步驟3。

5 基于改進(jìn)螢火蟲算法的模糊Petri網(wǎng)的自學(xué)習(xí)能力研究

人工智能方面的存在大量的優(yōu)化算法，這些算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合，在解決系統(tǒng)仿真、最優(yōu)化查找、網(wǎng)絡(luò)優(yōu)化、以及模式識(shí)別等問(wèn)題時(shí)，都取得不錯(cuò)的優(yōu)化效果，而將它們運(yùn)用到FPN 參數(shù)優(yōu)化的問(wèn)題上，大部分的研究都存在適應(yīng)能力不強(qiáng)，容易陷入局部最優(yōu)值的缺點(diǎn)。本文擬用CBOFA算法對(duì)給定的FPN 進(jìn)行優(yōu)化，并與已有的優(yōu)化算法DE 算法和PSO 算法優(yōu)化FPN作對(duì)比。

5.1 函數(shù)說(shuō)明

5.2 對(duì)比實(shí)驗(yàn)

為驗(yàn)證CBOFA在復(fù)雜的FPN中的優(yōu)化效果，因此采用圖1添加虛變遷的FPN模型，結(jié)合給定的推理算法，與DE、PSO算法做泛化對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)的期望參數(shù)設(shè)置為w1=0.2，w2=0.5，w3=0.3，w4=0.4，w5=0.6，u1=0.7，u2=0.9，u3=0.6，u4=0.8，u5=0.7，τ1=0.3，τ2=0.4，τ3=0.2，τ4=0.5，τ5=0.4，樣本數(shù)為10，樣本輸入如表1所示，種群數(shù)量為n=50，在推理函數(shù)中b=1 000，在CBOFA中初始步長(zhǎng)為1，光吸收系數(shù)為1，在DE算法中交叉概率設(shè)置為0.7，縮放因子0.6，在PSO算法中，粒子的最大速度為0.5。其中所有的算法均以Python實(shí)現(xiàn)。

表1 樣本超參數(shù)輸入

5.3 進(jìn)化過(guò)程比較

誤差均方差(Mean Squared Error，MSE)可用來(lái)反映參數(shù)的估計(jì)值與參數(shù)真值之間的差距，因此選用MSE作為一種進(jìn)化精度對(duì)比參數(shù)是一種有效的方式。圖3 (a)-(d)是三個(gè)算法的進(jìn)化曲線，反映的是三個(gè)算法在訓(xùn)練中，最優(yōu)解的權(quán)值w、確信度u 以及閥值t的誤差均方差進(jìn)化情況。對(duì)于總體的進(jìn)化曲線，從圖中可明顯的看出，無(wú)論是在單一的參數(shù)優(yōu)化，還是總的尋優(yōu)過(guò)程，CBOFA 都表現(xiàn)出較強(qiáng)的性能，其更高的精度，快速的收斂能力，對(duì)于FPN的自適應(yīng)能力的提升，具有一定的有效性。

圖3 MSE進(jìn)化曲線

5.4 泛化性驗(yàn)證

任取5組非樣本數(shù)據(jù)對(duì)FPN模型進(jìn)行參數(shù)推理，分別比較在不同的迭代次數(shù)下，改進(jìn)的螢火蟲算法CBOFA，DE算法和PSO算法求解精度，從驗(yàn)證三個(gè)算法優(yōu)化下FPN的泛化性能力，具體結(jié)果如下表2所示。

表2 算法推理結(jié)果比較

實(shí)驗(yàn)結(jié)果表明，實(shí)驗(yàn)初期T=50 代的情況下，CBOFA 便已經(jīng)將算法優(yōu)化較優(yōu)異的位置，而此時(shí)的DE 算法還距離理想的結(jié)果有所偏差，同時(shí)，我們根據(jù)PSO 的結(jié)果可看出，PSO 的也具有一定的優(yōu)勢(shì)，原因是FA 算法和PSO 算法有著相近的算法理念，均以群思想作為算法的基礎(chǔ)。在算法的中期T=100，DE 算法和PSO 由于其振蕩，其尋優(yōu)結(jié)果反而有所降低，而CBOFA卻有著不錯(cuò)的表現(xiàn)，這主要因?yàn)?，在改進(jìn)的FA算法，其步長(zhǎng)策略是一個(gè)類似高斯分布的函數(shù)，其在迭代中期，其步長(zhǎng)已經(jīng)進(jìn)入一個(gè)較小的數(shù)值范圍，不會(huì)有大幅度而擾動(dòng)而影響算法的精度。同時(shí)隨著迭代次數(shù)的增加，根據(jù)T=200 數(shù)據(jù)，在算法的后期，三個(gè)算法推理結(jié)果均達(dá)到一個(gè)較為有效的值，但明顯的可看出，改進(jìn)的FA 算法有著極優(yōu)的性能，這與CBOFA算法的特性有著很大的關(guān)系，這也表明改進(jìn)后的螢火蟲算法適用于FPN 的自學(xué)習(xí)能力的擴(kuò)展并具有一定的優(yōu)勢(shì)，特別在參數(shù)維度過(guò)大的情況下，改進(jìn)后的算法有著更高的適用性。

6 總結(jié)

群智能優(yōu)化算法在參數(shù)優(yōu)化算法的研究有很多，而與FPN 的結(jié)合尚且在起步階段，各類算法在優(yōu)化FPN 的問(wèn)題上都存在著許些不足，F(xiàn)A 算法作為一種新起的算法，其算法理念簡(jiǎn)單，算法實(shí)現(xiàn)的代碼量低，與優(yōu)化結(jié)果于自身的初始輸入?yún)?shù)關(guān)系不大的特性一經(jīng)提出，變得到許多學(xué)者的關(guān)注，其應(yīng)用領(lǐng)域包括[22]故障定位、特征選擇[23]、路徑規(guī)劃[24]等方面，而將FA與FPN的參數(shù)優(yōu)化目前在國(guó)內(nèi)外還少有案例。

本文在基本FA 的基礎(chǔ)上，通過(guò)改進(jìn)的K?means聚類、Levy飛行策略、改進(jìn)的振蕩策略、自適應(yīng)步長(zhǎng)、自適應(yīng)光強(qiáng)的引入，通過(guò)具體的FPN 模型，選擇合適的推理函數(shù)，對(duì)FPN 的三類參數(shù)：閾值、權(quán)值、確信度利用三個(gè)優(yōu)化算法進(jìn)行自適應(yīng)學(xué)習(xí)仿真實(shí)驗(yàn)，仿真結(jié)果顯示，改進(jìn)FA 算法CBOFA 在參數(shù)有化上優(yōu)于其它兩種優(yōu)化算法DE 和PSO，特別是在算法精度上面，CBOFA相比較其它兩種算法有著更加穩(wěn)定的輸出。