一類不可微優(yōu)化問題的混合螢火蟲算法

李琳娜, 方 銘, 黃瓊丹

(1.西安郵電大學 校友工作辦公室， 陜西 西安 710121; 2.西安郵電大學 計算機學院， 陜西 西安 710121;3. 西安郵電大學 通信與信息工程學院， 陜西 西安 710121)

l1模極小化問題已廣泛應用在稀疏信號處理和機器學習領域[1-4]。利用混合l1/l2范數(shù)最小化和正交匹配追求算法，設計了多輸入多輸出系統(tǒng)中稀疏有限脈沖響應決策反饋均衡器[1]；利用順序重加權l(xiāng)1范數(shù)最小化技術，研究了電子冷卻問題中二維熱傳導的熱源分布優(yōu)化問題[3]；將波束發(fā)生器輸出向量的l1模，作為成本函數(shù)的波束形成方法[4]。由于l1模極小化問題是不可微優(yōu)化問題，求解較為困難。利用凝聚熵函數(shù)法[5-7]，將l1模極小化問題轉化為可微優(yōu)化問題，可求解非線性l1模極小化問題，但此方法僅適用于求解連續(xù)性、可微分和小規(guī)模等問題[8-11]，對于目標函數(shù)及約束函數(shù)非光滑的問題，則需要不斷計算待求解問題的梯度信息并選取合適的初始點作為計算起點，求解難度大[7]。

螢火蟲算法[12-14](firefly algorithm,FA)是一種群體智能算法，具有不依賴于初始點選取和梯度信息等特點，可解決離散性、不確定性和大規(guī)模等問題，跟粒子群算法[15](particle swarm optimization,PSO)相比，收斂速度更快，已廣泛應用在人工智能、目標優(yōu)化和系統(tǒng)控制等領域。

為了解決非線性l1模極小化問題，本文提出一種改進的l1模極小化螢火蟲算法(l1firefly algorithm,LFA)。通過凝聚熵函數(shù)法及罰函數(shù)法[7]，將非線性l1模極小化問題轉化為光滑函數(shù)的無約束優(yōu)化問題[8]，并應用螢火蟲算法進行優(yōu)化求最優(yōu)解。

1 問題描述

非線性l1模極小化問題可描述為

(1)

其中，fi(x)是一簇光滑函數(shù)(i∈+),gj(x)是一簇光滑約束函數(shù)。由于絕對值函數(shù)的不可微性，導致此問題的目標函數(shù)f(x)是不可微函數(shù)，所以問題(1)是較為復雜的帶約束不可微優(yōu)化問題。

將函數(shù)f(x)等價為

構造函數(shù)f(x)的凝聚熵函數(shù)，通過引入下述相關定義及定理[7-8]，可將非線性l1模極小化問題轉化為可微優(yōu)化問題。

定義1定義函數(shù)

為問題(1)中目標函數(shù)f(x)在x∈n上的凝聚熵函數(shù)，p為可調節(jié)參數(shù)。

定理1對任何x∈n，函數(shù)Fp(x)隨參數(shù)p的增大而單調減少，且當p→+∞時，以f(x)為極限，即

Fs(x)≤Fr(x)s≤rs,r∈

由定理1可知，當p取的足夠大時，函數(shù)Fp(x)可近似替代目標函數(shù)f(x)。因此，當p→+∞時，問題(1)可近似為

minFp(x)
s.t.gj(x)≤0(j=1,2,…,n;x∈n)。

(2)

問題(2)中目標函數(shù)可微，但是約束函數(shù)仍不可微。因此，對約束函數(shù)進行處理，可將問題(2)轉換為目標函數(shù)與約束函數(shù)均可微的優(yōu)化問題。

定理2問題(2)的約束集合等價于極大值約束

定理2把多約束問題轉化為單約束問題，則問題(2)可等價于

minFp(x)
s.t.G(x)≤0。

(3)

定義2定義函數(shù)

為函數(shù)G(x)在x∈n上的凝聚熵函數(shù)，q為可調節(jié)參數(shù)。

定理3對任何x∈n，函數(shù)Gq(x)隨參數(shù)q的增大而單調減少，且當q→+∞時，以G(x)為極限，即

Gs(x)≤Gr(x)s≤rs,r∈,

