自適應(yīng)動態(tài)學(xué)習雞群優(yōu)化算法

顧艷春，魯海燕 ，2，向 蕾，沈莞薔，2

1.江南大學(xué) 理學(xué)院，江蘇 無錫 214122

2.江南大學(xué) 無錫市生物計算工程技術(shù)研究中心，江蘇 無錫 214122

1 引言

群智能優(yōu)化算法是通過模擬自然現(xiàn)象的物理規(guī)律及自然界各類生物種群的生活習性和行為特點而構(gòu)造的一類隨機優(yōu)化算法，如遺傳算法[1-2]（Genetic Algorithm，GA）、粒子群算法[3-4]（Particle Swarm Optimization，PSO）、蝙蝠算法[5]（Bat Algorithm，BA）、蜂群算法[6-7]（Artificial Bee Colony，ABC）等。這些算法為解決大量存在于計算科學(xué)、工程科學(xué)、管理科學(xué)等領(lǐng)域的復(fù)雜問題提供了新的求解途徑。

雞群算法[8]（Chicken Swarm Optimization，CSO）是2014年由孟獻兵等人提出的一種智能優(yōu)化算法，該算法具有原理簡單、易于實現(xiàn)和全局搜索能力較強等優(yōu)點，因此被廣泛研究并應(yīng)用于圖像處理[9]、電網(wǎng)優(yōu)化[10]、傳感器與通信[11]等優(yōu)化問題[12-14]。但雞群算法也存在求解精度偏低、局部求解能力較弱等問題，因此，眾多學(xué)者進行研究改進，提出了一系列改進雞群優(yōu)化算法。李振壁等人[15]將模擬退火的思想引入雞群算法，提高了算法的尋優(yōu)性能。史旭棟等人[16]把雞群算法和人工蜂群算法相融合，平衡了算法的全局和局部搜索能力。張慕雪等人[17]在算法的公雞更新公式中添加了向當前最優(yōu)個體和最差個體學(xué)習部分，提高了算法跳出局部極值的能力。鄭家明等人[18]在算法中用佳點集構(gòu)造初始種群，并引入了尋食速度因子和聚集度因子，提高了算法的穩(wěn)定性和求解精度。張瑩杰等人[19]改進了雞群算法的邊界約束處理機制，提高了算法的收斂速度。韓萌[20]將耗散結(jié)構(gòu)引至公雞位置的更新中，并對隨機選擇的個體進行差分變異操作，增強了算法的全局搜索能力。

上述改進算法在一定程度上提高了算法的尋優(yōu)能力，但仍存在著一些不足。比如，有些改進算法雖然提高了算法的求解精度，但算法的收斂速度較慢；還有些改進算法在求解高維問題上，仍存在早熟收斂等問題。為此，本文提出自適應(yīng)動態(tài)學(xué)習雞群優(yōu)化算法（ADLCSO），利用反向覓食機制和非線性遞減的學(xué)習因子來動態(tài)地自適應(yīng)更新種群中的公雞位置，以提高公雞個體跳出局部極值的能力，從而提高求解精度和收斂速度；同時利用整個種群中個體間適應(yīng)度值之差定義了一種新的種群相似度指標，根據(jù)該指標使母雞個體進行自適應(yīng)更新，在保持種群多樣性的同時使母雞個體朝著對整個群體較為有利的方向覓食。通過對12個經(jīng)典測試函數(shù)的仿真實驗，結(jié)果表明上述兩個更新策略能夠有效地提高雞群算法的求解精度和收斂速度，特別是在求解高維問題上ADLCSO算法比標準雞群算法有顯著優(yōu)勢。

2 雞群優(yōu)化算法

雞群算法是模擬雞群的等級制度和覓食行為的一種隨機優(yōu)化算法，該算法遵循如下規(guī)則：

（1）將整個雞群分成若干子群，每個子群都由一只公雞，若干只母雞和小雞組成，即子群的個數(shù)由公雞的個數(shù)決定。

（2）按照每只雞適應(yīng)度值的大小將種群分為公雞、母雞和小雞三種，其中適應(yīng)度較好的若干個體為公雞，適應(yīng)度較差的若干個體為小雞，其余的為母雞。

