灰狼與郊狼混合優化算法及其聚類優化

張新明 姜云 劉尚旺 劉國奇 竇智 劉艷

在現實世界中,無時無處無不面臨著優化問題.隨著社會的發展,急需處理的優化問題越來越多樣化并越來越復雜.而諸如牛頓法、梯度下降法等傳統的方法不能夠很好地處理這些急需解決的優化問題.因此,許多研究者建立了各種仿生類的智能計算模型,提出了許多智能優化算法.群智能優化算法(Swarm intelligence optimization algorithm,SIOA)是模擬自然界社會群體集體行為的一種智能優化方法[1],包括粒子群優化(Particle swarm optimization,PSO)算法[2]、灰狼優化算法(Grey wolf optimizer,GWO)[3]、郊狼優化算法(Coyote optimization algorithm,COA)[4]等.SIOA 具有易于實現、能有效處理全局優化和大規模優化問題等優勢,廣泛應用于多目標優化、數據聚類以及模式識別等諸多領域[5].但根據無免費午餐定理[6],沒有任何一種SIOA 能獨立地解決所有的優化問題,每種SIOA 都有自身的優勢和局限性.因此許多學者提出了大量新奇和改進的SIOA,其中包括算法的混合改進.兩種或多種算法的混合可以達到優勢互補,以獲得最佳的優化性能[7].

GWO 是由Mirjalili等[3]于2014 年提出的一種新穎的SIOA,具有原理簡單、開采能力強、可調參數少等優點,但存在易陷入局部最優、解決復雜優化問題性能差等缺點.因此許多學者對其進行了研究和改進,其中包括混合改進.例如張新明等[7]提出一種GWO 與人工蜂群算法的混合算法,其中在人工蜂群觀察蜂階段自適應融合GWO,以便增強開采能力和提高優化效率.Zhang等[8]提出一種基于生物地理學優化算法和GWO的混合算法,將改進的基于生物地理學優化算法和基于反向學習的GWO 混合,使得優化性能最大化.Teng等[9]提出一種PSO 與GWO 結合的混合算法,該算法具有更好的尋優能力和更強的魯棒性.Arora等[10]提出一種烏鴉搜索算法與GWO的混合算法,更有效地實現了全局優化.

COA 是由Pierezan等[4]于2018 年提出的一種模擬郊狼群居生活、成長、生死等現象的新型SIOA.COA 具有獨特的搜索模型和結構以及出色的優化能力,尤其在解決復雜優化問題優勢明顯,但仍存在搜索效率低、可操作性不強以及收斂速度慢等缺陷,且由于COA 提出的時間較短,需改進和完善并拓展其應用領域.鑒于GWO 和COA 各有優勢和不足,本文將兩種算法分別進行改進和簡化,得到改進的COA (Improved COA,ICOA)和簡化的GWO (Simplified GWO,SGWO),然后通過正弦交叉策略將ICOA 和SGWO 有機融合在一起,從而獲得了一種性能優越且高效的混合COA (Hybrid COA with GWO,HCOAG).另外,混合算法的研究一直是優化領域的熱點,因此研究GWO 與COA的混合是一項較有意義的工作.

1 灰狼優化算法

GWO 模擬了自然界中灰狼種群嚴格的社會等級制度和群體捕食行為.在其社會等級制度中,灰狼從高到低依次為α,β,δ,ω狼.其捕食行為是追蹤和接近獵物、追捕和包圍獵物、攻擊和捕殺獵物.GWO 將狼群中的α,β,δ,ω狼的位置分別代表第一最優解、第二最優解、第三最優解和候選解.灰狼包圍行為的數學模型為

其中,Dis是灰狼與獵物間的距離,t是當前迭代次數,Xp是獵物的位置向量,X是灰狼的位置向量.A和C是系數向量.系數a在迭代過程中從2線性遞減到0,MaxDT是最大迭代次數,r1和r2是[0,1]中的均勻分布隨機向量,c1為可調參數[11],?表示兩個向量各個對應的分量相乘.狩獵行為的數學模型為

其中,Disα,Disβ和Disδ分別表示當前狼與3 頭最優灰狼間的距離.式(12)代表ω狼在α,β和δ狼的引導下移動的新位置,即GWO 產生的新解.GWO的流程圖見圖1.

從上述描述和圖1 可知,與PSO 等經典的SIOA 相比,GWO的主要特點有:1)GWO 采用3 頭最優狼(最優解)引導ω狼圍獵,有較強的局部搜索能力,但在解決復雜優化問題時,容易陷入局部最優;2)GWO 僅有兩個參數a和c1,前者采用動態調整方式,后者c1常取常數2,調整的參數少,故可操作性強;3)原理簡單、易于實現,但更新是基于維的計算,需計算式(6)～(12),故計算復雜度較高;4)目標函數采用并行計算方式,故運行速度較快.

圖1 GWO的流程圖Fig.1 Flow chart of GWO

2 郊狼優化算法

COA 包含初始化參數和狼群、組內郊狼成長、郊狼生與死和被組驅離與接納[4]等4 個主要步驟.

2.1 參數初始化和隨機初始化郊狼群組

