臺亞麗，曾建潮，莫思敏

(太原科技大學(xué)復(fù)雜系統(tǒng)與計(jì)算智能實(shí)驗(yàn)室，太原 030024)

為提高微粒群算法(PSO)[1]的性能，文獻(xiàn)[2]提出了一種基于擬態(tài)物理學(xué)引斥力思想的擴(kuò)展微粒群算法(EPSO)[2]。該算法重新構(gòu)造了微粒間的信息交互和作用方式，使每個(gè)微粒獲得更加全面的的搜索信息，因此其具有較快的收斂速度和較高的種群多樣性，進(jìn)而提高了算法的全局性能。但是，對于一些測試函數(shù)，EPSO算法具有較弱的局部搜索能力。為了提高EPSO的算法性能，文獻(xiàn)[3]構(gòu)造了不同的無向自組織種群拓?fù)浣Y(jié)構(gòu)[3]。然而在無向自組織種群結(jié)構(gòu)中，相鄰微粒之間的影響是對等的，這樣就會存在被動(dòng)連接的微粒被動(dòng)地做全局搜索，從而減弱了EPSO算法的局部搜索能力。

EPSO算法是通過模擬生物社會群體行為而構(gòu)造的一個(gè)新穎的算法。如果使EPSO算法不僅模擬生物社會群體行為，而且模擬生物社會網(wǎng)絡(luò)結(jié)構(gòu)，將能更加真實(shí)模擬生物社會，涌現(xiàn)更多的復(fù)雜行為，進(jìn)而提高EPSO算法的性能。而在自然界和社會中存在大量的有向網(wǎng)絡(luò)，它們廣泛存在于社會、信息、科技、生物等領(lǐng)域，因此將有向的種群結(jié)構(gòu)作用于EPSO上，使得微粒之間的交互作用關(guān)系體現(xiàn)出有向性，對提高EPSO算法性能是非常重要和必要的。

目前，基于有向種群結(jié)構(gòu)的群智能算法研究較少。這些研究主要集中在：(1)理論上對有向網(wǎng)絡(luò)中節(jié)點(diǎn)的分布問題和基本理論進(jìn)行了綜述和拓展，為我們對有向網(wǎng)絡(luò)的研究提供了堅(jiān)實(shí)的理論基礎(chǔ)[4-5]；(2)為體現(xiàn)有向網(wǎng)絡(luò)中粒子之間影響的不平衡性構(gòu)造了有向加權(quán)函數(shù)模型[6]；(3)提出動(dòng)態(tài)有向拓?fù)浣Y(jié)構(gòu)，模擬現(xiàn)實(shí)復(fù)雜網(wǎng)絡(luò)中增長有向網(wǎng)絡(luò)演化模型構(gòu)造有向種群結(jié)構(gòu)，并對有向網(wǎng)絡(luò)演化過程中的度分布進(jìn)行分析[7-8]，以及構(gòu)造鄰域動(dòng)態(tài)變化的有向拓?fù)浣Y(jié)構(gòu)[9-10]，以提高微粒群在空間上的尋優(yōu)能力。

由于EPSO算法是最近提出的一個(gè)新穎的算法，因此尚無文獻(xiàn)研究EPSO算法的有向種群結(jié)構(gòu)。本文針對EPSO算法的特點(diǎn)以及其在無向自組織種群結(jié)構(gòu)研究中存在的不足，設(shè)計(jì)了各種靜態(tài)有向種群結(jié)構(gòu)，研究有向靜態(tài)結(jié)構(gòu)的特征度量對EPSO算法性能的影響，以獲得有利于EPSO算法進(jìn)化、提高EPSO算法性能的有向種群結(jié)構(gòu)及特征度量。

1 EPSO算法

