基于信息交互的改進雞群優(yōu)化算法

童斌斌，周曉南，何 慶*

(1.貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴州 貴陽 550025； 2.貴州大學(xué) 學(xué)報編輯部，貴州 貴陽 550025)

群體智能優(yōu)化算法是一種仿生學(xué)優(yōu)化算法，通過模擬生物的個體行為及群體行為發(fā)展而來[1]。如粒子群優(yōu)化(particle swarm optimization，PSO)算法、蟻群優(yōu)化(ant colony optimization，ACO)算法、人工魚群算法(artificial fish swarm algorithm，AFSA)、蝙蝠算法 (bat algorithm，BA)、人工蜂群 (artificial bee colony，ABC)算法等群體智能優(yōu)化算法[2-6]。目前，群體智能優(yōu)化算法已成為科學(xué)研究領(lǐng)域的熱門研究課題，并受到廣泛關(guān)注和應(yīng)用。

MENG等[7]于2004年提出了一種雞群優(yōu)化算法CSO，通過模擬雞群的等級制度、雞群的個體和群體行為，將雞群分為多個子群，每個子群只包含一只公雞，隨從多只母雞和多只小雞。不同類型的個體以不同的方式移動，且每個子雞群中個體都圍繞公雞來尋找食物。

由于雞群優(yōu)化算法具有高效、易于實現(xiàn)、參數(shù)少等優(yōu)點，不少專家學(xué)者對它進行改進并實際應(yīng)用。李鵬等[8]針對無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)節(jié)點定位精度不足的問題，提出一種與典型定位模型相結(jié)合的改進雞群優(yōu)化(integrated chicken swarm optimization，ICSO)算法。用pareto距離分級的分類算法優(yōu)化雞群算法種群比例，在母雞位置公式中引入隨機游走策略增大搜索范圍，對小雞的移動方式引入凈能量增益以提高定位精度。吳忠強等[9]針對雞群優(yōu)化算法本身存在高維度運算，易出現(xiàn)偏差，對其改進并應(yīng)用到光伏系統(tǒng)的最大功率點跟蹤(maximum power point tracking，MPPT)控制中。通過引入混沌序列方法，自適應(yīng)慣性權(quán)重，改進小雞個體的跟隨系數(shù)，來增加種群的均勻性、隨機性，同時改善了雞群優(yōu)化算法的部分巡游策略，避免算法因早熟收斂而陷入局部極值。崔東文[10]使用雞群優(yōu)化算法為投影跟蹤模型找到最優(yōu)的投影方向，并建立雞群優(yōu)化算法-投影跟蹤洪水和干旱災(zāi)害評估模型。以文山州1990—2013年洪旱災(zāi)害評估為例，利用一系列旱澇災(zāi)害預(yù)報的均值和方差，建立旱澇災(zāi)害評估的分類標準，評估實例，有效提高評估準確性，通過優(yōu)化投影方向，避免尋優(yōu)結(jié)果變化范圍過大的不足。

雖然CSO算法已經(jīng)應(yīng)用于諸多領(lǐng)域，但算法仍存在搜索活力不足、收斂能力差[11-12]等缺點，為此，國內(nèi)外學(xué)者一直在進一步研究和改進算法。楊菊蜻等[13]提出了一種混合改進的雞群優(yōu)化算法，通過引入反向?qū)W習、邊界變異操作，模擬退火算子，提高算法的全局搜索能力和整體性能，避免了CSO算法早熟收斂和易陷入局部最優(yōu)等問題。李賓等[14]針對CSO算法個體更新效率低和全局搜索能力弱等缺點，提出了一種改進的雞群優(yōu)化算法，該算法結(jié)合狼群優(yōu)化、粒子群及螢火蟲算法個體更新的思想，并引入去重算子和改進因子來提高ICSO算法的全局尋優(yōu)能力和精度。韓斐斐等[15]提出了一種改進版雞群優(yōu)化(enhanced chicken swarm optimization，ECSO)算法，對子雞群中的小雞、母雞、公雞的位置更新上分別加上“引領(lǐng)者”策略、偏好隨機游動策略以及自適應(yīng)變異策略，提升算法的收斂能力和搜索活力。楊小健等[16]引入交叉變異算子得到了一種遺傳雞群優(yōu)化(genetic chicken swarm optimization，GCSO)算法，提升了算法在求解高維問題上的魯棒性。

