楊小健，徐小婷，李榮雨

YANG Xiaojian,XU Xiaoting,LI Rongyu

南京工業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，南京 211800

School of Computer Science and Technology,Nanjing University of Technology,Nanjing 211800,China

1 引言

群體智能（Swarm Intelligence，SI）作為一個新興領(lǐng)域自從20世紀80年代以來引起了多個學(xué)科領(lǐng)域研究人員的關(guān)注，其中發(fā)展比較快的有生物、經(jīng)濟、人工智能、社會等學(xué)科領(lǐng)域，群體智能已經(jīng)成為這些交叉學(xué)科研究的熱點和前沿領(lǐng)域[1]。人們研究發(fā)現(xiàn)，在自然界中的有些群體當中單個個體沒有很高的智能，但個體之間可以通過分工合作、相互協(xié)調(diào)，完成復(fù)雜的任務(wù)，最終表現(xiàn)出較高的智能。群體智能優(yōu)化算法（Swarm Intelligence Algorithm，SIA），就是在此基礎(chǔ)上利用數(shù)學(xué)方法抽象出數(shù)學(xué)模型并設(shè)計出的具有強大的問題求解能力的新型隨機優(yōu)化算法[2-3]。相對于傳統(tǒng)算法，它具有自學(xué)習(xí)、自組織、自適應(yīng)的特征和簡單、通用、易懂、魯棒性強、并行處理等優(yōu)點，它在解決許多優(yōu)化問題當中顯示了強大的優(yōu)越性[4-5]。例如遺傳算法（Genetic Algorithm，GA）[6]、粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）[7-8]、螢火蟲算法（Firefly Algorithm，F(xiàn)A）[9]、共生生物搜索算法（Symbiotic Organisms Search，SOS）[10]、布谷鳥算法（Cuckoo Algorithm，CA）[11-12]、蝙蝠算法（Bat Algorithm，BA）[13]等。以上列舉的這些群體智能優(yōu)化算法對于解決各領(lǐng)域復(fù)雜的優(yōu)化問題提供了新的有效途徑，成為當前研究的熱點[14]。文獻[15]劉天堂等人將遺傳算法用于求解能力約束弧路徑問題；文獻[16]Yoshida H等人將粒子群算法用于電壓控制以及電壓安全評估方面；文獻[17]Gandomi A H等人將螢火蟲算法用于混合變量結(jié)構(gòu)優(yōu)化中；文獻[18]XiaoLY等人將螢火蟲算法用于電力負荷預(yù)測中；文獻[19]Yang X S等人將布谷鳥搜索算法用于結(jié)構(gòu)優(yōu)化問題途徑的求解中。同時新的群體智能優(yōu)化算法仍在不斷出現(xiàn)和發(fā)展過程中。