首先設置參數,如郊狼群規模N,郊狼組數Np,組內郊狼數Nc和MaxDT等,其中,N=Nc×Np.然后隨機初始化郊狼群組,第p組第c個郊狼第j維的隨機化操作如式(13).最后計算每頭郊狼soc的社會適應度值fit,如式(14).

其中,lbj和ubj分別表示郊狼第j維社會狀態因子的下界和上界,j=1,2,···,D,D為搜索空間的維度,r為[0,1]內均勻分布的隨機數,f表示適應度函數.

2.2 組內郊狼成長

組內最優狼alpha、組文化趨勢cult以及隨機選取的兩頭郊狼cr1和cr2影響組內郊狼的成長過程,即組內郊狼成長受δ1和δ2的影響.其中cult的計算如式(15)所示,即其每一個因素是組內所有郊狼對應社會因子的中位數(O為排名后的社會因子序列),故cult又稱中值郊狼.δ1和δ2計算見式(16)和式(17),郊狼的成長方式見式(18).

其中,new_socc是組內第c頭郊狼成長獲得的新解,r3和r4是[0,1]內均勻分布的隨機數.組內的郊狼成長后評估其社會適應能力如式(19)所示,new_fitc為新適應度值.

最后采用迭代貪心算法進行優勝劣汰(式(20)),如此新產生的更優郊狼參與組內其余郊狼成長以加快收斂速度.

2.3 郊狼生與死

幼郊狼 (pup)的誕生受隨機選擇父母郊狼的遺傳基因和環境因素的影響,見式(21)所示.

其中,rj是均勻分布在[0,1]內的隨機數;j1和j2是兩個隨機選擇的維度標號,以確保兩個父郊狼的基因能夠遺傳給幼狼;Rj是在第j維決策變量范圍內隨機產生的變異值;Ps和Pa分別是分散概率和關聯概率,它們決定著幼狼被遺傳和變異的情況,如式(22)和式(23)所示.

幼狼出生后,評估其社會適應能力,并依照其能力決定生與死,具體描述如下:在社會適應能力上,1)組內只有一個郊狼比幼狼差時,則此郊狼死亡,幼狼存活,并設它的年齡為0,即age=0;2)組內有多個郊狼比幼狼差時,能力差且年齡最大的郊狼死亡,幼狼存活,并設age=0;3)組內所有郊狼都比幼狼強時,幼狼死亡.

2.4 郊狼被驅離和接納

在COA 中,郊狼以Pe的概率被組驅離和接納.郊狼初始被隨機分配到組群中,但有時某些郊狼會離開它所在組群而加入另一組群,這種隨機驅離和接納用來保證組內郊狼的多樣性和組間信息共享,Pe的計算方式為

COA的偽代碼如算法1 所示.

算法1.COA 算法

從以上描述可知,與PSO 等經典的SIOA 相比,COA的主要優勢有:1)具有很好的搜索框架,即多組結構,郊狼隨機被組驅離和接納等使郊狼群具有多樣性,有較強的探索能力,能夠更好地解決復雜優化問題[12];2)組內最優郊狼和組內文化趨勢引導組內每個郊狼的成長,增強了局部搜索能力;3)郊狼組內的生與死受隨機選擇父郊狼的遺傳因子和環境變異因子影響,郊狼生與死算子使得COA具有一定的全局搜索能力.其主要不足有:1)結構復雜,計算復雜度高;2)采用迭代貪心算法,穩定性差,效率低;3)需調整的參數多,如Pe,Np和Nc等需調整,可操作性差;4)多組結構等雖然增強了探索能力,但組與組之間信息共享不足,導致搜索后期收斂速度慢.

3 灰狼與郊狼混合優化算法

3.1 提出HCOAG的動機

COA 與GWO 雖然同屬狼群算法,但二者有許多不同.如在搜索方式上,前者模擬郊狼的成長、生與死,而后者模擬灰狼的等級制度和狩獵模式;在引導上,前者僅僅使用一頭最好的狼來引導其它狼成長,而后者使用3 頭最優狼來引導其它狼搜索;在結構上,前者復雜,后者簡單;在產生新解方式上,前者有兩種方式,后者只有一種方式等等.因此,COA 和GWO 各有優勢和不足.為了彌補二者不足,本文將COA 和GWO 兩種狼群算法經過改進后進行了有機結合,從而獲得一種性能優越且高效的混合算法(HCOAG).

3.2 改進的郊狼優化算法

ICOA 主要包括高斯全局趨優成長算子和動態調整組內郊狼數方案.

3.2.1 高斯全局趨優成長算子

為了提高郊狼成長后的社會適應能力、組與組之間的信息共享程度及算法收斂速度,受Omran等[13]提出的全局最優和聲搜索算法中趨優策略及高斯分布的啟發,對其組內郊狼成長方式進行改進,提出一種高斯全局趨優成長算子.全局趨優算子充分利用郊狼種群當前全局最優郊狼的狀態信息,使郊狼成長向當前全局最優郊狼趨近,提高開采能力,也使得組內信息經全局最優解達到組間共享.高斯分布又稱為正態分布,與COA的均勻隨機分布[0,1]相比,可以增加搜索范圍,在一定程度上增強全局搜索能力.