擴(kuò)展微粒群算法(EPSO)是在標(biāo)準(zhǔn)微粒群算法(PSO)的基礎(chǔ)上，將微粒僅受自身歷史最好和種群歷史最好的影響，擴(kuò)展為微粒受種群中所有微粒歷史最好的影響。并根據(jù)擬態(tài)物理學(xué)中引斥力思想，重新構(gòu)造了微粒間的作用方式，將PSO中微粒僅受其他微粒吸引的作用方式，擴(kuò)展為微粒受比自身適應(yīng)值優(yōu)的微粒的吸引，同時(shí)受比自身適應(yīng)值劣的微粒的排斥，在引斥力的合力的作用下進(jìn)行速度和位置的更新[2]。

微粒間引斥力規(guī)則定義為：

微粒j吸引微粒i：pjk(t)-xik(t)，集合B(i)存放歷史最優(yōu)適應(yīng)值比微粒i適應(yīng)值優(yōu)的微粒。

微粒j排斥微粒i：-(pjk(t)-xik(t))，集合W(i)存放歷史最優(yōu)適應(yīng)值比微粒i適應(yīng)值劣的微粒。

其中：集合B(i)和W(i)的元素個(gè)數(shù)分別被表示為|B(i)|和|W(i)|.EPSO的速度和位置更新方程為：

(1)

xik(t+1)=xik(t)+vik(t+1)

(2)

其中：Pi={pi1,pi2,…,pin}代表微粒i所經(jīng)歷過的最好位置，Xi(t)={xi1(t),xi2(t),…,xin(t)}和Vi(t)={vi1(t),vi2(t),…,vin(t)}分別是第t代微粒i的位置和速度矢量，w為慣性權(quán)重，用來平衡算法的全局搜索和局部搜索，在區(qū)間[0，1]上取值，cj(j=1，…，N)是加速系數(shù)，rj是在[0，1]均勻分布的相互獨(dú)立的隨機(jī)數(shù)。

2 靜態(tài)有向種群結(jié)構(gòu)的特征度量對EPSO算法性能的影響

從收斂條件可知加速系數(shù)c和微粒的鄰居數(shù)量對微粒的收斂性起到重要的作用，因此EPSO算法性能受節(jié)點(diǎn)度和結(jié)構(gòu)的度分布的影響較大[3]。而在有向種群結(jié)構(gòu)中，考慮到連接有向邊的兩節(jié)點(diǎn)的受力情況不同，因此有向結(jié)構(gòu)中節(jié)點(diǎn)的出度和入度的變化是影響信息傳播和EPSO算法性能的重要因素。其次，隨著EPSO算法的進(jìn)化，微粒的適應(yīng)值不斷地發(fā)生變化，連接兩微粒的有向邊可能無助于微粒的進(jìn)化，需要重新選擇對象建立有向邊，因此在建立有向種群結(jié)構(gòu)中應(yīng)考慮適應(yīng)值對算法性能的影響。

2.1 節(jié)點(diǎn)出度值對算法性能的影響

在有向結(jié)構(gòu)中，有向邊以節(jié)點(diǎn)u為起點(diǎn)的邊的數(shù)目稱為u的出度，以節(jié)點(diǎn)u為終點(diǎn)的邊的數(shù)目稱為u的入度。

為了研究有向種群結(jié)構(gòu)中節(jié)點(diǎn)的出度對EPSO算法性能的影響，本節(jié)在環(huán)形有向結(jié)構(gòu)(如圖1(a))的基礎(chǔ)上分別對結(jié)構(gòu)中的每個(gè)節(jié)點(diǎn)i引kout條出度邊，這些邊分別指向編號為i+2，i+3，…，i+kout-1，i+kout的節(jié)點(diǎn)(如圖1(b))，通過調(diào)整kout值來改變節(jié)點(diǎn)i的出度值。

實(shí)驗(yàn)環(huán)境為：種群規(guī)模與函數(shù)維數(shù)相等，即N=n=30，慣性權(quán)重w從0.9到0.4線性遞減，最大進(jìn)化代數(shù)為20 000.表1記錄了算法獨(dú)立運(yùn)行30次各個(gè)測試函數(shù)的平均值和方差。

