動態(tài)調整成長方式的郊狼優(yōu)化算法及其應用

嚴逍亞，王振雷，王昕

（1.華東理工大學能源化工過程智能制造教育部重點實驗室，上海 200237；2.上海交通大學 電工與電子技術中心，上海 200240）

0 概述

在科學研究和工程應用中亟待解決的優(yōu)化問題越來越多，其多數(shù)為具有不確定性、多峰值、多模態(tài)特性的復雜優(yōu)化問題。隨著優(yōu)化問題的復雜性增加，傳統(tǒng)的數(shù)學方法很難有效地處理此類復雜優(yōu)化問題。此外，很多實際應用中的優(yōu)化問題都需要在滿足不同類型的約束條件下進一步追求解的質量，因為各種各樣約束條件的存在，縮減了問題的可行區(qū)域，搜索過程變得復雜，這更增加了計算的復雜性和求解的難度。

對比經(jīng)典的數(shù)學優(yōu)化方法，智能算法具有結構簡單、適用性強、參數(shù)較少、魯棒性強等優(yōu)點，這些進化算法往往同合適的約束處理方法相結合，從而更有效地處理約束方法，成為優(yōu)化領域研究發(fā)展的趨勢之一，如粒子群算法［1-2］、差分進化算法［3］、教學優(yōu)化算法［4-5］、人工蜂群算法［6］、鯨魚優(yōu)化算法［7］和水波優(yōu)化算法［8］等。進化算法與約束處理方法結合方式多樣，如文獻［4］針對算法尋優(yōu)時出現(xiàn)的不同情況分別調用合適的約束處理方法，從而提高了對約束條件處理的有效性。文獻［9］提出一種由學習和進化兩個階段構成的約束進化算法，學習階段用于挖掘約束與目標函數(shù)之間的相關性，進化階段利用相關性通過加權更新方法和存檔替換機制進行約束優(yōu)化。文獻［10］設計一種兩階段約束進化方法，通過當前種群的狀態(tài)調整適應度評價策略，使種群在一個階段中跨越不可行區(qū)域到達可行區(qū)域，在另一個階段沿著可行邊界擴散，以自適應地平衡目標和約束條件。雖然許多群智能算法已在求解約束優(yōu)化領域取得了較好的表現(xiàn)，但尋優(yōu)精度、穩(wěn)定性都有了進一步提升的空間。因此，設計尋優(yōu)精度與穩(wěn)定性更高的算法依然是研究的熱點。

郊狼優(yōu)化算法（Coyote Optimization Algorithm，COA）為PIEREZAN 教授［11］在2018 年提出的一種模擬郊狼成長、生死等現(xiàn)象的新型群智能算法，其獨特的算法結構為優(yōu)化過程中探索與開發(fā)的平衡提供了新的機制，故不少學者對其進行研究［12-13］，并應用到電力系統(tǒng)和物聯(lián)網(wǎng)等領域［14-16］。文獻［17］對基礎COA 算法進行了改進，利用全局最優(yōu)指導最差郊狼更新，同時加入一種隨機擾動操作來增加種群的多樣性，使算法能更大范圍地進行全局尋優(yōu)。文獻［18］提出一種相互作用的文化趨勢，使其值受到子種群個體彼此間作用的影響，從而增強了算法的全局搜索能力，將改進后的郊狼優(yōu)化算法應用到了醫(yī)學圖像增強問題上獲得了滿意的效果。文獻［19］用組外貪心策略取代原COA 算法的組內貪心策略，提高了算法的運行速度，同時通過郊狼間信息共享的方式增加了種群多樣性。文獻［20］將COA 和文化算法聯(lián)系起來，提出了文化郊狼算法，改善了COA 算法在探測與開發(fā)之間的平衡。