在組內郊狼成長過程中,在式(18)中引入趨優算子和高斯分布隨機因子,具體見式(25)和式(26).

式(25)中,GP為當前全局最優郊狼的狀態,δ3表示組內隨機選取的一個郊狼狀態 (cr1)與GP的差值.式(26)中,rn1和rn2是均值為0、方差為1的高斯(正態)分布產生的隨機數,new_soc1表示每頭郊狼在δ2和δ3的共同作用下成長產生的新狀態(新解).

從式(25)和式(26)可以看出,與COA 相比,在搜索前期,個體間差異大,縮放因子(高斯隨機數)變化范圍大,故增強了探索能力.在搜索后期,雖然還是采用高斯隨機數,但個體間差異小,δ2和δ3的值變小,故搜索范圍變小,強化開采能力.且由于采用全局最優解引導,故更增強了開采能力,同時上一組獲得的全局最優解,會作用于下一組的郊狼成長,如此形成一種信息共享的正反饋作用,大幅度加快了收斂速度.另外,所有組內郊狼成長后并行計算它們的適應度值和優勝劣汰,提高了運行速度和穩定性.

3.2.2 動態調整組內郊狼數方案

如上文所述,COA 有多個參數需要調整,可操作性差.對于以上改進的COA,主要有兩個參數Nc和Np對優化性能影響較大.在N固定下,如果Nc確定,則Np=N/Nc,即Np越大,Nc越少,成長操作少,但全局解的作用逐組增強,開采強;反之,成長操作多,Np少,全局解的作用減弱,開采弱.為了提高COA的可操作性,本文對Np和Nc參數進行動態調整.設N=100,則Np和Nc必須為100的因子,依據文獻[4],每組郊狼數不能超過14,所以Nc只能為4、5 和10.由于Nc不能少于3,這是因為組內郊狼成長至少需要3 頭郊狼,包括隨機選取的兩頭郊狼和組內最優郊狼.當Nc=4 時可選郊狼范圍受限制,所以Nc最可能的取值為5 和10,故具體的分配方式如圖2 所示,動態調整參數方案如算法2 所示.

圖2 組數 N p 與組內郊狼數 N c的分配圖Fig.2 Disposition graph of two parameters N c andNp

算法2.動態調整參數Nc和Np

在搜索后期,Nc=5,則Np=20,組數多,增強全局解的正反饋作用,局部搜索能力增強;在搜索前期,Nc=10,則Np=10,組數少,減弱全局解的正反饋作用,全局搜索能力增強.因此,動態調整組內郊狼數參數不僅提高了可操作性,而且可以更好地平衡探索與開采能力.另外,在動態調整參數之后,隨機分組,如此可以省去郊狼被組驅離與接納這個過程,從而不需要調整參數Pe,因此提高了可操作性.

3.3 簡化的灰狼優化算法

為了進一步解決COA 存在搜索效率低和易陷入局部最優的問題,本文引入GWO 搜索方式.首先提出一種精簡的GWO 搜索方式,即將式(6)～(11)與COA 組內郊狼進行融合并簡化,具體如式(27)～(29).

其中,tempc表示當前組第c個郊狼的狀態.NX1,NX2和NX3表示組內郊狼分別在GP,alpha和cult的引導下獲得成長的情況.從式(27)～(29)可以看出,這3 個式子去掉了式(6)～(8)中的可調參數向量C,保留GWO的優勢并克服其不足,即在SGWO 中,去掉C,無需調整c1,也省略了向量C的相關計算.所以,這種簡化的GWO 在保證其有較強開采能力的同時,提高了可操作性并降低了計算復雜度.為了更進一步簡化計算,SGWO 直接采用COA 中的當前全局最優郊狼、組內最優郊狼和中值郊狼(組內文化趨勢)的引導尋找最優解,無需尋找組內的第二和第三最優郊狼,如此SGWO 與COA 達到了一種高效融合.為方便理解SGWO,關于GWO 中的灰狼等級情況與SGWO 中的等級情況的對比見圖3 所示.

圖3 GWO 與SGWO的等級情況對比Fig.3 Comparison of hierarchies of GWO and SGWO

3.4 正弦交叉混合策略

為了平衡COA 組內郊狼成長的探索與開采能力,本文采用正弦交叉策略將ICOA 與SGWO 有機混合.其中交叉策略是指在一定概率的情況下,兩個解進行交叉得到一個新解.當概率為零時,兩個解的維值不交換;當概率為1 時,兩個解的維值全部交換,這兩種情況都不能產生新解.因此只有概率為一個適當的值時,兩個解的交叉效果才會達到最好.其中使用正弦函數概率模型使得探索和開采都有良好的表現,即使用正弦函數自適應控制交叉概率CR(在0.5 附近前期小幅度波動,后期大幅度跳動)可以兼顧組內郊狼的多樣性和收斂性[14],其計算式為

