一種新的粒子群拓撲設(shè)計準則

馬勝藍,葉東毅,楊玲玲

(1.福建省農(nóng)村信用社聯(lián)合社科技服務(wù)中心,福州350001;2.福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,福州350108)

一種新的粒子群拓撲設(shè)計準則

馬勝藍1,葉東毅2,楊玲玲2

(1.福建省農(nóng)村信用社聯(lián)合社科技服務(wù)中心,福州350001;2.福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院,福州350108)

粒子群優(yōu)化算法的搜索性能取決于算法探索和開發(fā)能力的平衡,與算法所使用的拓撲結(jié)構(gòu)相關(guān)。現(xiàn)有的粒子群拓撲結(jié)構(gòu)不能較好地平衡算法的探索性能和開發(fā)能力。為此,依據(jù)低配位數(shù)、高堆積密度和3D結(jié)構(gòu)等特征,提出一種新的拓撲設(shè)計準則。根據(jù)此準則,設(shè)計一種菱形十二面體的拓撲結(jié)構(gòu),該拓撲結(jié)構(gòu)由球體按照六方晶格和面心立方結(jié)構(gòu)堆積而成,是具有最大空間利用率的3D最密堆積結(jié)構(gòu),且擁有較低的平均配位數(shù)。實驗結(jié)果表明,與現(xiàn)有的拓撲結(jié)構(gòu)相比,該拓撲結(jié)構(gòu)搜索到全局最優(yōu)值的概率較高。

粒子群優(yōu)化算法;設(shè)計準則;配位數(shù);菱形十二面體;密堆積;3D結(jié)構(gòu)

1 概述

粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是由E-berhart和Kenney發(fā)明的一種全局優(yōu)化進化算法[1-2],作為一種重要的群智能算法,國內(nèi)外對此作了大量的研究工作。文獻[3]提出結(jié)合長期記憶禁忌搜索方法的粒子群并行子群優(yōu)化算法,文獻[4]將粒子群算法映射到博弈環(huán)境。

然而如何合理地利用自身經(jīng)驗信息和群體共享信息的問題一直未能有效解決。而Kenney研究出粒子群每個個體不應(yīng)該簡單地被鄰居中的最優(yōu)值所影響,因此,提出基于所有鄰居信息值的全息粒子群算法[5]。本文研究就是在此基礎(chǔ)下展開的。全息粒子群(Fully Informed Particle Swarm,FIP)可以看作一種深層次的社會網(wǎng)絡(luò)粒子群優(yōu)化算法,該優(yōu)化算法所利用的信息均來自于粒子的鄰域[6],并且提出了許多拓撲(例如All、Ring、Four clusters、Pyramid和Square),其中,馮諾依曼結(jié)構(gòu)即Square拓撲由于其較好的搜索能力而被推薦使用。為了增強全息粒子群算法的搜索能力,國內(nèi)也有部分學(xué)者對此做改進,如文獻[7]利用帶增強策略的全息粒子群算法用于解決屬性約簡問題。

根據(jù)晶體學(xué)的知識,提出一種新準則,它所設(shè)計出的拓撲結(jié)構(gòu)具有令人滿意的通信能力。在此準則下,PSO的探索能力和開發(fā)能力被粒子之間的化學(xué)鍵能E所影響。一般的,堆積密度和配位數(shù)可以直觀地反應(yīng)出晶體的鍵能,而相應(yīng)的鍵能決定著特定的堆積密度和配位數(shù),最終將會決定一個拓撲的結(jié)構(gòu)。因此,從晶體學(xué)概念映射到拓撲結(jié)構(gòu)中,堆積密度決定著粒子群在拓撲結(jié)構(gòu)內(nèi)部搜索到全局最優(yōu)值的概率,即影響著開發(fā)能力;而配位數(shù)反應(yīng)出需要多少個粒子去打破化學(xué)鍵才能探索到新的區(qū)域。本文設(shè)計的一個具有適當鍵能(即低的配位數(shù)、高堆積密度和3D結(jié)構(gòu))的拓撲,可以保證好的通信能力。對于Square拓撲,在本文提出的設(shè)計準則評估下,拓撲僅是一個按照網(wǎng)格規(guī)則堆積的平面2D點陣,并不滿足最密堆積。而當群體飛向一個局部最優(yōu)解,且全局最優(yōu)解在該局部最優(yōu)解的相反位置時,粒子群體由于僅為2D結(jié)構(gòu),很難搜索到全局最優(yōu)解。綜上所述,一個適當設(shè)計的拓撲結(jié)構(gòu)應(yīng)該能夠平衡PSO的探索和開發(fā)能力。

