一種新的粒子群拓?fù)湓O(shè)計(jì)準(zhǔn)則

馬勝藍(lán),葉東毅,楊玲玲

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

一種新的粒子群拓?fù)湓O(shè)計(jì)準(zhǔn)則

馬勝藍(lán)1,葉東毅2,楊玲玲2

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

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

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

1 概述

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

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

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

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

2 新的拓?fù)湓O(shè)計(jì)準(zhǔn)則

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

圖1 Square,All和Ring拓?fù)?/p>

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

2.1 配位數(shù)

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

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

2.2 球體堆積和最密堆積

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

圖2 FCC單位晶格

圖3 HCP單位晶格

2.3 設(shè)計(jì)準(zhǔn)則描述

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

(1)配位數(shù)

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

(2)堆積密度

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

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

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

接下來考慮粒子飛向局部最優(yōu)解區(qū)域,而全局最優(yōu)解正好處于相反位置的情形。如圖5所示的2D拓?fù)浣Y(jié)構(gòu),當(dāng)整個(gè)拓?fù)溱呄蛴谏习氩繀^(qū)域時(shí),下部的區(qū)域?qū)φ麄€(gè)粒子群體而言是塊盲區(qū)。而相反的,粒子群體若具有3D拓?fù)浣Y(jié)構(gòu)(圖6),它可以通過打破下平面的鍵,從而吸引整個(gè)拓?fù)涑蛐碌膮^(qū)域,因此,仍然有機(jī)會(huì)探索到全局最優(yōu)值所在的空間。

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

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

綜上所述,一個(gè)適當(dāng)?shù)逆I能體現(xiàn)為較低的配位數(shù),高堆積密度和3D結(jié)構(gòu),可以使得拓?fù)鋼碛懈玫耐ㄐ拍芰?。由此?gòu)建的拓?fù)?還常影響著打破鍵的時(shí)機(jī)。

3 菱形十二面體及特性

為了驗(yàn)證提出的準(zhǔn)則,本文根據(jù)此準(zhǔn)則設(shè)計(jì)出一種新的拓?fù)?并驗(yàn)證該新的拓?fù)涞乃阉髂芰Α?/p>

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

圖7 菱形十二面體

4 菱形十二面體與其他拓?fù)涞谋容^

本節(jié)主要比較菱形十二面體與其他的拓?fù)涞奶卣鳌?/p>

Square拓?fù)涫峭ㄟ^將球體按照網(wǎng)格方式排列而形成的,僅是平面點(diǎn)陣和2D堆積。因?yàn)?D最密堆積是由一個(gè)球體周圍圍繞著6個(gè)球體(六方點(diǎn)陣)方式堆積而成,所以Square并不滿足2D最密堆積。圖8顯示出Square拓?fù)涞恼骄Ц瘛?/p>

圖8 正方晶格

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

圖9 六方晶格

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

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

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

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

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

此外,All拓?fù)渲忻總€(gè)粒子需要N個(gè)決策粒子打破N個(gè)鍵去探索新的空間,導(dǎo)致了該拓?fù)浜茈y探索到新的空間。Ring拓?fù)鋬H需要2個(gè)決策粒子去打破2個(gè)鍵,這種過度簡(jiǎn)易的打破鍵的方式導(dǎo)致群體開發(fā)能力變?nèi)酢?/p>

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

圖12 Square類拓?fù)?/p>

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

最后,采用Mendes實(shí)驗(yàn)中所用的3個(gè)通信能力評(píng)價(jià)標(biāo)準(zhǔn)來評(píng)估如上拓?fù)洹Ｔ撛u(píng)價(jià)標(biāo)準(zhǔn)采用3個(gè)參數(shù)來評(píng)估拓?fù)涞乃阉髂芰?表1列出了拓?fù)涞?個(gè)統(tǒng)計(jì)量(平均距離、半徑及分布序列),其中,第1個(gè)參數(shù)表示信息廣播到整個(gè)拓?fù)湫枰钠骄螖?shù);第2個(gè)參數(shù)表示最大迭代次數(shù);第3個(gè)參數(shù)可以衡量信息通過拓?fù)鋫鞑サ难舆t情況的分布序列。注意的是分布序列的第1個(gè)數(shù)值表示的是圖的平均度,也可以用于表示平均配位數(shù)。

表1 拓?fù)鋱D統(tǒng)計(jì)量

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

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

5 實(shí)驗(yàn)結(jié)果與分析

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

5.1 3個(gè)獨(dú)立變量的實(shí)驗(yàn)結(jié)果

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

表2 標(biāo)準(zhǔn)化性能比較

表3 達(dá)到準(zhǔn)據(jù)的平均迭代次數(shù)

表4 達(dá)到準(zhǔn)據(jù)的概率 %

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

從表3可以看出,Square類的拓?fù)浔攘庑问骟w拓?fù)渌阉魉俣瓤?由于菱形十二面體需要搜索多一維的空間,因此其搜索速度會(huì)稍微偏慢。但考慮第3個(gè)參數(shù)的測(cè)試結(jié)果,菱形十二面體在有限的時(shí)間內(nèi)仍可以搜索到極優(yōu)值。

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

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

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

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

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

圖14 簡(jiǎn)單拓?fù)湫阅鼙容^

圖15 復(fù)雜拓?fù)湫阅鼙容^

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

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

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

6 結(jié)束語

本文將鍵能的3個(gè)特征(低配位數(shù)、高堆積密度和3D結(jié)構(gòu))用于評(píng)價(jià)粒子群的探索和開發(fā)能力,為了能夠有效地開發(fā)局部搜索空間和適時(shí)地探索到新的區(qū)域,提出一種新的PSO拓?fù)浣Y(jié)構(gòu)——菱形十二面體,該拓?fù)浣Y(jié)構(gòu)滿足3D最密堆積結(jié)構(gòu),且具有較低的平均配位數(shù),使其比之前研究推薦的Square拓?fù)渚哂懈鼉?yōu)的搜索能力。實(shí)驗(yàn)結(jié)果表明,基于菱形十二面體的粒子群優(yōu)化算法能夠更好地找到適應(yīng)值峰值和全局最優(yōu)值,具有較高的概率搜索到全局最優(yōu)解。雖然菱形十二面體搜索速度稍微緩慢,但是在限定時(shí)間內(nèi)仍然具有最高的解決優(yōu)化問題的概率。今后將進(jìn)行拓?fù)渌阉魉俣鹊膬?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] 馬勝藍(lán),葉東毅.一種帶禁忌搜索的粒子并行子群最小約簡(jiǎn)算法[J].智能系統(tǒng)學(xué)報(bào),2011,6(2):132-141.

[4] 馬勝藍(lán),葉東毅.一種基于博弈策略的群智能屬性約簡(jiǎn)算法[J].計(jì)算機(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] 馬勝藍(lán),葉東毅.信息熵最小約簡(jiǎn)問題的若干隨機(jī)優(yōu)化算法研究[J].模式識(shí)別與人工智能,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

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

2014-01-13

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

中文引用格式:馬勝藍(lán),葉東毅,楊玲玲.一種新的粒子群拓?fù)湓O(shè)計(jì)準(zhǔn)則[J].計(jì)算機(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.