黃光球，陸秋琴

西安建筑科技大學(xué) 管理學(xué)院，西安 710055

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

2 HS-CBCO 算法設(shè)計(jì)

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

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

2.1 算法場(chǎng)景設(shè)計(jì)

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

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

在一個(gè)生態(tài)系統(tǒng)中，每一種群都占有自己的生態(tài)位，生態(tài)位是指種群對(duì)多種資源的利用范圍。當(dāng)種群的生態(tài)位出現(xiàn)鑲嵌（又稱重疊）時(shí)，種群之間會(huì)產(chǎn)生競(jìng)爭(zhēng)關(guān)系。生態(tài)系統(tǒng)中已發(fā)現(xiàn)有5 種競(jìng)爭(zhēng)格局，即正態(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)系不是一成不變，而是隨時(shí)間變化的。若一個(gè)種群與另外一個(gè)種群存在競(jìng)爭(zhēng)關(guān)系，則它們之間就不存在互利關(guān)系，反之亦然。

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

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

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

2.2 水平結(jié)構(gòu)競(jìng)爭(zhēng)-互利群落動(dòng)力學(xué)模型

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

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

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

為簡(jiǎn)單起見(jiàn)，以后總假定資源譜的維數(shù)為1 維，即z為1 維，因此可將z的黑體去掉而表示為z。K個(gè)種群競(jìng)爭(zhēng)-互利群落的動(dòng)力學(xué)模型為：

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

為方便起見(jiàn)，令A(yù)=[αij]K×K，A稱為競(jìng)爭(zhēng)矩陣。當(dāng)A取不同的形式時(shí)，表示不同的競(jìng)爭(zhēng)格局。常見(jiàn)的競(jìng)爭(zhēng)矩陣A有如下5 種形式：

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

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

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

當(dāng)規(guī)定競(jìng)爭(zhēng)系數(shù)的自鑲嵌程度為1 時(shí)，便有：

（2）離散分布型。將K個(gè)種群進(jìn)行編號(hào)，使它們?cè)谫Y源空間彼此距離的大小可用下標(biāo)差的絕對(duì)值|i-j|來(lái)度量。不難認(rèn)為，競(jìng)爭(zhēng)現(xiàn)象是隨種群生態(tài)位間距加大而減弱的，于是競(jìng)爭(zhēng)系數(shù)可表示成：

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

（4）均勻型。設(shè)K個(gè)種群中的每個(gè)種群均以相同的程度a與其他種群競(jìng)爭(zhēng)，則：

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

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

2.3 算子設(shè)計(jì)方法

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

2.3.1 競(jìng)爭(zhēng)和互利種群集合確定方法

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

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

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

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

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

2.3.2 特征生物個(gè)體集合確定方法

對(duì)于當(dāng)前種群k，k∈P，當(dāng)前個(gè)體i∈Pk，有：

（1）競(jìng)爭(zhēng)型個(gè)體集合CI(k)。從當(dāng)前種群k的競(jìng)爭(zhēng)型種群集合CP(k)中的所有生物個(gè)體中，隨機(jī)選擇L個(gè)生物個(gè)體，由其編號(hào)形成競(jìng)爭(zhēng)型個(gè)體集合CI(k)。L稱為施加影響的個(gè)體數(shù)。

（2）互利型個(gè)體集合BI(k)。從當(dāng)前種群k的互利型種群集合BP(k)中隨機(jī)選擇L個(gè)生物個(gè)體，由其編號(hào)形成互利型個(gè)體集合BI(k)。

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

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

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

2.3.3 算子設(shè)計(jì)方法

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

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

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

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

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

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

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

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

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

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

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

2.4 HS-CBCO 算法設(shè)計(jì)

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

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

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

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

（6）結(jié)束。

2.5 HS-CBCO 算法的特點(diǎn)

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

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

2.6 HS-CBCO 算法的時(shí)間復(fù)雜度

Table 1 Table of HS-CBCO time complexity表1 HS-CBCO 時(shí)間復(fù)雜度計(jì)算表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

進(jìn)一步令：

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

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

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

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

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

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

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