上述改進雞群優(yōu)化算法在一定程度上提升了算法的性能，但是仍然存在高維問題求解困難、收斂速度慢等問題，且同一種子群中的不同個體之間沒有信息的交流。對此，本文提出了一種基于信息交互的改進雞群優(yōu)化算法ISCSO，將當前最優(yōu)位置的信息引入公雞和母雞的位置更新，使得不同類型個體之間有著更強的聯(lián)系，從而提升整個雞群的搜索能力；在此基礎(chǔ)上引入邊界變異策略，提升種群的多樣性。大量實驗表明，該算法在收斂速度，高維、超高維尋優(yōu)等方面都優(yōu)于雞群優(yōu)化算法及其改進算法。

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

在雞群優(yōu)化算法中，將雞群分為多個子群，雞群中適應(yīng)度最好的若干個體為公雞，最差的若干個體為小雞，剩下的個體為母雞，且每個子群中限制只存在一只公雞，子群中其他個體都圍繞公雞搜索移動。隨機建立小雞跟隨母雞、母雞跟隨公雞的等級制度，這種關(guān)系一旦確定，直到G代之后才會更新。

雞群中雞的類型分為3種：公雞、母雞和小雞。每種類型的個體的移動方式是不同的。子群中適應(yīng)度最好的若干個體是公雞，所對應(yīng)的位置更新方式如下所示：

(1)

(2)

式中：randn(0,σ2)為服從均值為0，方差為σ2的高斯分布；k∈[1,N],k≠i為公雞中不同于公雞i的個體，它是隨機選擇的；ε為很小的常數(shù)；f為適應(yīng)度。

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

(3)

其中：

(4)

A2=exp(fr2-fi)。

(5)

式中：r1為個體i所在子群的公雞；r2為隨機選擇的公雞個體或母雞個體(r1≠r2)。

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

(6)

式中：l為第i只小雞對應(yīng)的母雞；F為跟隨系數(shù)。

2 改進的雞群優(yōu)化算法ISCSO

2.1 進化機制的改變

CSO算法中的公雞、母雞和小雞的更新方式是不同的，相互之間沒有聯(lián)系，且子雞群中的每個個體都圍繞該子群的公雞尋找食物，公雞的隨機移動極易使得子群陷入局部最優(yōu)，同時，整個種群收斂速度較慢。針對上述缺點，本文在公雞和母雞之間增加信息交互，以提高算法的收斂能力和尋優(yōu)能力。

改進后公雞對應(yīng)的位置更新為

(7)

改進后母雞對應(yīng)的位置更新為

(8)

2.2 邊界變異的改進

雞群優(yōu)化算法在雞群搜索食物的過程，會有個體超出搜索邊界，因此，提出將超出搜索邊界的個體從最接近的邊界的位置重新開始搜索。位置更新為

(9)

式中：Lbj,Ubj分別為上界和下界。

顯然，讓上下界來代替約束值，會降低算法的收斂速度，同時減少種群的多樣性。本文提出的方法在邊界處理上加上隨機擾動，使得越界個體不再由邊界開始搜索，從而提升種群的多樣性，加快收斂速度，具體如下：

(10)

2.3 算法描述

綜合上述分析，將ISCSO算法的尋優(yōu)步驟描述如下：

步驟1設(shè)置ISCSO算法的相關(guān)參數(shù)，公雞、母雞、小雞所占種群比例，種群規(guī)模，更新代數(shù)等。

步驟2種群初始化，結(jié)合邊界變異進行越界處理，計算每個個體的適應(yīng)度，并記錄最優(yōu)個體及其位置。

步驟3確定個體的適應(yīng)度值，記錄當前全局最優(yōu)適應(yīng)度值即最優(yōu)個體位置，同時確定種群的等級制度。

步驟4進入迭代尋優(yōu)更新，判斷是否滿足更新條件。若條件不成立，則對小雞、公雞、母雞按式 (6) 和改進后的式(7) (8) 進行位置更新；若條件成立，則重新確定種群的等級制度和母子關(guān)系等。

