一種解決非光滑非凸優(yōu)化問題的暫態(tài)混沌神經(jīng)網(wǎng)絡

喻 昕，汪炎林，徐柳明，伍靈貞

(廣西大學 計算機與電子信息學院，南寧 530004)

1 前 言

在科學與工程應用中，優(yōu)化問題作為一類重點問題在最近幾十年內得到了廣泛的關注與發(fā)展.在1986年，由Hopfield 和 Tank[1]提出一種Hopfield神經(jīng)網(wǎng)絡(Hopfield Neural Network,HNN)作為解決優(yōu)化問題的并行計算模型，引起了大家的興趣并開始廣泛應用.Zhang等人[2]利用Lagarange乘子法創(chuàng)建了一個新的遞歸神經(jīng)網(wǎng)絡來處理凸光滑非線性優(yōu)化問題，Xia等人[3]提出了基于投影方法的遞歸神經(jīng)網(wǎng)絡用以解決光滑凸(偽凸)優(yōu)化問題.

不久后，應用范圍從光滑問題發(fā)展到非光滑優(yōu)化問題，如Li等人[4]在基于Clark次梯度的遞歸神經(jīng)網(wǎng)絡模型之中引入投影方法以解決n上閉凸子集的非凸非光滑優(yōu)化問題.Liu等人[5]嘗試投影方法建立遞歸神經(jīng)網(wǎng)絡模型解構線性等式和n上閉凸子集共同約束的非光滑非凸優(yōu)化問題.Bian等人[6]也開始利用光滑遞歸神經(jīng)網(wǎng)絡來解決非光滑非凸的優(yōu)化問題，使用光滑逼近技術即用一個與目標函數(shù)逼近的光滑函數(shù)構造光滑神經(jīng)網(wǎng)絡模型.Yu等人[7]基于微分包含的思想，建立了一個不依賴罰參數(shù)的神經(jīng)網(wǎng)絡模型用以解決非光滑非凸優(yōu)化問題.

然而上述的模型的本質仍是基于“梯度”或“次梯度”下降的動力系統(tǒng)，無法避免“陷入”局部最優(yōu)解.尤其是當優(yōu)化的目標函數(shù)是非凸時會存在多處局部最優(yōu)解，這將無法保證獲得全局最優(yōu)解.

為了解決這個問題，Aihara等人[8]受生物神經(jīng)元混沌特性的啟發(fā)，于1990年在HNN中增加一個自反饋項以引入混沌機制開創(chuàng)了混沌神經(jīng)網(wǎng)絡(Chaotic Neural Network,CNN).此后，Chen和Aihara[9]將模擬退火優(yōu)化算法引入到CNN中提出了暫態(tài)混沌神經(jīng)網(wǎng)絡(Transiently Chaotic Neural Network,TCNN).TCNN的動力系統(tǒng)對自反饋鏈接權值敏感，它可以類比模擬退火算法中一直衰減的溫度.當“溫度”較大時，整個系統(tǒng)處于“粗搜索”階段,搜索過程符合混沌動態(tài)的特性，會按照混沌軌道進行遍歷，并且不受目標函數(shù)的限制，能克服陷入局部最優(yōu)解；當“溫度”開始減少并達到一定程度時，系統(tǒng)進入“細搜索”階段，這時的自反饋權值對系統(tǒng)的影響變得很小，這時的神經(jīng)網(wǎng)絡類似于HNN，以粗搜索得到的解為初始點，根據(jù)HNN梯度下降機制在小范圍進行搜索，并收斂到一個平衡點，最終TCNN會收斂到一個全局最優(yōu)解.

TCNN提出后，不少學者對此展開研究.文獻[10，11]分別將TCNN應用于解決組播路由和蜂窩信道分配等組合優(yōu)化問題；Zhang等人[12]利用小波函數(shù)作為激活函數(shù)的TCNN來解決函數(shù)優(yōu)化問題；Babak等人[13]利用TCNN改進了反應曲面法在函數(shù)優(yōu)化問題中應用的性能.

借助腦電波的生物機制，分析不同頻率的正弦信號疊加形成的腦電波模型,Hu等人[14]用變頻正弦(Frequency Conversion Sinusoidal,FCS)函數(shù)與 Sigmoid 函數(shù)加權和作為混沌神經(jīng)元的激勵函數(shù),建立了一個新的神經(jīng)網(wǎng)絡模型 —變頻正弦混沌神經(jīng)網(wǎng)絡(Frequency Conversion Sinusoidal Chaotic Neural Network,FCSCNN)模型，并在文獻[15，16]進一步分析和優(yōu)化了這種新的模型.

