競爭合作行為下的深度演化算法*

陳海娟，馮 翔，2+，虞慧群

1.華東理工大學 信息科學與工程學院，上海200237

2.上海智慧能源工程技術研究中心，上海200237

1 引言

2017 年周志華等人提出的深度森林[1]引起了很大反響，它是一種基于決策樹森林而非神經網絡的深度學習模型，且它的性能可與深度神經網絡相媲美。在深度學習中，它有多個隱層，具有表征學習能力，且有大量的數據去訓練使得它的模型足夠復雜[2-3]。文獻[1]中指出，若能將這些屬性賦予其他一些合適的學習模型，或許也能取得和深度神經網絡類似的效果，但這并不是為了取代深度神經網絡現有的地位，而是為了解決現有復雜的實際問題，就要深化學習模型，積極探索多樣的深度模型。

近年來演化算法也取得了較大進展。如2008年，Simon 通過模擬自然界中的遷徙行為提出了遷徙算法（biogeography-based optimization，BBO）[4]；2013年，Cuevas提出社會蜘蛛算法（social spider optimization，SSO）來再現蜘蛛的社會行為[5]；2018 年，Alizadeh 等人通過人體免疫現象提出了人造免疫系統[6]等。雖然演化算法能解決一些優化問題，但本身卻存在易陷入局部最優、過早收斂以及難以適用于復雜的實際場景等問題。受深度森林的啟發，如果演化算法是一個合適的模型，將深度的概念引入到演化算法中，或許能提升演化算法的性能。基于此，本文將深度引入下面所提出的一種新的演化算法中，來探究深度與演化算法相結合的效果。

自然界中，大多數動物都分群而居[7]，物種之間及生物內部之間都存在生存競爭，能適應自然的才能留下來[8-9]。人類社會也是如此，帝國之間相互競爭，掠奪殖民地，在歷史演變過程中，一些國家被歷史淘汰，一些國家存活了下來，Atashpaz-Gargari等人通過對此研究提出了帝國競爭算法[10]。合作行為也是一種常見的自然行為，動物群體的集體智慧行為加強了個體之間的分工與合作，實現雙方互利共贏[11-12]。Szathmáry 就曾說過“合作可以推動合作行為人口結構的演變”。受此啟發，基于生物群模型、競爭模型以及合作模型，提出一種新的群體智能演化算法。

本文在新的群體智能演化算法中引入深度，相應的體現為多步迭代、特征變換以及模型足夠復雜。首先，算法是深度迭代的，通常算法只經過一層迭代，本文算法有兩層迭代，每層迭代多次來尋找最優解；其次，為了避免算法陷入局部最優，對生物群模型中的隨機者引入特征變換策略[13-14]，搜索其他成員未搜索的方向，可有效發掘潛在最優值，避免算法陷入局部最優；再者，算法引入了生物群模型、合作模型、競爭模型以及變步長模型，使得算法有一定的復雜性。對于變步長模型，通過每次演化過程中個體移動步長的動態調整，可實現算法收斂速度和算法精度的均衡[15]。

基于上面的描述，本文主要有以下幾方面的貢獻：

（1）啟發于周志華等人提出的深度森林[1]，提出將深度引入演化算法中；

（2）通過自然界中的分群和競爭合作現象，提出了生物群模型、競爭模型和合作模型，繼而提出一種基于競爭合作的新的演化算法；

（3）在演化算法中引入變步長機制，平衡了算法收斂速度和算法精度；

（4）將深度引入所提出的基于競爭合作的演化算法中，在十個優化函數和實際問題中驗證了所提深度算法的有效性。

2 生物模型

2.1 生物群模型

自然界中的大多數動物都是群居動物，它們分群而居，有一定的社會行為，在自然進化中，能適應自然者才能生存下來。

2.1.1 群分類

在群競爭合作優化（group competition cooperation optimization，GCCO）算法中，一個種族有N個群體，每個群體中有n個個體，每個群體有領導者、跟隨者以及隨機者這三種角色，每個角色在搜索獵物時有不同的搜索策略。

