基于有向加權(quán)復(fù)雜網(wǎng)絡(luò)的自適應(yīng)粒子群算法

黃 珍，曹曉麗

(蘭州文理學(xué)院數(shù)字媒體學(xué)院，甘肅 蘭州 730000)

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是一種基于群體智能的隨機(jī)優(yōu)化算法［1］.該算法類(lèi)似于鳥(niǎo)群覓食行為，通過(guò)種群內(nèi)部信息共享和個(gè)體間相互協(xié)作來(lái)搜索得到問(wèn)題的最優(yōu)解.鑒于算法具有容易實(shí)現(xiàn)、計(jì)算速度快、可以并行處理等優(yōu)點(diǎn)，粒子群優(yōu)化算法在神經(jīng)網(wǎng)絡(luò)訓(xùn)練、函數(shù)極值估計(jì)、人臉檢測(cè)與識(shí)別等領(lǐng)域已經(jīng)得到成功的應(yīng)用［2-4］.

在高維空間尋優(yōu)迭代過(guò)程中，標(biāo)準(zhǔn)粒子群優(yōu)化算法存在后期收斂速度慢和易陷入局部最優(yōu)的問(wèn)題，目前已經(jīng)有很多學(xué)者對(duì)其進(jìn)行改進(jìn)，如文獻(xiàn)［5］利用不同鄰域結(jié)構(gòu)的粒子群優(yōu)化算法進(jìn)行函數(shù)極值估計(jì)，在一定程度上提高了粒子尋優(yōu)性能.然而，不同問(wèn)題粒子群的拓?fù)浣Y(jié)構(gòu)也不一樣，算法開(kāi)始很難選擇最佳的粒子群拓?fù)浣Y(jié)構(gòu)，因此該算法的適應(yīng)性較差.文獻(xiàn)［6］利用無(wú)標(biāo)度網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的一些特性來(lái)優(yōu)化粒子群算法，使其在高維空間尋優(yōu)能力上有了進(jìn)一步的提高，但無(wú)標(biāo)度網(wǎng)絡(luò)并不一定是最優(yōu)的拓?fù)浣Y(jié)構(gòu).文獻(xiàn)［7］提出了一種自適應(yīng)的多向?qū)W習(xí)粒子群優(yōu)化算法，群體中的每個(gè)粒子不僅比較自身最優(yōu)解和整個(gè)群體的最優(yōu)解，同時(shí)還隨機(jī)和其他同維度的粒子最優(yōu)解相比較，從而完成自身速度的更新.該算法在解決高維優(yōu)化問(wèn)題時(shí)有了進(jìn)一步的提高，但沒(méi)有考慮粒子尋優(yōu)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，不同的鄰域網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)粒子群的最終尋優(yōu)結(jié)果有很大影響.

