水平結(jié)構(gòu)競爭-互利群落優(yōu)化算法*

黃光球，陸秋琴

西安建筑科技大學 管理學院，西安 710055

1 引言

工程中經(jīng)常遇到十分復雜的優(yōu)化問題，此類優(yōu)化問題既存在大量局部最優(yōu)解，其所包含的函數(shù)表達式又常常不可導，有時甚至連具體的函數(shù)表達式都無法知道。為了求解這些優(yōu)化問題的全局最優(yōu)解，目前所采用的方法是啟發(fā)式方法，群體智能優(yōu)化算法就是其中的一種，這類優(yōu)化算法對優(yōu)化問題的函數(shù)表達式?jīng)]有特殊限制，因而具有較廣泛的適用性[1]。常用的群智能優(yōu)化算法有：遺傳算法[2-3]、蟻群算法[4-5]、粒子群算法[6-7]、人工魚群算法[8]、生物地理學算法[9]、人工免疫算法[10]、蜂群算法[11]等。這類算法是依據(jù)一些簡單的自然現(xiàn)象而構(gòu)造出來的，而且這些自然現(xiàn)象難以采用合適的數(shù)學模型加以描述。

為了克服傳統(tǒng)群智能優(yōu)化算法存在的缺陷，本文選擇一種特殊的自然現(xiàn)象，即水平結(jié)構(gòu)下的生物群落競爭-互利進化現(xiàn)象[12-13]，構(gòu)造出了一種新的群智能優(yōu)化算法，即水平結(jié)構(gòu)競爭-互利群落優(yōu)化算法（horizontal structure competition-mutually beneficial community optimization，HS-CBCO）。由于水平結(jié)構(gòu)競爭-互利群落進化系統(tǒng)可采用種群動力學數(shù)學模型進行恰當描述，從而使HS-CBCO 算法奠定在堅實的數(shù)學理論基礎之上。

在自然界，任何種群都有確定的生態(tài)區(qū)域，它們在該區(qū)域中生存和繁衍。事實上，每一種群都占有自己的生態(tài)位[12]，生態(tài)位的鑲嵌是現(xiàn)實生物群落中的典型現(xiàn)象[13]。種群不但在同一生境中共存，而且是在消費相同的資源條件下共存。資源的局限性，使利用同一種群的資源相互制約。這樣，生態(tài)位的鑲嵌自然導致競爭關(guān)系，生態(tài)位決定著種群在競爭的群落結(jié)構(gòu)中的地位和作用，而不存在生態(tài)位的鑲嵌的種群又會形成互利關(guān)系。水平結(jié)構(gòu)競爭-互利群落進化指的是水平結(jié)構(gòu)下生態(tài)位存在鑲嵌的群落系統(tǒng)中的生物種群相互競爭、互利，共同進化的現(xiàn)象。目前，有關(guān)水平結(jié)構(gòu)競爭-互利群落進化系統(tǒng)理論研究已取得如下進展：

（1）群落水平結(jié)構(gòu)特征分析[14-15]。研究群落的水平結(jié)構(gòu)特征，以便對群落規(guī)模、營養(yǎng)供給水平和種群競爭和互利特征進行有效控制。

（2）營養(yǎng)水平對群落規(guī)模和群落結(jié)構(gòu)的影響[16-17]。研究群落的營養(yǎng)供給水平對群落規(guī)模和群落結(jié)構(gòu)的影響，發(fā)現(xiàn)其中的種群競爭和互利規(guī)律，為合理確定營養(yǎng)供給水平提供科學依據(jù)。

（3）群落結(jié)構(gòu)特征對種群變化特征的影響[18]。揭示在種群競爭和互利環(huán)境下的群落結(jié)構(gòu)特征對種群變化特征的制約規(guī)律，為有效控制種群變化特征提供科學依據(jù)。

上述有關(guān)水平結(jié)構(gòu)競爭-互利群落進化理論的研究為本文算法的進一步研究提供良好的支撐。本文著重解決如下問題：

（1）如何將水平結(jié)構(gòu)競爭-互利群落動力學模型轉(zhuǎn)化為能求解復雜優(yōu)化問題的群智能優(yōu)化算法。

（2）如何使得HS-CBCO 算法中的算子能充分反映不同種群內(nèi)個體之間的相互作用關(guān)系，以便體現(xiàn)水平結(jié)構(gòu)競爭-互利群落動力學理論的基本思想。

（3）如何證明HS-CBCO 算法的全局收斂性。

（4）如何確定HS-CBCO 算法的最佳參數(shù)設置。

（5）如何進行HS-CBCO 算法的求精和探索能力及其協(xié)調(diào)性分析。

2 HS-CBCO 算法設計

考慮優(yōu)化問題：

式中，Rn是n維歐氏空間；X=(x1,x2,…,xn)是一個n維決策向量；S為搜索空間；f(X) 為目標函數(shù)；gi(X)≥0 為第i個約束條件，i=1,2,…,I，I為不等式約束條件個數(shù)。目標函數(shù)f(X)和約束條件gi(X)不需要特殊的限制條件。