綜上，為了解決非凸非光滑優(yōu)化問題，本文提出一個能收斂到優(yōu)化問題關鍵點集的遞歸神經(jīng)網(wǎng)絡，并在此基礎上構建了一個暫態(tài)混沌神經(jīng)網(wǎng)絡，用于實現(xiàn)非凸優(yōu)化問題的全局尋優(yōu).

2 預備知識

考慮如下問題:

minf(x)s.t.g(x)≤0Ax=b

(1)

當x=(x1,x2,…,xn)T∈n，f:n→，目標函數(shù)是正則的，但可以是非凸的和非光滑的，g(x)=(g1(x),g2(x),…,gp(x))T:n→p是p-維向量值函數(shù)，gj(x)(j=1,2,…,p)是凸的，但可能是非光滑的，A∈m×n是滿行秩矩陣，而且b=(b1,b2,…,bm)T∈m.我們假設優(yōu)化問題(1)具有至少一個局部最小解.

定義：

S1={x:g(x)≤0}

S2={x:Ax=b}

則S=S1∩S2，S={x∈n:g(x)≤0,Ax=b}是優(yōu)化問題(1)的可行域.

為便于后續(xù)的證明，首先給出下面兩個假設：

這里:

J+(x)={j∈{1,2,…,p}:gj(x)>0}J0(x)={j∈{1,2,…,p}:gj(x)=0}

定義1.若對于集合E?Rn上的任意點x，都存在一個非空集合F(x)?Rn，則x→F(x)是E→Rn上的集值映射.若對于任意的開集V?F(x0)，都有一個相應的鄰域U，使得F(U)?V，則稱集值映射F:E→Rn在點x0∈E是上半連續(xù).

定義2.如果存在正整數(shù)k，ε，對任意的x1,x2∈x+εB(0,1)，|f(x1)-f(x2)|≤k(x1-x2)成立，則稱函數(shù)f:Rn→R在x∈Rn附近是Lipschitz的，如果f在其定義域每一個點的附近都是Lipschitz的，則稱f為局部Lipschitz的.

定義3.如果f:Rn→R在Rn上是局部Lipschitz的，則f在點x沿方向v∈Rn的廣義方向導數(shù)為：

如果f0(x;v)是有定義且有限的，f在x處的次微分可以定義為：

?f(x)={ξ∈Rn:f0(x;v)≥,?v∈Rn}

引理1(鏈式法則).

本文提出的神經(jīng)網(wǎng)絡動力學模型:

(2)

這里α是一個正比例罰參數(shù)，I是一個單位矩陣，P=AT(AAT)-1A.

函數(shù)β(t)是一個單調非減的函數(shù)，其形式如下：

tS2為進入可行域S2的時間上限.

3 收斂性分析

1)有限時間收斂到S2

定理1.若假設1,2成立，則從任意點x0∈Rn出發(fā)，神經(jīng)網(wǎng)絡(2)的狀態(tài)向量將在有限時間收斂進S2，其后不再離開.

證明：令K(x)=‖Ax(t)-b‖1，則K(x)是正則函數(shù)且?K(x)=ATh(Ax(t)-b).根據(jù)鏈式法則，存在ψ(t)∈h(Ax(t)-b)，θ(t)∈?f(x)，σ(t)∈?D(x)，使得:

由于A(I-P)=A-AAT(AAT)-1A=0,AAT是正定矩陣，則：

這里λm是矩陣AAT的最小特征值.由于A是行滿秩矩，所以λm(AAT)>0.對于任意x(t)?S2，根據(jù)函數(shù)h(x)的定義可知‖ψ(t)‖2≥1，因此:

(3)

若存在tS2

K(x(tS2))-K(x0)≤-λm(AAT)tS2

2)狀態(tài)變量x(t)有界

證明：第1步：當t∈[0,tS2]，β(t)=0神經(jīng)網(wǎng)絡(2)可以寫成:

(4)

根據(jù)鏈式法則，存在ψ(t)∈h(Ax(t)-b)，使得：

第2步：當t>tS2，由定理1可知，x(t)將在有限時間內收斂到S2，其后不再離開，且進入的時間上限為tS2.所以對t>tS2，有β(t)=1，x(t)∈S2，Ax(t)=b，神經(jīng)網(wǎng)絡(2)可以寫成:

(5)

根據(jù)鏈式法則，存在θ(t)∈?f(x)，σ(t)∈?D(x)，使得:

當x(t)∈S2S1，因為‖(I-P)θ(t)‖≤‖θ(t)‖，結合引理2，有:

此外，因為神經(jīng)網(wǎng)絡(2)的右邊部分是上半連續(xù)，且為非空緊凸值。因此在t∈[0,T)，對于初始條件x(0)=x0，神經(jīng)網(wǎng)絡(2)至少存在一個局部解x(t).

結合定理2和解的可擴展理論，局部解可以從t∈[0,T)擴展到t∈[0,+)，即神經(jīng)網(wǎng)絡(2)存在全局解.

3)有限時間收斂到S

因(I-P)2=I-P，(I-P)T=I-P，根據(jù)鏈式法則,存在θ(t)∈?f(x)，σ(t)∈?D(x)，使得:

將上式兩邊從tS2到t進行積分，得到:

D(x(t))≤D(x(tS2))-ε0(t-tS2)

(6)

當t≥D(x(tS2))/ε0+tS2時，D(x(t))≤0.

而D(x(t))≥0且有上界，結合{x:D(x(t))≤0}=S1，說明x(t)會在一定時間內進入S1，即進入可行域S.類似定理1，可證明神經(jīng)網(wǎng)絡的狀態(tài)變量x(t)在進入S后，不再離開.綜上，定理3證畢.

4)神經(jīng)網(wǎng)絡的精確性

定義4.優(yōu)化問題的關鍵點集合C為C={x∈S:0∈?f(x)+NS(x)}，其中NS(x)是x在可行域S上的法錐.

證明：由定理3可知，x(t)會進入S，并停留其中，不妨令x0∈S，則x(t)∈S，Ax(t)=b，β(t)=1，?D(x(t))=0.

(7)

其中θtn∈?f(xtn)，σtn∈?D(xtn).

因為?f(x)，?D(x)是上半連續(xù)的集值映射，可知:

那么，可以得出:

(8)

(9)

綜上，神經(jīng)網(wǎng)絡(2)的任一聚點都是優(yōu)化問題(1)的關鍵點，定理4得證.

5)收斂到C

證明：在定理4證明過程中得到，對于x0∈S，S有界，則f(x(t))有界.

假定:

對任意x(t)∈W，有0?κ(x(t)).因為κ(x(t))是緊凸集，則在W上存在最大值于最小值，分別表示為：

對任意時間間隔t∈[tn,tn+τ]，x(t)∈W，有0≤τ≤k/(4MW)，結合式(7)，有:

4 暫態(tài)混沌神經(jīng)網(wǎng)絡

若假設1,2成立，在神經(jīng)網(wǎng)絡(2)的基礎上，引入文獻[14]的FCSCNN模型，提出一種解決非光滑非凸優(yōu)化問題的暫態(tài)混沌神經(jīng)網(wǎng)絡.

(10)

yi(t+1)=kyi(t)+λ(t){-(I-P)[?f(x)+α‖?f(x)‖?D(x)]-ATh(Ax-b)}-zi(t)(xi(t)-I0)

(11)

zi(t+1)=(1-β1)zi(t)

(12)

(13)

(14)

S2(yi(t),ε2)=A(0)·exp(-u1|yi(t)|)· sin(yi(t)/(ε2·exp(-u2|yi(t)|)))

(15)

其中：

yi(t)為神經(jīng)元內部狀態(tài)；

xi(t)為神經(jīng)元輸出；

zi(t)神經(jīng)元自反饋連接權值；

ω是輸出比例系數(shù)，控制著函數(shù)的輸出范圍；

ε1為 Sigmoid 函數(shù)的陡度參數(shù)，ε2為FCS函數(shù)的陡度參數(shù)；

k為神經(jīng)隔膜的阻尼因子；

λ(t)為正值縮放因子；

I0為正值參數(shù)；

β1為z(t)的退火衰減因子,β2為λ(t)的退火衰減因子.

相對于神經(jīng)網(wǎng)絡(2)，暫態(tài)混沌神經(jīng)網(wǎng)絡可以看成在神經(jīng)網(wǎng)絡(2)的單層神經(jīng)網(wǎng)絡基礎上擴展成多層神經(jīng)網(wǎng)絡，所以對應的輸入輸出函數(shù)會有相應的調整.