全局耦合網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)之間都有邊連接［8］.作為基本粒子群的網(wǎng)絡(luò)鄰域結(jié)構(gòu)，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)(位置)都將與網(wǎng)絡(luò)中的其他所有節(jié)點(diǎn)(位置)相比較，從而選擇最優(yōu)的粒子進(jìn)行學(xué)習(xí).在所有網(wǎng)絡(luò)拓?fù)渲?，具有相同?jié)點(diǎn)數(shù)的全局耦合網(wǎng)絡(luò)具有最大的集聚系數(shù)(C =l)和最小的平均路徑長(zhǎng)度(L =1)［9］.然而在高維空間解中，傳統(tǒng)PSO 更容易陷入局部最優(yōu).在全局耦合網(wǎng)絡(luò)鄰域結(jié)構(gòu)中，粒子尋優(yōu)能力差以及尋優(yōu)方式呆板，小世界網(wǎng)絡(luò)模型鄰域結(jié)構(gòu)作為PSO 尋優(yōu)鄰域初始化有較好的表現(xiàn).本文提出利用小世界網(wǎng)絡(luò)模型鄰域結(jié)構(gòu)對(duì)PSO 進(jìn)行初始化，由于其鄰域結(jié)構(gòu)中每個(gè)粒子僅僅與網(wǎng)絡(luò)中的鄰居位置進(jìn)行比較，所以算法的收斂速度將進(jìn)一步提高，網(wǎng)絡(luò)中的每個(gè)粒子都能保持尋找最優(yōu)的解(即粒子群中解的多樣性)，在可接受的誤差范圍內(nèi)，小世界網(wǎng)絡(luò)作為粒子群的鄰域結(jié)構(gòu)具有較好的優(yōu)化效果.尤其在解決高維復(fù)雜函數(shù)問(wèn)題時(shí)，小世界網(wǎng)絡(luò)鄰域結(jié)構(gòu)效果更為明顯.PSO 算法最終收斂時(shí)，其粒子鄰域結(jié)構(gòu)的節(jié)點(diǎn)入度服從冪律分布［10］，因此可以把無(wú)標(biāo)度網(wǎng)絡(luò)作為粒子最終收斂時(shí)的粒子鄰域結(jié)構(gòu).基于以上內(nèi)容，本文提出小世界網(wǎng)絡(luò)模型向無(wú)標(biāo)度網(wǎng)絡(luò)模型進(jìn)化的動(dòng)態(tài)粒子鄰域拓?fù)浣Y(jié)構(gòu).

本文將復(fù)雜網(wǎng)絡(luò)中小世界網(wǎng)絡(luò)模型和無(wú)標(biāo)度網(wǎng)絡(luò)模型的網(wǎng)絡(luò)特性融入到粒子群優(yōu)化算法中，提出有向加權(quán)復(fù)雜網(wǎng)絡(luò)的粒子群優(yōu)化算法(Directed Weighted Complex Network Particle Swarm Optimization，DWCN -PSO).仿真結(jié)果表明，DWCN -PSO 算法尤其在高維空間尋優(yōu)時(shí)，性能及收斂速度都比標(biāo)準(zhǔn)PSO 有所提高.

1 基本粒子群優(yōu)化算法

粒子群優(yōu)化算法最初是從社會(huì)行為的模擬發(fā)展起來(lái)的具有全局搜索能力的智能群體算法［11］.在一個(gè)n 維的目標(biāo)搜索空間中，粒子群被初始化分布在空間中，每個(gè)粒子所在空間的位置表示一個(gè)具體問(wèn)題的解，系統(tǒng)中的每個(gè)粒子在目標(biāo)搜索空間中尋找最優(yōu)粒子的位置.假設(shè)系統(tǒng)中粒子的數(shù)目被初始化為N 個(gè)，第i 個(gè)粒子的位置由一個(gè)n 維的向量來(lái)表示，即xi= (xi，1，xi，2，…，xi，n)，i = 1，2，…，N，其中xi，j∈［aj，bj］，即aj≤xi，j≤bj．i = 1，2，…，N;j = 1，2，…，n.粒子的每一個(gè)位置對(duì)應(yīng)問(wèn)題域中的一個(gè)潛在解.粒子xi的適應(yīng)值代表一個(gè)具體問(wèn)題的潛在解，不同的適應(yīng)值表示解的優(yōu)劣性.一個(gè)n 維的向量表示為粒子i 的速度，即vi= (vi，1，vi，2，…，vi，n)，i = 1，2，…，N.pi= (pi，1，pi，2，…，pi，n)，i =1，2，…，N 表示為粒子i 到目前為止尋找到的最優(yōu)值，pg= (pg，1，pg，2，…，pg，n)，i = 1，2，…，N 表示為粒子群到目前為止找到的全局最優(yōu)值，粒子群優(yōu)化算法采用(1)式和(2)式進(jìn)行尋優(yōu)操作:

其中，i = 1，2，…，N;r1和r2是屬于［0，1］范圍內(nèi)的隨機(jī)數(shù);c1∈［0，2］和c2∈［0，2］表示為兩個(gè)學(xué)習(xí)因子.算法的最大迭代次數(shù)根據(jù)問(wèn)題的具體情況進(jìn)行設(shè)置或者設(shè)置成為迄今為止尋優(yōu)到的最佳位置且滿足預(yù)定閾值時(shí)的次數(shù).在高維空間尋優(yōu)迭代過(guò)程中，標(biāo)準(zhǔn)粒子群優(yōu)化算法存在后期收斂速度慢和易陷入局部最優(yōu)的問(wèn)題，如果采取一些優(yōu)化方法進(jìn)一步提高粒子的拓?fù)浣Y(jié)構(gòu)，無(wú)疑會(huì)提高粒子群優(yōu)化算法的性能.

2 有向加權(quán)復(fù)雜網(wǎng)絡(luò)的自適應(yīng)粒子群優(yōu)化算法

2.1 粒子群有向加權(quán)復(fù)雜網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型具體構(gòu)建如下:

定義1 設(shè)復(fù)雜網(wǎng)絡(luò)G = {V，E，W}，V 為頂點(diǎn)的集合，E 為邊的集合，W 為邊上權(quán)重的集合．A 為復(fù)雜網(wǎng)絡(luò)G 的鄰接矩陣，A = (aij)n×n．其中，aij表示節(jié)點(diǎn)i 和節(jié)點(diǎn)j 的連接關(guān)系:如果這兩個(gè)節(jié)點(diǎn)之間有邊相連，則aij為1，否則為0．W =(wij)n×n為網(wǎng)絡(luò)邊上權(quán)重矩陣，其中wij為邊aij上的權(quán)重．

節(jié)點(diǎn)i 的加權(quán)出度為:

節(jié)點(diǎn)i 的加權(quán)入度為:

鄰接矩陣A 為:

此時(shí)以一定的概率p 連邊，0 ＜p ＜1 ．其中:i =1，2，…，N;j = 1，2，…，N．i ≠j．D(xi，xj)表示兩粒子之間的歐氏距離，R 表示粒子之間歐氏距離鄰居閾值，f(xi)表示粒子的適應(yīng)值，V(f(xi)，f(xj))表示粒子i 與粒子j 的適應(yīng)值之差．

對(duì)網(wǎng)絡(luò)邊的權(quán)值進(jìn)行歸一化，即:

∑(wij)表示邊上權(quán)值和;權(quán)值歸一化后，0 ≤wij≤1 ．

2.2 粒子自適應(yīng)尋優(yōu)

把2．1節(jié)中構(gòu)建的復(fù)雜網(wǎng)絡(luò)模型引入到粒子群尋優(yōu)的網(wǎng)絡(luò)拓?fù)溧徲蚪Y(jié)構(gòu)中，考慮一個(gè)有向的小世界網(wǎng)絡(luò)到無(wú)標(biāo)度網(wǎng)絡(luò)動(dòng)態(tài)的演化過(guò)程．當(dāng)粒子最終收斂到最優(yōu)時(shí)，節(jié)點(diǎn)的入度服從冪律分布．在粒子群每次迭代過(guò)程中，粒子的網(wǎng)絡(luò)拓?fù)湓谌攵确膬缏煞植嫉臈l件下動(dòng)態(tài)進(jìn)行改變．本文粒子之間學(xué)習(xí)方式按以下3 個(gè)原則:

(1)采用最優(yōu)鄰居(位置)的方法進(jìn)行粒子尋優(yōu)．

網(wǎng)絡(luò)中的每個(gè)粒子在尋找自身最優(yōu)(pbest)位置的同時(shí)也向鄰居們的最優(yōu)(lbest)位置學(xué)習(xí)．當(dāng)粒子i 與粒子j 之間位置相距很近時(shí)，比如小于某閾值R 時(shí)，兩粒子互為鄰居，另外當(dāng)粒子i 與粒子j 之間位置大于某閾值R 時(shí)，此時(shí)以一定的概率p(0 ＜p ?1)互為鄰居(可視為虛擬鄰居)．