步驟5保存當前最優(yōu)個體及其位置。

步驟6判斷是否滿足程序終止條件。若滿足條件則程序終止，否則繼續(xù)執(zhí)行步驟4。

ISCSO算法流程如圖1所示。

3 實驗仿真與結(jié)果分析

3.1 雞群優(yōu)化算法仿真

為了檢驗本文方法的性能，通過選擇多組標準測試函數(shù)進行驗證。函數(shù)的具體形式見表1。測試函數(shù)集中的函數(shù)包含單峰、多峰、高維、低維等特征，能夠全面客觀地反映算法的尋優(yōu)性能。仿真實驗環(huán)境基于Windows 10操作系統(tǒng)，8 GB內(nèi)存，利用Matlab R2016b進行編程測試。

圖1 ISCSO算法流程Fig.1 ISCSO algorithm flowchart

仿真測試中，ISCSO算法的最大迭代次數(shù)M為1 000，種群大小N為100，維數(shù)D為30，所有測試函數(shù)的搜索范圍為[-100，100]。NR、NH、NC和NM所占比重分別是0.2、0.6、0.1、0.1，更新代數(shù)G=10，F(xiàn)為[0.5,1]的隨機數(shù)。為了消除算法的偶然性，每個測試函數(shù)獨立運行30次，得到測試函數(shù)的均值、方差。將本文ISCSO算法和CSO算法、OBSA-CSO算法[13]、GCSO(20D)算法[16]進行對比，結(jié)果見表2。表中Mean為均值，Std為方差。將ISCSO算法與雞群優(yōu)化算法進行仿真實驗，結(jié)果如圖2所示。為了仿真結(jié)果直觀清楚，圖2僅采用前100代數(shù)據(jù)進行分析,橫坐標代表迭代次數(shù)，縱坐標代表最優(yōu)函數(shù)值。對表2和圖2進行分析比較。

F1函數(shù)：該函數(shù)是一個單峰測試函數(shù)，擁有全局唯一一個最小值，能夠很好地體現(xiàn)算法的尋優(yōu)能力和收斂速度。由表2、圖2(a)可以看出，CSO算法不能尋找到理論最優(yōu)值且收斂速度較慢；文獻[13]雖然能找到理論最優(yōu)值，但是算法缺少了對方差的比較；文獻[16]不僅不能尋找到理論最優(yōu)值，而且在20維的情況下，算法也不能表現(xiàn)出較好的性能；本文ISCSO算法不僅能找到理論最優(yōu)值，而且算法在10代以內(nèi)已經(jīng)收斂，與CSO算法相比，不論是尋優(yōu)精度，還是收斂速度都體現(xiàn)出更好的魯棒性。

表1 測試算法性能的標準測試函數(shù)Tab.1 Standard test functions for testing algorithm performance

表2 與其他優(yōu)化算法對比Tab.2 Comparison with other optimization algorithms

F2函數(shù)：該函數(shù)功能很復(fù)雜，擁有很多局部最小值，能很好地檢驗算法跳出局部最優(yōu)的性能。由表2、圖2(b)可以看出，CSO算法不能尋找到理論最優(yōu)值且收斂速度較慢；文獻[13]雖然能找到理論最優(yōu)值，但是算法缺少了對方差的比較；文獻[16]不僅不能尋找到理論最優(yōu)值，而且在20維的情況下，算法也不能表現(xiàn)出較好的性能；ISCSO算法與其他算法相比，在尋優(yōu)精度和收斂速度上具有更高的性能，且算法更加穩(wěn)定。

F3函數(shù)：該函數(shù)是一個復(fù)雜多峰函數(shù)，擁有無數(shù)局部最優(yōu)點，極難尋到全局最優(yōu)解。由表2、圖2(c)可知，CSO算法不論是尋優(yōu)精度還是收斂速度，都不能達到理想效果；文獻[13]沒有做該函數(shù)的仿真；雖然文獻[16]在該函數(shù)求解上能找到理論最優(yōu)值，但ISCSO算法不僅能找到理論最優(yōu)值，而且與文獻[16]相比，增加了函數(shù)的維度，并在40代左右時收斂；ISCSO算法不論是尋優(yōu)精度還是收斂速度，都具有更好的性能。