（3）公雞、母雞、小雞三者之間的等級制度一旦確立將數(shù)代保持不變，等級制度每隔G(G∈[2,20])代更新一次。

（4）每個組內(nèi)母雞跟隨該組的公雞覓食，也可隨機偷取其他組內(nèi)食物；每組內(nèi)小雞跟隨媽媽母雞進行覓食。

（5）每一只雞的位置都對應(yīng)優(yōu)化問題的一個解。假設(shè)在一個種群里有N個個體，公雞、母雞、小雞、媽媽母雞的數(shù)量分別為NR、NH、NC、NM。媽媽母雞是從母雞中隨機選取，每個母雞媽媽有若干個孩子小雞。

（6）在雞群中，不同等級的雞的位置更新方式有所不同。公雞作為適應(yīng)度最好的雞群，在整個覓食過程中占據(jù)主導(dǎo)地位，可以在更廣泛的空間里尋找食物。公雞位置更新公式如下：

其中，randn(0,σ2)是均值為0、標準差為σ2的一個高斯分布；fi為個體i的適應(yīng)度值；ε為充分小的正數(shù)，以防止的分母取值為0；k為任一公雞個體的編號，且k≠i。

母雞位置更新公式如下：

其中，r1 為第i只母雞的配偶公雞個體的編號，r2 為隨機選取的任一公雞或母雞個體的編號，且r1 ≠r2，rand為[0，1]內(nèi)的隨機數(shù)。

小雞位置更新公式如下：

其中，xm,j(t)代表第t次迭代時第i只小雞的媽媽的位置，F(xiàn)L(FL∈[0,2])為跟隨系數(shù)。

3 自適應(yīng)動態(tài)學(xué)習雞群算法

本文在標準雞群優(yōu)化算法中引入了非線性遞減學(xué)習因子和反向覓食機制，使公雞個體在向全局最優(yōu)個體動態(tài)學(xué)習的同時還自適應(yīng)地進行反向覓食，可提高算法跳出局部極值的能力；此外定義了種群相似度指標，根據(jù)該指標使母雞個體進行自適應(yīng)更新，可進一步提高算法的性能。

其中，tmax為總迭代次數(shù)；w(t)為第t次迭代的學(xué)習因子；wmax和wmin為學(xué)習因子的最大值和最小值(wmax=0.9,wmin=0.4)。

在算法迭代前期，學(xué)習因子較大，從而使公雞個體有較大的學(xué)習范圍，不僅能擴大搜索區(qū)域，還能有利于跳出局部極值；而在算法后期搜索階段學(xué)習因子較小，有利于提高公雞群體的局部搜索能力，從而有利于找到全局最優(yōu)值。

3.1.2 公雞個體向最優(yōu)個體學(xué)習

公雞群體是整個種群中適應(yīng)度值最好的群體，它起著引領(lǐng)其他群體向全局最優(yōu)位置前進的作用。為了加快整個種群搜索到最優(yōu)解的速度，本文使公雞個體在向自身學(xué)習的同時還要向當前種群中最優(yōu)個體動態(tài)學(xué)習，從而能夠使公雞個體盡快地進入最優(yōu)解附近的區(qū)域。改進的公雞更新公式如下：

其中，xbest(t)為第t次迭代最優(yōu)個體的位置。

3.1.3 反向覓食機制

公雞個體向當前種群中最優(yōu)個體學(xué)習雖然能夠提升算法的收斂速度和求解精度，但在解決高維多峰函數(shù)時容易使大多數(shù)個體聚集在局部極值附近難以跳出，算法會出現(xiàn)早熟收斂的情況。

為了合理地判斷算法是否陷入局部極值，本文通過計算從第t+1-K次迭代到第t次迭代出現(xiàn)的K個最優(yōu)解的方差來檢測算法是否早熟收斂，計算公式如下：

3.1 基于反向覓食機制的公雞位置更新

3.1.1 非線性遞減學(xué)習因子

為了能較好地平衡雞群算法的全局和局部的搜索能力，本文在雞群算法的公雞更新公式中引入非線性遞減的學(xué)習因子，該學(xué)習因子的公式如下：