(2)隨機(jī)連接到非粒子連接鄰域的其他粒子(虛擬鄰居)．這樣可以當(dāng)粒子陷入局部最優(yōu)時(shí)有效跳出局部最優(yōu)值．

每個(gè)粒子在自身鄰居內(nèi)尋優(yōu)，當(dāng)粒子i 與粒子j 之間位置大于某閾值R 時(shí)，此時(shí)以一定的概率p(0 ＜p ?1)互為鄰居(可視為虛擬鄰居)，這樣當(dāng)粒子在空間距離閾值R 內(nèi)找不到最優(yōu)鄰居時(shí)可以有效地跳出局部極值，從而自適應(yīng)尋找全局最優(yōu)值．

(3)在粒子學(xué)習(xí)最優(yōu)鄰居的過(guò)程中引入動(dòng)態(tài)學(xué)習(xí)因子c2，使粒子的飛行慣性在空間上也是異質(zhì)的．這樣可以增強(qiáng)粒子之間學(xué)習(xí)的多樣性，避免粒子在高維空間尋優(yōu)時(shí)陷入局部最優(yōu)．

本文算法中粒子除了學(xué)習(xí)自己最優(yōu)位置外只向最優(yōu)鄰居位置學(xué)習(xí)，此時(shí)的鄰居也包括虛擬鄰居．當(dāng)粒子i 的鄰居很多時(shí)，只選取鄰居中的最優(yōu)粒子作為連邊鄰居，兩粒子的邊為aij，邊上的權(quán)值wij為兩粒子適應(yīng)值之差．兩粒子的適應(yīng)差越大，粒子i 學(xué)習(xí)最優(yōu)鄰居粒子j 的位置越迫切．在公式(1)中引入動(dòng)態(tài)學(xué)習(xí)因子c2和變慣性權(quán)重w，使得粒子的飛行慣性在時(shí)間上和空間上都是異質(zhì)的．改進(jìn)公式:

其中i = 1，2，…，N，w = (w1- w2)× (T -iter)/T+w2;w1和w2表示為慣性權(quán)重的初始值與終值;T 為迭代的最大次數(shù);iter 代表當(dāng)前的迭代次數(shù);c2= (1 + wij)c1;wij為歸一化后的邊權(quán)重;pl為最優(yōu)鄰居位置．

粒子的加權(quán)入度W2Di代表鄰居粒子向該粒子學(xué)習(xí)的程度，粒子的加權(quán)出度W1Di代表該粒子向其他鄰居粒子學(xué)習(xí)的程度，有向加權(quán)復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)加權(quán)入度W2Di為n，n ≥0 ，加權(quán)出度W1Di為1 或0(只向最優(yōu)鄰居粒子學(xué)習(xí)或沒(méi)有最優(yōu)鄰居粒子而不學(xué)習(xí))．當(dāng)粒子群算法收斂時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)入度服從冪律分布且當(dāng)網(wǎng)絡(luò)中粒子的最大加權(quán)入度W2Di大于某一閾值K 且加權(quán)出度W1Di為0 時(shí)，此時(shí)粒子找到最優(yōu)值．在這種拓?fù)浣Y(jié)構(gòu)的變化中，由于每個(gè)粒子都向自己最優(yōu)鄰居的位置進(jìn)行學(xué)習(xí)，從而使網(wǎng)絡(luò)中的節(jié)點(diǎn)入度服從冪律分布特征且有較大的異質(zhì)性．同時(shí)，這種隨機(jī)連邊的操作使得陷入局部最優(yōu)的粒子能夠跳出局部極值飛向非連接鄰域中的其他粒子位置．由于這種改進(jìn)是基于有向動(dòng)態(tài)鄰域結(jié)構(gòu)的，所以粒子可以自適應(yīng)找到最優(yōu)值．