本文采用的正弦交叉策略見算法3 所示,在rand＜CR的概率下,組內第c個郊狼D維中一些維的值采用SGWO 搜索方式獲取;反之,組郊狼的第c個郊狼D維中的其余維值采用高斯全局趨優成長算子獲取.這種交叉策略具有如下特點:1)增強了組內各類郊狼的信息交流;2)交叉兩個新解,二者的信息融合獲得有別二者的新解,增強了新解的多樣性,降低陷入局部最優的概率;3)前期在CR為0.5的附近小幅度波動,高斯全局趨優操作和GWO 操作以近似等概率的方式產生新解,多樣性強,強化探索能力;后期在CR為0.5的附近大幅度跳動,如此產生的新解以其中一種操作為主,多樣性降低,強化了開采能力.

算法3.正弦交叉策略

正弦交叉策略有機融合了兩種搜索方式,很好地平衡了成長過程的探索與開采能力.HCOAG的流程圖見圖4.

從圖4 可以看出,與COA 相比,HCOAG 主要有如下不同:1)成長方式采用正弦交叉策略融合高斯全局趨優方式和SGWO 方式;2)組內郊狼的適應度值采用并行計算;3)動態調整參數方案;4)丟棄了郊狼被組驅離與接納的過程.

圖4 HCOAG 流程圖Fig.4 Flow chart of HCOAG

4 函數優化實驗結果與分析

4.1 實驗環境配置及參數設置

為驗證HCOAG的有效性,本文采用經典基準函數和來自CEC2017的復雜函數進行優化實驗.CEC2017 包括單峰函數(F1～F3)、多峰函數(F4～F10)、混合函數(F11～F20)和復合函數(F21～F30),詳細情況見文獻[15].實驗環境采用主頻3.00 GHz的Inter(R)Core(TM)i5-7400 CPU 和內存8 GB的PC 機,操作系統采用64 位的Windows 10,編程語言采用MATLAB2017A.選取的對比算法包括GWO[3]、COA[4]、MEGWO (Multi-strategy ensemble GWO)[16]、DEBBO (Differential evolution and biogeography-based optimization)[17]、HFPSO(Hybrid firefly with PSO)[18]、SaDE (DE with strategy adaptation)[19]、SE04 (Spherical evolution)[20]、FWA (Fireworks algorithm)[21]和TLBO(Teaching-learning based optimization)[22].MEGWO 是最近提出的GWO 改進算法,文獻[16]表明它優于GWO 及其改進版以及其他的SIOA.DEBBO是DE 與BBO的混合算法,文獻[17]表明它優于DE 和BBO 及其他優秀的SIOA.HFPSO 是PSO和FA的混合算法,文獻[18]表明它優于PSO 和FA 等SIOA.SaDE 具有顯著優秀性能,文獻[19]表明SaDE 優于DE 等SIOA.SE04 是球形進化算法的變體之一,文獻[20]表明SE04 顯著優于GWO等算法.FWA 和TLBO 也是目前較為新型算法的代表.總之,這些對比算法具有較強的競爭性.

為公平起見,所有算法的公共參數設置相同.在CEC2017 上,依據文獻[15]的參數最佳推薦,D=30,最大函數評價次數10 000 ×D,獨立運行51 次.在經典函數的D=10 和D=30 上,MaxDT分別為100 和500,獨立運行30 次.依據文獻[4]的推薦,COA的最佳參數設置為:N=100,Nc=5,Np=20. HCOAG的N也設置為100,Np和Nc無需調整,算法其他參數采用相應文獻中推薦的最佳設置.

一般單峰函數用來考察一個算法的局部搜索能力,多峰函數考察其全局搜索能力,混合和復合函數考察其處理復雜問題的能力.本文采用均值(Mean)和方差(Std)分別評估一個算法的優化性能和穩定性.在解決極小值問題中,均值越小表示算法性能越好,方差越小表示算法穩定性越好.另外,還采用了排名(Rank)方法.其評價標準是先比較算法獲得的均值,均值越小算法名次越好;在均值相同的情況下,再比較方差,方差越小算法名次越好.結果表中的“Count”表示排名為第一的總次數,“Ave rank”表示平均排名情況,“Total rank”表示在“Ave rank”基礎上的總排名情況,最優者用加粗字體表示.

4.2 與不完全算法的對比分析

為驗證每個改進對HCOAG 優化性能的貢獻,將HCOAG 與其不完全算法HCOAG5(Nc=5和Np=20的HCOAG)、HCOAG10(Nc=10和Np=10的HCOAG)、ICOA、SGWO、GWO 和COA 在CEC2017的30 維函數上進行實驗,實驗結果如表1 所示.

