競(jìng)爭(zhēng)合作行為下的深度演化算法*

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

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

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

1 引言

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

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

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

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

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

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

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

（3）在演化算法中引入變步長(zhǎng)機(jī)制，平衡了算法收斂速度和算法精度；

（4）將深度引入所提出的基于競(jìng)爭(zhēng)合作的演化算法中，在十個(gè)優(yōu)化函數(shù)和實(shí)際問題中驗(yàn)證了所提深度算法的有效性。

2 生物模型

2.1 生物群模型

自然界中的大多數(shù)動(dòng)物都是群居動(dòng)物，它們分群而居，有一定的社會(huì)行為，在自然進(jìn)化中，能適應(yīng)自然者才能生存下來。

2.1.1 群分類

在群競(jìng)爭(zhēng)合作優(yōu)化（group competition cooperation optimization，GCCO）算法中，一個(gè)種族有N個(gè)群體，每個(gè)群體中有n個(gè)個(gè)體，每個(gè)群體有領(lǐng)導(dǎo)者、跟隨者以及隨機(jī)者這三種角色，每個(gè)角色在搜索獵物時(shí)有不同的搜索策略。

定義1（領(lǐng)導(dǎo)者）領(lǐng)導(dǎo)者是群體中搜索能力最強(qiáng)的，一個(gè)群體中只有一個(gè)領(lǐng)導(dǎo)者。

定義2（跟隨者）跟隨者是群體中搜索能力僅次于領(lǐng)導(dǎo)者的一些個(gè)體。

定義3（隨機(jī)者）隨機(jī)者是群體中搜索能力最弱的一些個(gè)體。

2.1.2 群行為

在群體中，領(lǐng)導(dǎo)者代表這個(gè)群體最好的搜索方向，它通過自學(xué)習(xí)來尋找更優(yōu)的搜索方向；對(duì)于跟隨者，它們向領(lǐng)導(dǎo)者學(xué)習(xí)，在領(lǐng)導(dǎo)者周圍搜索獵物；隨機(jī)者是群體中搜捕能力最差的一些個(gè)體，它們不向他人學(xué)習(xí)，常采用基于特征變換的隨機(jī)游走策略去搜捕領(lǐng)導(dǎo)者和跟隨者未搜索過的方向，以期望能發(fā)現(xiàn)好的獵物場(chǎng)地。根據(jù)上面的描述定義以下三種類型的群行為：

（1）個(gè)體自學(xué)習(xí)；

（2）個(gè)體向他人學(xué)習(xí)；

（3）個(gè)體不向他人學(xué)習(xí)，與他人持反對(duì)意見。

同時(shí)在群體內(nèi)和群體間還存在競(jìng)爭(zhēng)與合作行為。

2.2 競(jìng)爭(zhēng)模型

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

2.3 合作模型

自然界中存在競(jìng)爭(zhēng)，也存在合作，通過信息共享，群體可發(fā)現(xiàn)更優(yōu)的搜索方向。在GCCO 算法中存在兩種合作方式：群內(nèi)合作和群間合作。

在群體內(nèi)部，領(lǐng)導(dǎo)者將自己的搜索信息分享給追隨者，追隨者采用區(qū)域復(fù)制的方式在領(lǐng)導(dǎo)者周圍搜索獵物。在群體間，搜索能力相似的群體通過共享自己最優(yōu)的搜索方向來實(shí)現(xiàn)互利互贏，以勘探出更好的方向搜索，如圖2所示。

Fig.1 Competition mode圖1 競(jìng)爭(zhēng)模式

Fig.2 Cooperation mode圖2 合作模式

2.4 三種模型之間的關(guān)系

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

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

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

3 數(shù)學(xué)模型和算法

3.1 生物群數(shù)學(xué)模型

3.1.1 初始化種群

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

3.1.2 種群分類

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

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

3.1.3 群行為

（1）領(lǐng)導(dǎo)者行為：領(lǐng)導(dǎo)者有自學(xué)習(xí)能力，它位于最有前途的區(qū)域且具有最佳適應(yīng)值。

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

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

（2）跟隨者行為：跟隨者向領(lǐng)導(dǎo)者學(xué)習(xí)，在領(lǐng)導(dǎo)者附近搜捕獵物。

定義6（跟隨者行為）跟隨者采用區(qū)域復(fù)制的方式在領(lǐng)導(dǎo)者附近搜索獵物，通過式（10）更新位置。

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

（3）隨機(jī)者行為：隨機(jī)者不學(xué)習(xí)，與他人持反對(duì)意見。

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

算法1群分類模型算法

3.2 競(jìng)爭(zhēng)數(shù)學(xué)模型

由競(jìng)爭(zhēng)模型可知，一個(gè)種族中存在兩種類型的競(jìng)爭(zhēng)，群內(nèi)競(jìng)爭(zhēng)和群間競(jìng)爭(zhēng)，且這兩種競(jìng)爭(zhēng)是同時(shí)進(jìn)行的，如算法2所示。