根據(jù)提出的設(shè)計規(guī)則,本文設(shè)計出一種新的粒子群拓撲結(jié)構(gòu)。該拓撲結(jié)構(gòu)稱為菱形十二面體,它通過將球體按照六方晶格和面心立方結(jié)構(gòu)堆積而成,具有3D最密堆積和較低的平均配位數(shù)等特點。

2 新的拓撲設(shè)計準則

粒子群優(yōu)化算法的搜索過程實質(zhì)上就是社會群體交流信息的過程。為了構(gòu)建一個更緊湊的信息交流,前人在PSO中引入了一種社會網(wǎng)絡(luò)拓撲(如圖1所示),并構(gòu)建出一種全息粒子群[5]。這些拓撲極大地改進了PSO的搜索能力并影響著群體的通信能力。但是當前的研究并沒有提出一個令人滿意的拓撲設(shè)計準則。

圖1 Square,All和Ring拓撲

本文根據(jù)晶體學(xué)中的鍵能概念,提出一種新的設(shè)計準則。假設(shè)粒子群飛行在搜索空間中,粒子之間交流的信息被粒子間連接的化學(xué)鍵所影響,則鍵能決定著拓撲的結(jié)構(gòu)和對應(yīng)的特征。因此,在晶體學(xué)觀點中,鍵能是粒子群優(yōu)化算法的探索和開發(fā)能力的決定性因素。雖然不能直接簡單地計算出鍵能,但是配位數(shù)和堆積度可以間接地反映出鍵能的強度。其中,配位數(shù)常用來決定需要多少能量來打破鍵能,以此決定著探索能力;堆積密度影響著開發(fā)能力,進而影響著粒子在局部區(qū)域的搜索效率。此外,粒子群的適應(yīng)值還可以看作需要打破鍵或者重構(gòu)鍵的外部能量。雖然拓撲結(jié)構(gòu)是邏輯關(guān)系,并不是空間關(guān)系,但是空間緊致性可以反映出粒子的趨向性。

2.1 配位數(shù)

在離子晶體中,晶格能表示離子之間的鍵能強度:越大的晶格能將具有更穩(wěn)定的離子晶體。信息在離子之間傳遞被離子鍵所影響。離子鍵的本質(zhì)是正負離子之間的靜電力。如果2個離子可以看作球體的話,那么根據(jù)庫侖定律就可以得出如下結(jié)論:離子電荷越高,兩核間距越小,靜電作用越強,離子鍵越強,離子晶體就越穩(wěn)定。

已知配位數(shù)是一個可以反應(yīng)該鍵能的重要參數(shù),常指化合物中心原子周圍的配位原子個數(shù)[8-10]。正負離子半徑比影響著配位數(shù),進而影響化學(xué)晶體結(jié)構(gòu)的穩(wěn)定性[11]。當r+/r-＞0.414(r為正負離子的核間距離),配位數(shù)將大于4,形成穩(wěn)定晶體;當r+/r-＜0.414,配位數(shù)為4,晶體正好處于一個非穩(wěn)定的結(jié)構(gòu)。隨著r+持續(xù)的變大,配位數(shù)可以達到12個,相反的,隨著r+減小,配位數(shù)可以為3。

2.2 球體堆積和最密堆積

