求解高維優(yōu)化問題的新型平衡優(yōu)化器算法

申元霞,汪小燕,張學(xué)鋒

(安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,安徽 馬鞍山 243000)

1 引 言

目前,隨機(jī)優(yōu)化算法已經(jīng)成功應(yīng)用于工程優(yōu)化問題,如模式識別[1]、PID控制器[2]等.從算法的設(shè)計(jì)思路上可以將隨機(jī)優(yōu)化算法劃分4類,第1類是受生物進(jìn)化啟發(fā)提出的進(jìn)化優(yōu)化模型,如差分進(jìn)化算法[3]等.第2類模擬群居動物的行為而實(shí)現(xiàn)群智能優(yōu)化模型,如粒子群優(yōu)化算法[4]、灰狼優(yōu)化算法[5]等.第3類算法設(shè)計(jì)靈感來源于人類的社會行為,如教與學(xué)優(yōu)化算法[6]、帝國競爭優(yōu)化算法[7]等.第4類算法是模擬物理現(xiàn)象和規(guī)則設(shè)計(jì)的優(yōu)化模型,如重力搜索算法[8]、量子優(yōu)化算法[9]等.雖然各個優(yōu)化模型的設(shè)計(jì)思路不同,但是共同的目標(biāo)都是通過最短的搜索時(shí)間,尋找到待求解問題的全局最優(yōu)解.

平衡優(yōu)化器EO (Equilibrium Optimizer)[10]是2020年提出的一種新的隨機(jī)搜索優(yōu)化算法,算法的提出是受控制容積動態(tài)質(zhì)量平衡的物理現(xiàn)象啟發(fā).目前EO算法已有效解決二極管參數(shù)估計(jì)[11]、光伏參數(shù)估計(jì)[12]、圖像分割[13]、0-1背包[14]等工程優(yōu)化問題.

雖然EO算法在低維問題上展現(xiàn)良好的優(yōu)化性能,但是在求解高維問題上,EO算法進(jìn)化中后期會出現(xiàn)停滯現(xiàn)象.為了改善EO算法求解高維復(fù)雜問題的優(yōu)化性能,本文首先分析EO尋優(yōu)過程中陷入進(jìn)化停滯原因,接著提出了新型EO算法,新算法通過設(shè)計(jì)動態(tài)更新的生存概率來增強(qiáng)群體的探測能力;為了避免平衡池候選解同質(zhì)化,對候選解實(shí)施依概率自我學(xué)習(xí);同時(shí)將種群分為兩組,一組采用改進(jìn)EO策略學(xué)習(xí),另一組采用提出的混合反向?qū)W習(xí)機(jī)制,異構(gòu)學(xué)習(xí)模式可以避免群體陷入進(jìn)化停滯.對比實(shí)驗(yàn)結(jié)果表明改進(jìn)的EO算法在高維優(yōu)化問題上表現(xiàn)了良好的尋優(yōu)性能.

2 平衡優(yōu)化器(EO)

EO是通過質(zhì)量平衡方程中質(zhì)量在一個控制容積內(nèi)進(jìn)入、產(chǎn)生和離開的過程來模擬尋優(yōu)的過程.在EO中,將待求解問題的解看作控制容積內(nèi)濃度,尋優(yōu)的過程是受控容積內(nèi)濃度達(dá)到平衡狀態(tài)的過程.

假設(shè)Ci(t)是第i個個體第t時(shí)刻濃度向量,t+1時(shí)刻個體濃度的更新方程為:

(1)

式中i∈(1,…,N),N為種群規(guī)模.Ceq為平衡池中隨機(jī)選擇的一個候選解.V為單位值,取常值為1[10].

平衡池是為尋優(yōu)過程中提供候選解的集合,候選解是每次迭代后種群按個體適應(yīng)度排列,由排列前4位個體及其平均值組成.

(2)

(3)

β=(1-t/T)a2t/T

(4)

(5)

式中r2和r3為服從[0,1]之間的隨機(jī)數(shù);GP為生成概率,GP取值越小越利于個體的探索;越大則利于個體的局部學(xué)習(xí),文獻(xiàn)[10]取值為0.5.

3 EO尋優(yōu)行為分析

EO的尋優(yōu)方式不再是個體向最優(yōu)解逐漸逼近,而是從平衡池中隨機(jī)選擇一個候選解,以該候選解為中心,實(shí)施鄰域搜索,搜索半徑是由更新方程中的運(yùn)動項(xiàng)控制.為了便于分析,將EO模型簡化一維模型進(jìn)行討論,將式(5)代入式(1)可得式(6):