從表1 中可以看出,HCOAG5在單峰函數上獲得最好的結果次數最多,表明Np增大,在提高郊狼生與死的全局搜索能力的同時,大幅度提高了COA的開采能力,即HCOAG5中高斯趨優成長和GWO 搜索都采用當前全局最優郊狼引導,不僅獲得更好的全局最優解,這種全局最優解又作用于下一組郊狼的成長過程,如此形成正反饋機制:Np越大,開采越強,收斂速度越快.但容易陷入局部最優,如在多峰函數上的表現不盡人意.HCOAG10在多峰函數上表現出了良好的優化性能,表明Np變少,在提高組內郊狼成長的局部搜索能力的同時,正反饋減弱,開采能力降低,即陷入局部最優的概率也降低了.ICOA 中沒有精簡的GWO,整體來說優于COA,表明對COA的改進是有效的.SGWO在整體上優于GWO,表明SGWO 提高了GWO搜索能力.與GWO 相比,COA的優化性能更好,即COA 能更好地處理復雜優化問題.在7 個算法中,HCOAG的平均排名為2.20,COA、GWO、HCOAG5、HCOAG10、ICOA 和SGWO的平均排名分別為5.23、6.87、3.10、2.60、3.07 和4.93,總排名的名次分別為6、7、4、2、3 和5.在HCOAG 與6 種對比算法中,HCOAG 獲得了最好的優化性能,這也說明本文提出的算法是有效的.

表1 HCOAG 與其不完全算法的結果對比Table 1 Comparison results of HCOAG and its incomplete algorithms

表1 HCOAG 與其不完全算法的結果對比 (續表)Table 1 Comparison results of HCOAG and its incomplete algorithms (continued table)

表1 HCOAG 與其不完全算法的結果對比 (續表)Table 1 Comparison results of HCOAG and its incomplete algorithms (continued table)

4.3 在經典函數上的優化性能對比

為驗證HCOAG的性能,首先將其用于經典函數的優化實驗,并將其結果與COA、GWO、HFPSO和DEBBO的結果進行對比,實驗結果見表2.

為了能說明問題,選擇6 個經典的、具有代表性的基準函數的實驗結果作為示例進行分析和討論,這6 個函數的信息如表3 所示,其中f1～f3和f4～f6分別作為單峰函數和多峰函數的代表.在此實驗中,由于HCOAG 是COA 和GWO的混合算法,故選擇COA 和GWO 作為對比算法.HFPSO和DEBBO 是目前兩種較為優秀的混合算法,故選為HCOAG的對比算法.

從表2 可以看出,在D=10和D=30 上,COA無論是在單峰還是在多峰函數上優化性能最差,說明COA 在處理這些經典函數優化問題上無優勢.在單峰函數的均值和方差上,除了f3外,GWO 均優于HCOAG 以及其他3 種對比算法,證明了GWO具有較好的開采能力.在多峰函數上,HCOAG的性能最佳,說明GWO 與全局搜索能力強的COA混合有效.

表2 在6 個經典函數上的實驗結果對比Table 2 Comparison results on the 6 classic functions

表3 6 個經典函數的情況Table 3 Details of 6 classical benchmark functions

從整體上看,在D=10和D=30 上,HCO-AG的總體平均排名為1.33,其他算法的平均排名依次為:HFPSO (2.50)、GWO (2.75)、DEBBO(2.92)和COA (5.00).這些結果表明,HCOAG 不是對所有優化問題都有絕對優勢,在單峰函數上優化性能稍差.而GWO 在單峰函數上具有優勢,對HCOAG的性能具有一定的貢獻.從整體上看,HCOAG 在經典函數上具有較好的優化性能.

為直觀顯示HCOAG、COA、GWO、HFPSO和DEBBO的收斂性能,給出了這5 個算法的收斂圖.限于篇幅,本節在D=30 上選取2 個單峰函數(f1和f2)和2 個多峰函數(f5和f6),如圖5 所示.在單峰函數上,與HCOAG、COA、HFPSO 和DEBBO算法相比,GWO 收斂速度更快,表現出更好的收斂性能.在多峰函數上,與COA、GWO、HFPSO和DEBBO 算法相比,HCOAG 表現出了更好的收斂性能.綜上所述,表2 和圖5 說明了GWO 具有較好的局部搜索能力和收斂性能,也部分證明了利用GWO 局部搜索能力強的優勢對COA的混合改進是必要和可行的.

圖5 HCOAG 與對比算法在4 個經典函數上的收斂圖Fig.5 Convergence curves of HCOAG and the comparison algorithms on the 4 classical benchmark functions

4.4 在CEC2017 復雜函數上的優化性能對比

為了進一步驗證HCOAG的搜索能力,將其用在CEC2017 復雜函數上實驗,并將其結果與9 個代表性的先進算法COA、GWO、MEGWO、HFPSO、DEBBO、SaDE、SE04、FWA 和TLBO的實驗結果進行比較,其結果見表4,其中SaDE和SE04的實驗數據直接來自文獻[20].

表4 在30 維CEC2017 復雜函數上的優化結果對比Table 4 Comparison results on the 30-dimensional complex functions from CEC2017

表4 在30 維CEC2017 復雜函數上的優化結果對比 (續表)Table 4 Comparison results on the 30-dimensional complex functions from CEC2017 (continued table)

表4 在30 維CEC2017 復雜函數上的優化結果對比 (續表)Table 4 Comparison results on the 30-dimensional complex functions from CEC2017 (continued table)