定義1（領導者）領導者是群體中搜索能力最強的，一個群體中只有一個領導者。

定義2（跟隨者）跟隨者是群體中搜索能力僅次于領導者的一些個體。

定義3（隨機者）隨機者是群體中搜索能力最弱的一些個體。

2.1.2 群行為

在群體中，領導者代表這個群體最好的搜索方向，它通過自學習來尋找更優的搜索方向；對于跟隨者，它們向領導者學習，在領導者周圍搜索獵物；隨機者是群體中搜捕能力最差的一些個體，它們不向他人學習，常采用基于特征變換的隨機游走策略去搜捕領導者和跟隨者未搜索過的方向，以期望能發現好的獵物場地。根據上面的描述定義以下三種類型的群行為：

（1）個體自學習；

（2）個體向他人學習；

（3）個體不向他人學習，與他人持反對意見。

同時在群體內和群體間還存在競爭與合作行為。

2.2 競爭模型

在自然界中，群體之間必然存在生存競爭，群體中的個體也是如此。在GCCO 算法中，存在兩種競爭，群內競爭和群間競爭。在群體內，能力最差的個體將被淘汰；而在群體間，通常選擇一個搜索能力最弱的群體，在其他所有群體之間競爭以擁有這個最弱群體的生產者，而這個最弱群體中的其他個體則被淘汰。通常這兩種競爭是同步進行的，如圖1所示。

2.3 合作模型

自然界中存在競爭，也存在合作，通過信息共享，群體可發現更優的搜索方向。在GCCO 算法中存在兩種合作方式：群內合作和群間合作。

在群體內部，領導者將自己的搜索信息分享給追隨者，追隨者采用區域復制的方式在領導者周圍搜索獵物。在群體間，搜索能力相似的群體通過共享自己最優的搜索方向來實現互利互贏，以勘探出更好的方向搜索，如圖2所示。

Fig.1 Competition mode圖1 競爭模式

Fig.2 Cooperation mode圖2 合作模式

2.4 三種模型之間的關系

在GCCO 算法中，初始一個種族分散在N個群體中，每個群體中的n個個體被劃分為三個等級：領導者、跟隨者以及隨機者。在各個群體搜捕獵物的過程中，領導者帶領追隨者發掘更佳位置，隨機者通過特征變換的方式發掘未知位置，且群體內最差個體被淘汰。在群體之間，搜捕能力較強的群體爭奪搜捕能力最弱的群體中的領導者，最弱群體中的其余個體被淘汰。同時，能力值相近的群體之間相互合作，共同勘探更優的搜索位置。當這個種族演化到一個群體時，算法結束，這個群體中的領導者就代表了全局最優解。

圖3 是GCCO 算法的框架圖，由圖3 可知深度在GCCO 算法中體現在三方面：第一，算法是深度迭代的，算法通過N-1 次演化，演化成一個群體，每次演化中每個群體內部并行迭代τ次，即算法是通過(N-1)×τ次迭代完成的；第二，隨機者采用基于特征變換的方式去搜索未知領域，算法是特征變換的；第三，GCCO 算法中引入了多種模型，算法是具有一定的復雜性的。

Fig.3 Framework diagram of GCCO algorithm圖3 GCCO算法的框架圖

3 數學模型和算法

3.1 生物群數學模型

3.1.1 初始化種群

初始化的目的是形成算法初始的一個種族，一個種族有N個群體，每個群體中有三種類型的個體，每一個體存在兩種屬性，角度θ和方向D。在n維搜索空間中，第k次迭代中的第i個個體的當前位置為為個體的當前頭部角度，它的搜索方向是一單位矢量，由式（1）～式（3）計算得出[16-18]。

3.1.2 種群分類

根據適應度值將群體中的個體劃分為三類，即領導者、跟隨者以及隨機者。fit(popi,j)表示第i個群體中第j個個體的搜索能力，第i個群體的種群分類如算法1所示。

