徐衛(wèi)濱

(太原科技大學(xué)經(jīng)濟(jì)與管理學(xué)院，太原030024)

在現(xiàn)實(shí)世界中，許多系統(tǒng)都可以用復(fù)雜網(wǎng)絡(luò)來描述，如生物網(wǎng)絡(luò)中的代謝網(wǎng)[1]、蛋白質(zhì)網(wǎng)[2]等。這些真實(shí)的網(wǎng)絡(luò)，在變化的環(huán)境中通過不斷地改變結(jié)構(gòu)來保持他們的性能。

為了理解真實(shí)的網(wǎng)絡(luò)，學(xué)者們設(shè)計(jì)了各種各樣的、能夠反映真實(shí)網(wǎng)絡(luò)特征的網(wǎng)絡(luò)模型，如，ER隨機(jī)網(wǎng)絡(luò)模型[3]、WS小世界模型[4]和 BA 無標(biāo)度網(wǎng)絡(luò)模型[5]。這些反應(yīng)真實(shí)系統(tǒng)特征的網(wǎng)絡(luò)模型將有助于群智能算法問題中最優(yōu)種群結(jié)構(gòu)的設(shè)計(jì)[6]。SANTHOJI[7]提出設(shè)計(jì)群智能算法最優(yōu)種群結(jié)構(gòu)的方法論，其是以種群結(jié)構(gòu)具有較強(qiáng)的信息轉(zhuǎn)移能力、最少的邊(資源)和算法具有最優(yōu)的性能為目標(biāo)。同時(shí)，SANTHOJI以PSO算法為例，基于ER隨機(jī)網(wǎng)模型和NW小世界模型的演化機(jī)制研究了PSO問題最優(yōu)種群結(jié)構(gòu)。借鑒SANTHOJ設(shè)計(jì)PSO最優(yōu)結(jié)構(gòu)的方法論，基于ER隨機(jī)網(wǎng)絡(luò)模型演化機(jī)制，研究一種改進(jìn)蜂群算法(MABC)的最優(yōu)種群結(jié)構(gòu)，即以最小的資源(邊)，最大信息轉(zhuǎn)移能力(結(jié)構(gòu)熵)和最優(yōu)的MABC性能為目標(biāo)，設(shè)計(jì)最優(yōu)種群結(jié)構(gòu)。

1 網(wǎng)絡(luò)的特征度量

在對復(fù)雜網(wǎng)絡(luò)研究的過程中，學(xué)者們提出了一些概念和度量方法以表示網(wǎng)絡(luò)的結(jié)構(gòu)特征。

(1)度(k):節(jié)點(diǎn)i的度ki定義為與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目。

(2)度分布(P(k)):網(wǎng)絡(luò)度的分布情況用分布函數(shù)P(k)來描述。P(k)表示的是一個(gè)隨機(jī)選定的節(jié)點(diǎn)的度恰好為k的概率。pki表示微粒i具有度k的概率。

(3)平均度(＜k＞):網(wǎng)絡(luò)中所有節(jié)點(diǎn)i的度ki的平均值。

(4)結(jié)構(gòu)熵(E):熵表示系統(tǒng)存儲，處理和轉(zhuǎn)移信息的能力。在復(fù)雜網(wǎng)絡(luò)中，熵可以表示網(wǎng)絡(luò)結(jié)構(gòu)的異質(zhì)程度及網(wǎng)絡(luò)結(jié)構(gòu)轉(zhuǎn)移信息的能力。在復(fù)雜網(wǎng)絡(luò)里定義節(jié)點(diǎn)i的熵為:Ei=-pkilog2pki，則整個(gè)網(wǎng)絡(luò)的熵為:

2 ER隨機(jī)網(wǎng)絡(luò)模型

Erd?s和Rényi(ER)最早提出隨機(jī)網(wǎng)絡(luò)模型并進(jìn)行了深入研究，他們是用概率統(tǒng)計(jì)方法研究隨機(jī)圖統(tǒng)計(jì)特性的創(chuàng)始人。ER模型是基于一種“自然”的構(gòu)造方法:假設(shè)有n個(gè)節(jié)點(diǎn)，并假設(shè)每對節(jié)點(diǎn)之間相連的可能性都是常數(shù)0＜p＜1，這樣構(gòu)造出的網(wǎng)絡(luò)就是ER模型網(wǎng)絡(luò)。

圖1 不同概率p值的ER網(wǎng)絡(luò)模型Fig.1 ER network with different probability p