在均值和方差上,與MEGWO 相比,HCOAG 優于23 次.與同為混合算法的HFPSO 和DEBBO 相比,HCOAG 分別優于29 次和23 次.與SaDE 和SE04 相比,HCOAG 分別優于28 次和29 次.與FWA 和TLBO 相比,HCOAG 分別優于30 次和29 次.在總排名上,HCOAG 排名第一,接下來依次為MEGWO、DEBBO、SaDE、SE04、COA、TLBO、HFPSO、FWA、GWO.因此,HCOAG的性能優于9 個先進對比算法的性能.

4.5 收斂性能分析

為了驗證HCOAG的收斂性能,給出HCOAG與COA、MEGWO、DEBBO、TLBO 和HFPSO在CEC2017 測試集中30 維函數的收斂圖.受篇幅所限,本文僅選取有代表性的函數作為示例進行對比分析.在F1～F3中選取1 個單峰函數,即F1,在F4～F10中選取F5,F7,F8這3 個多峰函數,在F11～F20中選取F11,F12,F16,F17這4 個混合函數,在F21～F30中選取F21,F23,F24,F29這4 個復合函數,其收斂圖見圖6.

從圖6 中可以看出,在3 個函數F1,F5和F8上,隨著函數評價次數的增加,在收斂速度上,HCOAG 較對比算法要快得多,優勢明顯.在其余9 個函數上,雖然HCOAG的收斂速度優勢不是很明顯,但在收斂性能上也優于其他對比算法.總之,無論在單峰函數和多峰函數上,還是在混合函數和復合函數上,HCOAG的收斂速度都比其他對比算法的收斂速度快,表明HCOAG 具有更優秀的收斂性能.這些都說明,本文提出的高斯全局趨優成長算子、動態調整組內郊狼數方案以及簡化操作的GWO 搜索算子等的采用都為收斂速度的提升做出了貢獻,這些策略的融合使用是有效可行的.

圖6 HCOAG、COA、MEGWO、DEBBO、TLBO 和HFPSO的收斂圖Fig.6 Convergence curves of HCOAG,COA,MEGWO,DEBBO,TLBO,and HFPSO

4.6 時間對比分析

為了考察HCOAG的運行時間,直接采用第4.4 節的實驗.因為HCOAG 是COA 和GWO的混合算法,故僅記錄HCOAG、COA 和GWO 在30 維CEC2017 函數上的耗時,它們在獨立運行30次獲得不同函數類型的平均耗時結果見圖7.橫坐標為不同的函數類型,縱坐標為平均時間(s).

從圖7 可以看出,在單峰函數上,HCOAG 耗時(2.4443 s)是COA 耗時(2.9988 s)的81.51%,GWO 耗時(2.4222 s)是HCOAG 耗時(2.4443 s)的99.10%;在多峰函數上,HCOAG 耗時(2.9211 s)分別是COA(3.5503 s)和GWO(2.9233 s)耗時的84.25%和99.92%;在混合函數上,HCOAG 耗時(3.6246 s)是COA 耗時(4.2034 s)的86.23%,GWO 耗時(3.4981 s)是HCOAG 耗時(3.6246 s)的96.51%;在復合函數上,HCOAG 耗時(6.1480 s)是COA 耗時(7.0897 s)的86.72%,GWO 耗時(6.0822 s)是HCOAG 耗時(6.1480 s)的98.93%.故無論是單峰函數和多峰函數,還是混合函數和復合函數,HCOAG的耗時都與GWO 耗時大致持平.其主要原因是:1)HCOAG 與GWO 都采用并行計算模式,但GWO 結構簡單,而其產生新解的計算復雜度(見式(12))較高;2)HCOAG 雖然采用精簡GWO,但需要分組并在組內尋優,結構復雜,故二者耗時大致持平(HCOAG 耗時稍多于GWO的耗時).在耗時上,HCOAG 較COA 少,主要原因是:1)在成長過程的目標函數評價上,后者采用串行計算,前者采用并行計算減少了運行時間;2)雖然在成長過程中嵌入了GWO 搜索,但采用精簡的GWO 搜索方式并未增加多少計算成本;3)前者沒有郊狼被驅離和接納操作,節省了運行時間;4)動態調整方案減少了生與死操作次數.

圖7 HCOAG 與COA、GWO 在不同類別函數上的平均時間對比圖Fig.7 Comparison bars of average time of HCOAG,COA,and GWO on different kinds of functions

綜合第4.3～4.6 節,HCOAG 在較短的時間內能獲得最好的優化性能,說明了其優化效率高.

4.7 上下界分析

為了能夠更充分地評價HCOAG的性能,本節對其進行上下界分析,即在一個優化問題上,獨立運行一定次數后考察其最壞結果和最優結果.

因為本文將HCOAG 應用于CEC2017 復雜函數集上,此函數集有30 個不同的優化問題,其全局最優解對應的最優值不同,故其獲得的上下界也不同.限于篇幅,在CEC2017 四類函數上分別選取了同樣的一個函數(F1,F5,F11,F29)進行上下界討論,即在51 次的運行結果中選擇最好值和最差值分別作為本文提出算法在該函數上的上下界,并與對比算法中結果最好的算法(在F1和F5上選用COA;在F11和F29上選用DEBBO)獲得的上下界進行對比.