2.1 算法場景設計

在生態(tài)系統(tǒng)中，水平結(jié)構(gòu)是指多個不同類別的生物種群所消費的資源為同一類型。在同一水平結(jié)構(gòu)內(nèi)的種群間相互作用主要是競爭和互利。假設一個生態(tài)系統(tǒng)中有K個種群在其中活動，其編號分別為1,2,…,K，記為P={1,2,…,K}。

時期t，種群k內(nèi)有Nk(t)個生物個體（簡稱個體），這些個體的編號的集合記為，因此該生態(tài)系統(tǒng)中的個體總數(shù)為N(t)=M(K,t)，。若按種群編號順序?qū)λ蟹N群中的個體進行統(tǒng)一編號，則種群k內(nèi)的Nk(t)個個體的編號為Pk={1+M(k-1,t),2+M(k-1,t),…,Nk(t)+M(k-1,t)}。已知個體的編號為m，當m滿足M(u-1,t)＜m≤M(u,t)時，該個體所在的種群編號NL(m)=u。

在一個生態(tài)系統(tǒng)中，每一種群都占有自己的生態(tài)位，生態(tài)位是指種群對多種資源的利用范圍。當種群的生態(tài)位出現(xiàn)鑲嵌（又稱重疊）時，種群之間會產(chǎn)生競爭關(guān)系。生態(tài)系統(tǒng)中已發(fā)現(xiàn)有5 種競爭格局，即正態(tài)分布型（C1）、離散分布型（C2）、最鄰近型（C3）、均勻型（C4）、單調(diào)遞減型（C5），記為C={C1,C2,C3,C4,C5}。

在該生態(tài)系統(tǒng)中，不存在生態(tài)位鑲嵌的種群之間可能存在互利關(guān)系，但該互利關(guān)系不是一成不變，而是隨時間變化的。若一個種群與另外一個種群存在競爭關(guān)系，則它們之間就不存在互利關(guān)系，反之亦然。

在一個種群的內(nèi)部，各生物個體之間存在相互影響關(guān)系，這種相互影響關(guān)系分為兩種類型，即普通影響關(guān)系和強烈影響關(guān)系。所謂普通影響關(guān)系是指某個體受到其他普通個體的影響，而強烈影響關(guān)系是指某個體受到其他強壯個體的深刻影響。

種群中的生物個體在進化期間，其特征既會受到種群之間的競爭和互利影響，又會受到同一種群內(nèi)其他生物個體的影響，且這種影響是隨時間變化的。

下面將上述現(xiàn)象與優(yōu)化問題（1）的全局最優(yōu)解的求解過程對應起來，即有：生態(tài)系統(tǒng)與優(yōu)化問題（1）的搜索空間S相對應，時期t，該生態(tài)系統(tǒng)中的一個生物個體對應于一個優(yōu)化問題（1）的一個試探解，種群k所包含的Nk(t)個生物個體所對應的優(yōu)化問題（1）的試探解集為，其中，m=1,2,…,Nk(t) ；種群k中的一個個體的特征j對應于優(yōu)化問題（1）試探解中的一個變量；種群k中所有個體的特征數(shù)與試探解的變量數(shù)相同，都為n，令個體特征的編號集合Z={1,2,…,n}。個體適應度指數(shù)即IPI 指數(shù)（individual physique index）對應于優(yōu)化問題的目標函數(shù)值。試探解質(zhì)量越好，其對應的IPI指數(shù)越高，反之亦然。時期t，對于優(yōu)化問題（1），個體的IPI 指數(shù)計算方法為：

2.2 水平結(jié)構(gòu)競爭-互利群落動力學模型

假設種群所消費的資源以某種特性參數(shù)向量z表示，具有特征z的資源消耗數(shù)量由函數(shù)k(z)來確定。函數(shù)k(z)中z值的集合稱為資源譜。假設一種群資源消費以某種概率分布來描述其特性，其密度函數(shù)f(z)稱為資源利用函數(shù)，具有均值z0和有限方差σ2。這時，種群的生態(tài)位取決于資源譜上的點z0和給定的點z0附近隨機分布的密度函數(shù)f(z)。當一個群落由若干為共同的食物資源而進行競爭的種群構(gòu)成時，自然認為適合于不同種群的z0點彼此之間有一定距離。這種情況下，種群生態(tài)位鑲嵌所造成的競爭現(xiàn)象必然會在資源空間里相應的資源利用函數(shù)fi(z)產(chǎn)生定義域相交的現(xiàn)象。最簡單的例子如圖1所示，圖中fi(z)為形狀相同的正態(tài)分布密度曲線，沿著資源譜均值之間以距離d分離；k(z)=const，如果對所有曲線，w為均方差，那么比值w/d可視為生態(tài)位接近的度量，或者說是群落種間隔離度度量；按照穩(wěn)定性條件，比值w/d可以用于判斷生態(tài)位鑲嵌的界限[12-13]。

Fig.1 Niche mosaic of 1-D resource spectrum圖1 1 維資源譜的生態(tài)位鑲嵌