科學(xué)家們最初使用這種模型來解釋現(xiàn)實(shí)生活中的網(wǎng)絡(luò)。ER隨機(jī)網(wǎng)絡(luò)有一個(gè)重要特性，就是雖然節(jié)點(diǎn)之間的連接是隨機(jī)形成的，但最后產(chǎn)生的網(wǎng)絡(luò)的度分布是高度平等的，即大部分的節(jié)點(diǎn)的度都集中在某個(gè)特殊值附近，成鐘形的泊松分布規(guī)律。

圖2 ER網(wǎng)絡(luò)模型的度分布圖Fig.2 The degree distribution of ER netwrok

圖2中，橫坐標(biāo)k代表網(wǎng)絡(luò)的度，縱坐標(biāo)P(k)代表隨機(jī)取一節(jié)點(diǎn)度為k的概率。

3 改進(jìn)的蜜蜂群算法(MABC)

根據(jù)蜜蜂的交配行為和覓食行為，學(xué)者設(shè)計(jì)了蜜蜂群優(yōu)化算法[8-9]。其中文獻(xiàn)[9]根據(jù)蜜蜂的覓食行為設(shè)計(jì)出用于解決連續(xù)函數(shù)優(yōu)化問題蜂群算法(ABC)。ABC算法由三種蜂組成:引領(lǐng)蜂、跟隨蜂和偵察蜂。由于ABC算法采用比例的適應(yīng)值選擇策略，則易降低算法的種群多樣性和全局優(yōu)化性能，進(jìn)而導(dǎo)致算法停止進(jìn)化。針對這一問題，文獻(xiàn)[10]對其進(jìn)行改進(jìn)，不設(shè)置跟隨蜂，以使算法獲得更好的收斂效果。在MABC算法中，引領(lǐng)蜂按照式(1)進(jìn)行食物源開采:

其中，i表示第i個(gè)解(食物源)，k∈{1，2，…，N}(N表示種群規(guī)模)表示隨機(jī)選取的不同于i的解，j表示解的第j維向量(其是隨機(jī)選取的)。Φij是[-1，1]上的一個(gè)隨機(jī)數(shù)。

當(dāng)MABC算法搜索到的最好解在連續(xù)的limit次迭代內(nèi)未得到改善時(shí)，這個(gè)解(食物源)被放棄。同時(shí)，由偵察蜂通過式(2)隨機(jī)搜索產(chǎn)生一個(gè)新解作為解。

其中，i表示第i個(gè)解，xmin和xmax分別表示域的下限和上限。

3.1 改進(jìn)蜜蜂群算法步驟

Step 1 初始化，隨機(jī)產(chǎn)生N個(gè)解(引領(lǐng)蜂)作為食物源，并計(jì)算每個(gè)解的適應(yīng)值;

Step 2 依據(jù)式(1)，N個(gè)引領(lǐng)蜂進(jìn)行搜索產(chǎn)生新的N個(gè)解vi(i=1，…，N)，并計(jì)算其適應(yīng)值;

Step 3vi與xi的適應(yīng)值進(jìn)行比較，若vi的適應(yīng)值優(yōu)于xi，則用vi替換xi，將vi作為當(dāng)前最好解，否則保留xi;

Step 4 通過limit值判斷是否存在需要放棄的解，若存在，則依據(jù)式(2)產(chǎn)生新解，替代被放棄的解;

Step 5 比較N個(gè)解，保留最優(yōu)的作為全局最好解;

Step 6 迭代次數(shù)加1;

Step 7 判斷是否滿足終止條件，若滿足則輸出最優(yōu)結(jié)果，否則返回Step 2.

4 MABC的最優(yōu)種群結(jié)構(gòu)

在復(fù)雜網(wǎng)絡(luò)中，熵可以表示網(wǎng)絡(luò)結(jié)構(gòu)的異質(zhì)程度及網(wǎng)絡(luò)結(jié)構(gòu)信息轉(zhuǎn)移能力。當(dāng)結(jié)構(gòu)的熵值較小時(shí)，結(jié)構(gòu)轉(zhuǎn)移信息的能力較弱;當(dāng)結(jié)構(gòu)的熵值較大時(shí)，結(jié)構(gòu)轉(zhuǎn)移信息的能力較強(qiáng)。結(jié)構(gòu)中邊的數(shù)量(可以用結(jié)構(gòu)的平均度值來表示)可以表示求解函數(shù)優(yōu)化問題時(shí)所需花費(fèi)的成本代價(jià)。當(dāng)結(jié)構(gòu)邊的數(shù)量較少時(shí)，解決優(yōu)化問題所需的代價(jià)較小;而當(dāng)結(jié)構(gòu)邊的數(shù)量較大時(shí)，解決優(yōu)化問題所需的代價(jià)較大。算法性能表示了整個(gè)系統(tǒng)的功能。如果算法性能優(yōu)，則系統(tǒng)功能強(qiáng)，反之則不然。因此，評價(jià)算法最優(yōu)種群結(jié)構(gòu)的標(biāo)準(zhǔn)是:結(jié)構(gòu)熵、結(jié)構(gòu)的平均度(邊的數(shù)量)和算法的性能。獲得算法的最優(yōu)種群結(jié)構(gòu)需要最大化結(jié)構(gòu)熵、最小化結(jié)構(gòu)的平均度和最優(yōu)的算法性能。