式(11)表示神經(jīng)元內部狀態(tài)，同時也是神經(jīng)網(wǎng)絡的輸入層,其中大括號內的部分為遞歸神經(jīng)網(wǎng)絡，參數(shù)定義與神經(jīng)網(wǎng)絡(2)相同。由于暫態(tài)混沌神經(jīng)網(wǎng)絡的特性，初始點的選取范圍是n，即從神經(jīng)網(wǎng)絡(2)的擴展到無限制，這對神經(jīng)網(wǎng)絡的性能來說是一個提升.

式(12)是神經(jīng)元自反饋連接權值，控制著神經(jīng)網(wǎng)絡的混沌狀態(tài)的發(fā)生與結束.

式(13)是神經(jīng)網(wǎng)絡(2)的系數(shù)，控制著遞歸神經(jīng)網(wǎng)絡對混沌的影響.λ(t)一般需要一個較大的初始值保證足夠的影響.由于考慮的優(yōu)化問題是非凸的，為了防止輸出變量的波動，所以需要讓系數(shù)逐步縮小以保證能最終收斂到最優(yōu)點，所以用β2為退火衰減因子來控制λ(t)的縮小.

式(15)表示FCS函數(shù)，表示的是不同頻率正弦信號疊加的腦電波模型.將Sigmoid函數(shù)(式(14))與FCS函數(shù)的加權和作為混沌神經(jīng)元的激勵函數(shù)(式(10))，作用是非單調化激勵函數(shù)，得到更豐富的混沌特性，并且讓激勵函數(shù)更加接近真實生物神經(jīng)元的激活抑制模型同時還能滿足腦神經(jīng)不同活躍狀態(tài)的特點.yi(t)為函數(shù)自變量,表示腦電波活動的強弱;A(0)為正弦函數(shù)的幅值;ε2為正弦函數(shù)的陡度參數(shù),控制著正弦函數(shù)頻率;u1,u2均為正值參數(shù)；ε1為Sigmoid函數(shù)的陡度參數(shù)，c為FCS函數(shù)的比例系數(shù)(c≥0).令ε1=10，A(0)=0.8，ε2=0.02，u1=6，u2=1，c=0.5，S1(t)與x(t)的函數(shù)圖像如圖1所示.

圖1 Sigmoid和Sigmoid+0.5FCS激勵函數(shù)曲線對比Fig.1 Comparison of excitation function curves between sigmoid and sigmoid + 0.5FCS

圖1(a)為Sigmoid函數(shù)，圖1(b)為Sigmoid+0.5FCS函數(shù)，通過圖1的對比能看出，相對于最常見的激勵函數(shù)Sigmoid函數(shù)，加入FCS函數(shù)后的激勵函數(shù)不僅有著很強的非單調性，還表現(xiàn)出了Sigmoid函數(shù)的生物學特性，這意味著新的暫態(tài)混沌神經(jīng)網(wǎng)絡的神經(jīng)元動力特性更好，混沌的程度更高，這決定了新的神經(jīng)網(wǎng)絡模型具備更好的全局尋優(yōu)能力.

新的暫態(tài)混沌神經(jīng)網(wǎng)絡與HNN的優(yōu)化機制類似，將優(yōu)化問題的目標函數(shù)當做能量函數(shù)，之后的神經(jīng)網(wǎng)絡的動力學演化過程便是能量函數(shù)的全局尋優(yōu)過程，當神經(jīng)網(wǎng)絡最終能收斂到一個穩(wěn)定點時，與之相對神經(jīng)元的輸出結果就是優(yōu)化問題的(最優(yōu)/次優(yōu))解.

表1 與現(xiàn)有神經(jīng)網(wǎng)絡性能對比Table 1 Performance comparison with existing neural networks

通過表1可以看出，本文不需如文獻[5]一樣初始點受限，雖然本文可行域有界，但是本文有著其他參考文獻不具有的全局尋優(yōu)能力，且可行域有界是全局尋優(yōu)能力的保障.

接下來將通過仿真實驗來驗證本文提出的暫態(tài)混沌神經(jīng)網(wǎng)絡的全局尋優(yōu)能力.

5 仿真實驗

為了驗證本文提出的神經(jīng)網(wǎng)絡的性能，在Matlab2012a平臺上，用仿真實驗來驗證神經(jīng)網(wǎng)絡(2)和本文提出的暫態(tài)混沌神經(jīng)網(wǎng)絡的表現(xiàn).