雖然COA 算法貢獻了不同的算法結構和機制來實現(xiàn)優(yōu)化過程中探索和開發(fā)兩者之間的平衡［15］，但是在以下方面還有待提升：COA 通過子種群內頭狼和組文化趨勢兩者來指導組內郊狼社會位置更新，雖然增強了算法的開發(fā)能力，但在求解具有多個局部極值的優(yōu)化問題時，子種群中頭狼處于局部最優(yōu)位置的概率大幅增加，由于頭狼在搜索中的指導作用，子種群中其余郊狼很容易被頭狼引導至其處于的局部最優(yōu)位置，從而造成算法的早熟收斂；在COA 算法中每次迭代時，子種群內郊狼在相同的頭狼和組文化趨勢指導下一直保持著恒定的成長方式，隨著迭代的進行，種群相似度變高，弱化了算法的搜索能力；子種群內郊狼的信息共享程度不高，在求解復雜優(yōu)化問題時，全局搜索能力較弱。

本文提出一種動態(tài)調整成長方式的郊狼優(yōu)化算法（Coyote Optimization Algorithm with Dynamically adjusting Growth mode，DGCOA）。通過引入變異交叉策略增強種群多樣性，并提出一種新的郊狼成長更新方法，不僅加入全局最優(yōu)個體來指導搜索，而且在新的成長更新策略中根據(jù)種群中個體相似度的變化及時對郊狼成長方式進行調整，彌補基礎COA 不同個體間信息交互不足的問題，平衡算法全局探索和局部開發(fā)能力。將改進的COA 算法與自適應約束處理方法相結合來協(xié)調優(yōu)化目標和約束違反度，提高算法處理約束優(yōu)化問題時的效率。

1 郊狼優(yōu)化算法

1.1 種群初始化及隨機分組

在郊狼算法中，解個體被隨機分在Np個子種群，每個子種群中包含Nc只個體。第p個子種群里第c只郊狼個體在第j維的初始位置可表示為：

其中：lbj和ubj分別代表第j維搜索空間的下限和上限；rj為［0，1］內的一個隨機數(shù)。

每只郊狼對環(huán)境的適應度可用目標函數(shù)值表示為：

1.2 郊狼成長

其中：Op,t代表郊狼的社會位置排名。

兩者的影響因子δ1和δ2可按下式計算：

其中：cr1和cr2為在該子種群內任意選擇的兩只郊狼。

郊狼新的社會位置可按式（7）計算：

其中：r1和r2為［0，1］內的隨機數(shù)。

COA 算法擇優(yōu)選擇對環(huán)境適應度更高的郊狼保存下來，該過程可表示為：

1.3 郊狼生死

其中：r1和r2為在第p個群落里任意選擇的兩匹郊狼；j1和j2為任意選擇的兩個自變量維度；Ps為離散概率；Pa為關聯(lián)概率；Rj為第j維自變量取值范圍內的任意數(shù)；randj?[0,1]是對應第j維的隨機數(shù)。

Ps和Pa可用公式表示為：

其具體出生死亡選擇過程可用算法1 描述。其中，ω代表第p個子種群內比新出生的小狼適應度低的郊狼，φ代表這些郊狼的數(shù)目。

算法1出生死亡選擇行為偽代碼

某些郊狼有時會離開原始種群加入到另一個子種群里，此概率可用Pe 來表示為：

2 改進的郊狼優(yōu)化算法

2.1 變異交叉策略

在COA 算法中，各個子種群的頭狼和文化趨勢引導著群體向潛力區(qū)域前進。但隨著搜索的迭代進行，種群中的解個體會相互靠近，使得群體的多樣性逐步下降。當所有解個體聚集到一起時，整個種群多樣性不能得到更新，以致算法迭代有效性下降，搜索出現(xiàn)停滯。在這種情況下，可對解個體進行變異操作，在其附近位置產(chǎn)生新解，以此來增加種群多樣性。因此，引入差分進化算法中的變異交叉策略到COA 算法中，用于提高種群多樣性，減小算法早熟收斂的可能，提高算法收斂精度。

首先選取第c只郊狼對應的社會位置為父體向量，對應的變異向量可用公式表示為：

其中：r1和r2為在第p個子群落里任意選擇的兩只郊狼；為差分向量；F是變異因子，用其對差分向量進行縮放，控制搜索步長，一般在[0,2]之內選擇，通常取0.5，其值的大小決定了種群的分布情況。通過設置F在進化過程中的值，可以有效增加候選個體的數(shù)量，提高種群多樣性，使種群在全局范圍內進行搜索，增強算法的穩(wěn)定性。

利用父體向量和變異向量通過離散雜交產(chǎn)生實驗向量：