兩個種群在資源譜上利用資源的分離程度稱為生態(tài)位分離。d表示平均分離度，w稱為變異度，生態(tài)位分離度為d/w。當生態(tài)位充分分離時，d/w大；當生態(tài)位重疊時，d/w小。

為簡單起見，以后總假定資源譜的維數(shù)為1 維，即z為1 維，因此可將z的黑體去掉而表示為z。K個種群競爭-互利群落的動力學模型為：

式中，yi為種群i的規(guī)模；CP(i)為與種群i競爭的其他種群集合；BP(i)為與種群互利的其他種群集合；ri為種群i的內(nèi)稟增長率；ki為種群i的生態(tài)位容量，ki=∫k(z)fi(z)dz；βij為種群i與種群j之間的互利系數(shù)；αij為種群i與種群j之間的競爭系數(shù)，由下式計算：

為方便起見，令A=[αij]K×K，A稱為競爭矩陣。當A取不同的形式時，表示不同的競爭格局。常見的競爭矩陣A有如下5 種形式：

（1）正態(tài)分布型。對于每一個種群i，有：

式中，zi為生態(tài)位的中心點，為正態(tài)分布的方差。如果種群i和種群j生態(tài)位的中心點彼此相距dij，那么由式（4）可計算得：

如果所有fi(z)都有相同的方差，且順序號碼相鄰就意味著生態(tài)位相鄰，則dij=|i-j|d，且：

當規(guī)定競爭系數(shù)的自鑲嵌程度為1 時，便有：

（2）離散分布型。將K個種群進行編號，使它們在資源空間彼此距離的大小可用下標差的絕對值|i-j|來度量。不難認為，競爭現(xiàn)象是隨種群生態(tài)位間距加大而減弱的，于是競爭系數(shù)可表示成：

（3）最鄰近型。設K個種群中的每一種群僅和自己最鄰近的種群競爭，而不和其他種群競爭。這時如果用a表示兩個相鄰生態(tài)位鑲嵌的度量，那么競爭矩陣為：

（4）均勻型。設K個種群中的每個種群均以相同的程度a與其他種群競爭，則：

（5）單調(diào)遞減型。設K個種群中的每個種群均以單調(diào)遞減的程度a與其他種群競爭，則：

為快速計算，需將式（3）改為離散遞推形式：

2.3 算子設計方法

HS-CBCO 算法是利用水平結(jié)構(gòu)競爭-互利群落動力學理論構(gòu)造種群演化算子，以實現(xiàn)生物個體間信息交換，進而實現(xiàn)對優(yōu)化問題（1）的全局最優(yōu)解的搜索。

2.3.1 競爭和互利種群集合確定方法

對于當前種群k，k∈P，其競爭型種群集合CP(k)是依據(jù)競爭格局類型c確定的，即對于c∈C，有：

（1）若c=C1或C2或C5，則從種群集合P中選擇3 個編號最相近的種群，由其編號形成集合CP(k)，但k?CP(k)；種群i與種群k編號相近意味著|k-i|盡可能小，但k≠i。

（2）若c=C3，則將K個種群按其編號構(gòu)成一個閉環(huán)，即當k=1時，CP(k)={2,K}；當1 ＜k＜K時，CP(k)={k-1,k+1}；當k=K時，CP(k)={1,K-1}。

（3）若c=C4，則從K個種群中隨機選擇3 個種群，由其編號形成集合CP(k)，但k?CP(k)。

對于當前種群k，k∈P，其互利型種群集合BP(k)是從不參與競爭的種群集合P-CP(k)中隨機選擇3 個種群，這些種群與當前種群k形成互利關(guān)系集合BP(k)，但k?BP(k)。

2.3.2 特征生物個體集合確定方法

對于當前種群k，k∈P，當前個體i∈Pk，有：

（1）競爭型個體集合CI(k)。從當前種群k的競爭型種群集合CP(k)中的所有生物個體中，隨機選擇L個生物個體，由其編號形成競爭型個體集合CI(k)。L稱為施加影響的個體數(shù)。

（2）互利型個體集合BI(k)。從當前種群k的互利型種群集合BP(k)中隨機選擇L個生物個體，由其編號形成互利型個體集合BI(k)。

（3）普通影響型個體集合GI(k)。在當前種群k的所有個體集合Pk中，隨機選擇L個生物個體，由其編號形成普通影響型個體集合GI(k)。

（4）強烈影響型個體集合SI(k)。在當前種群k的所有個體集合Pk中，隨機選擇L個生物個體，這些個體的IPI 指數(shù)高于當前個體i，由其編號形成強烈影響型個體集合SI(k)。

（5）虛弱個體集合WI(k)。在當前種群k的所有個體集合Pk中，隨機選擇L個IPI 指數(shù)最低的生物個體，由其編號形成虛弱個體集合WI(k)。

2.3.3 算子設計方法

HS-CBCO 算法利用水平結(jié)構(gòu)競爭-互利群落動力學理論及其控制下的種群演變規(guī)律構(gòu)造種群演化算子，來實現(xiàn)個體間的信息交換，進而實現(xiàn)對優(yōu)化問題全局最優(yōu)解的搜索。HS-CBCO 算法的群演化算子如下所述。