從表1可以看出：(1)節(jié)點(diǎn)出度較小時(shí)的算法性能優(yōu)于出度較大時(shí)的算法性能；(2)對于全局最優(yōu)點(diǎn)在(1，1…，1)點(diǎn)的函數(shù)，有向結(jié)構(gòu)中節(jié)點(diǎn)的出度值較小，且加速系數(shù)c值也較小時(shí)，EPSO算法的性能較優(yōu)；(3)對于全局最優(yōu)點(diǎn)在(0，0…，0)點(diǎn)的函數(shù)，當(dāng)有向結(jié)構(gòu)中節(jié)點(diǎn)的出度值較小，加速系數(shù)c值較大時(shí)，EPSO算法的性能較優(yōu)；(4)對于所有的測試函數(shù)，在節(jié)點(diǎn)的出度較大(kout>5)的情況下，c值較大時(shí)的算法性能優(yōu)于c值較小時(shí)的算法性能。

在環(huán)形有向結(jié)構(gòu)中，當(dāng)節(jié)點(diǎn)的出度較小時(shí)，每個(gè)微粒受相鄰較少微粒的作用，在較小的c值下，微粒在每一維上所受的合力較小，有效提高了EPSO算法的局部搜索能力，當(dāng)c值較大時(shí)，微粒所受的合力較大， 算法具有較強(qiáng)的全局搜索能力。 當(dāng)節(jié)點(diǎn)的出度增加時(shí)，每個(gè)微粒受到較多微粒的作用，在較小的c值下，出度值大的節(jié)點(diǎn)對應(yīng)的微粒僅在很小的鄰域內(nèi)進(jìn)行搜索，因而影響算法的收斂速度，而在較大的c值下，微粒受到較大的合力作用，以相對較大的速度進(jìn)行全局搜索，算法的全局搜索能力較強(qiáng)。

表1 環(huán)形有向結(jié)構(gòu)不同出度下的EPSO性能Tab.1 Performances of EPSO at the ring-like directed structure with different outdegrees

2.2 節(jié)點(diǎn)入度值與適應(yīng)值對算法性能的影響

(1)理論上，隨著EPSO算法的進(jìn)化，當(dāng)連接有向邊的微粒的適應(yīng)值發(fā)生改變時(shí)，微粒都希望以較大的概率與適應(yīng)值較好的微粒相連接，以受到群體中適應(yīng)值較好微粒的力的作用。因此本節(jié)研究在初始結(jié)構(gòu)是環(huán)形的有向結(jié)構(gòu)中，節(jié)點(diǎn)的出度值保持不變，通過改變適應(yīng)值較優(yōu)節(jié)點(diǎn)的入度值來研究入度值與適應(yīng)值對算法性能的影響。實(shí)驗(yàn)環(huán)境為：種群規(guī)模N=10，函數(shù)維數(shù)n=30，w從0.9到0.4線性遞減，最大進(jìn)化代數(shù)為2 000.圖2以Sphere函數(shù)為例記錄了算法運(yùn)行過程中十個(gè)節(jié)點(diǎn)向最優(yōu)值靠近的情況。圖3則記錄了以Rosenbrock函數(shù)為例，種群規(guī)模與函數(shù)維數(shù)相等，即N=n=30，最大進(jìn)化代數(shù)為20 000時(shí)與EPSO算法的微粒平均適應(yīng)值的變化對比。

注：點(diǎn)所對應(yīng)的迭代次數(shù)為橫坐標(biāo)刻度的20倍圖2 節(jié)點(diǎn)出度不變而較優(yōu)節(jié)點(diǎn)入度增加時(shí)微粒適應(yīng)值的變化Fig.2 Fitness evolution in directed structure when outdegree of nodes is fixed，and indegree of the better particles increases