定義4（種群分類）對于任意個體gi,j，gi,j∈Ci，Ci={L,F,W}，其中Ci是第i個種群的分類，L、F以及W分別代表領導者、跟隨者以及隨機者。由生物群模型可知，在第i個種群中，領導者、跟隨者以及隨機者由式（4）～式（6）分別描述，δ表示搜索能力差值，在實際實驗中取適應度值排名前80%的個體為跟隨者。

3.1.3 群行為

（1）領導者行為：領導者有自學習能力，它位于最有前途的區域且具有最佳適應值。

定義5（領導者行為）領導者采用掃描定位機制尋找獵物，通過由white crappie 引入的基本掃描策略，將掃描場推廣到一個n維空間，其中θmax為最大追蹤角，λmax為最大追蹤距離。領導者分別向左、向右、向前掃描，在第k次迭代中領導者XL的掃描行為如式（7）～式（9）所示，領導者將從前方(z)、左方（l）以及右方(r)這三點去尋找最佳位置：

其中，c1～N(0,1)，c2是一個服從0-1均勻分布的n-1維序列。

（2）跟隨者行為：跟隨者向領導者學習，在領導者附近搜捕獵物。

定義6（跟隨者行為）跟隨者采用區域復制的方式在領導者附近搜索獵物，通過式（10）更新位置。

其中，c3是服從0-1均勻分布的n維序列。

（3）隨機者行為：隨機者不學習，與他人持反對意見。

定義7（隨機者行為）隨機者采用基于特征變換的隨機移動策略，搜索領導者和跟隨者未搜索過的區域，即隨機者雖自由移動，但采用的移動方向與領導者和跟隨者不同，通過式（11）～式（13）更新位置。

算法1群分類模型算法

3.2 競爭數學模型

由競爭模型可知，一個種族中存在兩種類型的競爭，群內競爭和群間競爭，且這兩種競爭是同時進行的，如算法2所示。

（1）群內競爭：每次演化過程中，每個群體內的個體根據自己的策略去尋找更優的搜捕方向，如果一個個體popi,j的適應度值最差，則popi,j?Ci。同時，為了保持群體數量穩定，隨機生成一個個體加入到群體中。

（2）群間競爭：群體之間通過競爭，淘汰一些弱勢群體，最終只有強者才能生存下來。

定義8（群間競爭）對于每一群體，abilityi表示第i個群體的綜合實力，則對于第i個群體，它的綜合實力由式（14）定義，其中ξ=0.1，再用式（15）正規化第i個群體的綜合實力值。

則群體i的占有率，對于N個群體則有向量P=[P1,P2,…,PN]。對應創建一個與P同樣大小的向量Q，則Q=[Q1,Q2,…,QN]，其中Q1,Q2,…,QN～U(0,1)，則有：

根據D向量，將最弱的群體中的領導者給D中概率最大的群體，最弱的群體消失，在演化最后，只剩下一個群體。

算法2競爭模型算法

3.3 合作數學模型

根據前面的合作模型可知，合作的形式有群內合作和群間合作，如算法3所示。

（1）群內合作：跟隨者的位置更新就是群內合作，跟隨者通過領導者分享的角度、位置信息來進行搜捕獵物，從而跳出自己搜索的局部最優。

（2）群間合作：相似群體向對方學習，以發掘出更優的搜索方向。

定義9（相似群體）在N個群體中，如果有群體Si和Sj滿足|abilityi-abilityj|=min|abilityi-abilityj|，其中i,j=1,2,…,N，則Si～Sj。

定義10（群間合作）相似群體中的跟隨者向對方的領導者學習以了解對方的最優搜索區域，相互合作，共同尋找更優的搜索空間，則對于第i個群體中的跟隨者，它像第j個群體中的領導者學習，位置更新公式如式（16）和式（17）所示，反之亦然。

算法3合作模型算法

3.4 變步長數學模型