由定理3可知，當q取的足夠大時，函數(shù)Gq(x)可近似替代目標函數(shù)G(x)。因此，當q→+∞時,問題(3)可近似為

minFp(x)
s.t.Gq(x)≤0，

(4)

此時，問題(4)中的目標函數(shù)與約束函數(shù)均光滑可微，便于問題求解。當p,q→+∞時，可用問題(4)的解近似代替問題(1)的解。

定義3稱函數(shù)

φ(x,η)=Fp(x)+ηGq(x),

(5)

為問題(4)的罰函數(shù)，η為罰因子。

式(5)將問題(4)轉化為無約束可微優(yōu)化問題，以式(5)作為目標函數(shù)，利用螢火蟲算法極小化該目標函數(shù)，在參數(shù)選取合理情況下，便可得到問題(4)的解，即問題(1)的高精度近似解。

對于無約束非線性l1模極小化問題，只需利用螢火蟲算法極小化問題(2)中的目標函數(shù)Fp(x)，即可求得問題(1)的高精度解。

2 螢火蟲算法

螢火蟲算法[16-18]是一種啟發(fā)式群智能優(yōu)化算法，其靈感來自于螢火蟲熒光閃爍的求偶行為。在螢火蟲算法中，個體之間存在自身亮度和吸引度兩個要素。個體自身亮度由其當前適應值決定，適應值越佳，自身亮度越高，所處位置就更優(yōu)。吸引度與亮度相關，亮度越高的個體吸引力更強，可以吸引亮度更弱的個體向自身靠近，如果亮度相同，則各自隨機移動。吸引度決定了個體在每次迭代中，靠近吸引個體移動的距離大小。為了符合自然界中光線傳播衰減規(guī)律，個體之間的相對亮度與吸引度和個體之間距離成反比。將個體所在位置坐標作為潛在解，利用發(fā)光特性，吸引視線內(nèi)螢火蟲相互靠近和移動，從而實現(xiàn)個體的位置更新，搜索最優(yōu)解。

從數(shù)學角度考慮螢火蟲算法，需要定義熒光的相對亮度、個體的吸引強度及位置更新公式等3個參數(shù)[12-13]。

定義4熒光的相對亮度

L=L0×e-βrij,

(6)

其中L0表示個體的最大熒光亮度，即rij=0處的螢光亮度，與適應值函數(shù)有關。β為光強度吸收因子，模擬光線傳播中的衰減現(xiàn)象，可設為常數(shù)。rij為個體i與j之間的直線距離，計算表達式為

(7)

其中，xik與xjk分別表示第i個個體與第j個個體位置的第k維坐標，n為空間維數(shù)，即問題變量個數(shù)。

定義5個體的吸引強度

σ=σ0×e-βrij,

(8)

其中σ0為最大吸引強度，即rij=0處的吸引強度。

定義6個體的位置更新公式為

xik=xik+σ(xjk-xik)+α(R-1/2),

(9)

其中α為步長,R為[0,1]均勻分布的隨機數(shù)。為了避免早熟收斂，加入隨機擾動因子α×(R-1/2)。α為線性遞減，在算法運行初期，可增強全局搜素能力；后期則利于局部精細搜索。

3 LFA算法

LFA算法利用凝聚熵函數(shù)將非線性l1模極小化問題的目標函數(shù)及約束函數(shù)分別轉化為單一光滑函數(shù)，構造此光滑目標函數(shù)與光滑約束函數(shù)的罰函數(shù)，再利用螢火蟲算法極小化該函數(shù)并求得最優(yōu)解。具體算法步驟如下。

步驟1算法初始化，給出光強度吸收因子β、p、步長α和最大熒光亮度σ0等基本參數(shù)，其中罰因子η>0。

步驟2在n維空間，隨機生成個體m的位置坐標。

步驟3計算第k代每個個體的目標值φ(x(k)η(k))，設置為各自最大熒光亮度L0。

步驟4根據(jù)式(6)、式(7)和式(8)，分別計算每個個體的相對熒光亮度L和吸引強度σ，并由相對熒光亮度決定個體移動方向。

步驟5令k=k+1,根據(jù)式(9)更新個體位置。

步驟6當滿足停止準則時，轉步驟7，否則，轉步驟3，進行新的搜索。

步驟7輸出個體所在位置坐標。