注：點(diǎn)所對應(yīng)的迭代次數(shù)為橫坐標(biāo)刻度的200倍圖3 出度不變較優(yōu)節(jié)點(diǎn)入度增加與EPSO平均適應(yīng)值比較Fig.3 Comparison of EPSO average fitness evolution indirected structure when outdegree is fixed, and indegreeof the better particles increases

從圖中可看出，當(dāng)種群中節(jié)點(diǎn)的出度值不變而適應(yīng)值好的節(jié)點(diǎn)的入度值增加時(shí)，微粒都以較快的速度向最優(yōu)值聚集，并且相對于EPSO算法，其平均動(dòng)態(tài)性能較好。這是由于在有向種群結(jié)構(gòu)中，有向邊起點(diǎn)微粒受終點(diǎn)微粒的力作用，而終點(diǎn)微粒不受起點(diǎn)微粒的力作用，因此隨著算法進(jìn)化，微粒斷開與適應(yīng)值變差的微粒的連接，受到適應(yīng)值好的微粒的力的作用時(shí)，能大大提高EPSO算法的性能。

(2)為了研究有向結(jié)構(gòu)中節(jié)點(diǎn)的適應(yīng)值對EPSO算法性能的影響，構(gòu)建星形的特殊有向結(jié)構(gòu)如圖4.以10個(gè)微粒(P0，P1，…，P9)的種群規(guī)模為例，其中微粒P1至P9僅與P0連接，且方向都指向P0，選擇30維的Sphere函數(shù)進(jìn)行實(shí)驗(yàn)，w從0.9到0.4線性遞減，最大迭代次數(shù)均為500.

圖4 星形有向結(jié)構(gòu)(中心點(diǎn)為P0)Fig.4 Star-like directed structure (center point is P0)

(a)首先研究當(dāng)星形結(jié)構(gòu)中心點(diǎn)微粒P0不固定時(shí)，十個(gè)微粒的適應(yīng)值的變化情況。由圖5可以看出，在星形有向結(jié)構(gòu)中，當(dāng)中心點(diǎn)微粒不固定時(shí)，種群呈現(xiàn)出非常好的多樣性，但是群體微粒的聚集性較差，所以該結(jié)構(gòu)下EPSO算法的具有較強(qiáng)的全局搜索能力，但是局部搜索能力較弱。

注：點(diǎn)所對應(yīng)的迭代次數(shù)為橫坐標(biāo)刻度的10倍圖5 星形有向結(jié)構(gòu)中P0不固定時(shí)微粒適應(yīng)值的變化Fig.5 Fitness evolution in the star-like directed structurewhen P0 is not fixed

(b)將中心點(diǎn)微粒P0固定在全局最優(yōu)點(diǎn)(0，0，…，0)時(shí)，其余微粒的適應(yīng)值的變化情況。由圖6可以看出，中心點(diǎn)微粒P0固定在最優(yōu)點(diǎn)時(shí)微粒向最優(yōu)值靠近的速度明顯快于不固定時(shí)的結(jié)構(gòu)，在該結(jié)構(gòu)下其余九個(gè)微粒迅速地向微粒P0運(yùn)動(dòng)，并都聚集在微粒P0的位置上，算法具有較快的信息傳播能力，因此該結(jié)構(gòu)下EPSO算法具有較強(qiáng)的局部搜索能力。

注：點(diǎn)所對應(yīng)的迭代次數(shù)為橫坐標(biāo)刻度的10倍圖6 星形有向結(jié)構(gòu)中P0固定在最優(yōu)點(diǎn)時(shí)微粒適應(yīng)值變化Fig.6 Fitness evolution in the star-like directed structurewhen P0 is fixed in the optimal position