F4函數(shù)：該函數(shù)是一個非凸函數(shù)，算法很難辨別該函數(shù)的尋優(yōu)方向，故極難尋到理論最優(yōu)值。由表2、圖2(d)可以看出，所有優(yōu)化算法都極難找到最優(yōu)值，ISCSO算法將尋優(yōu)范圍擴大到[-100，100]，雖不能找到理論最優(yōu)，但與其他優(yōu)化算法相比，尋優(yōu)精度更好，且收斂速度更快。

“逆推”的起點雖然是當下的世界，但能“推”到哪里其實就是找到某一個歷史上的節(jié)點，然后使這個節(jié)點再成為“順述”的起點……“逆推”是從當下的生活世界出發(fā)，目的在強調(diào)“當下”對于歷史敘述的意義以及地方人群的活動對形塑歷史的重要性。[注]趙世瑜：《結(jié)構(gòu)過程·禮儀標識·逆推順述——中國歷史人類學(xué)研究的三個概念》，《清華大學(xué)學(xué)報(哲學(xué)社會科學(xué)版)》2018年第1期；趙世瑜、李松、劉鐵梁：《“禮俗互動與近現(xiàn)代中國社會變遷”三人談》，《民俗研究》2016年第6期。

F5函數(shù)：該函數(shù)是一個復(fù)雜多峰函數(shù)，在[-5.12，5.12]范圍內(nèi)有無數(shù)個極小值點，是一種典型的非線性多模態(tài)函數(shù)，很難找到理論最優(yōu)值。本文將函數(shù)測試范圍擴大到[-100，100]，由表2、圖2(e)可以看出，CSO算法在該函數(shù)上可以找到理論最優(yōu)值但是收斂速度慢；文獻[13]也能找到函數(shù)最優(yōu)值，但是沒有做方差的比較，同時收斂速度較慢；文獻[16]在該函數(shù)處于20維的情況下，不僅無法找到理論最優(yōu)值，而且算法不夠穩(wěn)定；ISCSO算法在10代以內(nèi)就找到理論最優(yōu)值，比其他算法擁有更好的尋優(yōu)性能和收斂性能。

圖2 ISCSO與CSO收斂曲線Fig.2 ISCSO and CSO convergence curve

F6函數(shù)：該函數(shù)與F5函數(shù)類似，也是一個典型的非線性多模態(tài)函數(shù)，在取值范圍內(nèi)存在無數(shù)個極小值，且數(shù)目與問題維度相關(guān)，通常被認為是優(yōu)化算法中很難處理的復(fù)雜多峰函數(shù)。由表2、圖2(f)可以看出：CSO算法在該函數(shù)上可以找到理論最優(yōu)值但是收斂速度慢；文獻[13]也能找到函數(shù)最優(yōu)值，但是沒有做方差的比較，同時收斂速度較慢；文獻[16]在該函數(shù)處于20維的情況下，不僅無法找到理論最優(yōu)值，而且算法不夠穩(wěn)定；而ISCSO算法與其他算法相比，擁有更好的收斂速度和尋優(yōu)精度。

3.2 維度變化分析

為了觀察和比較ISCSO算法隨維度變化的影響，本次實驗添加了在50維和100維情況下，CSO算法與ISCSO算法的對比，如圖3—圖8所示。表3展示了CSO算法與ISCSO算法的對比結(jié)果。為排除算法偶然性，實驗中每個測試函數(shù)獨立運行30次，取均值和方差進行比較，其中，最大迭代次數(shù)M= 1 000，種群規(guī)模N=100，所有測試函數(shù)的搜索范圍為[-100，100]。NR、NH、NC和NM分別為0.2N、0.6N、0.1N、0.1N，F(xiàn)為[0.5，1]的隨機數(shù)，G= 10。

圖3 F1的收斂曲線Fig.3 Convergence curve of F1

圖4 F2的收斂曲線Fig.4 Convergence curve of F2

圖5 F3的收斂曲線Fig.5 Convergence curve of F3

圖6 F4的收斂曲線Fig.6 Convergence curve of F4

圖7 F5的收斂曲線Fig.7 Convergence curve of F5

圖8 F6的收斂曲線Fig.8 Convergence curve of F6

