王曉霞

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

0 引 言

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

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

1.1 降維變換及其性質

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

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

(1)

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

d(x,y)=

(2)

圖1 α-致密曲線的具體構造算法

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個子區(qū)間。

a=t0

(5)

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

(6)

limm→S'=Mn-1c

(7)

1.2 算 法

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

(8)

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

(9)

式(9)中λ～N(0,1)，Δθ～N(0,σ2)。基于降維的箱約束優(yōu)化近似算法的具體步驟如圖2所示。

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

2 實驗與分析

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

圖3中橫縱坐標分別為算法的迭代次數(shù)、每代的精英函數(shù)值?？芍恳淮€體的目標函數(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，可得最小值點θ*的值為0.79207，全局最小值f*(θ)的值為0.00413419。算例4中參數(shù)N取600，T取1000，Pc取0.9，Pm取0.35，可得最小值點θ*為1.53741，全局最小值f*(θ)為-0.59131344。

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

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

算例5：

算例6：

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

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

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

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

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

表1 函數(shù)的數(shù)值實驗結果

3 結 論

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