(c)當(dāng)適應(yīng)值最差的微粒在星形有向結(jié)構(gòu)P0位置時(shí)，由圖7可看出，該結(jié)構(gòu)下微粒的適應(yīng)值變化情況與函數(shù)最優(yōu)值不固定在中心點(diǎn)時(shí)情況相近，因此該結(jié)構(gòu)具有較強(qiáng)的全局搜索能力，同時(shí)局部搜索能力較弱。

3 不同有向結(jié)構(gòu)作用下的EPSO性能分析

針對不同的有向拓?fù)浣Y(jié)構(gòu)，即環(huán)形有向結(jié)構(gòu)、星形有向結(jié)構(gòu)，研究EPSO的算法性能。實(shí)驗(yàn)環(huán)境：種群規(guī)模與函數(shù)維數(shù)相等，即N=n=30，w從0.9到0.4線性遞減，最大進(jìn)化代數(shù)為20 000.對于環(huán)形有向結(jié)構(gòu)，根據(jù)2.1結(jié)論出度設(shè)為2，且全局最優(yōu)點(diǎn)在(1，1…，1)點(diǎn)的函數(shù)設(shè)置c=1.5，而全局最優(yōu)點(diǎn)在(0，0…，0)點(diǎn)的函數(shù)c=500.星形有向結(jié)構(gòu)中設(shè)置c=1.5.表2記錄了算法獨(dú)立運(yùn)行30次的平均值和方差。

注：點(diǎn)所對應(yīng)的迭代次數(shù)為橫坐標(biāo)刻度的10倍圖7 星形有向結(jié)構(gòu)中P0固定在最差點(diǎn)時(shí)微粒適應(yīng)值變化Fig.7 Fitness evolution in the star-like directed structurewhen P0 is fixed in the worst position

表2 EPSO作用在不同有向結(jié)構(gòu)下的性能比較Tab.2 Performance comparison of EPSO with different directed structures

由表2可知，對于大多數(shù)函數(shù)而言，作用在有向環(huán)形結(jié)構(gòu)上的EPSO算法性能較好。其原因可能是：有向環(huán)形結(jié)構(gòu)較之其他結(jié)構(gòu)具有較好的連通性，因此各節(jié)點(diǎn)的信息在環(huán)形結(jié)構(gòu)中傳播的較快；對EPSO而言，有向環(huán)形結(jié)構(gòu)具有較少的鄰居數(shù)量，因此在較小的加速系數(shù)c值下，算法具有較強(qiáng)的局部尋優(yōu)能力。

4 總結(jié)