表3 與雞群優(yōu)化算法的高維比較Tab.3 High-dimensional comparison with the chicken swarm optimization algorithm

從表2、表3可以看出：當問題維數(shù)由30變到50、100時，CSO算法已經(jīng)不能夠解決高維問題，無法找到最優(yōu)值，每上升一次維度，CSO算法的最優(yōu)解上升15～20個數(shù)量級，且方差隨之增大，顯然，CSO算法在高維問題解決上體現(xiàn)了不足；而本文ISCSO算法，從表3中F1、F3、F5、F6函數(shù)的測試結(jié)果看，隨著維度的提高，始終能找到理論最優(yōu)值，在函數(shù)F2上，也表現(xiàn)出與測試30維的結(jié)果相當，且方差很小，證明了算法的穩(wěn)定性較好。

根據(jù)上述結(jié)果分析，隨著維度的提升，算法的收斂速度和精度并沒有受到影響。從30維、50維和100維的相同測試函數(shù)的收斂圖可以看出，隨著維度提升，ISCSO算法都能快速達到收斂。通過實驗證明，ISCSO算法的尋優(yōu)能力和收斂速度得到了體現(xiàn)，具有很好的搜索活力和精度，能夠較好地解決高維和超高維問題。這些都歸因于在每一次位置更新時，引入了信息交互的成分，使得公雞和母雞之間的聯(lián)系更為緊密，同時，對超出邊界的個體引入了隨機因子，大大地增加了種群的多樣性，從而提升了種群的收斂速度。

綜上所述，ISCSO算法即便是在高維復(fù)雜的情況下，仍然能夠較好快速地向理論最優(yōu)值逼近，甚至大部分能找到理論最優(yōu)值，克服了雞群優(yōu)化算法求解高維問題準確性差、效率低的缺陷。

3.3 算法時間復(fù)雜度分析

對某些問題雖然理論上存在求得全局最優(yōu)解的精確算法，但前提是犧牲算法的時間復(fù)雜度和空間復(fù)雜度，實際應(yīng)用中無法同時滿足，所以通常需要在求解精度和求解時間上取得平衡[17]。時間復(fù)雜度指算法循環(huán)迭代一次所需的時間復(fù)雜度之和，通常用數(shù)量級符號階次表示。ISCSO算法在空間復(fù)雜度上與其他算法相當，這里只討論算法的時間復(fù)雜度，取循環(huán)迭代一次的結(jié)果來比較算法的時間復(fù)雜度。CSO算法和ISCSO算法在初始化位置的時間復(fù)雜度都為O(N×D)，計算適應(yīng)度值的時間復(fù)雜度都為O(N×D)，更新最好位置的時間復(fù)雜度都為O(N×D)，位置更新和下一步計算適應(yīng)度值的時間復(fù)雜度都為O(N×D)。通過分析，CSO算法和ISCSO算法的時間復(fù)雜度是相同的。在相同的時間復(fù)雜度下，本文ISCSO算法性能要遠高于CSO算法，與其他算法相比也有競爭性。

4 結(jié)語

本文針對CSO算法收斂速度慢，高維、超高維尋優(yōu)困難等缺點，提出了一種基于信息交互的改進雞群優(yōu)化算法ISCSO。該算法主要針對CSO算法做了兩點改進：(1)在CSO算法中動態(tài)加入當代最優(yōu)解的位置，調(diào)整公雞和母雞的移動，加強了公雞和母雞之間的聯(lián)系，從而提升種群的搜索活力；(2)對于超出邊界的個體，對其約束上加入隨機因子，使其不在邊界周圍移動，以提升種群的多樣性。本文通過多個基本測試函數(shù)進行仿真實驗，實驗結(jié)果表明：ISCSO算法在處理高維優(yōu)化問題上，相對雞群優(yōu)化算法，具有更好的算法性能，尤其是收斂速度和尋優(yōu)精度；同時與其他改進的CSO算法相比，ISCSO算法擁有較好的收斂能力和高維問題尋優(yōu)能力，具有一定的競爭性和穩(wěn)定性。下一步的研究著重于將改進后的ISCSO算法應(yīng)用于解決實際的優(yōu)化問題。