帶箱約束的非線性全局優(yōu)化問題降維算法研究①

王曉霞

(齊齊哈爾大學(xué)理學(xué)院,黑龍江 齊齊哈爾 161000 )

0 引 言

隨著社會(huì)科技、經(jīng)濟(jì)的迅速發(fā)展，全局最優(yōu)化問題經(jīng)常出現(xiàn)在經(jīng)濟(jì)模型、金融、圖像處理、環(huán)境工程學(xué)等方面[1]。全局優(yōu)化是優(yōu)化領(lǐng)域的重要內(nèi)容，全局優(yōu)化發(fā)展是指通過對(duì)最優(yōu)點(diǎn)的研究，找出最優(yōu)點(diǎn)特性、最優(yōu)點(diǎn)尋找途徑，并以此為目的組織算法，研究該算法的性質(zhì)和實(shí)際效果提取[2-3]。傳統(tǒng)的非線性規(guī)劃易陷于局部最優(yōu)解，很難得出全局最優(yōu)化的解，降維是處理維數(shù)較高空間問題的有力措施[4-5]。其中三角函數(shù)降維能夠有效地降低目標(biāo)函數(shù)維度，在其將n維空間函數(shù)轉(zhuǎn)換為一維空間函數(shù)后，得到的一維函數(shù)具備較強(qiáng)波動(dòng)性，通過遺傳算法對(duì)一維問題進(jìn)行求解[6]。求出來的一維問題的解即為多維空間問題的全局最優(yōu)解的近似解。本次研究在進(jìn)行帶箱約束的非線性全局優(yōu)化問題降維算法研究時(shí)，應(yīng)從約束函數(shù)角度出發(fā)，給定與約束函數(shù)緊密聯(lián)系的降維形式，找出約束下降維參數(shù)與致密度的聯(lián)系，以降維曲線長度估計(jì)計(jì)算量，最終提出理論算法。

1 以降維方法求解帶箱約束的非線性全局優(yōu)化問題

1.1 降維變換及其性質(zhì)

最優(yōu)化問題的一般表達(dá)式為minf(x)，s.t.cj(x)=0，j∈E，cj(x)≤0，j∈I其中x∈Rn為決策變量，f(x):Rn→R、cj(x):Rn→R分別為目標(biāo)函數(shù)、約束函數(shù)，集合X={x|cj(x)=0,j∈E;cj(x)≤0,j∈I;x∈Rn)}是相應(yīng)最優(yōu)化問題的可行域。指標(biāo)集由E={1,2,...,L}、I={p+1,p+2,...,m}進(jìn)行表示，點(diǎn)x處的緊約束以I(x)={j,cj(x)=0,j∈I∪E}進(jìn)行表示。研究通過基于降維的全局優(yōu)化近似算法，對(duì)帶箱約束的非線性全局問題進(jìn)行優(yōu)化求解。并且在區(qū)間[0,π]范圍中構(gòu)建降維公式，給出降維曲線的α-致密度后，根據(jù)降維曲線長度驗(yàn)證該近似算法[7]。

x1=rcos(θ),x2=rsin(θ)

(1)

利用阿基米德曲線以θ相關(guān)函數(shù)對(duì)r進(jìn)行表示，可得r=αθ，α>0，θ>0。式(1)轉(zhuǎn)化為x1=αθcos(θ)，x2=αθsin(θ)。研究將利用此三角函數(shù)類型作為降維曲線。本質(zhì)上來講，降維指通過空間填充曲線得到近似可行域，從而簡化目標(biāo)函數(shù)的變量數(shù)目，達(dá)到將多變量簡化為單變量的目的。降維假設(shè)空間Rn中，至少存在一點(diǎn)y∈X?Rn可以令d(x,y)≤α，即稱集合X在空間Rn中α-致密。

d(x,y)=

(2)

圖1 α-致密曲線的具體構(gòu)造算法

h:D→X,θh(θ)=(h1(θ),h2(θ),...,hn(θ))

(3)

H:[a,b]→RntH(t)=

(h1(t),h2(t),...,hn(t))

(4)

式(4)中H表示定義在區(qū)間[a,b]上的參數(shù)曲線，將[a,b]分成n個(gè)子區(qū)間。

a=t0

(5)

使Ht0,t1,...,tn成為一條過點(diǎn)Pi=H(ti)=(h1(ti),h2(ti),...,hn(ti))的折線，長度為Ln=L(Ht0,t1,...,tn)，則可知曲線H的長度L(H)存在時(shí)，其應(yīng)為Ln=L(Ht0,t1,...,tn)的上確界。當(dāng)H:[a,b]→Rn、H∈C1([a,b],Rn)時(shí)，曲線H的長度存在。

(6)

limm→S'=Mn-1c

(7)

1.2 算 法

γ∈U(-1,1),γ≠0

(8)

適應(yīng)度函數(shù)可取函數(shù)本身，即fit(θ)=f*(θ)，令父代為θ1,θ2，式(8)則為交叉子代的表達(dá)式。通過變異概率Pm判斷個(gè)體變異的需求，選擇一個(gè)個(gè)體，產(chǎn)生(0,1)間的隨機(jī)數(shù)，當(dāng)變異概率不小于隨機(jī)數(shù)時(shí)，變異子代的表達(dá)式為：