在幾何上,球體堆積指非重疊球體在一個封閉空間內(nèi)的堆積。這些球體具有相同大小的尺寸,利用該特性可以將堆疊的球體看作粒子群中的粒子。密堆積是相同大小球體的緊密排列,其中,已知的最密堆積方式為六方密堆積和立方密堆積[12]。立方密堆積(也稱為面心立方[13])按照ABCABC…規(guī)律重復(fù)堆積;而六方密堆積[14]是按照ABABAB…順序堆積。因為滑動一列粒子的位置并不會影響這些球體的體積,所以這2種堆積方式的密堆積度都等于。圖2顯示了面心立方(Face-Centered Cubic,FCC)的單位晶格,該晶格包含8個1/8的球體和6個半球體。圖3是六方密堆積(Hexagonal Close Packing,HCP)結(jié)構(gòu)的單位晶格,該晶格中,頂層和底層分別包括6個1/6球體和一個半球體,中間層包含3個球體。

圖2 FCC單位晶格

圖3 HCP單位晶格

2.3 設(shè)計準則描述

綜上分析,可以得出一種新的可以保證通信能力的拓撲設(shè)計準則:拓撲應(yīng)該具備適當?shù)逆I能,擁有較低的配位數(shù),高的堆積密度和3D結(jié)構(gòu)。該準則詳細的敘述如下:

(1)配位數(shù)

粒子鄰域的配位數(shù)越低,則該粒子可以更靈活地打破連接的化學(xué)鍵,從而搜索到新的空間;過低的配位數(shù)則會使整個晶體結(jié)構(gòu)松散。如2.1節(jié)所述,配位數(shù)為4時正好使晶體從穩(wěn)定狀態(tài)轉(zhuǎn)化為不穩(wěn)定狀態(tài),而且通過Mendes的實驗[5]也可以發(fā)現(xiàn)此個數(shù)下粒子群擁有較好的探索能力。根據(jù)離子晶體的知識可以近似確定一個好的拓撲配位數(shù)應(yīng)該接近于4。該數(shù)值越小將會使得晶體脆弱,而越大將會導(dǎo)致晶體缺乏彈性。

(2)堆積密度

這里的空間堆積緊密性間接反映出粒子群搜索的趨向性,雖然粒子群在搜索過程中,是根據(jù)自身局部領(lǐng)域的邏輯結(jié)構(gòu)信息,但是粒子的自身搜索卻是一個局部區(qū)域搜索,走向?qū)呄蛴诳臻g結(jié)構(gòu),最終收斂于局部最優(yōu)解。因為粒子之間的領(lǐng)域關(guān)系,正好也是粒子群將會聚集學(xué)習(xí)的方向,從空間角度上考慮也可以解釋粒子群會逐漸飛向局部最優(yōu)解中,所以本文在粒子群拓撲結(jié)構(gòu)的邏輯結(jié)構(gòu)上,也考慮了空間上的趨向性,對于邏輯拓撲上的空間特性也要求了堆積密度。先考慮2D空間內(nèi)全局最優(yōu)解正好處于拓撲內(nèi)的情況,圖4顯示了2種不同的拓撲,其全局最優(yōu)解(黑點)正好處于對應(yīng)的拓撲內(nèi)。每個球體的面積可以看成粒子的可視距離,粒子在自身的可視距離內(nèi)能夠直接找到全局最優(yōu)解。則密堆積度就可以用于表示拓撲范圍內(nèi)能搜索到最優(yōu)解的概率,所以,圖4(b)找到最優(yōu)解的概率更高。

圖4 2D空間內(nèi)粒子飛向拓撲內(nèi)部全局最優(yōu)解示意圖

類似的,在3D空間內(nèi)密堆積也可以表示為找到全局最優(yōu)解的概率,所以更高的密堆積度具有更強的本地開發(fā)能力。