①若i是全局最優(yōu)狀態(tài)，即i=1，則下一步轉(zhuǎn)移必選k=1（因?yàn)椴豢赡苻D(zhuǎn)移到比當(dāng)前狀態(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和當(dāng)前狀態(tài)i之間必至少存在一中間狀態(tài)k（如圖2所示），使得F1≤Fk＜Fi，即1 ≤k＜i，此時(shí)當(dāng)前狀態(tài)i可以轉(zhuǎn)移到狀態(tài)k上去（因?yàn)樾聽(tīng)顟B(tài)k比當(dāng)前狀態(tài)i更優(yōu)），也就是pi,k＞0，命題得證。

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

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

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

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

因C∞=C=(1)，T∞=0，故必有R∞=(1,1,…,1)T，這是因?yàn)橛墒剑?8）知轉(zhuǎn)移矩陣P′中每行的概率之和為1。因此有：

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

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

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

4.1 參數(shù)設(shè)置方法

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

（1）水平結(jié)構(gòu)競(jìng)爭(zhēng)-互利群落動(dòng)力學(xué)模型參數(shù)確定方法。該模型參數(shù)的選擇依據(jù)是確保yi(t)(i=1,2,…,K)具有較好的隨機(jī)性。依據(jù)文獻(xiàn)[12]介紹的參數(shù)取值方法并經(jīng)隨機(jī)化后，可得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。應(yīng)用此取值策略，當(dāng)K=10 時(shí)，任取第5 號(hào)種群進(jìn)行測(cè)試，種群中的個(gè)體數(shù)y5變化情況如圖3 所示。從圖3 可知，y5具有很好的隨機(jī)性。

Fig.3 Randomicity of individual y5in population 5圖3 第5 號(hào)種群中個(gè)體y5的隨機(jī)性

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

令Favg表示平均最優(yōu)目標(biāo)函數(shù)值，Tavg表示平均計(jì)算時(shí)間。當(dāng)L取不同值時(shí)，采用HS-CBCO 算法求解Bump 優(yōu)化問(wèn)題，令n=50，E0=0.01，K=10，G=108，運(yùn)行50 次，表2 描述了L與Favg和Tavg之間的關(guān)系。結(jié)果表明，當(dāng)L=3～6 時(shí)，F(xiàn)avg的精度達(dá)到最高，而Tavg增加較低。由此可見(jiàn)，L=3～6 為L(zhǎng)的最佳取值區(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 算法運(yùn)行50 次。表3 描述了參數(shù)E0與Favg和Tavg之間的關(guān)系。結(jié)果表明，當(dāng)E0=0.006～0.1 時(shí)，F(xiàn)avg的精度相對(duì)較高，且Tavg較少；當(dāng)E0＞0.2 時(shí)，Tavg增加很大，且Favg精度也大大降低；特別是當(dāng)E0=1 時(shí)，無(wú)法獲得最佳解。由此可見(jiàn)，E0=0.006～0.1 為E0的最佳取值區(qū)間。

令E0=0.01，L=3，G=108，HS-CBCO 算法運(yùn)行50 次。表4 描述了K與Favg、Tavg之間的關(guān)系。從表4 可以看到：當(dāng)K=8～16 時(shí)，F(xiàn)avg的精度相對(duì)較高，且Tavg較少；當(dāng)K＞18 時(shí)，Tavg增加很大，且Favg精度也逐步降低。由此可見(jiàn)，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ù)設(shè)置的普適性分析