有向加權(quán)復(fù)雜網(wǎng)絡(luò)的自適應(yīng)粒子群優(yōu)化算法具體步驟如下:

Step 1:確定學(xué)習(xí)因子c1、c2，隨機(jī)邊連接概率p，群體規(guī)模N，慣性權(quán)重的初始值w1與終值w2，粒子群進(jìn)化次數(shù)T.

Step 2:對(duì)粒子群中各粒子的位置和速度進(jìn)行隨機(jī)初始化且控制在一定范圍內(nèi).

Step 3:初始化粒子群網(wǎng)絡(luò)鄰域:計(jì)算每個(gè)粒子的適應(yīng)值f(xi)及其間的歐氏距離D(xi，xj)，按照2.1 中提出的復(fù)雜網(wǎng)絡(luò)模型對(duì)粒子群構(gòu)建復(fù)雜網(wǎng)絡(luò)鄰域結(jié)構(gòu)，計(jì)算對(duì)應(yīng)的鄰接矩陣A 和網(wǎng)絡(luò)邊權(quán)重矩陣W.

Step 4:計(jì)算每個(gè)粒子的適應(yīng)值f(xi)，和它自身到目前為止找到的最優(yōu)值pi進(jìn)行比較.如果pi沒(méi)有該粒子的當(dāng)前適應(yīng)值好，則使pi等于當(dāng)前適應(yīng)值;對(duì)每個(gè)粒子的適應(yīng)值f(xi)和鄰居最優(yōu)值pl進(jìn)行比較，如果pl沒(méi)有該粒子的當(dāng)前適應(yīng)值好，則使pl等于當(dāng)前適應(yīng)值.

Step 5:在網(wǎng)絡(luò)鄰域入度服從冪律分布的條件下所有粒子按照(8)式和(2)式尋優(yōu);當(dāng)粒子速度及位置越過(guò)搜索邊界時(shí)，自動(dòng)取邊界值;計(jì)算尋優(yōu)后的鄰接矩陣A 和網(wǎng)絡(luò)邊權(quán)重矩陣W;對(duì)粒子群中原有的網(wǎng)絡(luò)鄰接矩陣A 和網(wǎng)絡(luò)邊權(quán)重矩陣W 進(jìn)行動(dòng)態(tài)更新.

Step 6:檢查是否滿足終止條件(計(jì)算粒子群復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的最大加權(quán)入度W2Di和該節(jié)點(diǎn)的加權(quán)出度W1Di.當(dāng)最大加權(quán)入度W2Di大于某一閾值K 且加權(quán)出度W1Di為0 時(shí)，此時(shí)粒子找到最優(yōu)值).若是，則終止算法;否則轉(zhuǎn)Step4.

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

實(shí)驗(yàn)軟件平臺(tái)為 Windows 7 和 Matlab R2010a，硬件平臺(tái)為CPU Intel Core i5，內(nèi)存4 GB.測(cè)試函數(shù)如下:

參數(shù)設(shè)置:粒子群規(guī)模N =30，最大迭代次數(shù)Interation_max = 100，學(xué)習(xí)因子0 ＜ c1＜混沌系統(tǒng)的初值為x=0.1，y= -0.2.DWCNPSO 中wmax= 0．9 ，wmin= 0．4 ，p = 0．1 .把DWCNPSO 算法分別和PSO 和基于Cat 混沌映射的SFPSO 算法進(jìn)行對(duì)比分析.仿真結(jié)果如表1所示.

表1 4 種算法測(cè)試仿真結(jié)果比較

(1)基于其他網(wǎng)絡(luò)拓?fù)溧徲虻腜SO 比較:

由表1可知，對(duì)于函數(shù)f1、f2和f3來(lái)說(shuō)，本文算法的最優(yōu)值優(yōu)于其他所有算法，但沒(méi)有SFPSO算法的平均值好.對(duì)于函數(shù)f4來(lái)說(shuō)，本文算法的平均值和最優(yōu)值要優(yōu)于其他所有算法.從整體可知:PSO 算法的性能最差，本文算法的最優(yōu)值性能好，本文算法比其他算法更易找到全局最優(yōu)值.

圖1是4 種算法對(duì)測(cè)試函數(shù)的尋優(yōu)迭代曲線.為了更清晰地表達(dá)尋優(yōu)結(jié)果，對(duì)適應(yīng)值取以e 為底的對(duì)數(shù).由圖1(b)可知，SFPSO 算法和PSO 算法在迭代次數(shù)為10 的時(shí)候就陷入了局部最優(yōu)且迭代多次粒子仍不能自動(dòng)跳出局部極值，而本文算法不僅不易陷入局部極值而且收斂速度也比其他兩種算法快，在4 個(gè)測(cè)試函數(shù)中本文的算法都能夠找到最小值且在算法陷入局部最優(yōu)時(shí)，仍能夠通過(guò)隨機(jī)連邊操作自動(dòng)跳出局部最優(yōu)，在搜索精度和收斂性能上本文算法都是最好的.函數(shù)f1和f2用來(lái)測(cè)試算法能否找到全局最優(yōu)值，函數(shù)f3和f4用來(lái)測(cè)試算法能否在多個(gè)局部極值點(diǎn)的干擾下找到全局最優(yōu)值.由圖1(b)可知，本文算法的搜索精度最高，找到了全局最小值;由圖1(d)可知，本文算法較好地平衡了全局和局部搜索，不易陷入局部最優(yōu)且收斂速度較快，并找到全局最小值.

圖1 3 種算法對(duì)測(cè)試函數(shù)的尋優(yōu)迭代曲線

(2)網(wǎng)絡(luò)平均度對(duì)DWCNPSO 的影響

由上文實(shí)驗(yàn)結(jié)果可知，粒子群鄰域網(wǎng)絡(luò)的拓?fù)湫再|(zhì)對(duì)算法的尋優(yōu)結(jié)果有很大影響.對(duì)于同一種網(wǎng)絡(luò)，為了研究拓?fù)湫再|(zhì)的差異是否對(duì)PSO尋優(yōu)結(jié)果有一定的影響，本文以無(wú)標(biāo)度網(wǎng)為例，對(duì)PSO 粒子尋優(yōu)結(jié)果進(jìn)行分析.在無(wú)標(biāo)度網(wǎng)絡(luò)中，不同的網(wǎng)絡(luò)平均度代表著不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)［12］.下面對(duì)基于無(wú)標(biāo)度網(wǎng)絡(luò)鄰域拓?fù)涞牟煌W(wǎng)絡(luò)平均度的PSO 效果進(jìn)行分析.對(duì)Rosenbrock和Rastrigrin 函數(shù)進(jìn)行多次實(shí)驗(yàn)(200 次重復(fù)獨(dú)立的隨機(jī)實(shí)驗(yàn))，測(cè)試結(jié)果如圖2所示.對(duì)Rosenbrock 目標(biāo)函數(shù)來(lái)說(shuō)，在平均度為〈K〉 =6.01 與〈K〉 =7.85 的情況下粒子尋優(yōu)較好，而當(dāng)〈K〉 =10.23 時(shí)粒子尋優(yōu)時(shí)陷入了局部最優(yōu)，因此網(wǎng)絡(luò)平均度值的增加對(duì)Rosenbrock 函數(shù)的測(cè)試結(jié)果并不一定越好，而對(duì)Rastrigrin 函數(shù)來(lái)說(shuō)平均度〈K〉 =10.23 時(shí)，尋優(yōu)效果最佳.對(duì)于2 個(gè)目標(biāo)函數(shù)而言，PSO 在一個(gè)平均度值范圍內(nèi)，網(wǎng)絡(luò)上的粒子尋優(yōu)效果最佳.