例1.

minf(x)=-0.25x12+1.2x22+0.1x1x2+2x1-2x2s.t.g1(x)=-x1+x2-2≤0g2(x)=x1-2x2-2≤0g3(x)=-x1x2≤0x1+2x2=3

(16)

在例1中，f(x)和g3(x)非凸，但把x1=-2x2+3帶入后，f(x)和g3(x)在可行域上為凸函數(shù)，且可行域有界，那么優(yōu)化問題(16)有唯一全局最優(yōu)點x*=(0,1.5)T且能用神經(jīng)網(wǎng)絡(2)解決.

圖2 神經(jīng)網(wǎng)絡(2)在優(yōu)化問題(16)的運行軌跡圖Fig.2 Transient behaviors of neural network(2)in optimization problem(16)

例2.

(17)

容易看出優(yōu)化問題(17)中，可行域有界，且在可行域上，f(x)非凸，并有著多個關鍵點.

令步長l=0.001，α=3，選取2個不同的初始點(-3,5)T，(-3,-1)T，神經(jīng)網(wǎng)絡(2)最終分別收斂到(-2.9839,2.9859)T，(0.001,0.001)T，收斂軌跡如圖3、圖4所示.

圖3 神經(jīng)網(wǎng)絡(2)在初始點為(-3,5)T的軌跡圖Fig.3 Transient behaviors of neural network (2) with initial point (-3,5)T

從圖3、圖4可以看出，神經(jīng)網(wǎng)絡(2)在非凸優(yōu)化問題上有著一定的收斂能力，但是缺乏全局尋優(yōu)能力.同樣的問題在文獻[5-7]的模型上也存在，選初始點(-3,5)T，文獻[7]的模型的軌跡圖如圖5，能看出這個模型也沒有全局尋優(yōu)能力.那么，在優(yōu)化問題(17)上對本文提出的暫態(tài)混沌神經(jīng)網(wǎng)絡進行測試.

對例2，在本文提出的暫態(tài)混沌神經(jīng)網(wǎng)絡中選取參數(shù)如下：

圖4 神經(jīng)網(wǎng)絡(2)在初始點為(-3,-1)T的軌跡圖Fig.4 Transient behaviors of neural network (2) with initial point (-3,-1)T

圖5 文獻[7]的模型在初始點為(-3,5)T的軌跡圖Fig.5 Trajectories of the model in [7] at the initial point (-3,5)T

選神經(jīng)網(wǎng)絡(2)未能收斂到最優(yōu)點的初始點(-3,5)T，令z1(1)=z2(1)=3,λ(0)=0.5.運行結果見圖6，最終收斂到點(2.372×10-4,2.372×10-4)T，可以看成收斂到全局最優(yōu)點.

圖6 Fig.6

通過圖6(a)，圖6(b)可以看出，神經(jīng)網(wǎng)絡的輸出值x1,x2在前期的“粗搜索”過程中體現(xiàn)了明顯的混沌搜索的遍歷性，偽隨機性的特點，在160步時已收斂到最優(yōu)解附近，而圖6(c)則展示了神經(jīng)網(wǎng)絡的能量函數(shù)f(x)在經(jīng)過前期的混沌搜索后，約在同時收斂到最低點附近，并且馬上穩(wěn)點在最低點.這種準確，快速的尋優(yōu)效果很好的證明了本文提出的暫態(tài)混沌神經(jīng)網(wǎng)絡在函數(shù)優(yōu)化方面的全局尋優(yōu)能力.

圖7 Fig.7

6 總 結

本文提出了一種新型的遞歸神經(jīng)網(wǎng)絡方法，用來解決帶有不等式約束以及等式約束的非光滑非凸優(yōu)化問題.對神經(jīng)網(wǎng)絡的準確性與收斂性進行了嚴謹?shù)睦碚摲治?，并通過仿真實驗驗證了神經(jīng)網(wǎng)絡的性能.為實現(xiàn)神經(jīng)網(wǎng)絡的全局尋優(yōu)，在遞歸神經(jīng)網(wǎng)絡的基礎上構建了一個新的暫態(tài)混沌神經(jīng)網(wǎng)絡，并放開了遞歸神經(jīng)網(wǎng)絡對初始點的限制.通過仿真實驗，驗證了當可行域有界時，暫態(tài)混沌神經(jīng)網(wǎng)絡具有一定的全局尋優(yōu)能力.