非線性極小極大問題的分?jǐn)?shù)階粒子群算法

李昌興, 徐 邁, 惠莉萍

(1.西安郵電大學(xué) 理學(xué)院， 陜西 西安 710121; 2.西安科技大學(xué) 理學(xué)院， 陜西 西安 710054)

非線性極小極大問題(nonlinear minimax problem, NMP)是一類典型的非可微優(yōu)化問題，在工程優(yōu)化設(shè)計(jì)、電子線路優(yōu)化設(shè)計(jì)、計(jì)算機(jī)輔助幾何設(shè)計(jì)、最優(yōu)控制及對(duì)策論中有著廣泛應(yīng)用。工程實(shí)際中很多問題，如非線性L1、L∞擬合問題和非線性方程組求解，都可以轉(zhuǎn)化成極小極大問題的數(shù)學(xué)模型。

將信息論中的熵概念引入函數(shù)優(yōu)化領(lǐng)域，由此得出的極大熵函數(shù)轉(zhuǎn)化方法[1]可將非光滑問題轉(zhuǎn)化為光滑優(yōu)化問題，利用經(jīng)典優(yōu)化方法，如信賴域法、擬牛頓法、共軛梯度法、SQP方法等[2-6]，求解光滑優(yōu)化問題，即可得到非光滑問題的近似最優(yōu)解。然而，這些傳統(tǒng)優(yōu)化方法的計(jì)算效率受初始點(diǎn)的選取影響比較大，且大多算法都要使用目標(biāo)函數(shù)的梯度信息，這就給問題的求解帶來了困難。

智能優(yōu)化算法不需要使用函數(shù)的梯度信息和初始點(diǎn)，計(jì)算效率較高。其中，粒子群算法(particle swarm optimization，PSO)[7]的原理較為簡(jiǎn)單且程序容易實(shí)現(xiàn)，目前已被廣泛應(yīng)用于數(shù)值優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、數(shù)據(jù)挖掘和系統(tǒng)控制等領(lǐng)域。

對(duì)于非線性極小極大問題，可結(jié)合改進(jìn)的粒子群算法與極大熵函數(shù)求解[8]，也可結(jié)合差分進(jìn)化算法與極大熵函數(shù)法求解[9]，或者結(jié)合粒子群-鄰近點(diǎn)混合算法和極大熵函數(shù)法求解[10]。但是，粒子群算法是一種依概率收斂的隨機(jī)優(yōu)化算法，對(duì)多峰多谷的復(fù)雜優(yōu)化問題，易陷入局部最優(yōu)?；诜?jǐn)?shù)階速度的粒子群算法(PSO with fractional-order velocity，F(xiàn)OPSO)使用分?jǐn)?shù)階微分的定義，改進(jìn)了粒子群算法的速度更新公式[11]，相較于經(jīng)典粒子群算法，收斂速度更快。

本文將針對(duì)極小極大問題中，極大值函數(shù)不可微的特點(diǎn)，先用極大熵函數(shù)法將目標(biāo)函數(shù)轉(zhuǎn)化成可微函數(shù)，再利用分?jǐn)?shù)階粒子群算法求解可微的近似優(yōu)化問題。

1 極大熵函數(shù)法

考慮無約束優(yōu)化問題

利用極大熵函數(shù)法，可將無約束非線性極小極大問題轉(zhuǎn)化為光滑函數(shù)的無約束優(yōu)化問題。極大熵函數(shù)定義為[4]

(1)

其中，p≥1為控制參數(shù)，F(xiàn)p(x)即為函數(shù)f(x)在變量x∈n上的極大熵函數(shù)。

對(duì)于有限值p，F(xiàn)p(x)是可微的，且式(1)可以改寫為[4]

由此可得

函數(shù)Fp(x)的值隨著參數(shù)p的增加而單調(diào)減小，且當(dāng)p趨于無窮大時(shí)，F(xiàn)p(x)以f(x)為極限，即