其中，δ(t)為第t+1-K次迭代到第t次迭代出現(xiàn)的K個最優(yōu)解的方差；xmean為K個最優(yōu)解的均值。當δ(t)＜ε（ε為充分小的正數(shù)），表明連續(xù)K次迭代最優(yōu)解沒有發(fā)生明顯變化，則可認為算法出現(xiàn)早熟收斂現(xiàn)象。

為了提高算法跳出局部極值的能力，文獻[17]在算法陷入局部極值時使公雞個體向當前整個種群中最差粒子學(xué)習，使得整個雞群能夠以一定的概率跳出局部最優(yōu)區(qū)域，文獻[17]中的公雞更新公式為：

其中，xworst(t)為第t次迭代的最差解向量；Q為學(xué)習系數(shù)，在文獻[17]中Q=0.5。

文獻[17]的改進策略一定程度地增強了算法跳出局部最優(yōu)的能力，但使用常數(shù)學(xué)習系數(shù)不利于平衡全局與局部的搜索能力。為此，本文在公雞位置更新中引入反向覓食機制，當算法陷入局部極值時使公雞個體向遠離全局最優(yōu)位置的方向進行覓食，并且在更新公式中加入了非線性遞減的學(xué)習因子。此時公雞個體的更新公式為：

其中，xbest(t)為第t次迭代的最優(yōu)個體的位置。

3.2 基于種群相似度指標的母雞位置更新

3.2.1 種群相似度指標

當前種群的多樣性與算法的搜索能力密切相關(guān)，當種群多樣性較差時，算法的全局搜索能力較弱。因此，一些學(xué)者通過定義種群中個體之間的密集度來衡量當前種群多樣性的高低。王叢佼等人[21]定義群體適應(yīng)度值方差來反映種群中所有個體聚集程度，以此來改進差分進化算法。何瓊月等人[22]在改進粒子群算法時，用當前粒子之間的歐氏距離來定義種群的相似度。

本文在雞群算法中引入種群相似度概念，利用當前整個種群中每個個體與最優(yōu)個體之間的適應(yīng)度的差來定義整個種群的相似度，繼而根據(jù)種群的相似度對母雞個體進行自適應(yīng)更新。當兩個個體之間的適應(yīng)度差值較大時，很容易判斷這兩個個體相似度較低；當兩個個體之間的適應(yīng)度差值較小時，對個體之間相似度的判斷則較為困難。為了合理度量兩個個體之間的相似度高低，本文在設(shè)計相似度指標函數(shù)時需要遵循以下幾點要求：

（1）函數(shù)的值域為(0,1)。

（2）在自變量較小時，函數(shù)值對自變量變化比較敏感，函數(shù)的圖像較陡。

（3）在自變量較大時，函數(shù)值受自變量變化的影響較小，函數(shù)的圖像較緩。

遵循以上幾點要求，定義個體之間的相似度指標公式如下：

其中，fi為個體i的適應(yīng)度值；fp為當前種群中最優(yōu)個體的適應(yīng)度值；u(i,p)為個體i與最優(yōu)個體的相似度指標；a為固定常數(shù)，大量實驗表明，當a=5 時算法求解效果較好。

通過分析公式（14）知，函數(shù)u為增函數(shù)，當兩個個體之間適應(yīng)度的差值越大時，個體之間的相似度指標越大，兩個個體之間相似度就越低。為了更加直觀地看出相似度指標函數(shù)圖像前陡后緩的特點，特地給出了函數(shù)圖像（見圖1）。

圖1 u 函數(shù)的曲線圖

由公式（14）可得到個體與最優(yōu)個體之間的N（種群個數(shù)）個相似度指標值，然后對這N個指標值進一步求均值來度量整個種群的相似度。種群相似度指標s(t)的表達式如下：

其中，s(t)表示第t代的種群多樣性指標。當s(t)→1時，種群中個體的相似度較低，種群多樣性較好；當s(t)→0 時，種群中個體的相似度較高，種群多樣性較差。

3.2.2 母雞個體更新方式

根據(jù)上述的種群相似度指標，本文改進的母雞更新公式如下：

其中，h1 和h2 為雞群中的隨機個體的編號。若s(t)＜rand，則第i只母雞選擇隨機粒子進行隨機學(xué)習，以增加種群多樣性；若s(t)≥rand，則第i只母雞選擇最優(yōu)個體和自身所在子群的公雞個體學(xué)習，從而促使個體向最優(yōu)解靠近。