(6)

由式(6)可知當(dāng)r3

圖1 F隨迭代次數(shù)的取值變化圖Fig.1 Variation of F over course of iterations

當(dāng)r3≥GP時(shí),新個體的生成半徑是更新方程的第2項(xiàng)和第3項(xiàng)之和.第3項(xiàng)為0.5(r2/λ)F(1-F)(Ceq(t)-λCi(t)).令Ф=0.5F(1-F),由于F的取值范圍在[-1.264,1.264],所以Ф取值范圍在[-1.43,0.125].令Z=r2/λ,r2和λ均為獨(dú)立的[0,1]隨機(jī)變量,可計(jì)算Z的概率分布為式(7):

(7)

由式(7)可得,z取值在(0,1]之間的概率為0.5;當(dāng)z值大于1的概率隨著z值的增加而指數(shù)遞減.第3項(xiàng)可表示為ФZ(Ceq(t)-λCi(t)),由Z的概率分布可知,Z有50%取值概率可以壓縮Ф(Ceq(t)-λCi(t))的值,50%取值概率可以擴(kuò)大Ф(Ceq(t)-λCi(t))的值.當(dāng)r3≥GP時(shí),在第2項(xiàng)和第3項(xiàng)共同作用下群體偏向探索.但當(dāng)群體聚集,Ci(t)等同與Ceq(t)時(shí),第2項(xiàng)(Ci(t)-Ceq(t))F為零,而第3項(xiàng)為ФZ(1-λ)Ceq(t),仍具有個體更新的能力,但是由于Z和λ取值的限制,個體探索能力減弱.

4 改進(jìn)的EO(IEO)

標(biāo)準(zhǔn)的EO里生成概率取值為0.5.通過EO尋優(yōu)行為的分析可知,當(dāng)r3

4.1 自適應(yīng)的生成概率

固定的生成概率限制了群體的探索能力.為了提高群體在進(jìn)化中后期的探測能力,提出了自適應(yīng)的生成概率,定義見式(8):

GP(t)=g0-g1(1+t/T)

(8)

由式(8)可知生成概率隨著迭代次數(shù)的增加從g0-g1而遞減g0- 2g1,該策略讓群體隨著迭代次數(shù)的增加有更多機(jī)會進(jìn)行探索.

4.2 優(yōu)秀解的學(xué)習(xí)策略

EO學(xué)習(xí)策略是對平衡池中的候選解進(jìn)行利用和探索,候選解的質(zhì)量直接影響尋優(yōu)的效果.如果平衡池排名前4位的候選解產(chǎn)生聚集的情況,即使平衡池中有當(dāng)前種群的均值候選解,但是由于均值候選解被選中的概率只有0.2;因此這種情況易使整個群體陷入局部最優(yōu).候選解的自我學(xué)習(xí)可以幫助逃離當(dāng)前的局部最優(yōu).本文采用文獻(xiàn)[15]提出的學(xué)習(xí)策略,定義見式(9):

(9)

式(9)中L為學(xué)習(xí)步長,r4為[0,1]分布的隨機(jī)變量.當(dāng)Ceq從平衡池被選擇后,Ceq有50%的概率按式(9)學(xué)習(xí).

4.3 種群的異構(gòu)學(xué)習(xí)模式

雖然自適應(yīng)的生成概率增加了群體實(shí)施探索的機(jī)會,但是指數(shù)項(xiàng)F隨著迭代次數(shù)的增加將逐漸減小,這將使整個群體在進(jìn)化中后期探索能力不足.為了進(jìn)一步增強(qiáng)群體探索能力,本文提出混合反向?qū)W習(xí)策略,并對群體實(shí)施異構(gòu)學(xué)習(xí)模式.將種群分為兩個組,一個組采用改進(jìn)的EO學(xué)習(xí)策略,稱為E組;另一個組實(shí)施混合反向?qū)W習(xí)策略,稱為H組.

(10)

式中的Xmax和Xmin分別是待求問題的上限和下限;r5為[0,1]分布的隨機(jī)變量.新的個體是由E組的個體Ci和其反向?qū)W習(xí)個體加權(quán)得到,混合反向?qū)W習(xí)策略比單純的反向?qū)W習(xí)策略可以增加獲得優(yōu)秀個體的可能.

4.4 IEO算法流程

IEO偽代碼如算法所示.

算法.IEO

輸入:種群最大迭代數(shù)T;E組和M組種群規(guī)模分別為n和N-n;