4.1 節(jié)確定了參數(shù)L、E0、K的最佳取值區(qū)間。由于Bump 優(yōu)化問(wèn)題與工程中存在的一類優(yōu)化問(wèn)題相似，因此從求解Bump 優(yōu)化問(wèn)題所獲得的參數(shù)設(shè)置，具有一定的普適性。事實(shí)上，參數(shù)L、E0、K的取值并不要求太精確，不精確的參數(shù)取值僅影響計(jì)算時(shí)間的長(zhǎng)短，對(duì)求解精度的影響較小。優(yōu)化問(wèn)題的維數(shù)n對(duì)HS-CBCO 算法的求解時(shí)間有影響，參數(shù)L、E0、K的取值規(guī)律是，優(yōu)化問(wèn)題的維數(shù)n越高，L和K的取值應(yīng)越大，E0的取值應(yīng)越小。根據(jù)場(chǎng)景及需求進(jìn)行參數(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)化算法測(cè)試函數(shù)，該組測(cè)試函數(shù)包含有28 個(gè)經(jīng)過(guò)精心設(shè)計(jì)的基準(zhǔn)函數(shù)，這些基準(zhǔn)函數(shù)是由一些傳統(tǒng)的著名測(cè)試函數(shù)（如Sphere 函數(shù)、Schwefel 函數(shù)、Rastrigrin 函數(shù)、Ackley 函數(shù)、Griewangk 函數(shù)、Rosenbrock 函數(shù)等）經(jīng)改造而得，改造方法包括復(fù)雜旋轉(zhuǎn)和平移、條件數(shù)大幅提高和多函數(shù)鑲嵌等，從而使得這些基準(zhǔn)函數(shù)不再關(guān)于某點(diǎn)對(duì)稱，其表達(dá)式高度復(fù)雜，理論全局最優(yōu)解可隨機(jī)設(shè)置。這28 個(gè)基準(zhǔn)函數(shù)共分3 類：第一類是由F1～F5 等5 個(gè)單峰函數(shù)組成，這些單峰函數(shù)包含有極高的條件數(shù)，主要用于測(cè)試算法的求精能力；第二類是由F6～F20 等15 個(gè)多峰函數(shù)組成，這些多峰函數(shù)是由上述著名的測(cè)試函數(shù)經(jīng)旋轉(zhuǎn)平移后而形成，主要用于測(cè)試算法的探索能力；第三類是由F21～F28等8 個(gè)復(fù)合函數(shù)組成，這些復(fù)合函數(shù)是由若干個(gè)第一類和第二類函數(shù)經(jīng)復(fù)雜鑲嵌而形成，其函數(shù)表達(dá)式異常復(fù)雜，主要用于同時(shí)測(cè)試算法的求精能力和探索能力的協(xié)調(diào)性。本文選擇了6 個(gè)代表性的基準(zhǔn)函數(shù)，每類選2 個(gè)，如表5 所示。

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

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

用HS-CBCO 算法去求解表5 所示的6 個(gè)基準(zhǔn)函數(shù)，HS-CBCO 的參數(shù)設(shè)置為n=50，ε=10-10，K=10，L=3，E0=0.01，G=1010。與HS-CBCO 算法進(jìn)行比較的優(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]。計(jì)算時(shí)，這7 種算法的參數(shù)按表6 進(jìn)行設(shè)置。RC-GA 是一種新型實(shí)數(shù)編碼遺傳算法，其中的算子采用實(shí)數(shù)編碼設(shè)計(jì)，完全不同于傳統(tǒng)的GA 算法；DASA 是一種模仿蟻群算法的思路而完全重構(gòu)的新型算法；NP-PSO 是一種不需要進(jìn)行參數(shù)設(shè)置的粒子群算法；MBBO 對(duì)傳統(tǒng)的生物地理學(xué)算法的島嶼特征進(jìn)行了大幅修改，強(qiáng)化了都市特征；DE 是在傳統(tǒng)差分進(jìn)化算法中引入了局部誘導(dǎo)遺傳算子的新型差分進(jìn)化算法；SaDE 在傳統(tǒng)自適應(yīng)差分算法中引入了一種新的自適應(yīng)參數(shù)控制策略；ABC 是在傳統(tǒng)蜂群算法中引入了基因組合的蜂群算法。這7 個(gè)算法是其對(duì)應(yīng)傳統(tǒng)算法的較優(yōu)改進(jìn)版，特別適合求解高條件數(shù)單峰、多峰復(fù)合優(yōu)化問(wèn)題。

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

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

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

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

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

6 HS-CBCO 算法的性能分析

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

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

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

（3）求精和探索能力的協(xié)調(diào)性分析。從圖4（a）～圖4（f）可知，與其他被比較算法相比，HS-CBCO 算法的緩（求精能力)和陡（探索能力)交替出現(xiàn)，且緩的持續(xù)時(shí)間均較長(zhǎng)，陡的持續(xù)時(shí)間均較短，此表明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 算法的收斂過(guò)程不會(huì)出現(xiàn)忽大忽小的情形。從圖4 所示的樣本收斂曲線中的黑實(shí)線可知，HS-CBCO 算法的收斂過(guò)程與理論分析完全一致。

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

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

7 結(jié)束語(yǔ)

HS-CBCO 算法具有如下特點(diǎn)：

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

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

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

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

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

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

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

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

HS-CBCO 算法今后的改進(jìn)方向如下：

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

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

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