求解高維優化問題的遺傳雞群優化算法

楊小健，徐小婷，李榮雨

YANG Xiaojian,XU Xiaoting,LI Rongyu

南京工業大學 計算機科學與技術學院，南京 211800

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

1 引言

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

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

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

2 雞群算法（CSO）

2.1 算法介紹

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

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

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

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

原則4在每個子群中，所有雞跟隨公雞尋找食物，它們可以阻止其他雞偷取自己的食物。假設，每只雞可以隨機偷取已經被其他雞發現的食物，小雞尋找自己母親周圍的食物，并且主導能力越強的那些雞越有優勢尋找到食物。

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

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

公雞對應的位置更新公式為：

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

母雞對應的位置更新公式為：

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

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

小雞對應的位置更新公式為：

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

2.2 CSO算法性能分析

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

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

表1 3組基準函數在D=100時的實驗結果

3 遺傳雞群算法

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

3.1 公雞、母雞交配產生新小雞以及新生小雞淘汰更新過程

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

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

步驟3判斷是否發生基因突變（變異率pm=0.2），根據判斷結果得到新的公雞、母雞基因型。根據新得到的公雞、母雞基因型，求解對應的適應度函數值 fit11、fit22。

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

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

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

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

3.2 GCSO算法的實現步驟

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

步驟2計算t=0時雞群N的適應度函數值。

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

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

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

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

步驟7計算新解的適應度函數值，并與當前最優解作比較，如果新解的適應度函數值優于當前最優解的，則用新解替代當前最優解。

步驟8判斷是否滿足迭代終止條件，如果滿足則結束算法，輸出求解結果；否則轉到步驟3繼續迭代和判斷。

4 實驗結果及分析

4.1 基準函數類型及參數設置

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

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

4.2 對比實驗及結果分析

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

表2 基準函數

表3 四種算法的參數設置

表4 10組基準函數在D=20時的實驗結果

表5 10組基準函數在D=100時的實驗結果

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

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

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

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

表6 10組基準函數的平均錯誤率

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

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

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

4.3 算法復雜度分析

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

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

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

5 結束語

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

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

參考文獻：

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

[2]魏平，徐成賢，段成德.全局智能優化集成算法研究[J].西安交通大學學報，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]高維尚，邵誠，高琴.群體智能優化中的虛擬碰撞：雨林算法[J].物理學報，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]趙嘉，呂莉，孫輝.自適應精英反向學習的粒子群優化算法[J].小型微型計算機系統，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]周虎，趙輝，周歡，等.自適應精英反向學習共生生物搜索算法[J].計算機工程與應用，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]陳梅雯，鐘一文，王李進.一種求解多維全局優化問題的改進蝙蝠算法[J].小型微型計算機系統，2015，36（12）：2749-2753.

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

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

[16]Yoshida H，Kawata K，Fukuyama 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.