其中：j=1,2,…,D；jrand是［1，D］之間的隨機整數(shù)；CR?[0,1]是交叉概率；randj?[0,1]是對應于第j維的隨機數(shù)。

通過變異交叉策略產(chǎn)生Nc個實驗向量構成實驗種群Up,t。合并父體種群socp,t與實驗種群Up,t獲得組合子種群hp,t=socp,t∪Up,t，按照下文提出自適應約束處理方法，從中選擇Nc個較好個體形成更新的子種群socp,t。

2.2 新的成長更新策略

2.2.1 全局最優(yōu)影響因子的方式

1）G(Xi)=G(Xj)?f(Xi)

2）G(Xi)

在所有的郊狼中，對環(huán)境適應度最高的郊狼即為在第t次迭代時整個種群的最優(yōu)個體。故在第t次迭代時，整個種群的最優(yōu)個體可用公式表示為：

在COA 算法中，每個子種群中的郊狼僅通過所在子種群的頭狼alphap,t，以及該子種群的文化趨勢cultp,t兩者來指導其社會位置的更新，并沒有考慮到整個種群的最優(yōu)位置對郊狼位置更新的影響。因此，加入整個種群的最優(yōu)個體的方向信息來改進各個子種群中郊狼的位置更新方式。對第p個子種群內的第c只郊狼在第t次迭代時位置更新的影響因子δ3為：

在引入全局最優(yōu)引導搜索后，各個子種群中的郊狼各自以更快的收斂速度從不同的方向朝著可行區(qū)域進行靠攏逼近，從而大幅加快了COA 的收斂速度。

2.2.2 動態(tài)調整郊狼成長的方式

由式（3）可知，同一子種群內郊狼在相同的頭狼和文化趨勢與兩頭隨機挑選的郊狼的差值共同指導下保持著恒定的成長機制，而在每次迭代過程中，同一子種群內頭狼和文化趨勢相同，且隨機挑選的郊狼個體相似度無法保證，因此容易使得產(chǎn)生的新解相似度過高，以致于弱化算法的搜索能力，不易實現(xiàn)全局搜索。此外，郊狼在迭代過程中一直朝著所在子種群內頭狼和文化趨勢方向移動，增加了算法陷入局部最優(yōu)的可能。

為此，本文根據(jù)子種群內郊狼個體的相似度動態(tài)調整郊狼成長更新方式，如式（17）所示：

其中：r1、r2、r3和r4為［0，1］內的隨機數(shù)；cr3和cr4分別為在該子種群內任意選擇的兩只不同于cr1和cr2的郊狼；R為子種群中郊狼相似度；Pr為一常數(shù)。

計算方式如式（18）和式（19）所示：

其中：Count 為相似解的對數(shù)；Countmax為子種群內解的最大對數(shù)。通過兩者的比值來確定種群相似度。

新的成長更新方式引入了全局最優(yōu)解來指導位置更新，加快了算法的收斂速度。當相似度高時，根據(jù)方式1 對郊狼進行位置更新，郊狼的進化由cultp,t、alphap,t以及三者共同確定的方向信息來進行指導。此時，由于子種群內郊狼相似度高，δ1和δ2的值較小，從而使得算法在全局最優(yōu)解附近展開精細搜索，增強了算法的局部開發(fā)能力；當相似度低時，根據(jù)方式2 對郊狼進行位置更新，郊狼的進化由以及共同確定的方向信息來進行指導。此時子種群內郊狼相似度低，子種群內郊狼的差值模型不僅使得子種群內信息得到共享，實現(xiàn)了子種群內郊狼的經(jīng)驗交流，而且由于值較大，從而加大了算法的搜索步長，增強了算法的全局搜索能力。

算法2新的成長更新策略偽代碼

在算法迭代前期進行隨機全局搜索時，種群相似度較低，方式2 以更大的概率指導郊狼的進化，全局搜索能力較強，算法可以憑借更高的概率找到全局最優(yōu)解；在迭代后期進行局部開發(fā)時，種群相似度較高，方式1 以更大的概率指導郊狼的進化，局部開發(fā)能力較強，提高了算法的收斂精度。隨著迭代的進行，在新的成長更新策略指導下，算法根據(jù)種群的相似度選擇合適的位置更新方式，有效地平衡了算法的全局搜索能力與局部開發(fā)能力，使得算法的優(yōu)化性能得到提升。