輸出:種群最優(yōu)解gbest;

1.初始化E組種群C和H組種群X;

2.計(jì)算H組個體X的適應(yīng)度,將最優(yōu)適應(yīng)度值賦給Xgbest.

3.whilet<=Tdo

4.按式(8)計(jì)算GP(t);

5.fori←1 tondo

6.計(jì)算適應(yīng)度值f(C);按式(2)構(gòu)建平衡池ES;

9.end if

10.Ceq←隨機(jī)選擇平衡池ES優(yōu)秀個體;

11.if rand<0.5

12.Ceq按式(9)自我學(xué)習(xí);

13.end if

14.按式(1)、式(3)、式(4)、式(5)計(jì)算C(i);

15.end for

16.fori←1 toN-ndo

17.按式(10)計(jì)算X(i);

18.ifX(i)適應(yīng)度值優(yōu)于Xgbestthen

19.Xgbest←X(i)

20.end if

21.end for

23.end while

5 數(shù)值仿真實(shí)驗(yàn)及結(jié)果分析

5.1 測試函數(shù)

為了檢測本文算法的優(yōu)化能力,新算法(IEO)與標(biāo)準(zhǔn)EO、向量PSO算法(PPSO)[4]、 灰狼算法(GWO)[5]、動態(tài)TLBO算法(DTLBO)[6]、基于記憶導(dǎo)向的SCA算法(MSCA)[16]進(jìn)行比較.

表1 函數(shù)的定義Table 1 Define of benchmark test functions

采用文獻(xiàn)[10]給出的13個測試函數(shù),包括單調(diào)測試函數(shù)和多模測試函數(shù),測試函數(shù)定義如表1所示.在對比實(shí)驗(yàn)中,采用種群規(guī)模均為30,其中IEO中的E組和H組規(guī)模分別為20和10;最大迭代次數(shù)T=500,獨(dú)立運(yùn)行次數(shù)為25次,維數(shù)D為200和500.

參數(shù)設(shè)置:標(biāo)準(zhǔn)EO中GP=0.5,a1=2,a2=1;IEO中g(shù)0=0.8,g1=0.3,L=2(參照文獻(xiàn)[15]推薦值);MSCA中a(t):2→0,按文獻(xiàn)[16]設(shè)置不同引導(dǎo)個體數(shù)Δt;GWO中a:2→0;DTLBO中Jr=0.3,w=10;tf∈(0,2).每種算法運(yùn)行后記錄其平均適應(yīng)度值及其標(biāo)準(zhǔn)差,并用Wilcoxon秩和檢驗(yàn)(顯著性水平α=0.05)來評價(jià)IEO與其他算法之間性能差異.

5.2 實(shí)驗(yàn)結(jié)果分析

表2和表3分別給出了200維和500維條件下6種算法獨(dú)立運(yùn)行25次后獲得平均適應(yīng)度及其標(biāo)準(zhǔn)差.對于每個函數(shù)用加粗字體來表示獲取的最優(yōu)結(jié)果.

由表2和表3可知,除函數(shù)f8外,IEO在12個函數(shù)上200維和500變量的條件下尋優(yōu)結(jié)果要遠(yuǎn)優(yōu)于EO、GWO、MSCA、DTLBO和PPSO算法.對于函數(shù)f8,IEO尋優(yōu)結(jié)果要劣于MSCA、DTLBO和PPSO,優(yōu)于EO和GWO.IEO已找到200維和500維f9,f10和f11這3個多模函數(shù)的理論最優(yōu)值.IEO不僅獲得了較高精度的平均值,也獲得了低方差,說明算法也具有較好的穩(wěn)定性.用Wilcoxon秩和檢測的評價(jià)結(jié)果,可獲得6個算法平均排名,結(jié)果顯示在表2和表3的“rank”欄.從表中可知在200維和500維變量的條件下,IEO綜合排名均為第1.

DTLBO在f1～f7、f10、f11和f12函數(shù)上優(yōu)化結(jié)果優(yōu)于EO、GWO、MSCA和PPSO.在200維變量的條件下,DTLBO與IEO尋優(yōu)結(jié)果相同,找到了函數(shù)f9和f11的理論最優(yōu)解;在500維變量的條件下,DTLBO找到了函數(shù)f9的理論最優(yōu)解;DTLBO綜合排名均為第2,這表明DTLBO在高維優(yōu)化問題上也展現(xiàn)了良好的優(yōu)化性能.但是在求解精度上,與IEO還存在差距,如對于200維變量的條件下函數(shù)f3,DTLBO優(yōu)化結(jié)果精度為103,而IEO優(yōu)化結(jié)果精度為10-170;對于函數(shù)f6,DTLBO優(yōu)化結(jié)果精度為101,而IEO優(yōu)化結(jié)果精度為10-2.

