何星月,張 靖,覃 濤,何必濤,楊 靖+
(1.貴州大學(xué) 電氣工程學(xué)院,貴州 貴陽 550025;2.中國電建集團 貴州工程有限公司,貴州 貴陽 550025)
元啟發(fā)式算法是對自然界的生物現(xiàn)象或物理現(xiàn)象進行模擬,可以在高維且復(fù)雜的約束條件下快速地找到問題的全局最優(yōu)解。近年來一系列的元啟發(fā)式算法被提出[1-4],這些算法被廣泛的應(yīng)用于圖像分割、參數(shù)估計、特征選擇等領(lǐng)域[5-9]。
白骨頂雞算法由Iraj Naruei等[10]提出。通過對白骨頂雞的隨機運動、鏈?zhǔn)竭\動和領(lǐng)導(dǎo)運動等行為的模擬,構(gòu)建出一種有效的尋優(yōu)機制。相較于傳統(tǒng)算法,白骨頂雞算法具有結(jié)構(gòu)簡單、性能穩(wěn)定等優(yōu)點,但仍存在收斂速度慢、易陷入局部最優(yōu)等不足。
為改善上述缺陷,國內(nèi)外學(xué)者們提出了不同的改進策略。文獻[11]提出了一種刺激-響應(yīng)機制,根據(jù)響應(yīng)閾值,使蜜蜂在跟隨蜂和雇傭蜂之間轉(zhuǎn)換,以平衡算法的搜索與開發(fā)能力。文獻[12]根據(jù)三角形相似性原理提出了動態(tài)演化理論,以增強麻雀算法后期的開發(fā)能力。文獻[13]利用差分進化思想,在樽海鞘領(lǐng)導(dǎo)者位置更新中引入變異算子,幫助算法在后期跳出局部最優(yōu)。文獻[14]通過對正余弦算法搜索方程中引入社交和認知成分,結(jié)合灰狼算法良好勘探和開發(fā)平衡能力優(yōu)化了算法的尋優(yōu)性能。
為進一步提高算法尋優(yōu)精度及工程應(yīng)用價值,本文提出了基于拉丁超立方體的改進白骨頂雞算法(improved COOT algorithm based on Latin Hypercube,LHCOOT)。首先利用拉丁超立方體抽樣使種群分布更加均勻;引入非線性決策因子以權(quán)衡算法全局搜索和局部開發(fā)過程;采取動態(tài)邊界機制,加速算法收斂;對最優(yōu)個體進行柯西擾動并引入貪婪策略,避免算法陷入局部最優(yōu)。通過對16個基準(zhǔn)函數(shù)、高維函數(shù)和實際工程問題進行仿真實驗,驗證了LHCOOT算法的有效性。
白骨頂雞是一種小型水鳥,在水面上有許多不同的群體行為,包括普通個體的隨機運動、鏈?zhǔn)竭\動、引導(dǎo)運動以及領(lǐng)導(dǎo)者運動。該算法的具體步驟如下:
普通個體運動:該過程主要由3種運動狀態(tài)構(gòu)成,執(zhí)行機制如式(1)所示
(1)
式中:Rb、Rc為常量0.5。lead、chain、random表示引導(dǎo)運動、鏈?zhǔn)竭\動和隨機運動,分別如式(2)~式(4)所示
CootPos(i)=Lead(K)+2×R1×cos(2R)×
(Lead(K)-CootPos(i))
(2)
(3)
CootPos(i)=CootPos(i)+A×R2×(Q-CootPos(i))
(4)
式中:R是[-1,1]中的隨機數(shù),R1、R2是[0,1]中的隨機數(shù),K為領(lǐng)導(dǎo)者的索引,為普通個體分配領(lǐng)導(dǎo)者,如式(5)所示
K=1+(iMODNL)
(5)
式中:i是普通個體索引,NL為領(lǐng)導(dǎo)者的數(shù)量。
領(lǐng)導(dǎo)者運動:該運動根據(jù)式(6),利用最優(yōu)個體牽引領(lǐng)導(dǎo)者,幫助種群向最優(yōu)區(qū)域收斂
(6)
式中:gBest是當(dāng)前最優(yōu)個體位置,R3和R4是[0,1]中的隨機數(shù)。
元啟發(fā)式算法的收斂速度和收斂精度通常與初始種群的分布結(jié)構(gòu)息息相關(guān)。COOT算法以隨機方式生成的初始種群會導(dǎo)致個體在求解空間分布不均,影響初始種群的多樣性。相較于傳統(tǒng)的混沌映射[15]、佳點集[16]等初始化策略,拉丁超立方體抽樣[17](Latin Hypercube sampling,LHS)基于分層抽樣原理,可以實現(xiàn)非重疊采樣和變量范圍全覆蓋采樣,兼顧種群初始化的隨機性和均勻性。
(7)
式中:vij是與hij獨立的(0,1)上均勻分布的獨立蒙特卡洛樣本。按照上述步驟選取的m個點ci=(ci1,ci2,…,cim),i=1,2…m為一個拉丁超立方體樣本。
假設(shè)搜索空間為2維,搜索范圍為(0,1)。隨機種群初始化和拉丁超立方體初始化分布如圖1所示。
圖1 初始化種群分布
從圖1可以觀察到,隨機種群初始化個體粘連嚴重,均勻性不佳。拉丁超立方體初始化分布在整個解空間,且均勻分散在每個坐標(biāo)區(qū)間。因此,拉丁超立方體抽樣能有效提高初始種群多樣性,有助于加快算法收斂速度。
2.2.1 非線性決策因子
是否能合理地平衡算法全局搜索和局部開發(fā)能力將直接影響算法的尋優(yōu)能力。在COOT算法中,隨機運動將會在解空間生成一個隨機解,引導(dǎo)白骨頂雞位置更新。鏈?zhǔn)竭\動將兩個相鄰索引個體的平均位置作為更新位置。因此,鏈?zhǔn)竭\動幫助種群向同一方向匯聚,適合在算法前期加速算法收斂。而隨機運動在整個解空間生成一個隨機解,牽引算法跳出局部最優(yōu)。兩種位置更新的執(zhí)行機制如式(8)所示
(8)
因此,等于0.5的常量Rc,是控制算法全局搜索能力和局部開發(fā)能力的決策因子。常量型決策因子并不能適用于解決復(fù)雜高維的實際工程問題。因此,本文采用一種非線性決策因子,令算法在前期緩慢衰減,增大執(zhí)行鏈?zhǔn)竭\動的概率,幫助算法快速收斂。在算法后期迅速衰減,增大執(zhí)行隨機運動的概率,從而幫助算法跳出局部最優(yōu)。非線性決策因子的數(shù)學(xué)模型如式(9)所示
(9)
式中:Rv0為決策因子初值,本文取為1,t是模型控制因子,t的取值控制模型的衰減速度,t值越大,模型的衰減速度越慢。不同t值下非線性決策因子模型及常量0.5對比如圖2所示。
圖2 決策因子曲線
當(dāng)決策因子曲線在常量0.5上方時,算法會以大概率執(zhí)行鏈?zhǔn)竭\動。反之,會以大概率執(zhí)行隨機運動。經(jīng)多次實驗驗證,當(dāng)t取10時,算法效果最佳。
2.2.2 自適應(yīng)動態(tài)邊界
COOT算法在執(zhí)行隨機運動時,會在整個搜索空間中生成隨機解。如果該搜索空間不隨著迭代過程而相應(yīng)收斂,將會增大尋優(yōu)過程的盲目性和復(fù)雜度,造成算法收斂遲滯,迭代時間增加。因此,本文引入了自適應(yīng)動態(tài)邊界機制,加快算法收斂速度。動態(tài)邊界的上下界如式(10)所示
UB=α×max(X)
LB=α×min(X)
(10)
式中:X為整個種群的位置矩陣,α為自適應(yīng)映射系數(shù),如式(11)所示
α=1+0.2×(eL/Iter-1)
(11)
式中:L是當(dāng)前迭代次數(shù),Iter是最大迭代次數(shù)。隨機位置Q的生成如式(12)所示
Q=rand(1,d)×(UB-LB)+LB
(12)
從式(12)可以看出,邊界將隨著種群的移動而動態(tài)跟隨,隨著種群的收斂而相應(yīng)縮小。同時,為了避免迭代后期,種群收斂陷入局部最優(yōu),將動態(tài)邊界通過隨著迭代次數(shù)增大的映射系數(shù)放大,增加動態(tài)牽引力度,從而增大跳出局部最優(yōu)的概率。相較于逐維更新的動態(tài)邊界,利用種群確定邊界,可以避免不同維度間的相互干擾,提供一定裕量,提高尋優(yōu)能力。
領(lǐng)導(dǎo)者的迭代更新由最優(yōu)個體引導(dǎo),向著最優(yōu)位置靠近,導(dǎo)致算法后期種群多樣性降低,算法易陷入局部最優(yōu)。本文在原有算法中加入柯西變異算子,對最優(yōu)個體進行柯西擾動,擴大算法的局部搜索能力,增強種群的多樣性。
正態(tài)分布和柯西分布是兩種經(jīng)典的連續(xù)型概率分布,兩者的概率密度函數(shù)曲線如圖3所示,相較于正態(tài)分布,柯西分布原點處的峰值較小,從原點處的峰值到兩端的下降趨勢會更加平緩。因此,柯西變異擾動能力更強。通過融入柯西變異對最優(yōu)個體產(chǎn)生擾動,能夠幫助算法跳出局部極值。
圖3 概率密度函數(shù)曲線
對最優(yōu)個體添加柯西變異的模型為
Xnbest=Xbest×(1+cauchy(0,1))
(13)
式中:Xbest為最優(yōu)個體,Xnbest為變異后的個體,cauchy(0,1) 是服從中心為0,尺度參數(shù)為1的柯西分布隨機數(shù)。為保證變異之后的解優(yōu)于原始解,算法引入貪婪策略,對比擾動前后解的適應(yīng)度值,擇優(yōu)保留。貪婪策略的數(shù)學(xué)模型如式(14)所示
(14)
式中:f為適應(yīng)度函數(shù)。
綜合上述改進策略,LHCOOT的算法流程如圖4所示。
圖4 算法流程
時間復(fù)雜度作為評價算法性能的指標(biāo)之一,可以間接反映算法的尋優(yōu)效率。設(shè)標(biāo)準(zhǔn)白骨頂雞算法種群數(shù)量為N,搜索空間維度為n,最大迭代次數(shù)為M,領(lǐng)導(dǎo)雞群比例為NL,求解目標(biāo)函數(shù)適應(yīng)度時間為f(n)。 假設(shè)初始化參數(shù)時間為λ1,每一維產(chǎn)生服從均勻分布隨機數(shù)的時間為λ2,找到并保存適應(yīng)度最佳個體位置的時間為λ3,則算法總體初始化階段的時間復(fù)雜度為
T1(n)=O(λ1+N(nλ2+f(n))+λ3)=O(n+f(n))
在迭代過程中,普通個體更新階段,普通個體個數(shù)為N(1-NL), 設(shè)隨機運動、鏈?zhǔn)竭\動、領(lǐng)導(dǎo)運動每一維更新位置時間都近似為λ4,式(7)的決策機制時間為λ5,計算位置更新后的適應(yīng)度并與最優(yōu)位置比較的時間為λ6,根據(jù)式(3)更新參數(shù)A的時間為λ7,則此階段時間復(fù)雜度為
T2(n)=O(N(1-NL)(nλ4+f(n)+λ5+λ6)+λ7)=
O(n+f(n))
在領(lǐng)導(dǎo)者更新階段,領(lǐng)導(dǎo)者個數(shù)為N×NL,設(shè)白骨頂雞領(lǐng)導(dǎo)者每一維位置更新所需的時間為λ8,計算位置更新后的適應(yīng)度并與最優(yōu)位置比較的時間也為λ6,根據(jù)式(9)更新參數(shù)B的時間為λ9,則這一階段的時間復(fù)雜度為
T3(n)=O((N×NL)(nλ8+f(n)+λ6)+λ9)=
O(n+f(n))
由此,COOT算法總時間復(fù)雜度為
T(n)=T1(n)+M(T2(n)+T3(n))=O(n+f(n))
在LHCOOT中,在初始化階段,引入了拉丁超立方體抽樣初始化種群,相較于均勻分布初始化種群,算法時間復(fù)雜度保持不變,即T′1=T1; 在普通個體更新階段,設(shè)引入非線性決策因子時間為t1,貪婪策略的時間為t2,自適應(yīng)動態(tài)邊界包含在隨機運動更新位置時間仍然為λ4,因此LHCOOT算法這一階段的復(fù)雜度為
T′2(n)=O(N(1-NL)(n(λ4+t1)+f(n)+
λ5+λ6+t2)+λ7)=O(n+f(n))
在領(lǐng)導(dǎo)者更新階段,設(shè)柯西擾動的時間為t3,貪婪策略的時間仍為t2,則該階段時間復(fù)雜度為
T′3(n)=O((N×NL)(nλ8+f(n)+λ6)+λ9+
t2+t3)=O(n+f(n))
因此,LHCOOT算法總時間復(fù)雜度為
T′(n)=T′1(n)+M(T′2(n)+T′3(n))=O(n+f(n))
綜上所述,與COOT算法相比,LHCOOT算法所引入的改進策略并不會增加算法時間復(fù)雜度。
本文采用的仿真軟件為MATLAB 2015b,實驗環(huán)境為i7-10750H CPU,2.69 GHz主頻,16 GB運行內(nèi)存,操作系統(tǒng)為Windows 10(64位)。
選取粒子群算法(particle swarm optimization,PSO)、金豺優(yōu)化算法(golden jackal optimization,GJO)、樽海鞘群算法(salp swarm slgorithm,SSA)、白骨頂雞算法(COOT)、添加非線性決策因子的白骨頂雞算法(NDFCOOT)、融合Tent映射和萊維飛行的改進白骨頂雞算法[18](COOTTLCR)與本文LHCOOT算法進行對比實驗,上述算法統(tǒng)一最大迭代次數(shù)為500,種群規(guī)模為30,為降低算法結(jié)果偶然性,皆獨立運行30次。各算法參數(shù)設(shè)置見表1。
表1 對比算法參數(shù)設(shè)置
為了檢驗LHCOOT算法的尋優(yōu)能力,本文選取文獻[18]中的16個基準(zhǔn)測試函數(shù)進行仿真驗證,分別是單峰測試函數(shù)中的f1~f7,多峰測試函數(shù)中的f8~f13,固定維測試函數(shù)中具有代表性的f20、f22、f23,其中單峰與多峰測試函數(shù)維度為30。
表2中的平均值和標(biāo)準(zhǔn)差分別反映出算法的尋優(yōu)能力和穩(wěn)定性。對于單峰測試函數(shù),LHCOOT算法在f1~f4函數(shù)上遠優(yōu)于其它算法,能夠100%尋到函數(shù)的理論最優(yōu)值。在測試函數(shù)f6上LHCOOT算法僅僅以微弱的差距次于SSA算法。在f5與f7測試函數(shù)上,LHCOOT算法也都優(yōu)于其余元啟發(fā)式算法。LHCOOT算法對單峰函數(shù)良好的尋優(yōu)效果體現(xiàn)了其有著出色的全局搜索能力。
表2 基準(zhǔn)測試函數(shù)尋優(yōu)結(jié)果對比
對于多峰測試函數(shù),LHCOOT算法在尋優(yōu)精度上均優(yōu)于其它算法。其中,在函數(shù)f9、f11上,LHCOOT算法達到了100%的尋優(yōu)率。在函數(shù)f12、f13上,LHCOOT算法的尋優(yōu)精度遠遠高于其它元啟發(fā)式算法,超過了2~3倍數(shù)量級的尋優(yōu)精度。在函數(shù)f8上,LHCOOT算法雖然標(biāo)準(zhǔn)差稍次于COOTTLCR算法,但尋優(yōu)精度仍然保持最優(yōu)。對于固定維度測試函數(shù),在函數(shù)f14上,LHCOOT算法僅次于COOTTLCR算法,且已較接近理論最優(yōu)值。在函數(shù)f15、f16上,LHCOOT算法也保持著最好的尋優(yōu)精度。
相較于COOT算法,NDFCOOT算法與LHCOOT算法在f1~f4以及f6函數(shù)上都取得了明顯得進步,說明引入非線性決策因子,可以提高算法的全局搜索能力,加快算法收斂。而在多峰函數(shù)上NDFCOOT算法表現(xiàn)不佳,說明單一的非線性決策因子策略對后期跳出局部最優(yōu)幫助較低。而添加了柯西變異的LHCOOT算法,可以有效解決多峰函數(shù)上陷入局部極值點的問題。
綜上,LHCOOT算法在選取的測試函數(shù)上的表現(xiàn)優(yōu)于其它6種算法,驗證了算法良好的搜索能力和尋優(yōu)精度。
為了更清晰刻畫算法的動態(tài)尋優(yōu)性能,圖5給出了PSO、SSA、GJO、NDFCOOT、COOTTLCR、COOT、LHCOOT這7種算法在上述基準(zhǔn)測試函數(shù)(部分)的收斂曲線。從選擇出的9個測試函數(shù)的收斂曲線上,可以看出LHCOOT算法比標(biāo)準(zhǔn)的COOT算法以及其余各個算法收斂速度更快,收斂精度更高。
圖5 對比算法收斂曲線
其中,函數(shù)f1和f2尋優(yōu)效果遠遠好于其它算法,分別迭代了150次和340次便成功找到理論最優(yōu)值。這歸功于拉丁超立方體抽樣的非重疊采樣和全覆蓋采樣,使得初始種群多樣性遠高于其它算法的隨機初始化種群,有效加速算法收斂速度和收斂精度。在函數(shù)f7、f8、f9和f10上,雖然LHCOOT算法尋優(yōu)精度優(yōu)勢微弱,但收斂速度均為第一,收斂曲線在迭代前期便能迅速下降。在函數(shù)f6上,雖然收斂精度略次于SSA算法,但收斂速度在前期遠遠超過SSA算法。這表明自適應(yīng)動態(tài)邊界機制,生成的邊界空間可以動態(tài)跟隨種群的變化,大大加快算法收斂速度。同時依賴于非線性決策因子有效平衡了算法全局搜索和局部開發(fā)過程,增強了算法的尋優(yōu)能力。
在多峰測試函數(shù)f12上,LHCOOT算法在500次迭代結(jié)束時仍然保持著收斂狀態(tài),尋優(yōu)精度仍會隨著迭代次數(shù)增加而增加。相較于GJO算法和COOT算法等過早陷入局部最優(yōu),收斂精度提升緩慢甚至停滯,LHCOOT算法由于對最優(yōu)解使用了柯西擾動策略,逃離局部最優(yōu)能力顯著增加。
通過綜合對比分析,相較于其它6種元啟發(fā)式算法,LHCOOT算法的收斂速度和收斂精度占優(yōu),且有著較好逃離局部最優(yōu)能力。
為了檢驗算法在高維度、大規(guī)模問題下的尋優(yōu)能力,選擇LHCOOT算法與PSO、SSA、GJO、COOT算法對比。對表1中的單峰函數(shù)f1~f4和多峰函數(shù)f11~f13這7個基準(zhǔn)測試函數(shù)在維度D=50/100/300時進行尋優(yōu)。得出的實驗結(jié)果見表3。
表3 不同維度對比結(jié)果
從實驗結(jié)果可以看出,在各種高維情況下的單峰測試函數(shù)和多峰測試函數(shù),LHCOOT算法的尋優(yōu)精度均高于PSO、SSA、GJO、COOT算法。
對于單峰測試函數(shù),LHCOOT算法在50/100/300維中,都能夠收斂到理論最優(yōu)值,且標(biāo)準(zhǔn)差皆為0,體現(xiàn)了算法良好的魯棒性和尋優(yōu)能力。而其它4種算法在一定程度上收斂精度會隨著維度的增加而降低。由此可見,LHCOOT算法在求解單峰問題上未陷入“維數(shù)災(zāi)難”。
對于多峰測試函數(shù),在函數(shù)f11上,LHCOOT算法取得了不錯的收斂精度,且收斂精度與30維條件下一致,可見算法對高維度、大規(guī)模問題具有不錯的魯棒性。在函數(shù)f12、f13上,雖然LHCOOT算法的收斂精度和標(biāo)準(zhǔn)差未達到理想值,但收斂精度仍然高出其余各算法1~5個數(shù)量級不等。體現(xiàn)了LHCOOT算法具有良好的全局搜索和局部開發(fā)能力。
綜上所述,LHCOOT算法在解決高維度、大規(guī)模問題時,對維度的變化不敏感,仍然保證了良好的尋優(yōu)精度。其算法魯棒性、尋優(yōu)能力均優(yōu)于其余4種算法。
秩和檢驗又稱為維爾克松兩樣本檢驗,是一種非參數(shù)統(tǒng)計檢驗??梢宰鳛樗惴ㄐ阅艿脑u價指標(biāo)之一,用于驗證算法之間是否存在顯著差異。本文基于上文的16個基準(zhǔn)測試函數(shù),采用顯著水平p=5%情況下的秩和檢驗對LHCOOT算法與6種原啟發(fā)式算法(PSO、SSA、GJO、NDFCOOT、COOTTLCR、COOT)進行差異性檢驗。當(dāng)p<5%時,記為“+”,表示LHCOOT算法優(yōu)于對比算法;當(dāng)p>5%時,記為“-”,表示LHCOOT算法劣于對比算法;當(dāng)p為“NaN”時,表示不適應(yīng)于顯著性判斷,LHCOOT算法顯著性與對比算法相近。對比結(jié)果見表4,在各算法對比中,大多數(shù)的秩和檢驗p值小于顯著水平5%,表示LHCOOT算法整體上與其它算法具有顯著性差異,即LHCOOT算法具有更好的尋優(yōu)性能。
表4 秩和檢驗p值
為進一步驗證LHCOOT算法在處理實際工程優(yōu)化問題的可行性和有效性。本節(jié)使用標(biāo)準(zhǔn)焊接梁設(shè)計問題作為參考驗證。
焊接梁設(shè)計問題屬于典型的非線性規(guī)劃問題。在滿足設(shè)計變量的邊界條件和剪切應(yīng)力τ、彎曲應(yīng)力σ、梁條屈曲載荷Pc、末端偏差δ這4個工程約束指標(biāo)下盡可能降低焊接梁設(shè)計的制造成本。本節(jié)采用死刑懲罰函數(shù)機制作為非線性約束[19]。4個設(shè)計變量分別是焊縫寬度h、橫梁長度l、高度d和厚度b。
設(shè)計變量如式(15)所示
x=[x1,x2,x3,x4]=[h,l,d,b]
(15)
目標(biāo)函數(shù)如式(16)所示
(16)
約束條件如式(17)所示
(17)
式中:τmax=136000 psi,σmax=3000 psi,δmax=0.25 in,P、L、E、G為焊接梁問題工程常量,P=6000 lb,L=14 in,E=3×106psi,G=1.2×107psi。psi:磅平方英寸,lb:磅,in:英尺。
表5統(tǒng)計了LHCOOT算法與粒子群算法(PSO)、算數(shù)優(yōu)化算法(arithmetic optimization algorithm,AOA)[10]、海洋捕食者算法(marine predators algorithm,MPA)[20]、金豺優(yōu)化算法(GJO)[4]、斑點鬣狗優(yōu)化算法(spotted hyena optimizer,SHO)、變色龍群算法(chameleon swarm algorithm,CSA)[21]在求解焊接梁設(shè)計問題的4個設(shè)計變量和制造成本。從表中可以看出,LHCOOT算法的焊接梁制造成本最低,說明LHCOOT算法在求解此類工程問題的尋優(yōu)精度較高,進一步驗證了算法在實際應(yīng)用中的優(yōu)越性。
表5 焊接梁設(shè)計問題仿真結(jié)果
針對COOT算法的尋優(yōu)精度低,易陷入局部最優(yōu)等問題,提出了基于拉丁超立方體的改進白骨頂雞算法。利用拉丁超立方體抽樣使白骨頂雞初始種群更加均勻化;引入非線性決策因子和自適應(yīng)動態(tài)邊界的混合位置更新策略以完善3種運動的執(zhí)行機制,權(quán)衡算法全局搜索和局部開發(fā)過程;最后引入柯西變異和貪婪策略對最優(yōu)位置進行擾動,避免算法過早收斂。通過對16個基準(zhǔn)測試函數(shù)、部分高維函數(shù)以及算法秩和檢驗的實驗,表明LHCOOT算法在收斂速度、收斂精度以及逃離局部最優(yōu)的能力均有了不同程度的提升。通過實際工程優(yōu)化問題驗證算法在解決工程問題上的可行性。在下一步工作中,將考慮把算法應(yīng)用到深度學(xué)習(xí)領(lǐng)域,結(jié)合神經(jīng)網(wǎng)絡(luò)進行風(fēng)電功率的短期預(yù)測[22],拓展算法的實用價值。