基于ER隨機(jī)網(wǎng)絡(luò)模型的演化機(jī)制，以50維的Rosenbrock(收斂精度為1)函數(shù)為例，對MABC算法的最優(yōu)種群結(jié)構(gòu)進(jìn)行研究。

研究方法:對于有N個(gè)微粒的種群而言，共進(jìn)行次實(shí)驗(yàn)。第一次實(shí)驗(yàn)種群結(jié)構(gòu)邊的數(shù)量n=0條，第二次實(shí)驗(yàn)種群結(jié)構(gòu)邊的數(shù)量n=1條，第三次實(shí)驗(yàn)種群結(jié)構(gòu)邊的數(shù)量n=2條，依次類推，第次實(shí)驗(yàn)種群結(jié)構(gòu)邊的數(shù)量為條，即完全連接的結(jié)構(gòu)。

第i次實(shí)驗(yàn)執(zhí)行兩步:

(1)按照ER網(wǎng)絡(luò)模型演化機(jī)制以概率P=隨機(jī)連接每對節(jié)點(diǎn)，計(jì)算結(jié)構(gòu)的平均度和熵值，并將熵值歸一化，即H/Hmax;

(2)在最大迭代次數(shù)內(nèi)(MAXITER)運(yùn)行算法，計(jì)算算法的收斂率(算法達(dá)到函數(shù)收斂精度的次數(shù)與總共運(yùn)行次數(shù)的比值);

圖3 基于ER模型演化機(jī)制結(jié)構(gòu)平均度與熵值關(guān)系Fig.3 Relation between average degree and entropy of structure based on ER network evolution mechanism

圖4 基于ER模型演化機(jī)制結(jié)構(gòu)平均度和算法收斂率的關(guān)系Fig.4 Relation between average degree of structure based on ER network evolution mechanism and the rate of convergence of MABC algorithm

由圖3可知，當(dāng)平均度為0時(shí)，結(jié)構(gòu)熵值為0，表明結(jié)構(gòu)無信息轉(zhuǎn)移能力。隨著結(jié)構(gòu)平均度的增大，結(jié)構(gòu)的信息轉(zhuǎn)移能力增加且在平均度大約為2時(shí)達(dá)到最大，此時(shí)結(jié)構(gòu)的異質(zhì)程度達(dá)到最大。而在平均度為2-7的區(qū)間內(nèi)，雖然熵值有所下降，但是下降幅度較小，幾乎接近最大熵值。在平均度大約為25度左右時(shí)，熵值達(dá)到谷底。此后，熵值開始逐漸增加，在平均度大約為48時(shí)再次達(dá)到最大。然而在平均度為49時(shí)，熵值突然降到最低值0.結(jié)構(gòu)的信息轉(zhuǎn)移能力正比例于結(jié)構(gòu)的熵值。從圖4可知，當(dāng)平均度為0時(shí)，算法收斂率SR=0.隨著平均度的增大，算法收斂率SR迅速增長，當(dāng)平均度大約為6-7時(shí)，收斂率SR達(dá)到最大值。此后直到平均度為50時(shí)，算法始終保持相同的收斂率。當(dāng)平均度為0時(shí)，由孤立節(jié)點(diǎn)組成的結(jié)構(gòu)，雖然所用資源最少，但微粒間無任何信息的傳遞與共享，導(dǎo)致算法無法搜索到全局最優(yōu)解。隨著一些邊的加入，結(jié)構(gòu)轉(zhuǎn)移信息的能力有所增長，各別微粒間存在信息的傳遞與共享，收斂率SR開始增加，當(dāng)平均度達(dá)到大約6-7度時(shí)，結(jié)構(gòu)信息轉(zhuǎn)移的能力幾乎達(dá)到最大，而算法收斂率SR也達(dá)到了最大值。因此，基于ER隨機(jī)網(wǎng)絡(luò)模型演化機(jī)制以概率(結(jié)構(gòu)平均度為7)進(jìn)行結(jié)構(gòu)演化所獲得的結(jié)構(gòu)為MABC的最優(yōu)種群結(jié)構(gòu)。

5 仿真實(shí)驗(yàn)