（1）競爭算子。該算子依據(jù)競爭關(guān)系構(gòu)造，對當前種群k來說，k∈P，當前個體i∈Pk，由式（10）得：

（2）互利算子。該算子依據(jù)互利關(guān)系構(gòu)造，即對當前種群k來說，k∈P，當前個體i∈Pk，特征j∈Z，則由式（10）可得：

（3）普通影響算子。該算子依據(jù)普通影響關(guān)系構(gòu)造，即對于當前種群k，k∈P，當前個體i∈Pk，特征j∈Z，有：

式中，u1、u2從GI(k)中隨機選擇，且滿足u1≠u2；a=Rnd(-0.5,0.5)。

（4）強烈影響算子。該算子依據(jù)強烈影響關(guān)系構(gòu)造，即對于當前種群k，k∈P，當前個體i∈Pk，特征j∈Z，有：

式中，v1、v2從SI(kU)中隨機選擇，且滿足v1≠v2；γ=Rnd(-1,1)。

（5）新生算子。該算子用于為某個種群新生m個新個體，即對于種群k，k∈P，待新生的個體編號集合為NGk(m)，有：

式中，新生個體的編號c∈NGk(m)；c1、c2、c3從集合SI(k)中隨機選擇。

（6）死亡算子。該算子用于為某個種群清除m個虛弱個體，即對于種群k，k∈P，從集合WI(k)中挑出m個體進行清除。

（7）選擇算子。通過各算子產(chǎn)生新一代生物個體之后，將新一代個體與相應的父代個體進行比較，較優(yōu)者保存到下一代中。對于當前種群k，k∈P，當前個體i∈Pk，有：

2.4 HS-CBCO 算法設計

（1）初始化：令時期t=0，按第4.1 節(jié)介紹的方法設置HS-CBCO 算法涉及到的所有參數(shù)：演化時期數(shù)G、全局最優(yōu)解計算誤差ε、個體特征受影響的最大概率E0、施加影響的個體數(shù)L、種群數(shù)K；隨機選擇當前初始最優(yōu)解X*。

（2）按第4.1 節(jié)介紹的方法設置水平結(jié)構(gòu)競爭-互利群落動力學模型參數(shù)yi(0)，令Ni(0)=[yi(0)]，i=1,2,…,K；[y]表示對y取整；對各種群中的所有個體進行統(tǒng)一編號，生成個體集合，k=1,2,…,K。

（4）在競爭-互利格局集合C中為生態(tài)系統(tǒng)隨機指定一種競爭-互利格局c，依據(jù)c計算競爭矩陣A。

（5）執(zhí)行下列操作：

（6）結(jié)束。

2.5 HS-CBCO 算法的特點

（1）Markov 特性。從HS-CBCO 算法各算子的定義式（11）～式（15）知，時期t+1任何一新試探解的生成只與該試探解在時期t的狀態(tài)有關(guān)，而與該試探解在時期t以前是如何演變到時期t的狀態(tài)的歷程無關(guān)，因而HS-CBCO 算法具有Markov 特性。

（2）“步步不差”特性。從生長算子的定義式（16）知，HS-CBCO 算法的每步演化都不會向比當前狀態(tài)更差的狀態(tài)轉(zhuǎn)移，因而HS-CBCO 算法的演化過程具有“步步不差”特性。

2.6 HS-CBCO 算法的時間復雜度

Table 1 Table of HS-CBCO time complexity表1 HS-CBCO 時間復雜度計算表

2.7 HS-CBCO 算法的優(yōu)勢

定理1 若一個群智能優(yōu)化算法所擁有的算子越多，且各算子被隨機獨立調(diào)度執(zhí)行，則該算法的性能越優(yōu)良。

證明 假設一個群智能優(yōu)化算法有n個算子，當該算法求解優(yōu)化問題X時，這n個算子求解優(yōu)化問題X成功的概率分別為p1,p2,…,pn。因每個算子在求解優(yōu)化問題X時均是被隨機獨立調(diào)度執(zhí)行的，故該算法在其n個算子的聯(lián)合作用下求解優(yōu)化問題X成功的概率q為：

因0 ＜pi＜1，故0 ＜1-pi＜1，i=1～n；當n越大時，越小，而q則越大。此結(jié)論表明，若一個群智能優(yōu)化算法的算子越多，則該算法求解一個優(yōu)化問題時成功的概率越大。因此，算子越多，算法性能越優(yōu)良。

HS-CBCO 算法擁有10 個算子，且每個算子均是被隨機調(diào)度執(zhí)行的，故HS-CBCO 算法滿足定理1 的條件，因而HS-CBCO 算法具有優(yōu)良的性能。 □

與已有的基于種群動力學的優(yōu)化方法[19-20]相比，HS-CBCO 算法具有如下異同點：