（1）群內(nèi)競(jìng)爭(zhēng)：每次演化過程中，每個(gè)群體內(nèi)的個(gè)體根據(jù)自己的策略去尋找更優(yōu)的搜捕方向，如果一個(gè)個(gè)體popi,j的適應(yīng)度值最差，則popi,j?Ci。同時(shí)，為了保持群體數(shù)量穩(wěn)定，隨機(jī)生成一個(gè)個(gè)體加入到群體中。

（2）群間競(jìng)爭(zhēng)：群體之間通過競(jìng)爭(zhēng)，淘汰一些弱勢(shì)群體，最終只有強(qiáng)者才能生存下來。

定義8（群間競(jìng)爭(zhēng)）對(duì)于每一群體，abilityi表示第i個(gè)群體的綜合實(shí)力，則對(duì)于第i個(gè)群體，它的綜合實(shí)力由式（14）定義，其中ξ=0.1，再用式（15）正規(guī)化第i個(gè)群體的綜合實(shí)力值。

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

根據(jù)D向量，將最弱的群體中的領(lǐng)導(dǎo)者給D中概率最大的群體，最弱的群體消失，在演化最后，只剩下一個(gè)群體。

算法2競(jìng)爭(zhēng)模型算法

3.3 合作數(shù)學(xué)模型

根據(jù)前面的合作模型可知，合作的形式有群內(nèi)合作和群間合作，如算法3所示。

（1）群內(nèi)合作：跟隨者的位置更新就是群內(nèi)合作，跟隨者通過領(lǐng)導(dǎo)者分享的角度、位置信息來進(jìn)行搜捕獵物，從而跳出自己搜索的局部最優(yōu)。

（2）群間合作：相似群體向?qū)Ψ綄W(xué)習(xí)，以發(fā)掘出更優(yōu)的搜索方向。

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

定義10（群間合作）相似群體中的跟隨者向?qū)Ψ降念I(lǐng)導(dǎo)者學(xué)習(xí)以了解對(duì)方的最優(yōu)搜索區(qū)域，相互合作，共同尋找更優(yōu)的搜索空間，則對(duì)于第i個(gè)群體中的跟隨者，它像第j個(gè)群體中的領(lǐng)導(dǎo)者學(xué)習(xí)，位置更新公式如式（16）和式（17）所示，反之亦然。

算法3合作模型算法

3.4 變步長(zhǎng)數(shù)學(xué)模型

跟隨者采用固定步長(zhǎng)的區(qū)域進(jìn)行搜索，若在較大步長(zhǎng)的復(fù)制區(qū)域內(nèi)移動(dòng)，則算法收斂速度較快，但在接近全局最優(yōu)解時(shí)，會(huì)因步長(zhǎng)過大而在峰值附近振蕩，出現(xiàn)精度低的問題；若采用較小的步長(zhǎng)，算法優(yōu)化精度會(huì)提高，但是收斂速度太慢且易陷入局部最優(yōu)[19]。

通過分析步長(zhǎng)對(duì)算法性能的影響，在算法前期，采用較大的步長(zhǎng)來加快算法收斂；在算法后期，采用較小的步長(zhǎng)來盡可能逼近極值。結(jié)合迭代次數(shù)，為步長(zhǎng)引入一個(gè)權(quán)值，如式（18）所示，其中t為當(dāng)前迭代次數(shù)，T為總迭代次數(shù)，則跟隨者的移動(dòng)策略如式（19）所示。

3.5 GCCO算法

算法4GCCO算法

4 GCCO算法的理論證明

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

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

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

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

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

證明由假設(shè)2 可知，算法能夠獲得比當(dāng)前更好的解的概率是，那么有。由假設(shè)1 可知，優(yōu)化算法的適應(yīng)度值是非遞增的，由優(yōu)化算法所產(chǎn)生的值總是不差于目前的個(gè)體。結(jié)合假設(shè)1和假設(shè)2可知，算法總是能找到更好的解直到它收斂，因而可以證明算法是收斂的。 □

理論2算法E滿足假設(shè)1。

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

引理如果解空間S是有界的，并且適應(yīng)度函數(shù)在S上是連續(xù)的，那么算法E滿足假設(shè)2。

證明通常解空間可以分為兩部分：一是最優(yōu)點(diǎn)X*的鄰域部分，用S1表示；另一部分用S2表示，且S2=S-S1。則當(dāng)前解可以劃分為兩種情況：一是至少有一個(gè)解在S1內(nèi)；二是所有的解都在S2內(nèi)。

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

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

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

理論3算法E有一個(gè)有界的解空間S，當(dāng)適應(yīng)度函數(shù)在S上是連續(xù)的，則它是全局收斂的。