跟隨者采用固定步長的區域進行搜索，若在較大步長的復制區域內移動，則算法收斂速度較快，但在接近全局最優解時，會因步長過大而在峰值附近振蕩，出現精度低的問題；若采用較小的步長，算法優化精度會提高，但是收斂速度太慢且易陷入局部最優[19]。

通過分析步長對算法性能的影響，在算法前期，采用較大的步長來加快算法收斂；在算法后期，采用較小的步長來盡可能逼近極值。結合迭代次數，為步長引入一個權值，如式（18）所示，其中t為當前迭代次數，T為總迭代次數，則跟隨者的移動策略如式（19）所示。

3.5 GCCO算法

算法4GCCO算法

4 GCCO算法的理論證明

在GCCO算法中，一個種族被劃分為N個群體，由于存在群體間的競爭，種族每經歷一次演化，都有一個群體被淘汰，直到最后只有一個群體存活了下來。由于每個群體有相同的演化策略，將其定義為E，若E是收斂的，則整個算法就是收斂的。

對于任意一個優化問題＜A,g＞和隨機優化算法E，算法在第t次迭代的結果是Xt，則算法下一次迭代的結果Xt+1=E(Xt,?)，其中?表示由算法E找到的解。

假設1如果g(E(x,?))≤g(x)，則有g(E(x,?))≤g(?)。

假設2假定在第t次迭代后的解Xt不是最優的解，那么算法在第(t+1)次得到一個更優的解的概率是Pt+1∈(0,1)。

理論1如果一個算法滿足假設1 和假設2，那么這個算法是收斂的。

證明由假設2 可知，算法能夠獲得比當前更好的解的概率是，那么有。由假設1 可知，優化算法的適應度值是非遞增的，由優化算法所產生的值總是不差于目前的個體。結合假設1和假設2可知，算法總是能找到更好的解直到它收斂，因而可以證明算法是收斂的。 □

理論2算法E滿足假設1。

證明無論是否存在競爭和合作行為，算法E中的領導者都是最優的個體，這是由領導者的定義而來的。領導者通過自學習，將掃描的三個點與當前的位置比較來選擇最佳的搜捕方向，因此有g(Xl,t)≤g(Xl,t-1)，即g(E(X,?))≤g(X)。且在這次迭代之后，選出最優的粒子作為領導者，即。領導者的值是在這次迭代中值最小的粒子，因此也滿足g(E(X,?))≤g(?)，故算法E滿足假設1。 □

引理如果解空間S是有界的，并且適應度函數在S上是連續的，那么算法E滿足假設2。

證明通常解空間可以分為兩部分：一是最優點X*的鄰域部分，用S1表示；另一部分用S2表示，且S2=S-S1。則當前解可以劃分為兩種情況：一是至少有一個解在S1內；二是所有的解都在S2內。

如果當前第t次迭代的解屬于第一種情況，則由理論2 可知，在接下來迭代過程中，至少有一個解在S1中。這種情況同時滿足假設1和假設2，則由理論1可知，算法E最終收斂到最優解。

如果當前第t次迭代的解屬于第二種情況，由于g(xt)在S上是連續的，將Xm滿足||Xm-Xl||∞≤?和|g(Xm)-g(Xl)|＜ε(ε＞0)的集合記為M，則M?S1。且有：

從中可知，當0＜c＜2 時，0＜P{(Xm+ΔXm)∈M}＜1，這意味著這個點屬于M的概率是（0，1）。則在假設1的情況下可證明算法E滿足假設2。 □

理論3算法E有一個有界的解空間S，當適應度函數在S上是連續的，則它是全局收斂的。

證明由假設1 可知算法E是滿足假設2 的，則根據理論2，算法E是收斂的。但前提是適應度函數在有界的解空間內連續。 □

5 實驗和分析

這部分主要是對所提深度演化算法（GCCO）性能的分析，首先在十個優化函數上與帝國競爭算法（imperialist competitive algorithm，ICA）、社會蜘蛛算法（SSO）以及群搜索算法（group search optimizer，GSO）這三種算法比較，其次在提高上海市燃氣事故到場及時率問題中測試GCCO算法解決實際問題的能力。