（1）HS-CBCO 算法所依據(jù)的生物場景中詳細考慮了生物種群的水平營養(yǎng)結(jié)構(gòu)特點，而現(xiàn)有的其他基于種群動力學的優(yōu)化方法沒有考慮這一關(guān)鍵特征。

（2）HS-CBCO 算法將種群動力學中一些常規(guī)特征，如競爭、互利等特征，也包含到了算法中，該特點與基于種群動力學的優(yōu)化方法類似。

（3）由于存在上述（1）和（2）的特點，HS-CBCO 算法比基于種群動力學的優(yōu)化方法擁有更多的算子，故該算法特別適合應用于分布式多任務環(huán)境，如云計算環(huán)境。

3 HS-CBCO 算法的全局收斂性證明

在證明HS-CBCO 算法的全局收斂性之前，先介紹由Iisufescu 在文獻[21]提出的定理：

定理2 設P′是一N階可歸約隨機矩陣，也就是通過相同的行變換和列變換后可以得到P′=，其中C是M階本原隨機矩陣并且R≠0，T≠0，則有：

上述的矩陣是一個穩(wěn)定的隨機矩陣且P′∞=1′P′∞，P′∞=P′0P′∞唯一確定并且與初始分布無關(guān)，P′∞滿足如下條件：

利用定理2，不難證明HS-CBCO 算法的全局收斂性。其證明過程如下所述。

由算法HS-CBCO 算法知，優(yōu)化問題（1）的搜索空間等價于一個生態(tài)系統(tǒng)，該生態(tài)系統(tǒng)有K個種群；在時期t，種群k有Nk(t)個生物個體，k=1,2,…,K；將各種群中的所有生物個體重新排列成N(t)個生物個體，，形成新的生物個體序列為。每個生物個體（i=1,2,…,N(t)）即為優(yōu)化問題（1）的一個試探解，其目標函數(shù)值為（按式（1）計算），則所有生物個體的狀態(tài)所形成的集合為：

進一步令：

不失一般性，令F1即為所求的全局最優(yōu)解。將式（17）的下標取出形成一個集合，即：

集合U中的元素就是隨機搜索時每個生物個體可能所處的狀態(tài)。假設在某時期搜索到的最好目標函數(shù)值為Fi，其對應的狀態(tài)為i。顯然，由式（17）知，下一時期搜索時，若向更優(yōu)的狀態(tài)k轉(zhuǎn)移，則應滿足k＜i；相反，若向更差的狀態(tài)k轉(zhuǎn)移，則應滿足k＞i，如圖2 所示。

?Xt∈S有F1≤F(Xt)≤FN，將S劃分為非空子集為：

Fig.2 State transition in random search圖2 隨機搜索時狀態(tài)轉(zhuǎn)移圖

證明（1）對于式（19），設狀態(tài)i為時期t某生物個體Xt的狀態(tài)，該狀態(tài)i當然就是該生物個體至今已達到的最好狀態(tài)。在HS-CBCO 優(yōu)化算法中，每次進行新的演化都總是對該生物個體當前狀態(tài)i進一步向更好狀態(tài)的更新，即有：

上式的含義是：若i為時期t某生物個體的狀態(tài)（也必是該個體已達到的最好狀態(tài)），在時期t+1 該生物個體的演化只會向更好的狀態(tài)更新，因此從i開始不可能轉(zhuǎn)移到比i差的任何其他狀態(tài)上去；由式（17）知，若要Fk＞Fi，則比狀態(tài)i差的狀態(tài)k必滿足k＞i，也即最好狀態(tài)要么保持原狀，要么只能向更好的狀態(tài)更新（即做到步步不差），如圖2 所示。

（2）對于式（20），設某生物個體的當前狀態(tài)為i，當然必是該生物個體迄今為止已達到的最好狀態(tài)，在時期t+1，該生物個體隨機選擇各種算子以期轉(zhuǎn)移到更好的狀態(tài)上，有競爭算子、互利算子、普通影響算子、強烈影響算子可供選擇：

①若i是全局最優(yōu)狀態(tài)，即i=1，則下一步轉(zhuǎn)移必選k=1（因為不可能轉(zhuǎn)移到比當前狀態(tài)還差的狀態(tài)上去），即必以概率p1,1=1 轉(zhuǎn)移到該全局最優(yōu)狀態(tài)上去。因p1,1=1 ＞0，命題得證。

②若i不是全局最優(yōu)狀態(tài)，則在全局最優(yōu)狀態(tài)1和當前狀態(tài)i之間必至少存在一中間狀態(tài)k（如圖2所示），使得F1≤Fk＜Fi，即1 ≤k＜i，此時當前狀態(tài)i可以轉(zhuǎn)移到狀態(tài)k上去（因為新狀態(tài)k比當前狀態(tài)i更優(yōu)），也就是pi,k＞0，命題得證。

綜合上述情況，可得?k＜i,pi,k＞0。 □

定理3 HS-CBCO 算法具有全局收斂性。

根據(jù)引理中式（20）結(jié)論得：

由以上可知轉(zhuǎn)移矩陣P′是N(t)階可歸約隨機矩陣，滿足定理2 的條件，因此下式成立：