接下來考慮粒子飛向局部最優(yōu)解區(qū)域,而全局最優(yōu)解正好處于相反位置的情形。如圖5所示的2D拓撲結(jié)構(gòu),當整個拓撲趨向于上半部區(qū)域時,下部的區(qū)域?qū)φ麄€粒子群體而言是塊盲區(qū)。而相反的,粒子群體若具有3D拓撲結(jié)構(gòu)(圖6),它可以通過打破下平面的鍵,從而吸引整個拓撲朝向新的區(qū)域,因此,仍然有機會探索到全局最優(yōu)值所在的空間。

圖5 2D結(jié)構(gòu)的粒子飛向局部最優(yōu)解示意圖

圖6 3D結(jié)構(gòu)的粒子飛向局部最優(yōu)解示意圖

綜上所述,一個適當?shù)逆I能體現(xiàn)為較低的配位數(shù),高堆積密度和3D結(jié)構(gòu),可以使得拓撲擁有更好的通信能力。由此構(gòu)建的拓撲,還常影響著打破鍵的時機。

3 菱形十二面體及特性

為了驗證提出的準則,本文根據(jù)此準則設(shè)計出一種新的拓撲,并驗證該新的拓撲的搜索能力。

根據(jù)該準則設(shè)計一個拓撲,一般首選采用3D最密堆積結(jié)構(gòu)。若將球體按照六方晶格和面心立方體結(jié)構(gòu)堆積,中心球體與周圍的12個同等大小球體相切,這樣構(gòu)成的結(jié)構(gòu)可以為3D最密堆積結(jié)構(gòu)。如果僅簡單地連接這些球心而構(gòu)成拓撲,將嚴重地違反低配位數(shù)這條特征。根據(jù)“Kissing number problem”[15],這種排列將會擁有最高的配位數(shù)12。因此,本文將中心球體與周圍的球體相切的切面構(gòu)成一個新的拓撲,該拓撲稱為菱形十二面體[16]。它包括12個全等的菱形、24條邊及14個頂點。圖7顯示了由14個頂點12個菱形所構(gòu)成的菱形十二面體結(jié)構(gòu)。由于長對角線是短對角線的倍,因此菱形的銳角大小大約為70.53°。這種堆積拓撲滿足3D最密堆積,且具有堆積度74.05%,可以充分利用空間以達到最大的空間利用率。菱形十二面體的平均配位數(shù)僅為3.43,接近于準則設(shè)計的配位數(shù)標準4,所以,該拓撲在很大程度上滿足設(shè)計準則。

圖7 菱形十二面體

4 菱形十二面體與其他拓撲的比較

本節(jié)主要比較菱形十二面體與其他的拓撲的特征。

Square拓撲是通過將球體按照網(wǎng)格方式排列而形成的,僅是平面點陣和2D堆積。因為2D最密堆積是由一個球體周圍圍繞著6個球體(六方點陣)方式堆積而成,所以Square并不滿足2D最密堆積。圖8顯示出Square拓撲的正方晶格。

圖8 正方晶格

該晶格包括4個1/4的圓,則晶格內(nèi)圓面積為As=πr2;正方晶格的面積為:Au=4r2;則堆積密度為η=π/4=0.785 4。

圖9 六方晶格

從上述結(jié)果可以看出,在2D空間內(nèi),Square的堆積密度低于菱形十二面體的堆積密度,而在3D空間內(nèi)Square搜索到拓撲內(nèi)的全局最優(yōu)點的概率未知。也就是說,菱形十二面體的開發(fā)能力比Square可信。然而Square的整體堆積密度0.785 4高于菱形十二面體的0.740 5,使得Square仍然具有較高的搜索能力,但2D結(jié)構(gòu)限制了Square的通信能力,因此,具備3D結(jié)構(gòu)的菱形十二面體開發(fā)能力強于Square。