5.1 優化函數測試

這里采用的十個優化函數是文獻[5]中的部分函數，函數描述與文獻[5]中一致，實驗通過與GSO、ICA 以及SSO 這三種算法對比來驗證GCCO 算法的性能。在實驗中，算法的最大迭代次數均為1 000(τ=1 000)，初始種群大小為50(n=50)。每個算法的參數設置如表1所示。

表2 是GCCO 算法和其他三種算法在30 維的優化函數上的對比結果，表中加粗的字體表示函數值較低，實驗運行50次，在平均值和標準差這兩個指標上驗證算法性能。實驗結果表明GCCO算法只有在Rastrigin函數和Rosenbrock函數上的std指標性能不太理想，在其他函數上均有最優性能。且從圖4中可直觀看出，GCCO 算法在所有函數中均能尋得最優值，尤其在Salomon 函數和Sum-of-square 函數中，GCCO算法在前幾百次的迭代中就能尋得最優值0。

Table 1 Parameter settings for four algorithms表1 四個算法的參數設置

Table 2 Comparative experimental results on 30-dimensional optimization function表2 30維的優化函數上的對比實驗結果

Fig.4 Experimental results of GCCO algorithm and three other algorithms in 30 dimensions圖4 GCCO算法和其他三種算法在30維上的實驗結果圖

為了測試GCCO 算法解決高維問題的性能，分別在50維和100維的優化函數上對算法進行了測試，表3和表4是實驗結果，表中加粗的字體表示函數值較低。從表3 可以看出，在50 維優化問題中，GCCO算法只有在Griewank 函數中的性能僅次于SSO 算法，在其他函數均有最佳性能。在表4 中，GCCO 算法在100 維的Griewank 函數和Ackley 函數中的性能僅次于SSO算法，且在Penalized函數中的mean指標性能較差，在其他函數上也均有最佳性能。故可以看出在解決高維問題上，GCCO算法也有較好的性能。

Table 3 Comparative experimental results on 50-dimensional optimization function表3 在50維的優化函數上的對比實驗結果

為了更進一步分析算法的有效性，使用Wilcoxon測試和Friedman測試這兩個非參數統計技術來分析GCCO算法在30維連續優化問題上所獲得結果的性能[20-21]。Wilcoxon 測試的結果如表5 所示，Friedman測試的結果如圖5 所示。從表5 可以看出，除了SSO算法，其他算法的P值均小于0.05[21]，且6.457E-02也是很小的一個值，故GCCO 算法性能是優于其他三種算法的。圖5是秩和檢驗分析，顯示了各個算法的排名，值越小說明該算法越優，從中可以看出，在十個函數中GCCO算法均有最小排名。

Table 4 Comparative experimental results on 100-dimensional optimization function表4 在100維的優化函數上的對比實驗結果

Table 5 Wilcoxon test results on ten 30-dimensional optimization functions表5 在十個30維優化函數上的Wilcoxon測試結果

5.2 實際應用

在解決上海市燃氣事故到場及時率問題中，需對12 619 條燃氣數據進行數據預處理，先對上海市燃氣事故所在區域劃分柵格，再對事故時間段劃分時間片，將數據處理成一個行為柵格編號列為時間片編號的二維矩陣。

5.2.1 數據預處理

定義11（柵格）將空間分割成大小一致的網格，一個網格即為一個柵格，這里根據事故的墨卡托坐標將上海市劃分成a×a的柵格（單位m），得到每個柵格的編號(x,y)，共計b個柵格。其中x∈[c,d]，y∈[e,f]。

Fig.5 Friedman test on ten 30-dimensional optimization functions圖5 在十個30維基準函數上的Friedman測試

定義12（時間片）將燃氣事故數據始末時間段劃分為時間間隙為g小時的h等份，其中每一份即為一個時間片。

基于定義11 和定義12，則任意柵格在任意時間片內都有相應的狀態屬性state，這樣完成了對數據的預處理，將數據表示成了b×h的一個二維矩陣Matrix。