在實(shí)際數(shù)值計(jì)算時(shí)，只要參數(shù)p取得足夠的大，就可以使用極大熵函數(shù)Fp(x)代替不可微目標(biāo)函數(shù)f(x)，從而可將原來的非線性極小極大問題的求解轉(zhuǎn)化為一個(gè)易于求解的可微函數(shù)的無約束優(yōu)化問題。

2 分?jǐn)?shù)階粒子群算法

分?jǐn)?shù)階微積分(fractional calculus，F(xiàn)C)是數(shù)學(xué)分析的一個(gè)分支，也是應(yīng)用科學(xué)中的數(shù)學(xué)工具之一。它是經(jīng)典微積分的自然延伸，其微分算子及積分算子的階數(shù)可擴(kuò)展到實(shí)數(shù)或復(fù)數(shù)范圍。換言之，分?jǐn)?shù)階微積分是傳統(tǒng)積分和微分的泛化，它將非整數(shù)值包含到導(dǎo)數(shù)或者積分的冪中。因可用于大量自然現(xiàn)象的精確描述，分?jǐn)?shù)階微積分已被成功應(yīng)用于諸多科學(xué)領(lǐng)域，如工程科學(xué)、計(jì)算數(shù)學(xué)和流體力學(xué)等。事實(shí)上，針對(duì)服務(wù)于建模、曲線擬合、濾波、模式識(shí)別和邊緣檢測(cè)等應(yīng)用的眾多算法，分?jǐn)?shù)階微積分為提高其穩(wěn)定性、可控性、可觀察性和魯棒性等性能，發(fā)揮著重要作用。

一元函數(shù)x(t)的Grünwald-Letnikov分?jǐn)?shù)階微分定義為

(2)

其中，α∈(0,1]，Γ(·)是伽瑪函數(shù)。

式(2)揭示：雖然整數(shù)階導(dǎo)數(shù)僅僅意味著有限序列，但分?jǐn)?shù)階導(dǎo)數(shù)需要無限多項(xiàng)；整數(shù)導(dǎo)數(shù)是“局部”運(yùn)算符，與此相反，分?jǐn)?shù)階導(dǎo)數(shù)毫無疑問地包含了過去所有事件的“記憶”。

式(2)的近似表達(dá)式為

(3)

其中，T是采樣周期，r是截?cái)啻涡颉?/p>

分?jǐn)?shù)階模型具備固有的記憶特性，非常適合描述諸如不可逆性和混沌現(xiàn)象。據(jù)此可知，分?jǐn)?shù)階微積分工具非常適合描述粒子軌跡的動(dòng)態(tài)現(xiàn)象。使用分?jǐn)?shù)微積分，可以控制粒子群優(yōu)化算法的收斂速度。

為了修改速度導(dǎo)數(shù)的階數(shù)，需要重新排列粒子群算法的原始速度方程

vt+1=vt+φ1(pbest-x)+φ2(gbest-x),

(4)

該表達(dá)式可以重新寫為

vt+1-vt=φ1(pbest-x)+φ2(gbest-x)。

(5)

式(5)左側(cè)的vt+1-vt是階數(shù)α=1(假設(shè)T=1)時(shí)微分的離散形式，故有

Dα[vt+1]=φ1(pbest-x)+φ2(gbest-x)。

(6)

如果考慮分?jǐn)?shù)微積分的特點(diǎn)，速度微分的階數(shù)可以推廣為實(shí)數(shù)α∈[0,1]，這樣可以獲得更平滑的變化和更長(zhǎng)的記憶效應(yīng)?？紤]表達(dá)式(3)給出的微分的第一個(gè)r=4項(xiàng)，表達(dá)式(6)可改寫為[11]

當(dāng)r≥4時(shí)，實(shí)驗(yàn)測(cè)試可得相似結(jié)果。

實(shí)驗(yàn)測(cè)試中，根據(jù)表達(dá)式

α的值從0.9到0.4線性變化。其中，t為當(dāng)前迭代次數(shù)，而最大迭代次數(shù)IM=5 000。

3 結(jié)合極大熵的分?jǐn)?shù)階粒子群算法

