基于靜態(tài)有向種群結(jié)構的EPSO算法研究

臺亞麗，曾建潮，莫思敏

(太原科技大學復雜系統(tǒng)與計算智能實驗室，太原 030024)

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

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

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

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

1 EPSO算法

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

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

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

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

其中：集合B(i)和W(i)的元素個數(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為慣性權重，用來平衡算法的全局搜索和局部搜索，在區(qū)間[0，1]上取值，cj(j=1，…，N)是加速系數(shù)，rj是在[0，1]均勻分布的相互獨立的隨機數(shù)。

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

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

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

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

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

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

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

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

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

2.2 節(jié)點入度值與適應值對算法性能的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)

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

參考文獻：

[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] 莫思敏，曾建潮，謝麗萍.擴展的微粒群算法[J].控制理論與應用，2012，29(6)：811-812.

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

[4] 荊巧鋒，程志謙.有向網(wǎng)絡中節(jié)點分布的研究[J].洛陽工業(yè)高等?？茖W校學報，2007，17(5)：31-35.

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

[6] 方峻，唐普英，任誠.一種基于加權有向拓撲的改進粒子群算法[J].計算機技術與發(fā)展，2006，16(8)：62-65.

[7] 尹禮壽，趙治榮.有向復雜網(wǎng)絡中的度分布[J].運城學院學報，2009，27(2)：19-21.

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

[9] 姚燦中，楊建梅.一種基于有向動態(tài)網(wǎng)絡拓撲的粒子群優(yōu)化算法[J].計算機工程與應用，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.