因C∞=C=(1)，T∞=0，故必有R∞=(1,1,…,1)T，這是因為由式（18）知轉(zhuǎn)移矩陣P′中每行的概率之和為1。因此有：

上式表明，當k→∞時，概率pi,1=1，i=1,2,…,N(t)，也即無論初始狀態(tài)如何，最后都能以概率1 收斂到全局最優(yōu)狀態(tài)1 上。于是得：

因此，HS-CBCO 優(yōu)化算法具有全局收斂性?！?/p>

4 HS-CBCO 算法參數(shù)設置及其普適性

4.1 參數(shù)設置方法

HS-CBCO 算法參數(shù)包括兩部分：一部分是水平結(jié)構(gòu)競爭-互利群落動力學模型參數(shù)，該部分參數(shù)為算法內(nèi)置參數(shù)，無需用戶進行設置；另一部分是算法運行控制參數(shù)，此類參數(shù)需要用戶根據(jù)情況進行設置。

（1）水平結(jié)構(gòu)競爭-互利群落動力學模型參數(shù)確定方法。該模型參數(shù)的選擇依據(jù)是確保yi(t)(i=1,2,…,K)具有較好的隨機性。依據(jù)文獻[12]介紹的參數(shù)取值方法并經(jīng)隨機化后，可得ri=Rnd(0.3,0.4)，ki=Rnd(20,30)，yi(0)=Rnd(60,70)，i=1～K；a=0.5，βij=Rnd(0.17,0.24)，i,j=1～K。應用此取值策略，當K=10 時，任取第5 號種群進行測試，種群中的個體數(shù)y5變化情況如圖3 所示。從圖3 可知，y5具有很好的隨機性。

Fig.3 Randomicity of individual y5in population 5圖3 第5 號種群中個體y5的隨機性

（2）算法運行控制參數(shù)設置方法。HS-CBCO 算法的運行控制參數(shù)有：演化時期數(shù)G、全局最優(yōu)解計算誤差ε、個體特征受影響的最大概率E0、施加影響的個體數(shù)L、種群數(shù)K。G和ε是兩個互補參數(shù)，只要滿足其中一個即可。ε由所求解的工程優(yōu)化問題決定，通常可取ε=10-5～10-10即可，G由計算設備性能決定，G可取充分大，不妨設G=108～1010。HS-CBCO算法關(guān)鍵參數(shù)只有E0、L、K。因此，下面主要討論3 個關(guān)鍵參數(shù)E0、L、K的取值方法。由于Bump 優(yōu)化問題極難求解，且與一些工程優(yōu)化問題特征類似，故以Bump 優(yōu)化問題為例來探明E0、L、K的取值方法。Bump 優(yōu)化問題如下：

令Favg表示平均最優(yōu)目標函數(shù)值，Tavg表示平均計算時間。當L取不同值時，采用HS-CBCO 算法求解Bump 優(yōu)化問題，令n=50，E0=0.01，K=10，G=108，運行50 次，表2 描述了L與Favg和Tavg之間的關(guān)系。結(jié)果表明，當L=3～6 時，F(xiàn)avg的精度達到最高，而Tavg增加較低。由此可見，L=3～6 為L的最佳取值區(qū)間。

Table 2 Relation of L with Favgand Tavg表2 L 與Favg和Tavg之間的關(guān)系

令n=50，L=3，K=10，G=108，HS-CBCO 算法運行50 次。表3 描述了參數(shù)E0與Favg和Tavg之間的關(guān)系。結(jié)果表明，當E0=0.006～0.1 時，F(xiàn)avg的精度相對較高，且Tavg較少；當E0＞0.2 時，Tavg增加很大，且Favg精度也大大降低；特別是當E0=1 時，無法獲得最佳解。由此可見，E0=0.006～0.1 為E0的最佳取值區(qū)間。

令E0=0.01，L=3，G=108，HS-CBCO 算法運行50 次。表4 描述了K與Favg、Tavg之間的關(guān)系。從表4 可以看到：當K=8～16 時，F(xiàn)avg的精度相對較高，且Tavg較少；當K＞18 時，Tavg增加很大，且Favg精度也逐步降低。由此可見，K=8～16 為K的最佳取值區(qū)間。

Table 3 Relation of E0with Favgand Tavg表3 參數(shù)E0與Favg和Tavg之間的關(guān)系

Table 4 Relation of K with Favgand Tavg表4 K 與Favg和Tavg之間的關(guān)系

4.2 參數(shù)設置的普適性分析

4.1 節(jié)確定了參數(shù)L、E0、K的最佳取值區(qū)間。由于Bump 優(yōu)化問題與工程中存在的一類優(yōu)化問題相似，因此從求解Bump 優(yōu)化問題所獲得的參數(shù)設置，具有一定的普適性。事實上，參數(shù)L、E0、K的取值并不要求太精確，不精確的參數(shù)取值僅影響計算時間的長短，對求解精度的影響較小。優(yōu)化問題的維數(shù)n對HS-CBCO 算法的求解時間有影響，參數(shù)L、E0、K的取值規(guī)律是，優(yōu)化問題的維數(shù)n越高，L和K的取值應越大，E0的取值應越小。根據(jù)場景及需求進行參數(shù)調(diào)整的思路如下：