3.3 ADLCSO算法的求解步驟

自適應(yīng)動態(tài)學(xué)習改進雞群算法（ADLCSO）的求解步驟如下所述：

（1）種群初始化。設(shè)置種群數(shù)量N，公雞個數(shù)NR，母雞個數(shù)NH，小雞個數(shù)NC，小雞媽媽的個數(shù)NM，進化代數(shù)G，最大迭代次數(shù)tmax等相關(guān)參數(shù)。

（2）計算雞群里每個個體的適應(yīng)度值，設(shè)置整個雞群全局最優(yōu)位置，設(shè)置迭代次數(shù)t=1。

（3）根據(jù)公式（7）～（8）計算學(xué)習因子；根據(jù)公式（14）～（15）計算當前種群相似度指標值。

（4）若mod(t,G)=1，則根據(jù)雞群里每個粒子的適應(yīng)度值對雞群里每個個體進行排序，建立等級制度。

（5）如果t≥K,則根據(jù)公式（10）～（11）計算方差δ(t),然后轉(zhuǎn)步驟（6）；否則轉(zhuǎn)步驟（7）。

（6）如果δ(t)＜ε，則轉(zhuǎn)步驟（8）；否則轉(zhuǎn)步驟（7）。

（7）根據(jù)公式（9）對公雞個體進行更新。

（8）根據(jù)公式（13）對公雞進行位置更新。

（9）然后根據(jù)公式（16）對母雞位置更新。

（10）根據(jù)公式（6）對小雞位置更新。

（11）更新雞群中的全局最優(yōu)位置，t=t+1。

（12）若滿足算法終止條件，則迭代停止，輸出最優(yōu)解；否則轉(zhuǎn)步驟（3）。

4 數(shù)值實驗與結(jié)果分析

4.1 算法參數(shù)設(shè)置和測試函數(shù)

本文通過12 個基準測試函數(shù)對本文改進算法（ADLCSO）進行測試。為了保證比較的公平及合理性，令所有算法的種群規(guī)模為100，迭代次數(shù)為1 000，獨立運行30 次，所共有參數(shù)保持一致。各算法的參數(shù)設(shè)置見表1。在12 個測試函數(shù)中，f1～f4為單峰函數(shù)，f5～f11為多峰函數(shù)，f12為固定維數(shù)的多峰函數(shù)。函數(shù)理論最優(yōu)值都為0，12個基準測試函數(shù)表達式如下：

（1）Sphere函數(shù)

（2）BentCigar函數(shù)

（3）Discus函數(shù)

（4）High Conditioned Elliptic函數(shù)：

表1 三種算法的參數(shù)設(shè)置

（5）Ackley函數(shù)

（6）Griewank函數(shù)

（7）Rastrigin函數(shù)

（8）Powell函數(shù)

（9）Alpine函數(shù)

（10）Quartic函數(shù)

（11）Zakharov函數(shù)

（12）Bukin函數(shù)

4.2 兩種改進策略的有效性分析

為了驗證反向覓食機制和種群相似度指標的可行性和有效性，本文利用上述12 個函數(shù)對ADLCSO-I 算法和ADLCSO-II 算法進行測試。這里ADLCSO-I 算法是在CSO算法中只引入基于反向覓食機制的公雞位置更新策略；ADLCSO-II 算法是在CSO 算法中只引入基于種群相似度指標的母雞位置更新策略。ADLCSO-I算法和ADLCSO-II算法中的參數(shù)設(shè)置同表1中ADLCSO算法的參數(shù)設(shè)置相同。表2為對比實驗結(jié)果，圖2為3種不同策略對單峰函數(shù)f1和多峰函數(shù)f7的收斂圖。

圖2 部分測試函數(shù)的收斂圖

由表2 和圖2 可以看出，使用兩種改進策略的ADLCSO算法的尋優(yōu)精度、收斂速度和尋優(yōu)穩(wěn)定性都要優(yōu)于使用單一改進策略的ADLCSO-I算法和ADLCSO-II算法，ADLCSO-I 算法在大多函數(shù)優(yōu)化上的表現(xiàn)優(yōu)于ADLCSO-II 算法。單獨使用反向覓食機制和種群相似度對標準雞群算法性能的改進雖然有一定的效果但效果有限，組合的改進策略可以更加有效地提高算法的尋優(yōu)性能。