這里將討論另一種情形,即當全局最優(yōu)解處于拓撲外的情況。拓撲處理該情況的能力可以間接反映出設(shè)計準則的有效性,因為適當?shù)逆I能可以決定粒子打破鍵能而搜索到新的空間的時機。圖10顯示了全局最優(yōu)解在菱形十二面體的菱形面外的情形(灰點表示原子;白點表示粒子)。其中,2個球體之間的連線是這2個原子的鍵,如果一個粒子傾向于飛向全局最優(yōu)區(qū)域,它將在2輪迭代中傳輸自己的信息給菱形上的另外3個粒子,然后該菱形上的粒子一起決定是否要打破該鍵,所以最終打破鍵的能量將由這4個粒子來決定。一旦該鍵被打破,這個新的信息將會通過中間球體傳播到剩余的11個原子。通過這種方式,整個拓撲將會逐漸地移向新的空間區(qū)域。可以說菱形十二面體擁有菱形搜索的特征,它需要4個決策粒子和2輪信息傳播延遲去打破一個原子鍵來探索到新的區(qū)間。從本質(zhì)上看該結(jié)構(gòu)的搜索速度有點緩慢,卻可以有效地搜索本地區(qū)域。

圖10 3D空間菱形十二面體粒子飛向全局最優(yōu)解示意圖

在Square拓撲中,每個粒子完全等價于原子。當一個粒子傾向于飛向全局最優(yōu)解時,它必須首先在一輪迭代中通知它的4個鄰域,如圖11,白點表示原子或者粒子。之后該粒子與鄰域一起打破鍵,從而探索到新的空間。所以,Square需要5個決策粒子和1輪信息傳播延遲去打破4個原子鍵來探索新的空間。該拓撲具有足夠的決策粒子,并能夠較快地探索到新的空間,但是打破過多的鍵導(dǎo)致了拓撲結(jié)構(gòu)的不穩(wěn)定。

圖11 Square的粒子飛向全局最優(yōu)解示意圖

此外,All拓撲中每個粒子需要N個決策粒子打破N個鍵去探索新的空間,導(dǎo)致了該拓撲很難探索到新的空間。Ring拓撲僅需要2個決策粒子去打破2個鍵,這種過度簡易的打破鍵的方式導(dǎo)致群體開發(fā)能力變?nèi)酢?/p>

綜上所述,適當?shù)逆I能會影響著PSO的通信能力,而且菱形十二面體比Square擁有更適當?shù)逆I能,這間接加強了本文提出的設(shè)計準則的可信度。為了驗證該結(jié)論,本文通過大量的優(yōu)化問題來比較Square拓撲和菱形十二面體拓撲,如圖12和圖13所示。首先根據(jù)粒子的個數(shù)定義出2類拓撲,即簡單和復(fù)雜拓撲,其中,帶有16個粒子的Square拓撲(16-Square)、帶有20個粒子的Square拓撲(20-Square)和簡單菱形十二面體(Rhombic Dodecahedron)為簡單拓撲;帶有24個粒子的Square拓撲(24-Square)和2-菱形十二面體(由2個菱形十二面體拼接而成)為復(fù)雜拓撲。

圖12 Square類拓撲

圖13 菱形十二面體和2-菱形十二面體

最后,采用Mendes實驗中所用的3個通信能力評價標準來評估如上拓撲。該評價標準采用3個參數(shù)來評估拓撲的搜索能力,表1列出了拓撲的3個統(tǒng)計量(平均距離、半徑及分布序列),其中,第1個參數(shù)表示信息廣播到整個拓撲需要的平均迭代次數(shù);第2個參數(shù)表示最大迭代次數(shù);第3個參數(shù)可以衡量信息通過拓撲傳播的延遲情況的分布序列。注意的是分布序列的第1個數(shù)值表示的是圖的平均度,也可以用于表示平均配位數(shù)。

表1 拓撲圖統(tǒng)計量

以菱形十二面體為例計算如上參數(shù),首先采用Floy-Warshall算法[17]計算出等權(quán)重拓撲的最短路徑,通過這些最短路徑,任意兩點間的平均距離和半徑都可以算出。菱形十二面體的最大傳播距離為4,則該拓撲的半徑為4。如第3節(jié)中所示,菱形十二面體擁有2類頂點,則擁有2類分布序列。在該拓撲中,有8個頂點擁有序列＜4,4,4,1＞,6個頂點擁有序列＜3,6,3,1＞,所以,最終的分布序列為＜3.43,5.14,3.43,1＞。