雞群算法（Chicken Swarm Optimization，CSO）[20]是由Meng XB等人于2014年在第五屆群體智能國際會議中提出的一種群體智能優(yōu)化算法。和粒子群優(yōu)化算法、差分進化算法[21等智能優(yōu)化算法相比，該算法能夠在全局范圍內(nèi)隨機搜索，從而得到全局最優(yōu)解的概率大大增加。這表明雞群算法在求解全局最優(yōu)問題時確實顯示出一定的優(yōu)越性，但是文獻[20]只是在低維時（維數(shù)D=10）對基準測試函數(shù)進行了求解，它沒有考慮高維的情況并作進一步的求解與分析。

本文首先求解出高維時(D=100)的實驗數(shù)據(jù)，通過分析實驗結(jié)果，發(fā)現(xiàn)算法出現(xiàn)了尋優(yōu)精度降低、收斂速度變慢、偏離了全局最優(yōu)的情況。針對這種不足，提出一種基于交叉、變異的遺傳雞群算法（Genetic Chicken Swarm Optimization，GCSO），該算法在標準雞群算法的基礎(chǔ)上，利用遺傳算法的交叉、變異特性，增加公雞和母雞交配產(chǎn)生新小雞的概念，根據(jù)設(shè)定的交配周期和小雞淘汰更新周期，適應(yīng)度函數(shù)值最差的那部分小雞被及時淘汰掉，適應(yīng)度函數(shù)值較好的小雞則被保留下來，按照設(shè)定的交配周期和淘汰更新周期進行小雞的迭代及判斷。為了驗證本文所提算法的可行性和優(yōu)越性，實驗求解了10組基準函數(shù)問題。實驗結(jié)果表明，在高維情況下，該算法確實可以防止算法陷入局部最優(yōu)，并改善了算法的收斂性能以及穩(wěn)定性和魯棒性。

2 雞群算法（CSO）

2.1 算法介紹

CSO算法是根據(jù)自然界中雞群的等級制度及分配原則建立的，它歸納為以下4點原則。

原則1一個雞群包括若干子群，每個子群中包括一只公雞、若干母雞和小雞。

原則2通過適應(yīng)度函數(shù)值來建立等級制度并區(qū)分不同類型的雞。在雞群中，選取適應(yīng)度函數(shù)值最差的若干個體作為小雞，最好的若干個體作為公雞，剩余的若干個體就作為母雞；每個子群當中適應(yīng)度函數(shù)值最好的個體作為公雞，適應(yīng)度函數(shù)值最差的那部分作為小雞，母雞隨機選擇子群，同時母雞和小雞之間的母子關(guān)系也是隨機建立的。

原則3在每個子群中，等級制度、主導(dǎo)關(guān)系、母子關(guān)系是確定不變的，只有到達更新周期G時才會重新建立。

原則4在每個子群中，所有雞跟隨公雞尋找食物，它們可以阻止其他雞偷取自己的食物。假設(shè)，每只雞可以隨機偷取已經(jīng)被其他雞發(fā)現(xiàn)的食物，小雞尋找自己母親周圍的食物，并且主導(dǎo)能力越強的那些雞越有優(yōu)勢尋找到食物。

在CSO算法中，假設(shè)整個雞群數(shù)量為N，最好的RN只被假定為是公雞，它們可以在更廣泛的空間尋找食物，最差的CN只被視為小雞，其余的HN只被視為母雞，MN只被視為可以生育小雞的母雞。通過適應(yīng)度函數(shù)值 f來反映不同雞的地位和競爭力。適應(yīng)度函數(shù)值越好的個體代表地位更高，競爭力也越強，越會先得到食物。

根據(jù)等級制度及分配原則，可以確定公雞、母雞、小雞的位置更新公式如下所示。

公雞對應(yīng)的位置更新公式為：

式（1）中，Randn(0 ,σ2)表示標準差為 σ2、均值為0的正態(tài)分布；ε為一個取值非常小，無限接近0的常數(shù)，主要用于避免誤差；k表示在公雞組隨機選擇的可以代表公雞的指數(shù)；f表示x對應(yīng)的適應(yīng)度函數(shù)值。

母雞對應(yīng)的位置更新公式為：

式（3）中，Rand表示在[0 ,1]均勻取值的隨機數(shù)；r1∈[1 ,N ]，它表示與母雞i對應(yīng)的公雞；r2∈[1 ,N]，表示雞群中隨機選取的公雞或母雞，且r1≠r2。

通過分析式（4）、（5），可以得出 S2＜1＜S1。假設(shè)S1=0，則母雞i只跟隨其他的雞尋找食物；假設(shè)S2=0，則母雞i只尋找自己領(lǐng)地范圍內(nèi)的食物。

小雞對應(yīng)的位置更新公式為：

式（6）中，表示小雞i母親的位置；FL∈[0 ,2]，反映了小雞跟隨母親尋找食物的本領(lǐng)。

2.2 CSO算法性能分析

CSO算法只是在低維(D=10)情況下求解與分析的，為了分析CSO算法在高維時的情況，文中選取了以往求解優(yōu)化問題最常用的3組基準函數(shù)作為求解對象，在100維時進行了求解，并對比了GA和PSO兩種優(yōu)化算法。求解結(jié)果如表1所示。

通過表1，可以得出當高維時（D=100），CSO算法和GA算法以及PSO算法的實驗結(jié)果對比沒有像在低維時(D=10)那樣明顯的優(yōu)勢，基準函數(shù)Griewank和Rosenbrock的取值不理想。尤其是函數(shù)Rosenbrock的取值（粗體部分）已經(jīng)明顯偏離全局最優(yōu)解，收斂精度大大降低，算法性能表現(xiàn)不佳。

表1 3組基準函數(shù)在D=100時的實驗結(jié)果

3 遺傳雞群算法

針對CSO算法存在的不足，本文提出一種基于交叉、變異的遺傳雞群優(yōu)化算法（GCSO）。該算法的基本原理是：（1）引進交配周期（mating cycles），利用遺傳算法的交叉、變異特性，增加公雞和母雞交配產(chǎn)生新小雞的概念；通過交叉、變異過程得到新生小雞，并根據(jù)設(shè)定的條件判斷新生小雞的性別。（2）引進小雞淘汰更新周期（update cycles），淘汰更新率為0.1。這個過程中，適應(yīng)度函數(shù)值最差的那部分（前10%）小雞被淘汰掉，保留下來的小雞繼續(xù)充當新的小雞角色。（3）引進平均錯誤率(AER)，以評估算法對每組基準函數(shù)的平均錯誤率。

3.1 公雞、母雞交配產(chǎn)生新小雞以及新生小雞淘汰更新過程

步驟1從所有公雞組當中選擇相應(yīng)的基因片段，確定基因型，求解得到其適應(yīng)度函數(shù)值 fit1；同理，從所有母雞組當中選取相應(yīng)的基因片段，確定基因型，求解得到其適應(yīng)度函數(shù)值 fit2。

步驟2對選取的公雞和母雞基因片段進行重組（交叉率pc=0.8），得到新的公雞和母雞基因型。

步驟3判斷是否發(fā)生基因突變（變異率pm=0.2），根據(jù)判斷結(jié)果得到新的公雞、母雞基因型。根據(jù)新得到的公雞、母雞基因型，求解對應(yīng)的適應(yīng)度函數(shù)值 fit11、fit22。

步驟4比較 fit11、fit22和 fit1、fit2的大小。如果 fit11＜fit1、fit22＜fit2，則用 fit11和 fit22替代 fit1和 fit2，并將其作為新生小雞基因，將小雞基因型進行存儲（孵化階段）。

步驟5選擇新出生小雞的前10%進行更新，根據(jù)更新結(jié)果作出判斷，最終淘汰適應(yīng)度函數(shù)值差、有缺陷的小雞。

根據(jù)GCSO算法的基本原理（3），平均錯誤率公式定義如下：

式（7）中，i∈[1,2,…,10]，取整數(shù)；g′為最優(yōu)值的平均值，ki表示第i組基準函數(shù)對應(yīng)的全局最優(yōu)解。

3.2 GCSO算法的實現(xiàn)步驟

步驟1初始化雞群，設(shè)置種群規(guī)模N、公雞數(shù)量RN、母雞數(shù)量HN、小雞數(shù)量CN、雞媽媽數(shù)量MN、更新周期G、交配周期mating cycles、小雞淘汰更新周期update cycles、交叉算子 pc、變異算子 pm、最大迭代次數(shù)iterMAX、問題維度D等。

步驟2計算t=0時雞群N的適應(yīng)度函數(shù)值。

步驟3判斷t%G=0是否成立，若成立，則根據(jù)適應(yīng)度函數(shù)值在雞群中建立等級制度。并根據(jù)等級制度把整個雞群劃分成若干個不同的子群，在每個子群中確立母雞和小雞之間的對應(yīng)關(guān)系。

步驟4對于，判斷i表示的對象，當i表示公雞時，根據(jù)式（1）求解；當i表示母雞時，根據(jù)式（3）求解；當i表示小雞時，根據(jù)式（6）求解。

步驟5判斷是否滿足交配周期條件，若滿足，則通過交配步驟得到新生小雞。

步驟6判斷是否滿足淘汰更新周期條件，若滿足，則對新生小雞進行更新與淘汰。

步驟7計算新解的適應(yīng)度函數(shù)值，并與當前最優(yōu)解作比較，如果新解的適應(yīng)度函數(shù)值優(yōu)于當前最優(yōu)解的，則用新解替代當前最優(yōu)解。

步驟8判斷是否滿足迭代終止條件，如果滿足則結(jié)束算法，輸出求解結(jié)果；否則轉(zhuǎn)到步驟3繼續(xù)迭代和判斷。

4 實驗結(jié)果及分析

4.1 基準函數(shù)類型及參數(shù)設(shè)置

為了驗證文中所提算法的可行性和有效性，實驗通過對10組基準函數(shù)分別在維度D=20和D=100時進行求解，同時與GA、PSO、CSO三種算法進行對比。為了公平起見，所有的算法種群規(guī)模N為100，每種算法獨立運行30次，仿真軟件為matlab2014a，最大迭代次數(shù)iterMAX 為1 000。

實驗時，選取的10組基準函數(shù)包括單模態(tài)和多模態(tài)兩種情況。其中，F(xiàn)2、F7、F8、F9、F10為單模態(tài)；F1、F3、F4、F5、F6為多模態(tài)。通過對單模態(tài)和多模態(tài)兩類函數(shù)的求解，得出的結(jié)果具有普遍性，可以更全面地反映文中各種算法的性能。10組基準函數(shù)類型如表2所示。四種算法的參數(shù)設(shè)置如表3所示。

4.2 對比實驗及結(jié)果分析

實驗通過求解10組基準函數(shù)的最好值、最差值、平均值、標準差來判斷算法解的優(yōu)劣。在相同目標條件之下，最好值和最差值反映了算法的取值情況；平均值反映了算法所能達到的求解精度；標準差反映了算法的穩(wěn)定性和魯棒性。10組基準函數(shù)分別在維度D=20和D=100時的求解結(jié)果如表4和表5所示。表中求解結(jié)果最好的值用粗體表示。

表2 基準函數(shù)

表3 四種算法的參數(shù)設(shè)置

表4 10組基準函數(shù)在D=20時的實驗結(jié)果

表5 10組基準函數(shù)在D=100時的實驗結(jié)果

通過表4可以得到，在D=20時GCSO算法和CSO算法的實驗結(jié)果遠遠優(yōu)于GA算法和PSO算法的實驗結(jié)果。進一步分析GCSO算法和CSO算法的實驗結(jié)果，發(fā)現(xiàn)GCSO算法的實驗結(jié)果均優(yōu)于CSO算法的實驗結(jié)果，尤其是對于基準函數(shù)F5、F6、F9，GCSO算法可以達到全局最優(yōu)，而CSO算法卻沒有達到全局最優(yōu)。

通過表5可以得到，D=100時CSO算法已經(jīng)明顯偏離全局最優(yōu)，F(xiàn)1、F4、F7、F8、F9的求解結(jié)果顯示其已經(jīng)明顯陷入局部最優(yōu)，求解結(jié)果不理想。同時GCSO算法卻能克服局部收斂并得到較好的結(jié)果，這從除F4之外的9組基準函數(shù)的實驗結(jié)果均可體現(xiàn)出來。

綜合表4和表5可以得到，在D=20和D=100時GCSO算法的求解結(jié)果均優(yōu)于CSO算法的求解結(jié)果，且遠遠優(yōu)于GA算法和PSO算法的求解結(jié)果。此外，由于平均值反映了算法所能達到的求解精度；標準差反映了算法的穩(wěn)定性和魯棒性。通過表4和表5也可得出GCSO的求解精度、穩(wěn)定性以及魯棒性優(yōu)于CSO、PSO、GA這三種算法的。

為了反映10組基準函數(shù)在各種算法運行下的平均錯誤率，根據(jù)公式（7）得到的實驗結(jié)果如表6所示。

表6 10組基準函數(shù)的平均錯誤率

通過表6，可以得出GCSO算法的平均錯誤率最低。尤其在F1～F5、F7～F10這9組基準函數(shù)上和其他三種算法求解結(jié)果的數(shù)量級相差很大，區(qū)分度好。

為了更為直觀地反映每種算法的尋優(yōu)精度以及收斂速度。在D=100時，每種函數(shù)獨立運行30次，得到在D=100時的函數(shù)收斂曲線圖，如圖1所示。

通過圖1，可以看出GCSO算法的收斂精度和收斂速度均優(yōu)于CSO算法，且遠遠優(yōu)于PSO算法和GA算法的。這體現(xiàn)了GCSO算法在高維時，也能保持良好的性能。

4.3 算法復(fù)雜度分析

算法的復(fù)雜度評估主要包括空間復(fù)雜度和時間復(fù)雜度兩方面。

空間復(fù)雜度是指算法在計算機內(nèi)執(zhí)行時所需要的最大存儲空間的度量。文中四種算法的空間復(fù)雜度相當。時間復(fù)雜度是指一種算法執(zhí)行時所消耗時間的度量。對于群體智能優(yōu)化算法而言，時間復(fù)雜度正比于種群規(guī)模N和迭代次數(shù)t。通過分析，可以得出GA算法的時間復(fù)雜度為O(Nt)；PSO算法的時間復(fù)雜度為O(Nt)；CSO算法的時間復(fù)雜度為O(Nt)；GCSO算法的時間復(fù)雜度為O(2Nt)(O(Nt+Nt))。由于迭代次數(shù)很大(t=1 000)，所以時間復(fù)雜度主要取決于迭代次數(shù)t。GCSO算法的時間復(fù)雜度和其他三種算法相比，計算成本有所增加，但仍在可接受的范圍之內(nèi)。

圖1 GA、PSO、CSO和GCSO對10組基準函數(shù)在D=100時的收斂曲線比較

5 結(jié)束語

開發(fā)能力和探索能力是影響算法性能的兩大決定因素，如何把握兩者之間的矛盾平衡一直是智能優(yōu)化算法重點關(guān)注的方面。針對CSO算法在求解高維復(fù)雜優(yōu)化問題時存在收斂速度慢、尋優(yōu)精度不高、容易陷入局部最優(yōu)等不足，本文提出一種GCSO算法。該算法是在CSO算法基礎(chǔ)上增加公雞和母雞交配、變異產(chǎn)生新小雞的概念，設(shè)定公雞、母雞交配周期和小雞淘汰更新周期，并引入了交叉算子、變異算子以及衡量算法求解值和實際值之間誤差的平均錯誤率AER。實驗時和GA、PSO、CSO三種算法進行了對比。仿真實驗分別從解的質(zhì)量、平均錯誤率、尋優(yōu)精度以及收斂速度等角度對各種算法進行了測試和驗證。10組基準函數(shù)的仿真結(jié)果表明，文中提出的GCSO算法在尋優(yōu)精度、平均錯誤率、解的質(zhì)量、穩(wěn)定性以及魯棒性等方面均是最優(yōu)的。尤其在高維時也能保持良好的性能，從而證明了該算法對于有效求解高維復(fù)雜優(yōu)化問題的可行性和有效性。

然而，文中提出的GCSO算法也存在局限性，相比其他三種優(yōu)化算法，參數(shù)數(shù)量有所增加，同時在D=100時對F4求解結(jié)果不是特別理想（雖然和其他三種算法相比求解結(jié)果較好，但針對F4本身而言求解結(jié)果不理想）。其實，F(xiàn)4函數(shù)的求解結(jié)果不理想的原因可以由“No free lunch”理論來解釋。它告訴我們沒有哪一種算法可以解決所有類型的優(yōu)化問題。因此每種優(yōu)化算法才有了不斷完善與改進的空間。基于以上原因，如何進一步改善提出算法的性能，使其適合更多的測試函數(shù)，同時考慮將這種思想應(yīng)用到其他實際工程問題的求解當中，這將是下一步要做的工作。

參考文獻：

[1]張鵬，劉弘，劉鵬.改進的蜂群算法及其在CBD選址規(guī)劃中的應(yīng)用[J].計算機科學(xué)，2013（8）：210-213.

[2]魏平，徐成賢，段成德.全局智能優(yōu)化集成算法研究[J].西安交通大學(xué)學(xué)報，2009，43（12）：60-64.

[3]Beheshti Z，Shamsuddin S M H.A review of populationbased meta-heuristic algorithms[J].International Journal of Advance in Soft Computing&Its Applications，2013，5（1）：1-35.

[4]高維尚，邵誠，高琴.群體智能優(yōu)化中的虛擬碰撞：雨林算法[J].物理學(xué)報，2013，62（19）：28-43.

[5]Grefenstette J J.Optimization of control parameters for genetic algorithm[J].IEEE Transactions on Systems，Man and Cybernetics，1986，16（1）：122-128.

[6]Lev B，Tsoukalas J.An introduction to genetic algorithms[J].Interfaces，1999，29（3）：105-107.

[7]Fourie P C，Groenwold A A.The particle swarm optimization algorithm in size and shape optimization[J].Structural and Multidisciplinary Optimization，2002，23（4）：259-267.

[8]趙嘉，呂莉，孫輝.自適應(yīng)精英反向?qū)W習(xí)的粒子群優(yōu)化算法[J].小型微型計算機系統(tǒng)，2015，36（9）：2166-2171.