求解凝聚熵函數(shù)Fp(x)和Gq(x)時，當參數(shù)p,q選取過大，則會引起指數(shù)部分過大，導致數(shù)據(jù)溢出，無法得到結果輸出；若p,q取值較小，則計算精度得不到有效保證，因此作以下處理。

取臨界正整數(shù)M，使eM+1發(fā)生數(shù)據(jù)溢出，且eM未發(fā)生。

(1)對函數(shù)Fp(x)，令

若pFk(x)≤M,則

若pFk(x)

(2)對函數(shù)Gq(x)，令

若qGk(x)≤M,則

若qGk(x)>M,則

Gq(x)=±Gk(x)，

其中，當Gq(x)為正時，右式取“+”號，當Gq(x)為負時，右式取“-”號。

4 數(shù)值實驗對比及結果分析

LFA算法的性能主要由凝聚熵函數(shù)調節(jié)參數(shù)的取值和搜索解的能力兩個方面因素決定,實驗分別對這兩個因素進行探討。

實驗平臺為Windows 10、64位操作系統(tǒng)，因特爾i3雙核、64位處理器，主頻1.7Ghz，4G內(nèi)存，實驗所涉及算法使用C++語言編程實現(xiàn)。

4.1 數(shù)值算例

例1問題

最優(yōu)解

x*=(1,0)T,f(x*)=cos 1,

或者

x*=(-1,-0)T,f(x*)=cos (-1)

例2問題

最優(yōu)解

x*=(0,0)T,f(x*)=0

例3問題

最優(yōu)解

x*=(0,1)T,f(x*)=4

4.2 實驗分析

實驗1驗證調節(jié)參數(shù)p對LFA算法性能的影響。例1是無約束非線性l1模極小化問題，算法精度ε=10-6，個體數(shù)m=100，空間維數(shù)n=2，最大吸引度σ0=1.0，光強吸收因子β=1.0，步長α=0.5，解的空間范圍限定在[-1,+1]。分別對比p取不同值時，文獻[7]、文獻[8]、文獻[11]和LFA算法的求解結果,如表1所示。

表1 不同p值對比結果

由表1可知，文獻[7]與文獻[8]算法求解初期，需要設置初始點x(0)，對于不同的初始點，求解的最優(yōu)點可能會不同，這是由于在求解梯度時，梯度下降方向唯一造成的。若選取不當?shù)某跏键c，則會對最后的計算結果產(chǎn)生較大影響，甚至造成錯解或者漏解。例1有一對對稱解，文獻[7]與文獻[8]算法均發(fā)生了漏解現(xiàn)象。文獻[11]求解此問題時，與LFA算法均屬群體智能算法。在p取值相同的情況下，LFA算法求解精度比文獻[7]和文獻[8]較高，同時，不依賴于初始點的選取，所以不會產(chǎn)生漏解現(xiàn)象。當p值增大，例1的解都更加精確，因此，在實際解決此類問題時，p的取值應當更大。

圖1 例2函數(shù)圖像

算例算法x?f(x?) 成功率%例2LFA(0.00015,0.00003)4.49021e-006100.00PSO(-0.00043,0.00061)0.0001198.00GA(-0.00009,-0.00095)0.0001996.00BA(0.00004,0.00062)7.75508e-00598.00例3LFA(0.00003,0.99991)4.00012100.00PSO(0.00004,1.00017)4.00129100.00GA(0.00002,1.00096)4.0067798.00BA(-0.00016,0.99997)4.0009798.00

由表2可以看出，對于復雜的非線性l1模極小化問題，以上4種群體智能算法均能取得滿意解，但LFA算法對待優(yōu)化問題進行了熵函數(shù)處理，使待求解函數(shù)變的光滑，搜索成功率也高于其他3種算法。圖2和圖3分別為例2和例3的收斂曲線，可以看出,LFA比其他3種算法下降的更快,因此收斂速度較快。

圖2 例2收斂曲線

圖3 例3收斂曲線

5 結語

LFA算法不依賴初始點信息，且無需梯度信息，采用凝聚熵函數(shù)法及罰函數(shù)法將非線性l1模極小化問題轉化為光滑函數(shù)的無約束優(yōu)化問題，再利用螢火蟲算法進行優(yōu)化搜索最優(yōu)解。數(shù)值實驗結果表明，LFA算法的求解精度和搜索成功率均比PSO算法、GA算法和BA算法高，可有效求解非線性l1模極小化問題。