將極大熵函數(shù)法和分?jǐn)?shù)階粒子群算法相結(jié)合，給出一種解決非線性極小極大問題的新算法。

3.1 粒子群速度更新公式的改進(jìn)

選用速度更新公式[11]

(7)

位置更新公式不變，仍為

xt+1=xt+vt+1。

(8)

3.2 算法步驟

步驟1對(duì)每個(gè)粒子初始化，確定粒子群規(guī)模N、加速常數(shù)c1和c2、問題維數(shù)d、最大迭代次數(shù)IM、問題的位置和速度的上下限，并隨機(jī)產(chǎn)生N個(gè)初始位置和N個(gè)初始速度。

步驟2將極大熵函數(shù)代替原目標(biāo)函數(shù)作為適應(yīng)度值函數(shù)，計(jì)算每個(gè)粒子的適應(yīng)度值vf。

步驟3對(duì)每個(gè)粒子，若粒子的適應(yīng)度值vf優(yōu)于歷史的個(gè)體最優(yōu)位置Pi的適應(yīng)度值，則將當(dāng)前適應(yīng)度值設(shè)置為個(gè)體極值Ibest，當(dāng)前位置為個(gè)體最優(yōu)位置Pi。

步驟4對(duì)每個(gè)粒子，若粒子的適應(yīng)度值vf優(yōu)于歷史的全局最優(yōu)位置Pg的適應(yīng)度值，則將當(dāng)前適應(yīng)度值設(shè)置為全局極值Gbest，當(dāng)前位置為全局最優(yōu)位置Pg。

步驟5根據(jù)公式(7)，更新粒子的速度，并將其限制在Vmax內(nèi)。

步驟6根據(jù)公式(8)，更新粒子的位置，并將其限制在[Xmin,Xmax]內(nèi)。

步驟7如果達(dá)到終止條件，則輸出問題的解；否則更新迭代次數(shù)，并轉(zhuǎn)到步驟2。

3.3 重要說明

(1) 在轉(zhuǎn)化極大熵函數(shù)時(shí)，由于要求p的值足夠大，所以計(jì)算機(jī)在計(jì)算時(shí)易導(dǎo)致epfi(x)發(fā)生數(shù)據(jù)溢出，故在計(jì)算時(shí)采用與文獻(xiàn)[8]中相同的計(jì)算技巧來避免數(shù)值溢出。

(2) 對(duì)于較為復(fù)雜的非線性極小極大問題，將粒子群規(guī)模取大以達(dá)到避免早熟收斂的目的。

4 數(shù)值實(shí)驗(yàn)

取參考文獻(xiàn)[5-6，8，12-15]中的8個(gè)非線性極小極大問題做測(cè)試。

問題1(Charalambous-Conn 2問題)

參數(shù)n=2,m=3。

f2(x)=(2-x1)2+(2-x2)2,

f3(x)=2e(-x1+x2)。

問題2(Charalambous-Conn 1問題)

參數(shù)n=2,m=3。

f2(x)=(2-x1)2+(2-x2)2,

f3(x)=2e(-x1+x2)。

問題3參數(shù)n=2,m=3。

f2(x)=sinx1,f3(x)=cosx2。

問題4參數(shù)n=3,m=6。

f3(x)=x1+x2+x3-1,

f4(x)=x1+x2-x3+1,

問題5(Wong1問題) 參數(shù)n=7,m=5。

f1(x)=(x1-10)2+5(x2-12)2+

f3(x)=f1(x)+10(7x1+3x2+

問題6參數(shù)n=3,m=30。

fi(x)=-fi-15(x)(i=16,17,…,30)。

ui=i,vi=16-i,wi=min{ui,vi},y=(y1,y2,…,y15)= (0.14,0.18,0.22,0.25,0.29,0.32,0.35,0.39, 0.37,0.58,0.73,0.96,1.34,2.10,4.39)。

問題7(Demyanov-Malozemov問題)

參數(shù)n=2,m=3。

f1(x)=5x1+x2,f2(x)=-5x1+x2,

問題8(Rosen-Suzuki問題)

參數(shù)n=4,m=4。

5x2-21x2+7x4,

x1-x2+x3-x4-8),