（1）若n≤100，則L=3，E0=0.01，K=8～10。

（2）若100 ＜n≤500，則L=4，E0=0.005，K=9～12。

（3）若500 ＜n≤1 000，則L=5，E0=0.000 1，K=11～14。

（4）若n＞1 000，則L=6，E0=0.000 05，K=13～16。

5 HS-CBCO 算法與其他算法的性能比較

CEC 2013[22]是一組新的群智能優(yōu)化算法測試函數(shù)，該組測試函數(shù)包含有28 個經(jīng)過精心設計的基準函數(shù)，這些基準函數(shù)是由一些傳統(tǒng)的著名測試函數(shù)（如Sphere 函數(shù)、Schwefel 函數(shù)、Rastrigrin 函數(shù)、Ackley 函數(shù)、Griewangk 函數(shù)、Rosenbrock 函數(shù)等）經(jīng)改造而得，改造方法包括復雜旋轉(zhuǎn)和平移、條件數(shù)大幅提高和多函數(shù)鑲嵌等，從而使得這些基準函數(shù)不再關(guān)于某點對稱，其表達式高度復雜，理論全局最優(yōu)解可隨機設置。這28 個基準函數(shù)共分3 類：第一類是由F1～F5 等5 個單峰函數(shù)組成，這些單峰函數(shù)包含有極高的條件數(shù)，主要用于測試算法的求精能力；第二類是由F6～F20 等15 個多峰函數(shù)組成，這些多峰函數(shù)是由上述著名的測試函數(shù)經(jīng)旋轉(zhuǎn)平移后而形成，主要用于測試算法的探索能力；第三類是由F21～F28等8 個復合函數(shù)組成，這些復合函數(shù)是由若干個第一類和第二類函數(shù)經(jīng)復雜鑲嵌而形成，其函數(shù)表達式異常復雜，主要用于同時測試算法的求精能力和探索能力的協(xié)調(diào)性。本文選擇了6 個代表性的基準函數(shù)，每類選2 個，如表5 所示。

Table 5 Benchmark function optimization problems表5 基準函數(shù)優(yōu)化問題

在表5 中，優(yōu)化問題的維數(shù)為n；O是一個n維決策向量，O的值隨機產(chǎn)生。這些基準函數(shù)的形式可參見文獻[22]。

用HS-CBCO 算法去求解表5 所示的6 個基準函數(shù)，HS-CBCO 的參數(shù)設置為n=50，ε=10-10，K=10，L=3，E0=0.01，G=1010。與HS-CBCO 算法進行比較的優(yōu)化算法為：RC-GA（real-coded genetic algorithm）[2]、DASA（differential ant-stigmergy algorithm）[4]、NP-PSO（non-parametric particle swarm optimization）[23]、MBBO（metropolis biogeography-based optimization）[9]、DE（differential evolution）[24]、SaDE（differential evolution algorithm with self-adaptive strategy）[25]和ABC（artificial bee colony algorithm）[11]。計算時，這7 種算法的參數(shù)按表6 進行設置。RC-GA 是一種新型實數(shù)編碼遺傳算法，其中的算子采用實數(shù)編碼設計，完全不同于傳統(tǒng)的GA 算法；DASA 是一種模仿蟻群算法的思路而完全重構(gòu)的新型算法；NP-PSO 是一種不需要進行參數(shù)設置的粒子群算法；MBBO 對傳統(tǒng)的生物地理學算法的島嶼特征進行了大幅修改，強化了都市特征；DE 是在傳統(tǒng)差分進化算法中引入了局部誘導遺傳算子的新型差分進化算法；SaDE 在傳統(tǒng)自適應差分算法中引入了一種新的自適應參數(shù)控制策略；ABC 是在傳統(tǒng)蜂群算法中引入了基因組合的蜂群算法。這7 個算法是其對應傳統(tǒng)算法的較優(yōu)改進版，特別適合求解高條件數(shù)單峰、多峰復合優(yōu)化問題。

用這些算法獨立求解每個基準函數(shù)51 次，表7列出了最優(yōu)目標函數(shù)的平均值（Average）、中位數(shù)（Median）、標準差（STD）、計算時間（Time），并對每種算法進行排序。表7 的Rank1 是按該算法的平均最佳目標函數(shù)值的精度進行的排名，Rank2 是按平均最佳目標函數(shù)的精度與平均計算時間的長短兩者綜合進行的排名。

Table 6 Parameter settings of compared algorithms表6 被比較算法的參數(shù)設置

從表7 可以看出各算法的排名按精度或按精度+計算時間的最終排名均為：

HS-CBCO>SaDE>DE>DASA>MBBO>ABC>NP-PSO>RC-GA

圖4（a）～圖4（f）說明各算法求解6 個基準函數(shù)時的樣本收斂曲線。為了突出這些樣本收斂曲線的變化，水平和垂直軸采用對數(shù)刻度。