表2 各個算法在函數(shù)變量為200維的實(shí)驗(yàn)結(jié)果Table 2 Optimization results of each algorithm on 13 test functions of 200 dimensions

表3 各個算法在函數(shù)變量為500維的實(shí)驗(yàn)結(jié)果Table 3 Optimization results of each algorithm on 13 test functions of 500 dimensions

對于函數(shù)f8,與其他5種算法相比,PPSO獲得最優(yōu)解.但是PPSO在其他12個函數(shù)上優(yōu)化結(jié)果均要劣于其他算法.收斂曲線分析可以直觀地觀察算法陷入停滯現(xiàn)象和收斂速度.圖2給出了6種算法在D=500時(shí)的收斂曲線.由圖2可以看出,IEO的收斂速度快,在給定代數(shù)下的收斂精度也達(dá)到最高.

從f9和f10收斂曲線圖可以看出,IEO可以快速尋找到理論最優(yōu)值.從f5、f6和f12收斂曲線圖可以看出,IEO具有良好的尋優(yōu)能力,不僅沒有在進(jìn)化的中后期陷入進(jìn)化停滯,而且在進(jìn)化后期仍具有強(qiáng)的搜索能力,不斷提高解的精度.特別對于f5,IEO在進(jìn)化過程中,也進(jìn)入局部收斂,但是在進(jìn)化后期可以逃逸局部極值繼續(xù)尋優(yōu).除了f1,EO在其他5個函數(shù)進(jìn)化過程的中后期均陷入進(jìn)化停滯,也無法逃離局部極值.DTLBO的收斂速度優(yōu)于EO、GWO、MSCA和PPSO,但是在f5、f6、f10和f12的進(jìn)化過程中也陷入了局部收斂.

由上述分析可知,IEO具有高的收斂精度和快的收斂速度,而且受維度變化影響小,求解高維優(yōu)化問題具有良好穩(wěn)定性.這主要是因?yàn)镮EO自適應(yīng)生成概率使得算法在進(jìn)化初期局部利用和全局探索的概率相當(dāng),群體可以快速地學(xué)習(xí)平衡池的優(yōu)秀候選解,從而獲得好的收斂速度.隨著迭代次數(shù)的增加,由于E組學(xué)習(xí)模式中指數(shù)項(xiàng)的遞減,群體逐漸進(jìn)入聚集;但是平衡池優(yōu)秀解的自我學(xué)習(xí)和H組的混合反向?qū)W習(xí)可以幫助從局部極值中跳出.綜上所述,在高維條件下IEO在求解精度、收斂速度和穩(wěn)定性方面都展現(xiàn)較好的進(jìn)化尋優(yōu)性能.

圖2 6種算法在6個函數(shù)上的收斂曲線Fig.2 Convergence performance of the six algorithms on the 6 test functions

6 結(jié)束語

本文針對標(biāo)準(zhǔn)平衡優(yōu)化器易出現(xiàn)進(jìn)化停滯的問題進(jìn)行了分析.通過分析得出,標(biāo)準(zhǔn)平衡優(yōu)化器固定的進(jìn)化概率、平衡池中候選解的集聚和中后期指數(shù)項(xiàng)的遞減都可能導(dǎo)致進(jìn)化停滯.基于標(biāo)準(zhǔn)平衡優(yōu)化器的尋優(yōu)分析,提出改進(jìn)的平衡優(yōu)化器(IEO).首先設(shè)計(jì)了自適應(yīng)調(diào)整的生成概率,在平衡算法的利用與探索的同時(shí),提高算法在中后期的探索能力以防止算法陷入停滯.接著對平衡池的候選解進(jìn)行自我學(xué)習(xí),不僅可以有效提高群體的收斂速度索,同時(shí)可以避免候選解的集聚.最后通過異構(gòu)雙組的學(xué)習(xí)模式,讓輔助群組在中后期提供探索動力.實(shí)驗(yàn)結(jié)果表明 IEO在求解高維函數(shù)優(yōu)化問題具有一定優(yōu)勢,可以達(dá)到較好的收斂速度和收斂精度.接下來的研究方向是將本文算法擴(kuò)展到高維多目標(biāo)問題求解上.