[9]Yang X S.Firefly algorithm，stochastic test functions and design optimization[J].International Journal of Bio-inspired Computation，2010，2（2）：78-84.

[10]周虎，趙輝，周歡，等.自適應(yīng)精英反向?qū)W習(xí)共生生物搜索算法[J].計算機工程與應(yīng)用，2016，52（19）：161-166.

[11]Walton S，Hassan O，Morgan K，et al.Modified cuckoo search：A new gradient free optimization algorithm[J].Chaos Solitons&Fractals，2011，44（9）：710-718.

[12]Rajabioun R.Cuckoo optimization algorithm[J].Applied Soft Computing，2011，11（8）：5508-5518.

[13]陳梅雯，鐘一文，王李進.一種求解多維全局優(yōu)化問題的改進蝙蝠算法[J].小型微型計算機系統(tǒng)，2015，36（12）：2749-2753.

[14]孔飛，吳定會.一種改進的雞群算法[J].江南大學(xué)學(xué)報：自然科學(xué)版，2015，14（6）：681-688.

[15]劉天堂，江志斌，胡鴻韜，等.加強的混合遺傳算法求解能力約束弧路徑問題[J].上海交通大學(xué)學(xué)報，2013，47（4）：619-625.

[16]Yoshida H，Kawata K，F(xiàn)ukuyama Y，et al.A particle swarm optimization for reaction power and voltage control considering voltage security assessment[J].IEEE Transactions on Power Systems，2000，15（4）：1232-1239.

[17]Gandomi A H，Yang X S，Alavi A H.Mixed variable structural optimization using firefly algorithm[J].Computers&Structures，2011，89（23/24）：2325-2336.

[18]Xiao L Y，Shao W，Liang T L，et al.A combined model based on multiple seasonal patterns and modified firefly algorithm for electrical load forecasting[J].Applied Energy，2016，167：135-153.

[19]Gandomi A H，Yang X S，Ajavi A H.Cuckoo search algorithm：A metaheuristic approach to solve structural optimization problems[J].Engineering with Computers，2013，29（1）：17-35.

[20]Meng X B，Liu Y，Gao X Z，et al.A new bio-inspired algorithm：Chicken swarm optimization[C]//5th International Conference on Swarm Intelligence，2014：86-94.

[21]Das S，Suganthan P N.Differential evolution：A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation，2011，15（1）：4-31.