(9)

式(9)中λ～N(0,1)，Δθ～N(0,σ2)?；诮稻S的箱約束優(yōu)化近似算法的具體步驟如圖2所示。

圖2 基于降維的箱約束優(yōu)化近似算法

2 實(shí)驗(yàn)與分析

研究將采用數(shù)學(xué)軟件MATLAB R2017b對(duì)基于降維的箱約束優(yōu)化近似算法進(jìn)行數(shù)值模擬，并將之取得的結(jié)果與原函數(shù)本身的精確最優(yōu)解作出比較。選擇六個(gè)算例，執(zhí)行基于降維的箱約束優(yōu)化近似算法，在將之降維成一維函數(shù)后，執(zhí)行遺傳算法。

圖3中橫縱坐標(biāo)分別為算法的迭代次數(shù)、每代的精英函數(shù)值?？芍恳淮€(gè)體的目標(biāo)函數(shù)值均隨著迭代次數(shù)的增加而減少，算例1最終收斂至0，算例2最終收斂至-0.2。

圖3 算例1、2精英函數(shù)值隨著迭代次數(shù)的變化情況

算例3：

10.1[(x2-1)2+(x4-1)2]+

19.8(x2-1)(x4-1)，s.t.-

2≤xi≤2,i=1,2,3,4

算例4：

minG(x1,x2,...,x6)=

算例3中參數(shù)N取400，T取1000，Pc取0.9，Pm取0.2，可得最小值點(diǎn)θ*的值為0.79207，全局最小值f*(θ)的值為0.00413419。算例4中參數(shù)N取600，T取1000，Pc取0.9，Pm取0.35，可得最小值點(diǎn)θ*為1.53741，全局最小值f*(θ)為-0.59131344。

圖4中橫縱坐標(biāo)分別為算法的迭代次數(shù)、每代的精英函數(shù)值?？芍恳淮€(gè)體的目標(biāo)函數(shù)值均隨著迭代次數(shù)的增加而減少，算例3最終收斂至0，算例4最終收斂至-0.6。

圖4 算例3、4精英函數(shù)值隨著迭代次數(shù)的變化情況

算例5：

算例6：

s.t.-1≤xi≤1,i=1,2,...,40。

對(duì)二者執(zhí)行基于降維的箱約束優(yōu)化近似算法，在將之降維成一維函數(shù)后，執(zhí)行遺傳算法。算例5、算例6中參數(shù)一致，N取600，T取1000，Pc取0.9，Pm取0.1?？傻盟憷?的最小值點(diǎn)θ*為0.99446，全局最小值f*(θ)為-0.98856804，算例6的最小值點(diǎn)θ*為0.94743，全局最小值f*(θ)為-0.96549770

圖5中橫縱坐標(biāo)分別為算法的迭代次數(shù)、每代的精英函數(shù)值。可知每一代精英個(gè)體的目標(biāo)函數(shù)值均隨著迭代次數(shù)的增加而減少，算例5、算例6最終均收斂至-1。

圖5 算例5、6精英函數(shù)值隨著迭代次數(shù)的變化情況

表1中θ*表示f*(θ)最優(yōu)點(diǎn)，min指f*(θ)最優(yōu)值，Global min表示標(biāo)準(zhǔn)算例最優(yōu)值。由表1可知，研究采用的基于降維的箱約束優(yōu)化近似解法具備有效性；同時(shí)在數(shù)值效果方面，低維的函數(shù)擁有更高的精度。

表1 函數(shù)的數(shù)值實(shí)驗(yàn)結(jié)果

3 結(jié) 論

研究通過三角函數(shù)對(duì)帶箱約束的非線性全局優(yōu)化問題進(jìn)行降維變換，將多維函數(shù)轉(zhuǎn)換為一維函數(shù)，隨后利用遺傳算法對(duì)一維函數(shù)進(jìn)行處理。研究結(jié)果表明，隨著迭代次數(shù)的逐漸增加，每一代精英個(gè)體的目標(biāo)函數(shù)值逐漸減小；六個(gè)帶箱約束的非線性全局優(yōu)化問題的算例中，原函數(shù)本身的精確最優(yōu)解與基于降維的箱約束優(yōu)化近似解法相比，二者解出來的值基本一致。也就是說，以一維問題的最優(yōu)解得出原n維箱式約束問題最優(yōu)解的近似。綜上所述，實(shí)驗(yàn)采取的基于降維的箱約束優(yōu)化近似解法是科學(xué)有效的，其能在保證精確率的前提下，成功降低問題難度；同時(shí)，在數(shù)值效果方面，低維的函數(shù)擁有更高的精度。研究雖然取得了一定成就，但在多目標(biāo)多維全局優(yōu)化問題上仍有進(jìn)一步探討的必要，希望隨著了解更多的α-致密曲線，未來能夠推廣三角函數(shù)降維曲線的應(yīng)用范圍。