4.3 學(xué)習因子的有效性分析

本文在公雞個體位置的更新公式中加入了非線性遞減的學(xué)習因子，為了驗證該策略的優(yōu)越性，利用上述前9個測試函數(shù)對ADLCSO-I和ADLCSO-Iw進行實驗對比。這里ADLCSO-Iw算法是把ADLCSO-I算法中的學(xué)習因子替換成文獻[17]中的常數(shù)因子(w=0.5)。表3為實驗結(jié)果，圖3表示兩種算法尋優(yōu)收斂曲線圖。

表2 不同改進策略下ADLCSO算法的測試結(jié)果

由表3中數(shù)據(jù)可以看出，對于函數(shù)f1～f4和f8～f9來說，ADLCSO-I 算法的求解精度要優(yōu)于ADLCSO-Iw 算法。對于函數(shù)f5～f7，兩種學(xué)習因子求得的結(jié)果相同，但從圖3 上可以看出，ADLCSO-I 算法比 ADLCSO-Iw 算法的收斂速度有明顯的提高。綜上分析，無論是求解單峰函數(shù)還是多峰函數(shù)，非線性遞減的學(xué)習因子總體上都要優(yōu)于常數(shù)學(xué)習因子。

4.4 與標準算法實驗對比

本文通過求解上述12 個測試函數(shù)對標準雞群算法（CSO）、標準粒子群算法（PSO）和本文改進算法（ADLCSO）的性能進行比較。各算法參數(shù)設(shè)置見表1。表4 記錄了3 種算法求解的結(jié)果，圖4 表示在30 維問題上3種算法的收斂曲線圖。

圖3 ADLCSO-I算法和ADLCSO-Iw算法求解部分測試函數(shù)的收斂圖

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

從表4中可以看出，對于大部分測試函數(shù)，ADLCSO算法得到的平均值和標準差都為0，這說明ADLCSO算法的求解精度和穩(wěn)定性比其他兩種算法更高。

對于多峰函數(shù)f5、f9和f10，CSO 算法和 PSO 算法的尋優(yōu)精度明顯不如ADLCSO 算法，并且隨著維數(shù)的增加，CSO 算法和PSO 算法的尋優(yōu)效果有所下降，但ADLCSO 算法在高維上依舊能收斂到較高精度。對于多峰函數(shù)f6和f7，在10 維和30 維問題上CSO 算法和ADLCSO 算法的求解結(jié)果都達到了0，PSO 算法求解結(jié)果較差；但是在100 維的問題上時，CSO 算法和PSO 算法都出現(xiàn)陷入局部極值，ADLCSO算法卻依舊能收斂到最優(yōu)解。對于函數(shù)f11，CSO算法和PSO算法陷入局部極值，但ADLCSO算法在求解100維問題時求解精度達到了2.175 8E-205。以上分析說明在求解高維問題時，CSO算法和PSO算法都容易陷入局部極值，但ADLCSO算法依舊能收斂到較高精度，甚至對于大部分函數(shù)能求解到理論最優(yōu)值。

4.4.2 收斂速度分析

由圖4 可以看出，隨著迭代次數(shù)的增加，ADLCSO算法的收斂曲線下降很快，且在求解大部分函數(shù)時都能快速收斂到理論最優(yōu)解。

為了對比ADLCSO 算法在求解不同維數(shù)上的性能，本文給出了ADLCSO 算法在不同維數(shù)下的收斂圖（圖5）。從圖5 的收斂曲線可以得到，即使在求解高維問題時，ADLCSO算法的收斂速度仍然很快。

表4 三種算法的性能測試結(jié)果

綜合以上分析，與CSO 算法和PSO 算法相比，ADLCSO算法在穩(wěn)定性、求解精度與收斂速度上均有顯著提高。

4.5 與其他改進雞群算法的比較

將本文所提出的ADLCSO算法與PRCSO[17]、ICSO[18]、ICCSO[19]、DMCSO[20]和 GCSO[23]進行對比，對比數(shù)據(jù)見表5。5種改進雞群算法的參數(shù)設(shè)置和數(shù)據(jù)均來自于對應(yīng)的參考文獻。在表5 中，D為算法求解的問題維數(shù)，T為算法最大迭代次數(shù)。