2.3 邊界處理方法

在算法尋優(yōu)過程中，當新產(chǎn)生的解個體超出自變量上下限時，通常將其設為上下限值，但是目標函數(shù)的最優(yōu)解往往不在搜索邊界上，簡單地將越界變量置于上下限上，會造成資源的浪費。故將越界分量按下式進行處理［21］，增強種群多樣性，同時降低了下次迭代產(chǎn)生新位置越過尋優(yōu)邊界的幾率。

其中：r為[0,1]內的隨機數(shù)；ubj、lbj分別為xij的上限值和下限值。

2.4 約束處理方法

合理有效地對約束進行處理，平衡可行解與不可行解的關系是獲得約束優(yōu)化問題最優(yōu)解的關鍵?？紤]到在求解約束優(yōu)化問題時，郊狼種群在尋優(yōu)迭代中必定會經(jīng)過不可行情形、半可行情形和可行情形3 種狀態(tài)，因此，本文在執(zhí)行完上述新的成長更新策略之后，依據(jù)各個子種群在迭代過程中所處的情形，分別調用3 種不同的約束處理技術來與改進后的郊狼優(yōu)化算法相結合，實現(xiàn)目標函數(shù)和約束違反度兩者的平衡，使得改進后的郊狼優(yōu)化算法可以充分發(fā)揮其新的成長更新方式的搜索性能。

1）在不可行情形下，利用文獻［22］提出約束處理技術把無約束優(yōu)化問題構造為多目標優(yōu)化問題，然后通過Pareto 支配方法找出子代種群中的所有非支配個體，并分別隨機替換一個父代種群中被它支配的個體（如果存在的話）。然后找出上述非支配個體中約束違反度最小的最優(yōu)個體，若其沒有替換父代種群中的個體，則使其隨機替換父代種群中的某個個體，已達到利用最優(yōu)個體持續(xù)地引導種群向可行區(qū)域靠近的目的。

2）在半可行情形下，利用一種適應值轉換機制［23］把約束優(yōu)化問題構造為無約束優(yōu)化問題，依據(jù)新構造的解適應度函數(shù)對個體進行選擇，將攜帶重要信息的不可行個體和優(yōu)秀的可行個體保留到下一代群體中。具體過程如下：

（1）將種群分成可行集合Z1和不可行集合Z2，對應解Xi的目標函數(shù)值f(Xi)按式（21）轉換為：

其中：?為可行解比 例；Xbest和Xworst分別為可 行集合中最優(yōu)及最差解。

（2）對轉換得到的目標函數(shù)值和約束違反度按式（22）和式（23）進行標準化：

（3）構造出的適應度函數(shù)可表示為：

可以看出在這種方法下，可行解依據(jù)目標函數(shù)值進行評價選擇，不可行解同時考慮了目標函數(shù)值和約束違反度后進行評價選擇，實現(xiàn)了目標函數(shù)和約束違反度之間的平衡。

3）在可行情形下，種群中全部是可行解，約束優(yōu)化問題能夠被當作無約束優(yōu)化問題求解，利用目標函數(shù)對個體進行評價即可。

改進的郊狼優(yōu)化算法根據(jù)尋優(yōu)過程中種群在解空間的不同狀態(tài)，自主選擇合適有效的約束處理方法，完成對約束優(yōu)化問題求解。

2.5 算法實施步驟

將上述差分變異策略引入COA 算法，并修改郊狼成長方式形成改進后的COA 算法。結合自適應約束處理方法，DGCOA 算法的實施步驟如算法3 所示。DGCOA 算法流程如圖1 所示。

圖1 DGCOA 算法流程Fig.1 DGCOA algorithm procedure

算法3DGCOA 算法偽代碼