從表1可以看出,菱形十二面體類的拓撲,頂點直接可以傳輸?shù)焦?jié)點的個數(shù)低于Square類的拓撲,但是中間的傳輸過程可以影響更多的鄰域。這就使得菱形十二面體搜索速度會有點緩慢,但是它具備足夠的決策粒子去打破關(guān)鍵鍵,從而能夠探索到新的空間。雖然這會導(dǎo)致較長的搜索時間,但是可以避免粒子擴散。該分析同時也證實了菱形十二面體的特性。

5 實驗結(jié)果與分析

正如文獻[5-6]研究中所描述的,粒子自身的索引可以從鄰域列表中去除,并且沒有任何社會心理學(xué)原則說明個體的經(jīng)驗在一定程度上有助于自身的學(xué)習(xí)。因此,接下去的實驗中將主要討論自身索引從鄰域列表中去除的情況。實驗包括2個部分:第1個部分利用Mendes的3個評價變量和5種算法模式來測試拓撲結(jié)構(gòu);第2部分利用更多的優(yōu)化函數(shù)來比較Square和菱形十二面體拓撲結(jié)構(gòu)。

5.1 3個獨立變量的實驗結(jié)果

本節(jié)使用3個獨立變量來測試特定PSO拓撲的性能。第1個獨立變量是標準化的性能,它通過分別歸一化每個測試函數(shù)結(jié)果來找到一個最小的平均值,并且關(guān)注在較小的迭代次數(shù)內(nèi)的結(jié)果;第2個獨立變量是達到一個準據(jù)的平均迭代個數(shù),表示著搜索速度;第3個獨立變量為測試成功概率,即達到準據(jù)的概率。采用文獻[5]給出的測試函數(shù)、準據(jù)和定義的9種不同更新粒子群經(jīng)驗值的粒子群算法。表2～表4展示了3個變量的測試結(jié)果,其中,加粗表示算法采用該種拓撲具有最好的結(jié)果;∞表示在10 000次迭代循環(huán)中無法達到準據(jù)。

表2 標準化性能比較

表3 達到準據(jù)的平均迭代次數(shù)

表4 達到準據(jù)的概率 %

從表2可以看出,當利用 FIPS、Self、wSelf、Canonasym和wFIPSasym算法時,菱形十二面體表現(xiàn)出很好的性能,這說明菱形十二面體能夠快速地求出適應(yīng)值峰值。另外可以看出,由于簡單拓撲結(jié)構(gòu)較小,與復(fù)雜拓撲相比,因此它可以較快地找到適應(yīng)值峰值。

從表3可以看出,Square類的拓撲比菱形十二面體拓撲搜索速度快,由于菱形十二面體需要搜索多一維的空間,因此其搜索速度會稍微偏慢。但考慮第3個參數(shù)的測試結(jié)果,菱形十二面體在有限的時間內(nèi)仍可以搜索到極優(yōu)值。

從表4可以看出,2-菱形十二面體具有最高的概率找到全局最優(yōu)解。由于菱形十二面體類的模型具有較強的搜索能力,它可以較好地解決那些復(fù)雜的非對稱搜索任務(wù)。

5.2 優(yōu)化能力比較

本節(jié)將給出更詳細的比較,測試的函數(shù)細節(jié)可以在文獻[18]得到,并且按序測試,實驗過程利用40次計算的平均值。

在簡單拓撲中,原始粒子群、基于20-Square和16-Square的粒子群這3個算法相比較,基于菱形十二面體的粒子群算法在標號1,2,6,16,17,18和19的基準函數(shù)上具有較低的平均值。單獨比較菱形十二面體與16-Square,菱形十二面體拓撲在函數(shù)1～函數(shù) 6、函數(shù) 8～函數(shù) 13、函數(shù) 15～函數(shù) 19和函數(shù)21～函數(shù)22上生成了更接近于最優(yōu)解的結(jié)果。在復(fù)雜拓撲中,2-菱形十二面體在大多數(shù)函數(shù)上比24-Square找到更優(yōu)的結(jié)果。