圖2 兩種算法對(duì)測(cè)試函數(shù)的尋優(yōu)迭代曲線

4 算法分析

4.1 算法收斂性分析

基本粒子群優(yōu)化算法在迭代到最后都能滿足收斂條件，文獻(xiàn)［13］證明了該算法是收斂的.當(dāng)公式(1)中w ＜1、c ＞0 且c = c1+ c2、2w -c +2 ＞0 時(shí)，基本粒子群算法是收斂的，收斂區(qū)域如圖3所示.本文算法是通過(guò)構(gòu)建粒子群復(fù)雜網(wǎng)絡(luò)以及增加自適應(yīng)學(xué)習(xí)因子c2來(lái)對(duì)基本粒子群優(yōu)化算法進(jìn)行改進(jìn)，算法的搜索機(jī)制并沒(méi)有改變.在本文算法中c = c1+c2= c1+(1 +wi，j)c1=(2 +wi，j)c1，由于0 ＜c ＜2w +2 ，所以當(dāng)0 ＜c1時(shí)，本文所提出的算法也是收斂的，從上面的實(shí)驗(yàn)結(jié)果可知，本文算法不僅收斂而且收斂速度有很大的提高.

圖3 基本算法參數(shù)收斂區(qū)域

4.2 算法復(fù)雜度分析

衡量一個(gè)算法優(yōu)劣的一個(gè)重要指標(biāo)就是時(shí)間復(fù)雜度［14］.假設(shè)粒子群搜索空間維數(shù)為D，粒子數(shù)目記為N，粒子群迭代的最大次數(shù)記為T(mén).在標(biāo)準(zhǔn)粒子群優(yōu)化算法中，粒子位置的初始化以及速度的初始化分別為O(ND)，計(jì)算粒子適應(yīng)值的時(shí)間復(fù)雜度為O(N2)，對(duì)粒子位置以及速度進(jìn)行更新操作的時(shí)間復(fù)雜度分別為O(ND).在本文算法中，由于初始化粒子群時(shí)引入了小世界網(wǎng)絡(luò)模型且構(gòu)建有向加權(quán)復(fù)雜網(wǎng)絡(luò)的時(shí)間復(fù)雜度為O(N2)，本文算法在時(shí)間上有所增加.然而，本文算法能夠較好解決高維空間求解問(wèn)題，并且在算法陷入局部最優(yōu)時(shí)，仍能夠通過(guò)隨機(jī)化連邊操作跳出局部最優(yōu)值.在高維空間尋優(yōu)迭代過(guò)程中，對(duì)于標(biāo)準(zhǔn)粒子群優(yōu)化算法所帶來(lái)的后期收斂速度慢和易陷入局部最優(yōu)的問(wèn)題相比，構(gòu)建復(fù)雜網(wǎng)絡(luò)的時(shí)間是可以接受的.在實(shí)際應(yīng)用中，復(fù)雜問(wèn)題的搜索空間維數(shù)都比較大，此時(shí)本文算法更具有優(yōu)越性.

5 結(jié)語(yǔ)