改進的郊狼優(yōu)化算法通過執(zhí)行變異交叉策略和邊界處理方法，增加了種群多樣性，降低了算法早熟收斂現(xiàn)象發(fā)生的概率，提高了算法的穩(wěn)定性；通過引入全局最優(yōu)引導搜索，大幅加快了算法的收斂速度；通過種群中個體相似度來對郊狼成長更新方式進行動態(tài)選擇，提高了算法的收斂精度。綜上所述，改進后的郊狼優(yōu)化算法無論是在尋優(yōu)穩(wěn)定性，還是在收斂精度和收斂速度方面都做出了改進，尋優(yōu)能力具有很大競爭性。

3 數(shù)值實驗與分析

3.1 參數(shù)設置

本文將DGCOA 的尋優(yōu)結果與COA、ICTLBO［4］、ODPSO［2］、IWWO［8］、E-BRM［24］和MGABC［6］算法進行對比。其中，ICTLBO 與本文DGCOA 均是針對約束問題的分種群算法。DGCOA 算法中的參數(shù)設置為：Np=10，Nc=14；變異交叉策略中的變異算子和交叉算子分別設置為：F=0.5，CR=0.8；相似度閾值根據(jù)實驗結果對比取最優(yōu)值Pr=0.3；等式約束容忍度δ=0.000 1；最大函數(shù)評價次數(shù)（Max_NFEs）設定為240 000。COA中相關參數(shù)與DGCOA 設置相同。

各算法獨立運行25 次，記錄各算法運行結果的平均值Mean 和標準差Std 如表1 所示。表中f(X*)為目前已知最優(yōu)解X*處的目標函數(shù)值，NF 表示在全部運行次數(shù)內沒有找到可行解，將在全部對比算法中取得最優(yōu)的平均值和標準差加黑標注。部分算法在測試函數(shù)上的收斂曲線對比如圖2 所示。其中選取的對比算法均為對應文獻中表現(xiàn)最優(yōu)的約束進化算法，其結果分別取自于對應的參考文獻。圖2 中ICTLBO 的收斂曲線由其源代碼運行所獲得。

圖2 DGCOA、COA 與ICTLBO 算法收斂曲線Fig.2 Convergence curves of DGCOA，COA and ICTLBO algorithms

表1 不同算法在CEC2006 測試函數(shù)上最終結果比較Table 1 Comparison of final results of different algorithms on CEC2006 test function

3.2 測試函數(shù)結果與分析

本文采用平均值（Mean）和標準差（Std）作為評價各算法優(yōu)化性能的標準，平均值越小算法的收斂精度越高，標準差越小算法的穩(wěn)定性越好。

由表1 可以看出，在收斂精度方面，DGCOA 在函數(shù)g02、g13、g17、g21 和g23 上獲得了較高的收斂精度，分別取得了第4、第3、第3、第3 和第2 的排名。在其余17 個函數(shù)上，DGCOA 在7 種對比算法中獲得了最優(yōu)的平均值，即收斂精度最高。特別地，在函數(shù)g10、g19 上，僅有DGCOA 算法能夠以較高精度收斂至其最優(yōu)值，獲得全局最優(yōu)解；在穩(wěn)定性方面，DGCOA 在函數(shù)g01、g04、g06、g10、g12、g18 和g19 上取得了最小的標準差，即穩(wěn)定性最高。相較COA 算法僅在函數(shù)g06、g12 和g24 上可以穩(wěn)定地獲得最優(yōu)解，對于函數(shù)g14、g17 和g21 無法獲得可行解的情況，DGCOA 無論是在收斂精度還是在穩(wěn)定性方面都獲得了很大的提高；相較其他6 種算法，DGCOA 在大部分測試函數(shù)上的收斂精度和穩(wěn)定性也都能夠獲得具有高競爭力的結果。

由圖2 的算法收斂曲線可以看出，相較COA 算法，在相同函數(shù)評估次數(shù)的前提下，對于圖中所有測試函數(shù)，DGCOA 算法均能以更快的收斂速度收斂到其所能找到的最優(yōu)值附近，并具有更高的收斂精度。和同為分種群類智能優(yōu)化算法的ICTLBO 相比，在函數(shù)g01 上，DGCOA 收斂速度和收斂精度都具有較高競爭性；在函數(shù)g02 和g05 上，DGCOA 在早期迭代階段收斂速度稍遜于ICTLBO，但在后期，DGCOA同樣具有較高競爭性，與ICTLBO 的收斂速度和收斂精度不相上下；在函數(shù)g11 和g15 上，DGCOA 早期迭代階段收斂速度優(yōu)于ICTLBO，且在迭代后期能以較高的收斂精度收斂于最優(yōu)解；在函數(shù)g17 上，DGCOA 在早期迭代階段收斂速度稍遜于ICTLBO，沒有很快找到可行解，但在后期，DGCOA 的收斂速度超過了ICTLBO。