由表5可以看出，ADLCSO算法的求解結(jié)果整體上優(yōu)于其他5種對比算法。

維數(shù)為30，算法迭代次數(shù)為500 時，ADLCSO 算法的尋優(yōu)效果明顯優(yōu)于ICSO 算法。對于函數(shù)f6和f7，ADLCSO 算法和ICSO 算法的求解結(jié)果都為0，但是由圖4的收斂曲線可知，在求解函數(shù)f6和f7時，ADLCSO算法在迭代40次左右就收斂了，而從文獻[18]中可以看出ICSO算法在迭代300次左右才收斂。

維數(shù)為 100，迭代次數(shù)為1 000 時，ADLCSO 算法求解的結(jié)果整體上優(yōu)于DMCSO 算法和GCSO 算法。對于函數(shù)f5，ADLCSO算法的求解的平均值稍差于GCSO算法；但是ADLCSO 算法得到的標準差卻為0，在求解穩(wěn)定性上ADLCSO算法明顯優(yōu)于GCSO算法。

以上分析說明，與以上5 種相關(guān)改進算法相比，ADLCSO算法的求解性能最好。

4.6 ADLCSO算法的時間復(fù)雜度分析

在標準雞群算法CSO 中，假設(shè)解空間的維數(shù)為n，種群大小為N，各參數(shù)的初始設(shè)置、生成一個均勻隨機數(shù)、求目標函數(shù)值、將所有個體的適應(yīng)值排序并得到當代最優(yōu)個體適應(yīng)度值的時間分別為t1、t2、f(n)、t3，則算法初始化階段的時間復(fù)雜度為：

圖4 3種算法求解測試函數(shù)的收斂圖

圖5 ADLCSO算法在不同維數(shù)下的部分測試函數(shù)收斂圖

表5 不同改進算法的對比實驗結(jié)果

進入迭代后，在雞群個體位置更新階段，假設(shè)：迭代次數(shù)為m，公雞個數(shù)為N1，母雞個數(shù)為N2，小雞個數(shù)為N3，新產(chǎn)生個體的適應(yīng)度計算時間為f(n)；公雞個體每一維進行位置更新的時間為t4；母雞個體每一維進行位置更新的時間為t5；個體每一維進行位置更新的時間為t6；新舊個體適應(yīng)值比較互換的時間為t7；每一次更新種群等級制度的時間為t8；則雞群個體位置更新階段的時間復(fù)雜度函數(shù)為：

綜上所述，標準雞群算法的時間復(fù)雜度為：

ADLCSO 算法在標準雞群算法的基礎(chǔ)上增加了公雞位置更新中的學(xué)習因子、方差和母雞位置更新中的相似度指標。假設(shè)：計算一次迭代的學(xué)習因子的時間為t9，計算一次迭代的方差的時間為t10，計算當前個體與最優(yōu)個體的相似度指標的時間為t11，則計算學(xué)習因子、方差和相似度指標的時間復(fù)雜度為：

從而ADLCSO算法的時間復(fù)雜度為：

由此可知，本文算法ADLCSO 和標準雞群算法CSO的時間復(fù)雜度依舊在同一個數(shù)量級。

5 總結(jié)

本文在雞群算法的基礎(chǔ)上提出了自適應(yīng)動態(tài)學(xué)習雞群優(yōu)化算法，在算法中引入反向覓食機制和種群相似度指標，分別對公雞和母雞的位置更新公式進行自適應(yīng)調(diào)整，并在公雞位置更新公式中加入非線性遞減學(xué)習因子。反向覓食機制增強了種群跳出局部極值的能力，提高了算法的收斂速度和求解精度；非線性遞減學(xué)習因子的引入較好地平衡了算法全局探索和局部開發(fā)能力，增強了算法的穩(wěn)定性；通過種群相似度指標對母雞的位置進行自適應(yīng)更新，抑制了種群多樣性的衰減，提高了算法的求解精度。最后，通過對12 個經(jīng)典測試函數(shù)的仿真實驗，驗證了ADLCSO算法的優(yōu)越性。