證明由假設(shè)1 可知算法E是滿足假設(shè)2 的，則根據(jù)理論2，算法E是收斂的。但前提是適應(yīng)度函數(shù)在有界的解空間內(nèi)連續(xù)。 □

5 實(shí)驗(yàn)和分析

這部分主要是對(duì)所提深度演化算法（GCCO）性能的分析，首先在十個(gè)優(yōu)化函數(shù)上與帝國(guó)競(jìng)爭(zhēng)算法（imperialist competitive algorithm，ICA）、社會(huì)蜘蛛算法（SSO）以及群搜索算法（group search optimizer，GSO）這三種算法比較，其次在提高上海市燃?xì)馐鹿实綀?chǎng)及時(shí)率問題中測(cè)試GCCO算法解決實(shí)際問題的能力。

5.1 優(yōu)化函數(shù)測(cè)試

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

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

Table 1 Parameter settings for four algorithms表1 四個(gè)算法的參數(shù)設(shè)置

Table 2 Comparative experimental results on 30-dimensional optimization function表2 30維的優(yōu)化函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果

Fig.4 Experimental results of GCCO algorithm and three other algorithms in 30 dimensions圖4 GCCO算法和其他三種算法在30維上的實(shí)驗(yàn)結(jié)果圖

為了測(cè)試GCCO 算法解決高維問題的性能，分別在50維和100維的優(yōu)化函數(shù)上對(duì)算法進(jìn)行了測(cè)試，表3和表4是實(shí)驗(yàn)結(jié)果，表中加粗的字體表示函數(shù)值較低。從表3 可以看出，在50 維優(yōu)化問題中，GCCO算法只有在Griewank 函數(shù)中的性能僅次于SSO 算法，在其他函數(shù)均有最佳性能。在表4 中，GCCO 算法在100 維的Griewank 函數(shù)和Ackley 函數(shù)中的性能僅次于SSO算法，且在Penalized函數(shù)中的mean指標(biāo)性能較差，在其他函數(shù)上也均有最佳性能。故可以看出在解決高維問題上，GCCO算法也有較好的性能。

Table 3 Comparative experimental results on 50-dimensional optimization function表3 在50維的優(yōu)化函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果

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

Table 4 Comparative experimental results on 100-dimensional optimization function表4 在100維的優(yōu)化函數(shù)上的對(duì)比實(shí)驗(yàn)結(jié)果

Table 5 Wilcoxon test results on ten 30-dimensional optimization functions表5 在十個(gè)30維優(yōu)化函數(shù)上的Wilcoxon測(cè)試結(jié)果

5.2 實(shí)際應(yīng)用

在解決上海市燃?xì)馐鹿实綀?chǎng)及時(shí)率問題中，需對(duì)12 619 條燃?xì)鈹?shù)據(jù)進(jìn)行數(shù)據(jù)預(yù)處理，先對(duì)上海市燃?xì)馐鹿仕趨^(qū)域劃分柵格，再對(duì)事故時(shí)間段劃分時(shí)間片，將數(shù)據(jù)處理成一個(gè)行為柵格編號(hào)列為時(shí)間片編號(hào)的二維矩陣。

5.2.1 數(shù)據(jù)預(yù)處理

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

Fig.5 Friedman test on ten 30-dimensional optimization functions圖5 在十個(gè)30維基準(zhǔn)函數(shù)上的Friedman測(cè)試

定義12（時(shí)間片）將燃?xì)馐鹿蕯?shù)據(jù)始末時(shí)間段劃分為時(shí)間間隙為g小時(shí)的h等份，其中每一份即為一個(gè)時(shí)間片。

基于定義11 和定義12，則任意柵格在任意時(shí)間片內(nèi)都有相應(yīng)的狀態(tài)屬性state，這樣完成了對(duì)數(shù)據(jù)的預(yù)處理，將數(shù)據(jù)表示成了b×h的一個(gè)二維矩陣Matrix。

在實(shí)際上海市燃?xì)馐鹿实綀?chǎng)及時(shí)率問題中，state的值如下所示，負(fù)數(shù)值越小表示相應(yīng)的事故優(yōu)先級(jí)越低，事故時(shí)間段為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 目標(biāo)函數(shù)定義

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

5.2.3 實(shí)驗(yàn)結(jié)果

在這部分，加入全局搜索（global search）的實(shí)驗(yàn)結(jié)果，即對(duì)所有柵格（1 000×2 000個(gè)柵格）進(jìn)行遍歷，算出所有柵格分別設(shè)立站點(diǎn)后的未及時(shí)率，求出未及時(shí)率最多能降低到35.681%，這是最優(yōu)的一個(gè)結(jié)果。

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

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

Fig.6 Experimental comparison of four algorithms圖6 四種算法實(shí)驗(yàn)對(duì)比

6 總結(jié)與展望

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