6 HS-CBCO 算法的性能分析

6.1 求精和探索能力及其協(xié)調(diào)性分析

（1）求精能力分析。從圖4（a）～圖4（f）可知，HSCBCO 算法的收斂曲線在一些時間段內(nèi)較其他算法的收斂曲線上升緩慢，且持續(xù)時間長。此說明HSCBCO 算法提升最優(yōu)解精度的演化十分明確，該特征表明HS-CBCO 算法的求精能力較其他算法強。另外，由表7 可知，HS-CBCO 算法求解F2、F4、F6、F19時，能獲得其理論全局最優(yōu)解；HS-CBCO 算法求解F22、F28 時，所獲得的全局最優(yōu)解均優(yōu)于其他被比較算法。此說明HS-CBCO 算法較其他被比較算法具有更好的求精能力。

（2）探索能力分析。從圖4（a）～圖4（f）可知，HSCBCO 算法的收斂曲線在一些時間段內(nèi)較其他算法的收斂曲線陡，此說明HS-CBCO 算法提升IPI 指數(shù)的耗時很短，該特征表明HS-CBCO 算法探索新空間的能力較其他被比較算法更強。

（3）求精和探索能力的協(xié)調(diào)性分析。從圖4（a）～圖4（f）可知，與其他被比較算法相比，HS-CBCO 算法的緩（求精能力)和陡（探索能力)交替出現(xiàn)，且緩的持續(xù)時間均較長，陡的持續(xù)時間均較短，此表明HS-CBCO 算法的求精和探索能力的協(xié)調(diào)性均優(yōu)于其他被比較算法。

Table 7 Comparison of optimum solutions obtained by each algorithm表7 各算法求解結(jié)果的比較

Fig.4 Sample convergence curves圖4 樣本收斂曲線

6.2 收斂性精度和收斂速度分析

（1）收斂性分析。從定理3 可知，HS-CBCO 算法具有全局收斂性；又從2.5 節(jié)知，HS-CBCO 算法具有“步步不差”特性，此表明HS-CBCO 算法的收斂過程不會出現(xiàn)忽大忽小的情形。從圖4 所示的樣本收斂曲線中的黑實線可知，HS-CBCO 算法的收斂過程與理論分析完全一致。

（2）收斂速度分析。在求解過程中，若HS-CBCO算法經(jīng)常出現(xiàn)較陡的收斂曲線，說明HS-CBCO 算法的收斂速度較快。從圖4（a）～圖4（f）的黑實線可知，HS-CBCO 算法收斂較快。

（3）收斂精度分析。在求解后期，若HS-CBCO算法的收斂曲線上升緩慢，且持續(xù)時間長，說明HSCBCO 算法提升全局最優(yōu)解精度的過程十分明確。從圖4（a）～圖4（f）的后段黑實線可知，HS-CBCO 算法均能獲得很高精度的全局最優(yōu)解。

7 結(jié)束語

HS-CBCO 算法具有如下特點：

（1）HS-CBCO 算法依據(jù)水平結(jié)構(gòu)競爭-互利群落動力學模型構(gòu)造，可將生物個體科學地劃分成許多種類，從而大幅提升了生物個體的多樣性。

（2）HS-CBCO 算法依據(jù)水平結(jié)構(gòu)競爭-互利群落動力學模型來確定生物個體數(shù)，從而使得生物個體數(shù)確定的科學性得到提升，避開了人為確定生物個體數(shù)的困擾。

（3）HS-CBCO 算法中運用水平結(jié)構(gòu)競爭-互利群落動力學模型開發(fā)出了競爭算子、互利算子、普通影響算子和強烈影響算子。競爭算子和互利算子可實現(xiàn)個體跨種群交換信息，而普通影響算子和強烈影響算子可實現(xiàn)種群內(nèi)部生物個體之間的信息交換，從而實現(xiàn)生物個體間信息的充分交換。

（4）HS-CBCO 算法的新生算子可適時補充新個體到種群中，而死亡算子可將種群中的虛弱個體適時清除掉，從而大幅提升算法跳出局部陷阱的能力。

（5）HS-CBCO 算法所涉及的參數(shù)的絕大部分依據(jù)水平結(jié)構(gòu)競爭-互利群落動力學模型來確定，無需人為設置；而需要人為設置的參數(shù)卻很少，且易于設置。

（6）HS-CBCO 算法的求精能力和探索能力及其兩者的協(xié)調(diào)性均優(yōu)良。

（7）HS-CBCO 算法的演化過程具有Markov 特性和“步步不差”特性，從而使得該算法具有全局收斂特征。

（8）HS-CBCO 算法具有科學理論作為支撐，易于進行深入分析。

HS-CBCO 算法今后的改進方向如下：

（1）深入研究各算子的動態(tài)特征。

（2）深入研究算法在求解過程中各種群的動態(tài)特征。

（3）對HS-CBCO 算法進行改進，使之適應復雜水平結(jié)構(gòu)種群競爭、互利環(huán)境。