為了直觀和方便對比,對3 個算法獲得的結果進行了統一的處理:即將每個算法每次獨立運行結果減去理想的最優函數值作為最終結果,讓每個函數的理想最優值為0.在4 個函數上的上下界結果見表5.

表5 在30 維CEC2017 復雜函數上的上下界結果對比Table 5 Comparison of upper and lower bounds on the 30-dimensional complex functions from CEC2017

從表5 可以看出,在4 個函數上,無論上界還是下界,HCOAG 都比對比算法小,說明本文提出的算法比對比算法好,也證明了本文提出算法的有效性.

4.8 漸進收斂性分析

依據文獻[23]的隨機泛函分析方法原理,本節對HCOAG的收斂性進行分析.從算法3的描述和HCOAG 流程圖(圖4)可以看出,HCOAG 由3個算子完成新解的產生,即高斯全局趨優成長算子、簡化GWO 搜索算子以及生與死算子.高斯全局趨優成長算子類似DE (Differential evolution)中的DE/rand-to-best/1/bin 變異算子;簡化GWO 搜索算子類似DE 中的DE/best/1/bin 變異算子;生與死算子相當于遺傳算法中的變異算子.3 個算子產生的新解都采用貪心算法嚴格基于優勝劣汰策略,通過淘汰新解與原解中較差者產生更優的新一代個體.故對于最小優化問題,HCOAG 評價函數序列為單調非遞增序列.為了證明HCOAG的漸近收斂性,首先做如下定義.

定義1.設Q(t)表示X(t)的中間群體,Vc,j(t+1)∈Q(t+1),則HCOAG 搜索算子定義如下:

高斯全局趨優成長與簡化GWO 搜索混合算子定義為

假設f(X)為 最小優化函數,解空間S=X|X={x1,x2,···,xD}且Lj ≤xj ≤Uj,j=1,2,···,D}為D維歐氏空間 RD的有界子空間.為了在進行數值計算時不受計算精度的限制,設定HCOAG的計算精度保留到小數點后第k位數字.

定義2.兩種算子的混合策略是一種按照概率CR/D和(1-CR/D)對群體中個體向量的每一維分量分別采用簡化GWO 搜索算子和高斯全局趨優成長算子以及在每一組中最差郊狼上采用生與死算子進行重組變換的過程,它是解空間上的一種隨機映射ψ:Ω×S→S2,可定義為

定理1.HCOAG的一次迭代所形成的隨機映射ψ′是一個隨機壓縮算子.

再依據文獻[23]引理2,即可得到HCOAG 漸進收斂的結論,即定理2.

定理2.設ψ′為HCOAG 形成的隨機壓縮算子,則ψ′具有唯一的隨機不動點,即HCOAG 是漸進收斂的.

4.9 Wilcoxon 符號秩檢驗和Friedman 檢驗

Wilcoxon 符號秩檢驗方法[24]是一種非參數統計性檢驗方法,目的在于檢驗兩個樣本均值之間的顯著差異.其中p值由R+和R-計算可得,R+表示正秩總和,R-表示負秩總和,具體見式(34)和式(35),di為兩種算法在n個問題中第i個問題上的性能分數的差值.當HCOAG 算法與對比算法性能相同時,對應的秩平分給R+和R-.為檢驗HCOAG 與表4 中對比算法的顯著性差異,在軟件IBM SPSS Statistics 24 上實現Wilcoxon 檢驗,結果如表6 所示.表6 中,n/w/t/l表示在n個函數上HCOAG分別優于對比算法w次,與對比算法相等t次,劣于對比算法l次.

從表6 可以看出,與COA 和GWO 相比,p值分別為1.3039×10-7和1.8626×10-9,均小于0.05,表明HCOAG 顯著優于COA 和GWO,再一次說明COA 和GWO 二者的改進與混合是有效的.HCOAG 與MEGWO、HFPSO、DEBBO、SaDE、SE04、FWA 和TLBO 相比的p值均小于0.05,表明HCOAG 也顯著優于這些對比算法.

表6 Wilcoxon 符號秩檢驗結果Table 6 Wilcoxon sign rank test results

Friedman 檢驗是一種非參數雙向方差分析方法[24],目的在于檢測兩個或多個觀測數據之間的顯著性差異.具體實現過程分為3 步:1)收集每個算法或者問題的觀測結果;2)對于每個問題i的從1(最好結果)到k(最差結果)的排名值,定義為(1 ≤j≤k);3)在所有問題中求出每個算法的平均排名,得到最后排名在零假設下所有算法的行為相似(它們的秩Rj相等),Friedman統計值Ff的計算方式如式(36),當n和k足夠大時(根據經驗n＞ 10,k＞ 5),它是按照k-1 自由度的x2分布的.為了再次驗證HCOAG的顯著性,依據表4 對HCOAG 和對比算法在軟件IBMSPSS Statistics 24 上實現Friedman 檢驗,其結果如表7 所示.