圖14和圖15顯示出性能結(jié)果比較,縱坐標表示歸一化的數(shù)值結(jié)果,在歸一化條件下,越低值則意味著更優(yōu)的性能,越接近于最優(yōu)解。

圖14 簡單拓撲性能比較

圖15 復(fù)雜拓撲性能比較

從圖14可以看出,基于菱形十二面體的粒子群算法在函數(shù)7和函數(shù)14上雖然擁有最高的值,但是實際的結(jié)果已經(jīng)非常接近于最優(yōu)解。另外可以看出,基于20-Square拓撲的粒子群優(yōu)化算法處于最低的線,這點較好地說明粒子的個數(shù)對搜索能力有較大的影響。然而,僅比較16-Square和菱形十二面體,后一個拓撲的曲線顯然低于前一個拓撲的曲線;雖然Square-16的粒子個數(shù)大于菱形十二面體,但是搜索能力顯著低于菱形十二面體。

在圖15中,2-菱形十二面體僅在函數(shù)3、函數(shù)14和函數(shù)20上搜索結(jié)果略差于Square-24,在其他函數(shù)上都優(yōu)于Square-24并且非常接近于最優(yōu)解。

綜上所述,菱形十二面體具有很強的搜索能力,并且可以很快地達到適應(yīng)值峰值,與現(xiàn)有的拓撲結(jié)構(gòu)相比,該拓撲結(jié)構(gòu)搜索到全局最優(yōu)值的概率較高。如果粒子群的個數(shù)對于求解任務(wù)來說不是主要的影響因素,且搜索任務(wù)重點在于粒子的搜索能力,那么菱形十二面體拓撲是個首選。若粒子的個數(shù)也成為關(guān)鍵因素,2-菱形十二面體拓撲是更好的選擇。

6 結(jié)束語

本文將鍵能的3個特征(低配位數(shù)、高堆積密度和3D結(jié)構(gòu))用于評價粒子群的探索和開發(fā)能力,為了能夠有效地開發(fā)局部搜索空間和適時地探索到新的區(qū)域,提出一種新的PSO拓撲結(jié)構(gòu)——菱形十二面體,該拓撲結(jié)構(gòu)滿足3D最密堆積結(jié)構(gòu),且具有較低的平均配位數(shù),使其比之前研究推薦的Square拓撲具有更優(yōu)的搜索能力。實驗結(jié)果表明,基于菱形十二面體的粒子群優(yōu)化算法能夠更好地找到適應(yīng)值峰值和全局最優(yōu)值,具有較高的概率搜索到全局最優(yōu)解。雖然菱形十二面體搜索速度稍微緩慢,但是在限定時間內(nèi)仍然具有最高的解決優(yōu)化問題的概率。今后將進行拓撲搜索速度的優(yōu)化,以提高基于菱形十二面體的粒子群優(yōu)化算法的處理速度。

[1] Kennedy J,Eberhart R C.Particle Swarm Optimization[C]//Proceedings of IEEE International Conference on Neural Networks.[S.l.]:IEEE Press,1995:1942-1948.

[2] Shi Y,EberhartR C.A Modified ParticleSwarm Optimizer[C]//Proceedings of IEEE International Conference of Evolutionary Computation.[S.l.]:IEEE Press,1998:69-73.

[3] 馬勝藍,葉東毅.一種帶禁忌搜索的粒子并行子群最小約簡算法[J].智能系統(tǒng)學(xué)報,2011,6(2):132-141.

[4] 馬勝藍,葉東毅.一種基于博弈策略的群智能屬性約簡算法[J].計算機工程與應(yīng)用,2012,48(1):145-149.

[5] Mendes R,Kennedy J.The Fully Informed Particle Swarm:Simpler,Maybe Better[J].IEEE Transactions on Evolutionary Computation,2004,8(3):204-210.