2x1-x2-x4-5)。

在主頻為2.80 GHz的windows10系統(tǒng)下，使用MATLAB R2014a軟件進(jìn)行仿真實(shí)驗(yàn)，算法執(zhí)行50次，各問題的最優(yōu)解迭代過程和50次運(yùn)行結(jié)果變化分別如圖1和圖2所示。相關(guān)參數(shù)設(shè)置如下：控制參數(shù)p的值設(shè)置為105；加速常數(shù)c1=c2=1.449 45；粒子群規(guī)模為500；最大迭代次數(shù)為5 000；最大速度為2；粒子搜索范圍根據(jù)問題變化，問題1、問題2和問題8的搜索范圍為[-2,2]，問題3和問題4的搜索范圍為[-1,1]，問題5的搜索范圍為[-5,5]，問題6的搜索范圍為[-4,4]，問題7的搜索范圍為[-3,3]。計(jì)算結(jié)果和平均運(yùn)行時(shí)間見表1。

圖1 各問題的最優(yōu)解迭代過程

圖2 各問題50次運(yùn)行結(jié)果變化

算例算法搜到的最優(yōu)值收斂時(shí)迭代次數(shù)50次搜索成功率/%平均運(yùn)行時(shí)間/s例1本文算法x*=(1.000 000 000 0, 1.000 000 000 0)TFp(x*)=2.000 000 000 014910036.085 9文獻(xiàn)[12]x*=(1,1)T; Fp(x*)=2---文獻(xiàn)[13]2.001 415---文獻(xiàn)[14]x*=(1.000 008, 1.000 019)TFp(x*)=2.000 071---例2本文算法x*=(1.139 037 653 0, 0.899 559 937 6)TFp(x*)=1.952 224 493 97210033.203 9文獻(xiàn)[8]x*=(1.139 042 920 5, 0.899 556 536 1)TFp(x*)=1.952 224 494-100-文獻(xiàn)[12]x*=(1.139 037 652, 0.899 559 938 4)TFp(x*)=1.952 224 494---文獻(xiàn)[13]1.952 253---例3本文算法x*=±(0.453 296 230 8, -0.906 592 474 1)TFp(x*)=0.616 432 435 69810034.258 1文獻(xiàn)[5]x*=(0.453 3, -0.906 6)TFp(x*)=0.437 9---文獻(xiàn)[6]0.616 433---文獻(xiàn)[8]x*=±(0.453 293 317 2, -0.906 591 789 5)TFp(x*)=0.616 432 435 6-100-例4本文算法x*=(0.328 259 953 4, 0, 0.131 320 064 1)TFp(x*)=3.599 719 299 87610037.915 6文獻(xiàn)[5]x*=(0.328 3, 0, 0.131 3)TFp(x*)=-1.074 1---文獻(xiàn)[6]3.599 72---文獻(xiàn)[12]x*=(0.328 259 95, 0, 0.131 320 063 6)TFp(x*)=3.599 719 300---例5本文算法x*=(2.330 499 393 8, 1.951 372 389 8,-0.477 541 376 5, 4.365 726 185 8,-0.624 486 980 3, 1.038 130 998 8, 1.594 226 719 4)TFp(x*)=680.630 057 374 422010041.966 4文獻(xiàn)[6]680.63---文獻(xiàn)[14]x*=(2.330 5, 1.951 4, -0.477 54, 4.365 7, -0.624 49, 1.038 1, 1.594 2)TFp(x*)=680.630 1---文獻(xiàn)[15]680.630 06---例6本文算法x*=(0.053 469 387 8, t, -(3.5+t))T(-1.6≤t≤-0.4)Fp(x*)=0.050 816 326 59310043.004 5文獻(xiàn)[6]0.050 816 9---文獻(xiàn)[12]x*=±(0.053 469 387 76,t,3.5-t)T(0.5≤t≤1.5)Fp(x*)=0.050 816 326 53---例7本文算法x*=(0.000 000 000 0, -3.000 000 000 0)TFp(x*)=-3.000 000 000 01810031.017 1文獻(xiàn)[13]-3---例8本文算法x*=(0.000 000 000 0, 1.000 000 000 0,2.000 000 000 0, -1.000 000 000 0)TFp(x*)=-44.000 000 000 0126 110031.786 3文獻(xiàn)[8]x*=(0.007 155 659 5, 1.017 545 258 6,1.989 755 776 4, -1.008 662 343 0)TFp(x*)=-43.997 888 387 3-100-文獻(xiàn)[13]-43.999 8---文獻(xiàn)[14]x*=(0.000 158 83, 0.998 69, 2.000 49, -0.999 677)TFp(x*)=-43.999 99---

