非線性極小極大問題的分數階粒子群算法

李昌興, 徐 邁, 惠莉萍

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

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

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

智能優化算法不需要使用函數的梯度信息和初始點，計算效率較高。其中，粒子群算法(particle swarm optimization，PSO)[7]的原理較為簡單且程序容易實現，目前已被廣泛應用于數值優化、神經網絡訓練、數據挖掘和系統控制等領域。

對于非線性極小極大問題，可結合改進的粒子群算法與極大熵函數求解[8]，也可結合差分進化算法與極大熵函數法求解[9]，或者結合粒子群-鄰近點混合算法和極大熵函數法求解[10]。但是，粒子群算法是一種依概率收斂的隨機優化算法，對多峰多谷的復雜優化問題，易陷入局部最優。基于分數階速度的粒子群算法(PSO with fractional-order velocity，FOPSO)使用分數階微分的定義，改進了粒子群算法的速度更新公式[11]，相較于經典粒子群算法，收斂速度更快。

本文將針對極小極大問題中，極大值函數不可微的特點，先用極大熵函數法將目標函數轉化成可微函數，再利用分數階粒子群算法求解可微的近似優化問題。

1 極大熵函數法

考慮無約束優化問題

利用極大熵函數法，可將無約束非線性極小極大問題轉化為光滑函數的無約束優化問題。極大熵函數定義為[4]

(1)

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

對于有限值p，Fp(x)是可微的，且式(1)可以改寫為[4]

由此可得

函數Fp(x)的值隨著參數p的增加而單調減小，且當p趨于無窮大時，Fp(x)以f(x)為極限，即

在實際數值計算時，只要參數p取得足夠的大，就可以使用極大熵函數Fp(x)代替不可微目標函數f(x)，從而可將原來的非線性極小極大問題的求解轉化為一個易于求解的可微函數的無約束優化問題。

2 分數階粒子群算法

分數階微積分(fractional calculus，FC)是數學分析的一個分支，也是應用科學中的數學工具之一。它是經典微積分的自然延伸，其微分算子及積分算子的階數可擴展到實數或復數范圍。換言之，分數階微積分是傳統積分和微分的泛化，它將非整數值包含到導數或者積分的冪中。因可用于大量自然現象的精確描述，分數階微積分已被成功應用于諸多科學領域，如工程科學、計算數學和流體力學等。事實上，針對服務于建模、曲線擬合、濾波、模式識別和邊緣檢測等應用的眾多算法，分數階微積分為提高其穩定性、可控性、可觀察性和魯棒性等性能，發揮著重要作用。

一元函數x(t)的Grünwald-Letnikov分數階微分定義為

(2)

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

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

式(2)的近似表達式為

(3)

其中，T是采樣周期，r是截斷次序。

分數階模型具備固有的記憶特性，非常適合描述諸如不可逆性和混沌現象。據此可知，分數階微積分工具非常適合描述粒子軌跡的動態現象。使用分數微積分，可以控制粒子群優化算法的收斂速度。

為了修改速度導數的階數，需要重新排列粒子群算法的原始速度方程

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

(4)

該表達式可以重新寫為

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

(5)

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

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

(6)

如果考慮分數微積分的特點，速度微分的階數可以推廣為實數α∈[0,1]，這樣可以獲得更平滑的變化和更長的記憶效應。考慮表達式(3)給出的微分的第一個r=4項，表達式(6)可改寫為[11]

當r≥4時，實驗測試可得相似結果。

實驗測試中，根據表達式

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

3 結合極大熵的分數階粒子群算法

將極大熵函數法和分數階粒子群算法相結合，給出一種解決非線性極小極大問題的新算法。

3.1 粒子群速度更新公式的改進

選用速度更新公式[11]

(7)

位置更新公式不變，仍為

xt+1=xt+vt+1。

(8)

3.2 算法步驟

步驟1對每個粒子初始化，確定粒子群規模N、加速常數c1和c2、問題維數d、最大迭代次數IM、問題的位置和速度的上下限，并隨機產生N個初始位置和N個初始速度。

步驟2將極大熵函數代替原目標函數作為適應度值函數，計算每個粒子的適應度值vf。

步驟3對每個粒子，若粒子的適應度值vf優于歷史的個體最優位置Pi的適應度值，則將當前適應度值設置為個體極值Ibest，當前位置為個體最優位置Pi。

步驟4對每個粒子，若粒子的適應度值vf優于歷史的全局最優位置Pg的適應度值，則將當前適應度值設置為全局極值Gbest，當前位置為全局最優位置Pg。

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

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

步驟7如果達到終止條件，則輸出問題的解；否則更新迭代次數，并轉到步驟2。

3.3 重要說明

(1) 在轉化極大熵函數時，由于要求p的值足夠大，所以計算機在計算時易導致epfi(x)發生數據溢出，故在計算時采用與文獻[8]中相同的計算技巧來避免數值溢出。

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

4 數值實驗

取參考文獻[5-6，8，12-15]中的8個非線性極小極大問題做測試。

問題1(Charalambous-Conn 2問題)

參數n=2,m=3。

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

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

問題2(Charalambous-Conn 1問題)

參數n=2,m=3。

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

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

問題3參數n=2,m=3。

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

問題4參數n=3,m=6。

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

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

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

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

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

問題6參數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問題)

參數n=2,m=3。

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

問題8(Rosen-Suzuki問題)

參數n=4,m=4。

5x2-21x2+7x4,

x1-x2+x3-x4-8),

2x1-x2-x4-5)。

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

圖1 各問題的最優解迭代過程

圖2 各問題50次運行結果變化

算例算法搜到的最優值收斂時迭代次數50次搜索成功率/%平均運行時間/s例1本文算法x*=(1.000 000 000 0, 1.000 000 000 0)TFp(x*)=2.000 000 000 014910036.085 9文獻[12]x*=(1,1)T; Fp(x*)=2---文獻[13]2.001 415---文獻[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文獻[8]x*=(1.139 042 920 5, 0.899 556 536 1)TFp(x*)=1.952 224 494-100-文獻[12]x*=(1.139 037 652, 0.899 559 938 4)TFp(x*)=1.952 224 494---文獻[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文獻[5]x*=(0.453 3, -0.906 6)TFp(x*)=0.437 9---文獻[6]0.616 433---文獻[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文獻[5]x*=(0.328 3, 0, 0.131 3)TFp(x*)=-1.074 1---文獻[6]3.599 72---文獻[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文獻[6]680.63---文獻[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---文獻[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文獻[6]0.050 816 9---文獻[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文獻[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文獻[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-文獻[13]-43.999 8---文獻[14]x*=(0.000 158 83, 0.998 69, 2.000 49, -0.999 677)TFp(x*)=-43.999 99---

由圖1和圖2可見，本文算法收斂快(收斂時迭代次數見表1)、穩定性好。由表1可見，本文算法的計算結果整體優于文獻[5-6，8，12-15]中的結果。

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

5 結語

本文針對極小極大問題中極大值函數不可微以及智能優化算法不需要使用函數的梯度信息和初始點的特點，提出了一種將分數階粒子群算法與極大熵函數法相結合的新算法來解決非線性極小極大問題。首先利用極大熵函數法將目標函數轉化成可微的函數；其次利用分數階粒子群算法求解可微的近似優化問題。數值實驗結果表明，本文提出的算法是一個可以解決非線性極小極大問題的有效算法。