[6] Kennedy J.Small Worlds and Mega-minds:Effects of Neighborhood Topology on Particle Swarm Performance[C]//Proceedings of Congress on Evolutionary Computation.Washington D.C.,USA:IEEE Computer Society,1999:1931-1938.

[7] 馬勝藍,葉東毅.信息熵最小約簡問題的若干隨機優(yōu)化算法研究[J].模式識別與人工智能,2012,25(1): 96-104.

[8] De A K.A Text Book of Inorganic Chemistry[M].[S.l.]: New Age International Publishers,2003.

[9] Hermann A,Matthias L,Peter S.The Search for the Species with the Highest Coordination Number[J]. Angewandte Chemie International Edition,2007, 46(14):2444-2447.

[10] McNaught A,Wilkinson A.Compendium of Chemical Terminology[M].[S.l.]:Wiley-Blackwell,1997.

[11] Pauling L.The Principles Determining the Structure of Complex Ionic Crystals[J].Journal of the American Chemical Society,1929,51(4):1010-1026.

[12] Hales T C.A Proof of the Kepler Conjecture[J].Annals of Mathematics,2005,162(3):1065-1185.

[13] Weisstein E W.Cubic Close Packing[EB/OL].(2011-08-21). http://mathworld.wolfram.com/CubicClosePacking.html.

[14] Weisstein E W.HexagonalClosePacking[EB/OL]. (2011-08-15).http://mathworld.wolfram.com/Hexagonal ClosePacking.html.

[15] Conway J H,Sloane N J A.Sphere Packings,Lattices,and Groups[M].New York,USA:Springer-Verlag,1993.

[16] Williams R.The Geometrical Foundation of Natural Structure:A Source Book of Design[M].New York, USA:Dover Publications,1979.

[17] Floyd R W.Algorithm 97:ShortestPath[J].Communications of the ACM,1962,5(6):344-345.

[18] Yao Xin,Liu Yong,Lin Guangmin.Evolutionary Programming Made Faster[J].IEEE Transactions on Evolutionary Computation,1999,3(2):82-102.

編輯 劉 冰

A New Design Criteria of Particle Swarm Topology

MA Shenglan1,YE Dongyi2,YANG Lingling2
(1.Science and Technology Service Center,Fujian Rural Credit Union,Fuzhou 350001,China; 2.College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China)

The ability of taking both the exploitation and exploration into account is a key to ensure good performance of the Particle Swarm Optimization(PSO)algorithm.This ability is to a large extent associated with the topological structures used in the algorithm.Most commonly used topologies are usually not quite favorable for assuring this ability,leading to the so-called dilemma of exploitation and exploration.This paper proposes a new design criteria for topologies by introducing such factors as low coordination number,high packing density and 3D structure.According to this rule,a new neighborhood topology for PSO is designed.The new topology,named rhombic dodecahedron,usually is used in crystallology and formed by packing spheres in hexagonal lattice and face-centered cubics,turns out to be of a 3D-close packing with the maximum space utilization with a low average coordination number.Experimental results on benchmark functions show that the proposed topology has a higher probability of finding the global optimum compared with existing topologies.

Particle Swarm Optimization(PSO)algorithm;design criteria;coordination number;rhombic dodecahedron;close packing;3D structure

1000-3428(2015)01-0200-07

A

TP18

10.3969/j.issn.1000-3428.2015.01.037

馬勝藍(1986-),男,碩士,主研方向:智能計算,數(shù)據(jù)挖掘;葉東毅,教授、博士生導(dǎo)師;楊玲玲,碩士。

2014-01-13

2014-03-12 E-mail:msl1121@vipqq.com

中文引用格式:馬勝藍,葉東毅,楊玲玲.一種新的粒子群拓撲設(shè)計準則[J].計算機工程,2015,41(1):200-206.

英文引用格式:Ma Shenglan,Ye Dongyi,Yang Lingling.A New Design Criteria of Particle Swarm Topology[J]. Computer Engineering,2015,41(1):200-206.