基于拉丁超立方體的改進白骨頂雞算法

何星月，張 靖，覃 濤，何必濤，楊 靖+

(1.貴州大學 電氣工程學院，貴州 貴陽 550025；2.中國電建集團 貴州工程有限公司，貴州 貴陽 550025)

0 引 言

元啟發(fā)式算法是對自然界的生物現(xiàn)象或物理現(xiàn)象進行模擬，可以在高維且復雜的約束條件下快速地找到問題的全局最優(yōu)解。近年來一系列的元啟發(fā)式算法被提出[1-4]，這些算法被廣泛的應用于圖像分割、參數(shù)估計、特征選擇等領域[5-9]。

白骨頂雞算法由Iraj Naruei等[10]提出。通過對白骨頂雞的隨機運動、鏈式運動和領導運動等行為的模擬，構建出一種有效的尋優(yōu)機制。相較于傳統(tǒng)算法，白骨頂雞算法具有結構簡單、性能穩(wěn)定等優(yōu)點，但仍存在收斂速度慢、易陷入局部最優(yōu)等不足。

為改善上述缺陷，國內(nèi)外學者們提出了不同的改進策略。文獻[11]提出了一種刺激-響應機制，根據(jù)響應閾值，使蜜蜂在跟隨蜂和雇傭蜂之間轉換，以平衡算法的搜索與開發(fā)能力。文獻[12]根據(jù)三角形相似性原理提出了動態(tài)演化理論，以增強麻雀算法后期的開發(fā)能力。文獻[13]利用差分進化思想，在樽海鞘領導者位置更新中引入變異算子，幫助算法在后期跳出局部最優(yōu)。文獻[14]通過對正余弦算法搜索方程中引入社交和認知成分，結合灰狼算法良好勘探和開發(fā)平衡能力優(yōu)化了算法的尋優(yōu)性能。

為進一步提高算法尋優(yōu)精度及工程應用價值，本文提出了基于拉丁超立方體的改進白骨頂雞算法(improved COOT algorithm based on Latin Hypercube，LHCOOT)。首先利用拉丁超立方體抽樣使種群分布更加均勻；引入非線性決策因子以權衡算法全局搜索和局部開發(fā)過程；采取動態(tài)邊界機制，加速算法收斂；對最優(yōu)個體進行柯西擾動并引入貪婪策略，避免算法陷入局部最優(yōu)。通過對16個基準函數(shù)、高維函數(shù)和實際工程問題進行仿真實驗，驗證了LHCOOT算法的有效性。

1 白骨頂雞算法COOT

白骨頂雞是一種小型水鳥，在水面上有許多不同的群體行為，包括普通個體的隨機運動、鏈式運動、引導運動以及領導者運動。該算法的具體步驟如下：

普通個體運動：該過程主要由3種運動狀態(tài)構成，執(zhí)行機制如式(1)所示

(1)