本文提出的基于有向加權(quán)復(fù)雜網(wǎng)絡(luò)的自適應(yīng)粒子群優(yōu)化算法，通過(guò)引入復(fù)雜網(wǎng)絡(luò)模型以及動(dòng)態(tài)學(xué)習(xí)因子，提高了粒子之間學(xué)習(xí)的多樣性，從而使粒子能夠快速找到最優(yōu)解，并且在算法陷入局部最優(yōu)時(shí)，仍然能夠通過(guò)隨機(jī)化連邊等操作較快地跳出局部最優(yōu)，進(jìn)而飛向全局最優(yōu).在算法復(fù)雜度上，對(duì)于標(biāo)準(zhǔn)粒子群優(yōu)化算法所帶來(lái)的后期收斂速度慢和易陷入局部最優(yōu)的問(wèn)題相比，構(gòu)建復(fù)雜網(wǎng)絡(luò)的時(shí)間是可以接受的.在實(shí)際應(yīng)用中，復(fù)雜問(wèn)題的搜索空間維數(shù)都比較大，而粒子數(shù)目一般設(shè)置為N(N ＜50 )，此時(shí)本文算法更具有優(yōu)越性.仿真實(shí)驗(yàn)結(jié)果也表明，本文算法與標(biāo)準(zhǔn)粒子群算法以及基于Cat 混沌映射的SFPSO 算法相比較，具有更好的搜索精度且不易陷入局部最優(yōu)，尤其在高維搜索空間尋優(yōu)過(guò)程中，本文算法搜索后期具有較快的收斂速度.

［1］Kennedy J，Eberhert R.Particle swarm optimization［C］.IEEE International Conference on Neural Networks，1995:1942 -1948.

［2］吳正科，楊青真，施永強(qiáng)，等.帶粒子釋放和速度限制的粒子群算法［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(3):682 -685.

［3］Alfi A.Particle swarm optimization algorithm with dynamic inertia weight for online parameter identification applied to Lorenz chaotic system［J］.International Journal of Innovative Computing，Information and Control，2012，8(2):1191 -1203.

［4］李朔楓，李太勇.一種基于距離的自適應(yīng)模糊粒子群優(yōu)化算法［J］.計(jì)算機(jī)科學(xué)，2011，38(8):257 -259.

［5］Kennedy J.Small worlds and mega - minds:effects of neighborhood topology on particle swarm performance［C］.Proceedings of 1999 Congress on Evolutionary Computation.Washington D.C.，USA 1999.

［6］姚燦中，楊建梅.靜態(tài)與動(dòng)態(tài)SF 拓?fù)溧徲驅(qū)SO 改進(jìn)算法的分析［J］.小型微型計(jì)算機(jī)系統(tǒng)，2012，33(5):1113 -1116.

［7］闞超豪.多向?qū)W習(xí)自適應(yīng)的粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49(6):23 -28.

［8］朱大勇，張新麗，李樹(shù)全.利用局部拓?fù)湫畔l(fā)現(xiàn)模糊社團(tuán)結(jié)構(gòu)［J］.電子科技大學(xué)學(xué)報(bào)，2011，40(1):73 -79.

［9］Jiménez，Abigail.A complex network model for seismicity based on mutual information［J］.Physica A:Statistical Mechanics and its Applications，2013，392(10):2498 -2506.

［10］Qu Kaiming，Peng Haipeng，F(xiàn)u Peilu，et al.Topology identification of complex network via fast converging particle swarm optimization algorithm［J］.Journal of Nanjing University of Science and Technology，2012，36(2):84 -89.

［11］Gutierrez A L.Comparison of different pso initialization techniques for high dimensional search space problems:a test with FSS and antenna arrays［C］.Proceedings of the 5th European Conference on Antennas and Propagation (EUCAP)，2011:965 -969.

［12］Zhu Zhiliang，Lin Sen，Cui Kun，et al.Network topology layout algorithm based on community detection of complex networks［J］.Journal of Computer -Aided Design and Computer Graphics，2011，23(11):1808-1815.

［13］申元霞，王國(guó)胤，曾傳華.PSO 模型種群多樣性與學(xué)習(xí)參數(shù)的關(guān)系研究［J］.電子學(xué)報(bào)，2011，39(6):1238 -1244.

［13］胡旺，張?chǎng)?一種基于進(jìn)化過(guò)程學(xué)習(xí)的粒子群優(yōu)化算法［J］.計(jì)算機(jī)科學(xué)，2012，39(4):193 -195.