由圖1和圖2可見，本文算法收斂快(收斂時(shí)迭代次數(shù)見表1)、穩(wěn)定性好。由表1可見，本文算法的計(jì)算結(jié)果整體優(yōu)于文獻(xiàn)[5-6，8，12-15]中的結(jié)果。

對(duì)于例1，搜索得到的最優(yōu)解2就是已知的精確解，與文獻(xiàn)[12]的結(jié)果相同，比文獻(xiàn)[13]的結(jié)果2.001 415和文獻(xiàn)[14]的結(jié)果2.000 071都要精確；對(duì)于例2，本文搜索得到的最優(yōu)解1.952 224 493 9比文獻(xiàn)[8]的結(jié)果1.952 224 494 0、文獻(xiàn)[12]的結(jié)果1.952 224 494和文獻(xiàn)[13]的結(jié)果1.952 253都要好；對(duì)于例3，本文搜索得到的最優(yōu)解0.616 432 435 6與文獻(xiàn)[8]的結(jié)果0.616 432 435 6相同，比文獻(xiàn)[5]的結(jié)果0.437 9準(zhǔn)確，比文獻(xiàn)[6]的結(jié)果0.616 433更好；對(duì)于例4，本文搜索得到的最優(yōu)解3.599 719 299 8比文獻(xiàn)[5]的結(jié)果-1.0741準(zhǔn)確，比文獻(xiàn)[6]的結(jié)果3.599 72和文獻(xiàn)[12]的結(jié)果3.599 719 300都要好；對(duì)于例5，本文搜索得到的最優(yōu)解680.630 057 374 4比文獻(xiàn)[6]的結(jié)果680.63、文獻(xiàn)[14]的結(jié)果680.630 1和文獻(xiàn)[15]的結(jié)果680.630 06都要好；對(duì)于例6，本文搜索得到的最優(yōu)解0.050 816 326 5比文獻(xiàn)[6]的結(jié)果0.050 816 9和文獻(xiàn)[12]的結(jié)果0.050 816 326 53都要好；對(duì)于例7，本文搜索得到的最優(yōu)解-3與文獻(xiàn)[13]的結(jié)果-3一樣；對(duì)于例8，本文搜索得到的最優(yōu)解-44是已知精確解，比文獻(xiàn)[8]的結(jié)果-43.997 888 387 3、文獻(xiàn)[13]的結(jié)果-43.999 8和文獻(xiàn)[14]的結(jié)果-43.999 99都更好。

5 結(jié)語

本文針對(duì)極小極大問題中極大值函數(shù)不可微以及智能優(yōu)化算法不需要使用函數(shù)的梯度信息和初始點(diǎn)的特點(diǎn)，提出了一種將分?jǐn)?shù)階粒子群算法與極大熵函數(shù)法相結(jié)合的新算法來解決非線性極小極大問題。首先利用極大熵函數(shù)法將目標(biāo)函數(shù)轉(zhuǎn)化成可微的函數(shù)；其次利用分?jǐn)?shù)階粒子群算法求解可微的近似優(yōu)化問題。數(shù)值實(shí)驗(yàn)結(jié)果表明，本文提出的算法是一個(gè)可以解決非線性極小極大問題的有效算法。