EPSO是一個(gè)新提出的算法。在EPSO算法中微粒之間的作用機(jī)制完全不同于在PSO算法下微粒之間的作用機(jī)制。EPSO算法具有較好的全局搜索能力，但是其局部尋優(yōu)能力卻非常弱。因此將EPSO算法作用于有向的種群結(jié)構(gòu)，通過有向種群結(jié)構(gòu)來提高算法的局部尋優(yōu)能力。本文研究了有向環(huán)形結(jié)構(gòu)、有向環(huán)基礎(chǔ)上不同出度的有向結(jié)構(gòu)以及中心點(diǎn)適應(yīng)值不同(隨機(jī)適應(yīng)值、適應(yīng)值最優(yōu)、適應(yīng)值最差)的星形有向結(jié)構(gòu)的拓?fù)涮卣鲗PSO算法性能的影響，得出了以下結(jié)論：(1)在有向種群結(jié)構(gòu)中，節(jié)點(diǎn)的出度是影響EPSO算法性能的重要因素。節(jié)點(diǎn)的出度較小時(shí)的EPSO算法局部尋優(yōu)能力優(yōu)于出度較大時(shí)的EPSO算法。因?yàn)楫?dāng)節(jié)點(diǎn)的出度較小時(shí)，每個(gè)微粒受相鄰較少微粒的作用，在較小的c值下，微粒在每一維上所受的合力較小，EPSO算法局部搜索能力較強(qiáng)。而隨著節(jié)點(diǎn)出度值的增加，EPSO算法的全局尋優(yōu)能力變強(qiáng)，而局部尋優(yōu)能力變差。這是因?yàn)槊總€(gè)微粒所受相鄰較多微粒的作用，具有較快的搜索速度，而不能精細(xì)的搜索某一區(qū)域。在出度值較大的情況下，c值較大時(shí)算法性能優(yōu)于c值較小時(shí)的算法性能。因?yàn)楫?dāng)c值較大時(shí)微粒受到較大的合力作用，算法的全局搜索能力較強(qiáng)，而在較小的c值下，微粒僅能在其很小的鄰域附近進(jìn)行搜索，進(jìn)而影響算法性能。(2)適應(yīng)值的變化是影響EPSO算法的又一重要因素。當(dāng)適應(yīng)值較優(yōu)的節(jié)點(diǎn)的入度增加時(shí)，與其連接的節(jié)點(diǎn)對應(yīng)的微粒受到適應(yīng)值較優(yōu)微粒的力的作用，算法最優(yōu)信息的傳播速度較快。因此增加種群中適應(yīng)值較好的微粒的入度值，能有效提高EPSO的算法性能。在特殊結(jié)構(gòu)星形有向結(jié)構(gòu)中，當(dāng)最優(yōu)適應(yīng)值固定在中心位置時(shí)，其余微粒均受到最優(yōu)適應(yīng)值微粒的力的作用，以較快的速度聚集到最優(yōu)位置附近，有效提高了EPSO算法的局部搜索能力。(3)有向環(huán)形結(jié)構(gòu)較之其他有向結(jié)構(gòu)具有較好的連通性，因此各節(jié)點(diǎn)的信息在環(huán)形結(jié)構(gòu)中傳播的較快；對EPSO而言，有向環(huán)形結(jié)構(gòu)具有較少的鄰居數(shù)量，因此在較小的加速系數(shù)c值下，算法具有較強(qiáng)的局部尋優(yōu)能力。

參考文獻(xiàn)：

[1] KENNEDY J，EBERHART R C.Particle Swarm Optimization[C]∥Proceedings of the IEEE International Conference on Neural Networks，Perth，Australia.Piscataway，NJ：IEEE Press，1995，IV：1942-1948.

[2] 莫思敏，曾建潮，謝麗萍.擴(kuò)展的微粒群算法[J].控制理論與應(yīng)用，2012，29(6)：811-812.

[3] 莫思敏，曾建潮.基于群體交互自組織種群結(jié)構(gòu)的擴(kuò)展微粒群算法研究[D].蘭州：蘭州理工大學(xué)，2012.

[4] 荊巧鋒，程志謙.有向網(wǎng)絡(luò)中節(jié)點(diǎn)分布的研究[J].洛陽工業(yè)高等專科學(xué)校學(xué)報(bào)，2007，17(5)：31-35.

[5] 黃紅球.對有向網(wǎng)絡(luò)理論及應(yīng)用的一些研究[D].武漢：武漢理工大學(xué)，2007.

[6] 方峻，唐普英，任誠.一種基于加權(quán)有向拓?fù)涞母倪M(jìn)粒子群算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16(8)：62-65.

[7] 尹禮壽，趙治榮.有向復(fù)雜網(wǎng)絡(luò)中的度分布[J].運(yùn)城學(xué)院學(xué)報(bào)，2009，27(2)：19-21.

[8] 馬秀娟.基于BA 無標(biāo)度的復(fù)雜有向網(wǎng)絡(luò)演化模型[J].電子設(shè)計(jì)工程，2012，20(16)：11-13.

[9] 姚燦中，楊建梅.一種基于有向動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涞牧Ｗ尤簝?yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(27)：15-17.

[10] MOHAIS A S，WARD C，POSTHOFF C.Randomized directed neighborhoods with edge migration in particle swarm optimization[C]∥Proceeding of the IEEE Congress on Evolutionary Computation，USA：IEEE Press，2004(1)：548-555.