為了驗(yàn)證上述最優(yōu)種群結(jié)構(gòu)的性能，選擇了4個(gè)經(jīng)典函數(shù)對在最優(yōu)種群結(jié)構(gòu)和完全種群結(jié)構(gòu)下算法性能進(jìn)行了評價(jià)。實(shí)驗(yàn)環(huán)境為種群規(guī)模N=50，所有函數(shù)維數(shù)n=50.算法停止準(zhǔn)則為最大迭代次數(shù)，即MAXITER=6 000.實(shí)驗(yàn)數(shù)據(jù)均源于算法獨(dú)立運(yùn)行20次的平均抽樣。

(1)Rosenbrock函數(shù)，單峰函數(shù)，在xi=1達(dá)到最小值0.

(2)sphere函數(shù)，單峰函數(shù)，在xi=0達(dá)到最小值0.

(3)Schwefel Problem 2.26函數(shù)，多峰函數(shù)，在xi=(420.968 7，…，420.968 7)達(dá)到最小值 -418.982 9n.

(4)Griewank函數(shù)，多峰函數(shù)，在xi=0大到最小值0.

表1 在最優(yōu)結(jié)構(gòu)平均度7和完全連接結(jié)構(gòu)平均度49下MABC算法性能Tab.1 Performances of MABC in the optimal structure with average degree 7and full-connected structure with average degree 49

從表1可知，基于ER隨機(jī)網(wǎng)絡(luò)模型的演化機(jī)制，在結(jié)構(gòu)平均度為7和49時(shí)算法具有幾乎相同的性能，而平均度為7時(shí)結(jié)構(gòu)中邊的數(shù)量遠(yuǎn)小于平均度為49時(shí)，即僅需要較少的資源就可以使MABC算法獲得好的性能，且此時(shí)的結(jié)構(gòu)具有較強(qiáng)的信息轉(zhuǎn)移能力，即較大的結(jié)構(gòu)熵值。仿真實(shí)驗(yàn)再次表明了基于ER隨機(jī)網(wǎng)絡(luò)模型的演化機(jī)制以概率P=(結(jié)構(gòu)平均度為7)進(jìn)行結(jié)構(gòu)演化所獲得的結(jié)構(gòu)為MABC算法的最優(yōu)種群結(jié)構(gòu)。

6 結(jié)論

本文采用SANTHOJI提出的方法論研究了一種改進(jìn)ABC算法(MABC)的最優(yōu)種群結(jié)構(gòu)。研究表明基于ER隨機(jī)網(wǎng)絡(luò)模型演化機(jī)制以概率P=(結(jié)構(gòu)平均度為7)進(jìn)行結(jié)構(gòu)演化可獲得MABC算法的最優(yōu)種群結(jié)構(gòu)。也就是說，當(dāng)結(jié)構(gòu)平均度為7時(shí)，結(jié)構(gòu)具有較強(qiáng)的信息轉(zhuǎn)移能力，同時(shí)算法可以獲得較好的性能。

[1]JEONG H，TONLBOR B，AIBERT R，et al.The1argescale organization of metabolic networks[J].Nature，2000，407:651-654.

[2]JEONG H，MASON S，BARABASI A L，et al.Lethality and centrality in Protein networks[J].Nature，2001，411:41-42.

[3]ERDOS P，RENYI A.On the evolution of random graphs[J].Publications of the Mathematical Institute of the Hungarian Academy of sciences，1960，5:17-61.

[4]WATTS D J，STROGATZ S H.Collective dynamics of‘small-world’networks[J].Nature，1998，393:440-442.

[5]BARABASI A L，ALBERT R.Emergence of scaling in random networks[J].Science，1999，286:509-512.

[6]穆華平，曾建潮，焦長義.基于小世界鄰域結(jié)構(gòu)的微粒群算法研究[J].太原科技大學(xué)學(xué)報(bào)，2009，30(1):7-11.

[7]SANTHOJI KATARE，DAVID H WEST.Optimal Complex Networks Spontaneously Emerge When Information Transfer is Maximized at Least Expense:A Design Perspective[J].Nature Physics，2006，11:26-35.

[8]PHAM D T，KOG E，GHANBARZADEH A，et al.The Bees Algorithm-A Novel Tool for Complex Optimisation Problems[C]//IPROMS 2006 Proceeding 2nd InternationalVirtual Conference on Intelligent Production Machines and Systems.Oxford，England:Elsevier，2006:231-235.

[9]KARABOGA D.An Idea Based on Honey Bee Swarm for Numerical Optimization[R].Tvrkey:Rciyes University，Engineering Faculty，Computer Engineering Department，2005.

[10]徐衛(wèi)濱.無選擇策略的改進(jìn)蜜蜂群算法[J].太原科技大學(xué)學(xué)報(bào)，2011，32(5):343-346.