從表7 可以看出,在30 維復雜函數上,通過Friedman 檢驗獲得的漸進顯著性p值為6.3128×10-31,由于得到的漸進顯著性小于0.01,所以在30維上HCOAG 與對比算法之間存在顯著性的差異.HCOAG 算法的秩均值(1.73)最小,隨后依次是MEGWO、DEBBO、SaDE、SE04、COA、TLBO、HFPSO、FWA 和GWO,表明HCOAG的優化性能最好.結合Wilcoxon 符號秩檢驗和Friedman 檢驗結果可以得出,HCOAG 總體上明顯優于先進的對比算法.

表7 Friedman 檢驗結果Table 7 Friedman test results

5 HCOAG 在K-Means 聚類優化上的應用

聚類在數據挖掘領域發揮著十分重要的作用,通過對聚類的數據分析可以得到數據的具體分布情況以及掌握數據類型的特點[25].其中,最常用的聚類方法是K-Means 方法[26],其在n個樣本數據中的具體實現過程如下:首先隨機產生K個初始聚類中心,然后計算每個樣本與各聚類中心的距離,接著將樣本與距離最近的聚類中心劃分到一個組內,形成K個組,最后重新計算每個組內所有樣本的均值作為新聚類中心并進行下一次劃分,如此迭代執行劃分過程直到滿足終止條件為止.K-Means 方法具有原理簡單、可伸縮性好以及效率高等優勢,但存在對初始點敏感和易陷于局部最優等問題.目前已有研究將SIOA 運用到K-Means 聚類中,很好地解決了K-Means 算法存在的一些問題[25,27].本節采用HCOAG 優化K-Means 聚類以解決其對初始點敏感等問題,其中,目標函數的定義為

其中,E是數據集中所有數據點到所屬聚類的聚類中心的距離和,K是聚類中心個數,ck是第k個聚類中心位置,Ck是第k個聚類簇,xi是聚類族Ck中第i個數據點.將HCOAG 應用到K-Means上,首先假設每頭郊狼由k個聚類中心組成,則解向量的維數應等于k× 數據樣本的特征數,目標函數采用式(37);接著執行HCOAG,直到滿足算法的終止條件,輸出最優聚類中心.

實驗采用UCI 數據庫(http://archive.ics.uci.edu/ml/datasets.php)中7 個標準數據集(見表8 第1 列)來驗證HCOAG 在K-Means 聚類優化上的有效性,數據集名稱后的括號內的數字為樣本數、屬性數和聚類數.選取的5 個對比算法包括:COA、MEGWO、HFPSO、擅長聚類優化的改進的粒子群優化算法(Improved PSO,IPSO)和改進的遺傳算法(Improved genetic algorithm,IGA).其中,IPSO 和IGA 來自“http://yarpizcom/64/ypml101-evolutionary-clustering”.所有算法的公共參數設置相同:N=50,MaxDT=200,Num=30.表8是6 種算法獨立運行30 次獲得的均值、方差和排名結果.

從表8 可知,HCOAG 在7 個數據集上的均值和方差得到排名第一5 次,其次是HFPSO 和IPSO 均為1 次,COA、MEGWO 和IGA 均獲得0次第一.HCOAG的平均排名為1.43,其他算法的平均排名順序依次為:IPSO、IGA、MEGWO、HFPSO 和COA.以上結果都表明HCOAG 在KMeans 聚類上的優化性能最好.總之,HCOAG 在K-Means 聚類優化中獲得競爭性的優化性能,能夠更好地處理聚類優化問題.

表8 6 種算法在K-Means 聚類優化上的結果對比Table 8 Comparison results of the 6 algorithms on K-Means clustering optimization

6 結束語

針對COA 存在的不足,本文提出了一種COA與GWO的混合算法(HCOAG).首先,改進COA(ICOA).1)在成長過程中,提出一種高斯全局趨優成長算子,提高了搜索能力;2)提出一種動態調整組數方案,搜索前期采用較少組數,減弱全局最優解的正反饋作用,強化探索能力,后期采用較多組數,增強全局最優解的正反饋作用,強化開采能力,并提高可操作性.然后,對GWO 進行改進,提出了一種精簡的GWO (SGWO),在發揮其局部搜索能力強的優勢同時,提高了可操作性.最后,采用正弦交叉策略將ICOA 與SGWO 有機融合,很好地平衡了組內郊狼的探索與開采能力,從而獲得了最佳優化性能.大量經典函數與CEC2017復雜函數優化的實驗結果表明,在經典函數上,COA不及GWO;在復雜函數上,GWO 不及COA;而HCOAG 在兩類優化問題上都有更好的性能,說明二者混合有必要和有效;與其他先進的對比算法相比,HCOAG具有更好的優化性能.K-Means 聚類優化結果表明,與對比算法相比,HCOAG 獲得了競爭性的優化性能.

總之,與COA 相比,HCOAG 具有如下優勢:1)普適性強,經典函數和復雜函數優化以及聚類優化3 組實驗結果表明,HCOAG 都有更好的表現;2)耗時少,因此有更好的搜索效率;3)更好的收斂質量;4)更強的穩定性和魯棒性,5)可操作性更強.

COA 是最近提出的一種SIOA,尚有許多地方需要探討和完善,本文僅是一種混合改進研究的嘗試.未來將進一步改進COA,對其進行深入的理論研究,并拓展其應用領域.