式中：Rb、Rc為常量0.5。lead、chain、random表示引導運動、鏈式運動和隨機運動，分別如式(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為領導者的索引，為普通個體分配領導者，如式(5)所示

K=1+(iMODNL)

(5)

式中：i是普通個體索引，NL為領導者的數(shù)量。

領導者運動：該運動根據(jù)式(6)，利用最優(yōu)個體牽引領導者，幫助種群向最優(yōu)區(qū)域收斂

(6)

式中：gBest是當前最優(yōu)個體位置，R3和R4是[0，1]中的隨機數(shù)。

2 改進白骨頂雞算法LHCOOT

2.1 基于拉丁超立方體的初始化種群

元啟發(fā)式算法的收斂速度和收斂精度通常與初始種群的分布結構息息相關。COOT算法以隨機方式生成的初始種群會導致個體在求解空間分布不均，影響初始種群的多樣性。相較于傳統(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為一個拉丁超立方體樣本。

假設搜索空間為2維，搜索范圍為(0，1)。隨機種群初始化和拉丁超立方體初始化分布如圖1所示。

圖1 初始化種群分布

從圖1可以觀察到，隨機種群初始化個體粘連嚴重，均勻性不佳。拉丁超立方體初始化分布在整個解空間，且均勻分散在每個坐標區(qū)間。因此，拉丁超立方體抽樣能有效提高初始種群多樣性，有助于加快算法收斂速度。

2.2 混合位置更新策略

2.2.1 非線性決策因子

是否能合理地平衡算法全局搜索和局部開發(fā)能力將直接影響算法的尋優(yōu)能力。在COOT算法中，隨機運動將會在解空間生成一個隨機解，引導白骨頂雞位置更新。鏈式運動將兩個相鄰索引個體的平均位置作為更新位置。因此，鏈式運動幫助種群向同一方向匯聚，適合在算法前期加速算法收斂。而隨機運動在整個解空間生成一個隨機解，牽引算法跳出局部最優(yōu)。兩種位置更新的執(zhí)行機制如式(8)所示

(8)

因此，等于0.5的常量Rc，是控制算法全局搜索能力和局部開發(fā)能力的決策因子。常量型決策因子并不能適用于解決復雜高維的實際工程問題。因此，本文采用一種非線性決策因子，令算法在前期緩慢衰減，增大執(zhí)行鏈式運動的概率，幫助算法快速收斂。在算法后期迅速衰減，增大執(zhí)行隨機運動的概率，從而幫助算法跳出局部最優(yōu)。非線性決策因子的數(shù)學模型如式(9)所示

(9)

式中：Rv0為決策因子初值，本文取為1，t是模型控制因子，t的取值控制模型的衰減速度，t值越大，模型的衰減速度越慢。不同t值下非線性決策因子模型及常量0.5對比如圖2所示。

圖2 決策因子曲線

當決策因子曲線在常量0.5上方時，算法會以大概率執(zhí)行鏈式運動。反之，會以大概率執(zhí)行隨機運動。經(jīng)多次實驗驗證，當t取10時，算法效果最佳。

2.2.2 自適應動態(tài)邊界

COOT算法在執(zhí)行隨機運動時，會在整個搜索空間中生成隨機解。如果該搜索空間不隨著迭代過程而相應收斂，將會增大尋優(yōu)過程的盲目性和復雜度，造成算法收斂遲滯，迭代時間增加。因此，本文引入了自適應動態(tài)邊界機制，加快算法收斂速度。動態(tài)邊界的上下界如式(10)所示

UB=α×max(X)
LB=α×min(X)

(10)

式中：X為整個種群的位置矩陣，α為自適應映射系數(shù)，如式(11)所示

α=1+0.2×(eL/Iter-1)

(11)

式中：L是當前迭代次數(shù)，Iter是最大迭代次數(shù)。隨機位置Q的生成如式(12)所示

Q=rand(1，d)×(UB-LB)+LB

(12)

從式(12)可以看出，邊界將隨著種群的移動而動態(tài)跟隨，隨著種群的收斂而相應縮小。同時，為了避免迭代后期，種群收斂陷入局部最優(yōu)，將動態(tài)邊界通過隨著迭代次數(shù)增大的映射系數(shù)放大，增加動態(tài)牽引力度，從而增大跳出局部最優(yōu)的概率。相較于逐維更新的動態(tài)邊界，利用種群確定邊界，可以避免不同維度間的相互干擾，提供一定裕量，提高尋優(yōu)能力。

2.3 柯西變異

領導者的迭代更新由最優(yōu)個體引導，向著最優(yōu)位置靠近，導致算法后期種群多樣性降低，算法易陷入局部最優(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ōu)保留。貪婪策略的數(shù)學模型如式(14)所示

(14)

式中：f為適應度函數(shù)。

2.4 改進算法流程圖

綜合上述改進策略，LHCOOT的算法流程如圖4所示。

圖4 算法流程

2.5 時間復雜度分析

時間復雜度作為評價算法性能的指標之一，可以間接反映算法的尋優(yōu)效率。設標準白骨頂雞算法種群數(shù)量為N，搜索空間維度為n，最大迭代次數(shù)為M，領導雞群比例為NL，求解目標函數(shù)適應度時間為f(n)。 假設初始化參數(shù)時間為λ1，每一維產(chǎn)生服從均勻分布隨機數(shù)的時間為λ2，找到并保存適應度最佳個體位置的時間為λ3，則算法總體初始化階段的時間復雜度為

T1(n)=O(λ1+N(nλ2+f(n))+λ3)=O(n+f(n))

在迭代過程中，普通個體更新階段，普通個體個數(shù)為N(1-NL)， 設隨機運動、鏈式運動、領導運動每一維更新位置時間都近似為λ4，式(7)的決策機制時間為λ5，計算位置更新后的適應度并與最優(yōu)位置比較的時間為λ6，根據(jù)式(3)更新參數(shù)A的時間為λ7，則此階段時間復雜度為

T2(n)=O(N(1-NL)(nλ4+f(n)+λ5+λ6)+λ7)=
O(n+f(n))

在領導者更新階段，領導者個數(shù)為N×NL，設白骨頂雞領導者每一維位置更新所需的時間為λ8，計算位置更新后的適應度并與最優(yōu)位置比較的時間也為λ6，根據(jù)式(9)更新參數(shù)B的時間為λ9，則這一階段的時間復雜度為

T3(n)=O((N×NL)(nλ8+f(n)+λ6)+λ9)=
O(n+f(n))

由此，COOT算法總時間復雜度為

T(n)=T1(n)+M(T2(n)+T3(n))=O(n+f(n))

在LHCOOT中，在初始化階段，引入了拉丁超立方體抽樣初始化種群，相較于均勻分布初始化種群，算法時間復雜度保持不變，即T′1=T1； 在普通個體更新階段，設引入非線性決策因子時間為t1，貪婪策略的時間為t2，自適應動態(tài)邊界包含在隨機運動更新位置時間仍然為λ4，因此LHCOOT算法這一階段的復雜度為

T′2(n)=O(N(1-NL)(n(λ4+t1)+f(n)+
λ5+λ6+t2)+λ7)=O(n+f(n))

在領導者更新階段，設柯西擾動的時間為t3，貪婪策略的時間仍為t2，則該階段時間復雜度為

T′3(n)=O((N×NL)(nλ8+f(n)+λ6)+λ9+
t2+t3)=O(n+f(n))

因此，LHCOOT算法總時間復雜度為

T′(n)=T′1(n)+M(T′2(n)+T′3(n))=O(n+f(n))

綜上所述，與COOT算法相比，LHCOOT算法所引入的改進策略并不會增加算法時間復雜度。

3 實驗結果及分析

3.1 對比算法及參數(shù)設置

本文采用的仿真軟件為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，為降低算法結果偶然性，皆獨立運行30次。各算法參數(shù)設置見表1。

表1 對比算法參數(shù)設置

3.2 測試函數(shù)

為了檢驗LHCOOT算法的尋優(yōu)能力，本文選取文獻[18]中的16個基準測試函數(shù)進行仿真驗證，分別是單峰測試函數(shù)中的f1～f7，多峰測試函數(shù)中的f8～f13，固定維測試函數(shù)中具有代表性的f20、f22、f23，其中單峰與多峰測試函數(shù)維度為30。

3.3 尋優(yōu)精度分析

表2中的平均值和標準差分別反映出算法的尋優(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 基準測試函數(shù)尋優(yōu)結果對比

對于多峰測試函數(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算法雖然標準差稍次于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)精度。

3.4 算法收斂曲線

為了更清晰刻畫算法的動態(tài)尋優(yōu)性能，圖5給出了PSO、SSA、GJO、NDFCOOT、COOTTLCR、COOT、LHCOOT這7種算法在上述基準測試函數(shù)(部分)的收斂曲線。從選擇出的9個測試函數(shù)的收斂曲線上，可以看出LHCOOT算法比標準的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算法。這表明自適應動態(tài)邊界機制，生成的邊界空間可以動態(tài)跟隨種群的變化，大大加快算法收斂速度。同時依賴于非線性決策因子有效平衡了算法全局搜索和局部開發(fā)過程，增強了算法的尋優(yōu)能力。

在多峰測試函數(shù)f12上，LHCOOT算法在500次迭代結束時仍然保持著收斂狀態(tài)，尋優(yōu)精度仍會隨著迭代次數(shù)增加而增加。相較于GJO算法和COOT算法等過早陷入局部最優(yōu)，收斂精度提升緩慢甚至停滯，LHCOOT算法由于對最優(yōu)解使用了柯西擾動策略，逃離局部最優(yōu)能力顯著增加。

通過綜合對比分析，相較于其它6種元啟發(fā)式算法，LHCOOT算法的收斂速度和收斂精度占優(yōu)，且有著較好逃離局部最優(yōu)能力。

3.5 不同維度下算法對比分析

為了檢驗算法在高維度、大規(guī)模問題下的尋優(yōu)能力，選擇LHCOOT算法與PSO、SSA、GJO、COOT算法對比。對表1中的單峰函數(shù)f1～f4和多峰函數(shù)f11～f13這7個基準測試函數(shù)在維度D=50/100/300時進行尋優(yōu)。得出的實驗結果見表3。

表3 不同維度對比結果

從實驗結果可以看出，在各種高維情況下的單峰測試函數(shù)和多峰測試函數(shù)，LHCOOT算法的尋優(yōu)精度均高于PSO、SSA、GJO、COOT算法。

對于單峰測試函數(shù)，LHCOOT算法在50/100/300維中，都能夠收斂到理論最優(yōu)值，且標準差皆為0，體現(xiàn)了算法良好的魯棒性和尋優(yōu)能力。而其它4種算法在一定程度上收斂精度會隨著維度的增加而降低。由此可見，LHCOOT算法在求解單峰問題上未陷入“維數(shù)災難”。

對于多峰測試函數(shù)，在函數(shù)f11上，LHCOOT算法取得了不錯的收斂精度，且收斂精度與30維條件下一致，可見算法對高維度、大規(guī)模問題具有不錯的魯棒性。在函數(shù)f12、f13上，雖然LHCOOT算法的收斂精度和標準差未達到理想值，但收斂精度仍然高出其余各算法1～5個數(shù)量級不等。體現(xiàn)了LHCOOT算法具有良好的全局搜索和局部開發(fā)能力。

綜上所述，LHCOOT算法在解決高維度、大規(guī)模問題時，對維度的變化不敏感，仍然保證了良好的尋優(yōu)精度。其算法魯棒性、尋優(yōu)能力均優(yōu)于其余4種算法。

3.6 Wilcoxon秩和檢驗

秩和檢驗又稱為維爾克松兩樣本檢驗，是一種非參數(shù)統(tǒng)計檢驗?？梢宰鳛樗惴ㄐ阅艿脑u價指標之一，用于驗證算法之間是否存在顯著差異。本文基于上文的16個基準測試函數(shù)，采用顯著水平p=5%情況下的秩和檢驗對LHCOOT算法與6種原啟發(fā)式算法(PSO、SSA、GJO、NDFCOOT、COOTTLCR、COOT)進行差異性檢驗。當p<5%時，記為“+”，表示LHCOOT算法優(yōu)于對比算法；當p>5%時，記為“-”，表示LHCOOT算法劣于對比算法；當p為“NaN”時，表示不適應于顯著性判斷，LHCOOT算法顯著性與對比算法相近。對比結果見表4，在各算法對比中，大多數(shù)的秩和檢驗p值小于顯著水平5%，表示LHCOOT算法整體上與其它算法具有顯著性差異，即LHCOOT算法具有更好的尋優(yōu)性能。

表4 秩和檢驗p值

4 工程問題應用分析

為進一步驗證LHCOOT算法在處理實際工程優(yōu)化問題的可行性和有效性。本節(jié)使用標準焊接梁設計問題作為參考驗證。

焊接梁設計問題屬于典型的非線性規(guī)劃問題。在滿足設計變量的邊界條件和剪切應力τ、彎曲應力σ、梁條屈曲載荷Pc、末端偏差δ這4個工程約束指標下盡可能降低焊接梁設計的制造成本。本節(jié)采用死刑懲罰函數(shù)機制作為非線性約束[19]。4個設計變量分別是焊縫寬度h、橫梁長度l、高度d和厚度b。

設計變量如式(15)所示

x=[x1，x2，x3，x4]=[h，l，d，b]

(15)

目標函數(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]在求解焊接梁設計問題的4個設計變量和制造成本。從表中可以看出，LHCOOT算法的焊接梁制造成本最低，說明LHCOOT算法在求解此類工程問題的尋優(yōu)精度較高，進一步驗證了算法在實際應用中的優(yōu)越性。

表5 焊接梁設計問題仿真結果

5 結束語

針對COOT算法的尋優(yōu)精度低，易陷入局部最優(yōu)等問題，提出了基于拉丁超立方體的改進白骨頂雞算法。利用拉丁超立方體抽樣使白骨頂雞初始種群更加均勻化；引入非線性決策因子和自適應動態(tài)邊界的混合位置更新策略以完善3種運動的執(zhí)行機制，權衡算法全局搜索和局部開發(fā)過程；最后引入柯西變異和貪婪策略對最優(yōu)位置進行擾動，避免算法過早收斂。通過對16個基準測試函數(shù)、部分高維函數(shù)以及算法秩和檢驗的實驗，表明LHCOOT算法在收斂速度、收斂精度以及逃離局部最優(yōu)的能力均有了不同程度的提升。通過實際工程優(yōu)化問題驗證算法在解決工程問題上的可行性。在下一步工作中，將考慮把算法應用到深度學習領域，結合神經(jīng)網(wǎng)絡進行風電功率的短期預測[22]，拓展算法的實用價值。