綜上所述，圖2 進一步證明了改進COA 算法無論是在收斂精度還是在收斂速度方面都得到了很大提升。

3.3 Wilcoxon 符號秩檢驗

本文采用Wilcoxon 符號秩和檢驗統(tǒng)計方法［19］來評價DGCOA 與表1 中其他算法兩兩之間差異的顯著性。其中R+表示正秩總和，R?表示負秩總和。對兩種算法之間的統(tǒng)計比較結果采用符號“+”“?”“≈”表示。“+”和“?”分別說明前一個算法明顯優(yōu)于或明顯差于后2 個算法；“≈”說明2 個算法沒有明顯差異。Wilcoxon 符號秩和檢驗結果如表2 所示。

表2 Wilcoxon 符號秩和檢驗結果Table 2 Wilcoxon signed-rank and test results

從表2 可以看出，DGCOA 算法明顯優(yōu)于COA、ODPSO、E-BRM 和MGABC算法，與ICTLBO 和IWWO 算法之間無明顯差異。

4 工程優(yōu)化問題結果及分析

為進一步檢驗DGCOA 算法解決實際工程問題的有效性，選取3 個較為經(jīng)典的約束工程設計問題［5］對DGCOA 算法進行測試。

1）Welded Beam 問題

本文DGCOA 算法運行結果和其他算法在Welded Beam 問題上的比較如表3 所示?？梢钥闯鯥CTLBO、IFOA 和DGCOA 在每次運行中均能獲得最優(yōu)解，且DGCOA 取得了最小的標準差，即DGCOA 穩(wěn)定性更好。

表3 不同算法在Welded Beam 問題上的結果比較Table 3 Comparison of results of different algorithms on the Welded Beam problem

2）Tension String Design 問題

本文DGCOA 算法運行結果和其他算法在Tension String Design 問題上的比較如表4 所示。可以看出IFOA 和DGCOA 在每次運行中均能獲得最優(yōu)解，且DGCOA 取得了最小的標準差，即DGCOA穩(wěn)定性更好。

表4 不同算法在Tension String Design問題上的結果比較Table 4 Comparison of results of different algorithms on Tension String Design problem

3）Pressure Vessel 問題

本文DGCOA 算法運行結果和其他算法在Pressure Vessel 問題上比較如表5 所示?？梢钥闯鯥CTLBO、COMDE 和DGCOA 在每次運行中均能獲得最優(yōu)解，且DGCOA 取得了最小的標準差，即DGCOA 穩(wěn)定性更好。

表5 不同算法在Pressure Vessel 問題上的結果比較Table 5 Comparison of results of different algorithms on the Pressure Vessel problem

5 結束語

本文提出一種動態(tài)調整成長方式的郊狼優(yōu)化算法求解復雜優(yōu)化問題。通過引入變異交叉策略增加種群多樣性，協(xié)助算法獲得全局最優(yōu)解，并給出一種新的成長更新策略，加入全局最優(yōu)影響因子，以提高算法的收斂速度。此外設計兩種不同的成長方式，通過各個子種群中郊狼個體的相似度來對郊狼成長更新方式進行動態(tài)選擇，有效平衡算法的全局探索與局部開發(fā)，同時彌補基礎COA 算法中子種群內郊狼個體信息共享不足的問題。最后將改進的郊狼算法與自適應約束處理技術相結合，實現(xiàn)對約束優(yōu)化問題的有效求解。實驗結果表明，相比COA、ICTLBO、ODPSO等算法，DGCOA算法具有較高的收斂精度和穩(wěn)定性。雖然本文算法在求解高維復雜約束優(yōu)化問題時能夠找到可行解，但是求解精度還有待提高。下一步將通過與更先進的方法結合來改進郊狼算法的尋優(yōu)性能，提升其在求解高維優(yōu)化問題時解的質量。