在實際上海市燃氣事故到場及時率問題中，state的值如下所示，負數值越小表示相應的事故優先級越低，事故時間段為2016 年9 月4 日—2018 年11 月26 日，且a=256，b=7 140，c=52 000，d=54 000，e=14 000，f=15 000，g=4，h=4 878。

5.2.2 目標函數定義

在GCCO算法中，每個群體初始化50個粒子，每個粒子有兩個維度，分別代表柵格的x坐標和y坐標，則每當粒子Z移動到一個位置時，粒子Z的適應度值就等于在這個位置設立一個站點后的上海市未及時率。設立一個站點后的未及時率的計算為：粒子Z按列遍歷矩陣Matrix（即按時間片遍歷每個時間片內的柵格），按優先級查看未及時到達事故，計算站點（粒子）到對應柵格的時間T（T=），若一個優先級有多起事故且能在30 min內到達的處理距離最近的事故，否則轉看下一個優先級的事故，且每個時間片只能處理一個未及時到達事故，將其負的狀態值改為1。將這個過程定義為ACT，令ACT(z)為設立站點z后未及時到達的事故數。用SUM表示總事故數，則未及時率unarriverate=，通過粒子演化，找出未及時率最低的粒子，即最優站點的位置。

5.2.3 實驗結果

在這部分，加入全局搜索（global search）的實驗結果，即對所有柵格（1 000×2 000個柵格）進行遍歷，算出所有柵格分別設立站點后的未及時率，求出未及時率最多能降低到35.681%，這是最優的一個結果。

在算法參數設置中，和上面優化函數設置相同，將GCCO 算法與ICA、SSO、GSO 算法以及global search 進行對比，算法運行50 次。由表6 可知，在解決大數據量的實際問題中，GCCO 算法是明顯優于ICA 算法的，GCCO 算法將未及時率從初始48.819%降低到了35.841%，雖然GCCO 算法比SSO 算法（降到了36.360%）和GSO算法（降到了36.408%）只分別多優化了0.52個百分點和0.57個百分點左右，但在實際設立站點問題中，未及時率最多能降低到35.681%，一個站點的設立只能顧及方圓15 km的區域，多優化0.52 個百分點和0.57 個百分點能體現出GCCO 算法的性能是比GSO算法和SSO算法優越的。且GCCO算法與全局搜索相比只差了0.16 個百分點，但所花費的時間確是遠遠少于全局搜索的時間的，花費少量的時間卻能獲得較好的效果這是所需要的。從圖6可直觀地看出，GCCO 算法收斂速度較快，且能尋得最優值，這些都證明了將深度引入演化算法來解決實際問題的有效性。

Table 6 Performance comparison of five algorithms on reducing untimely rate problem表6 五種算法在降低未及時率問題上的性能對比

Fig.6 Experimental comparison of four algorithms圖6 四種算法實驗對比

6 總結與展望

本文將深度引入演化算法中，提出一種基于群競爭合作行為的深度演化算法（GCCO算法），算法通過多步迭代可以實現極值問題的求解。在算法中引入競爭模型和合作模型提高算法的性能，在跟隨者移動過程中，采用變步長策略，均衡了算法精度和收斂速度問題。在隨機者移動過程中，采用基于特征變換的游走方式，避免算法陷入局部最優。將所提深度算法在十個基準函數上進行了測試，并分別在30維、50維以及100維上檢測算法的性能，實驗結果表明，相對于ICA、SSO以及GSO算法，GCCO算法表現出良好的性能，并使用非參數統計技術Wilcoxon測試和Friedman測試來分析GCCO算法在30維連續優化問題中的性能。最后為了驗證算法在解決實際問題上的有效性，將算法用于12 619 條上海市燃氣事故數據中，找出合適的位置來設立站點降低上海市事故未及時率。實驗結果也驗證了GCCO算法解決大數據量的實際問題的能力，但是本文所提出的深度演化算法還只在初級階段，今后還需對深度與演化算法進行更深入復雜的研究。