劉昕1,2,皮建勇1,2
?。?.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,,貴州 貴陽 550025;2.貴州大學(xué) 云計(jì)算與物聯(lián)網(wǎng)研究中心,,貴州 貴陽550025)
摘要:針對標(biāo)準(zhǔn)粒子群算法易陷入局部極值和優(yōu)化精度較低的缺點(diǎn),,結(jié)合復(fù)雜系統(tǒng)理論提出一種多層次粒子群算法,,通過在算法結(jié)構(gòu)中引入中間結(jié)構(gòu)層,分別定義了進(jìn)行大范圍的較優(yōu)值搜索的粒子和在較優(yōu)值周圍進(jìn)行精細(xì)搜索的粒子,,增加了粒子群的多樣性,,有效協(xié)調(diào)了粒子的尋優(yōu)能力。采用了兩種標(biāo)準(zhǔn)測試函數(shù)對算法性能進(jìn)行了實(shí)驗(yàn),,結(jié)果表明,,該算法可有效避免陷入局部最優(yōu),并在保證運(yùn)行速度的同時(shí)提高了求解精度,。
關(guān)鍵詞:粒子群優(yōu)化算法,;分層結(jié)構(gòu);粒子群多樣性
中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:ADOI: 10.19358/j.issn.1674-7720.2017.04.008
引用格式:劉昕,,皮建勇.一種基于中間結(jié)構(gòu)層的分層粒子群算法[J].微型機(jī)與應(yīng)用,,2017,36(4):25-28.
0引言
粒子群算法是基于群體智能理論的優(yōu)化算法,其原理和機(jī)制簡單,、清晰,、易于實(shí)現(xiàn),并且所需參數(shù)少,、收斂速度快,、魯棒性強(qiáng),是智能優(yōu)化算法中的一個(gè)研究熱點(diǎn),,目前已廣泛應(yīng)用于函數(shù)尋優(yōu),、系統(tǒng)建模、決策支持以及模糊系統(tǒng)控制等諸多領(lǐng)域,。
粒子群算法是典型的群智能算法,,而群智能系統(tǒng)實(shí)際上是一類復(fù)雜系統(tǒng),這類系統(tǒng)具有自適應(yīng)性,、涌現(xiàn)性和開放性,,研究者通常會(huì)引入中間結(jié)構(gòu)層來研究復(fù)雜系統(tǒng)。中間結(jié)構(gòu)層屬于一種模塊化和損害控制策略,,借助中間結(jié)構(gòu)層可以更容易研究復(fù)雜系統(tǒng)中各組成部分之間相互作用所涌現(xiàn)出的特性與規(guī)律,。
本文基于復(fù)雜系統(tǒng)理論,在粒子群算法中引入中間結(jié)構(gòu)層,,提出了一種多層次粒子群算法,,此算法改進(jìn)了粒子間信息的共享方式,增強(qiáng)了粒子多樣性,。實(shí)驗(yàn)證明,,該算法在保證收斂速度的同時(shí),可以有效跳出局部極值,,并提高算法的全局搜索能力和求解精度,。
1標(biāo)準(zhǔn)粒子群算法
1.1標(biāo)準(zhǔn)PSO
粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)是人們在研究鳥類的群體行為基礎(chǔ)上提出的一種群智能算法,,其基本思想是通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解[1]。在算法中,,每個(gè)優(yōu)化問題的潛在解被抽象成D維搜索空間上的一個(gè)點(diǎn),,稱之為“粒子”,粒子通過跟蹤“個(gè)體極值(pbest)”和“全局極值(gbest)”來更新自己的位置,。算法流程如下:
?。?)初始化一群隨機(jī)粒子(種群規(guī)模為m),初始化內(nèi)容包括粒子的速度信息與位置信息,;
?。?)計(jì)算每個(gè)粒子的適應(yīng)值,即目標(biāo)函數(shù)值,;
?。?)對每個(gè)粒子,將其適應(yīng)值與其經(jīng)過的最優(yōu)位置作比較,,適應(yīng)度高的成為個(gè)體的當(dāng)前Pbest,;
(4)對每個(gè)粒子,,將其適應(yīng)值與群體所經(jīng)過的最好位置作比較,,適應(yīng)度高的作為當(dāng)前的全局最優(yōu)解Gbest;
(5)根據(jù)速度和位置更新公式調(diào)整粒子速度和位置,;
?。?)未達(dá)到結(jié)束條件則轉(zhuǎn)(2)。
算法終止條件一般為最大迭代次數(shù)或粒子群搜索到的最優(yōu)位置,,滿足預(yù)定最小適應(yīng)閾值,。
在PSO中,速度決定了粒子運(yùn)動(dòng)的方向和速率,,位置則是粒子所代表的解在解空間的位置,是評(píng)估該解質(zhì)量的基礎(chǔ),。
速度更新公式和位置更新公式如下:
式(1)的第一部分表示上次速度的影響,,w是慣性權(quán)重,它使粒子保持運(yùn)動(dòng)慣性,,使其有擴(kuò)展搜索空間的趨勢,,有能力探索新的區(qū)域。第二部分來自于粒子個(gè)體的經(jīng)驗(yàn),,是從當(dāng)前點(diǎn)指向粒子歷史最好點(diǎn)的一個(gè)矢量,;第三部分是一個(gè)從當(dāng)前點(diǎn)指向種群最好點(diǎn)的矢量,反映了粒子間的全局協(xié)同合作和知識(shí)共享,。其中c1和c2代表加速系數(shù),,即個(gè)體經(jīng)驗(yàn)與社會(huì)經(jīng)驗(yàn)對粒子的影響程度,。Rand是隨機(jī)數(shù)。m為種群規(guī)模,,一般設(shè)置在20~100之間,,若側(cè)重于減少運(yùn)行時(shí)間,則種群規(guī)??稍O(shè)為40左右,,若偏向于高精度和高穩(wěn)定性,則可設(shè)為60或80,。
1.2相關(guān)研究
PSO算法既有深刻的智能背景,、適合科學(xué)研究,又簡單易實(shí)現(xiàn),、適合工程應(yīng)用,。因此一經(jīng)提出便引起信息和進(jìn)化計(jì)算科學(xué)領(lǐng)域?qū)W者們的廣泛關(guān)注,形成了一個(gè)新的熱點(diǎn),,目前已有大量研究者從參數(shù)設(shè)置,、拓?fù)浣Y(jié)構(gòu)等角度對傳統(tǒng)PSO進(jìn)行了研究與改進(jìn)。
1.2.1參數(shù)設(shè)置
粒子群算法所需參數(shù)少,,但是對參數(shù)依賴性較大,,因此相關(guān)參數(shù)的設(shè)定對PSO的優(yōu)化性能有著重要影響。
慣性權(quán)重方面:研究表明較大的慣性權(quán)重有利于粒子群在更大的解空間內(nèi)進(jìn)行搜索,,從而跳出局部最優(yōu)值,,而較小的慣性權(quán)重有利于算法的收斂。SHI等人提出了慣性權(quán)重隨著迭代次數(shù)線性遞減的模型,。一般情況下將慣性權(quán)重的初始值設(shè)置為0.9,,隨著迭代次數(shù)遞減到0.4,算法開始階段,,大的慣性權(quán)重可以使算法不容易陷入局部最優(yōu),,到算法的后期,小的慣性權(quán)重可以使收斂速度加快,,使收斂更加平穩(wěn)[2],。
加速系數(shù)方面:一般被設(shè)為相同的值,最常見的是2,,另一個(gè)常見的取值為1.494 45,。彭宇等人利用方差分析法分析了慣性權(quán)重和加速系數(shù)對算法性能的影響,并給出了這兩種參數(shù)的設(shè)置參考原則[3],。ZHAN等提出了一種使用聚類的方法對進(jìn)化狀態(tài)進(jìn)行判斷并且對加速系數(shù)進(jìn)行相應(yīng)調(diào)整的方案[4],。
1.2.2拓?fù)浣Y(jié)構(gòu)研究
在PSO算法中,粒子之間通過相互學(xué)習(xí)尋找最優(yōu)解,這種學(xué)習(xí)通過共享粒子所發(fā)現(xiàn)的最優(yōu)解來實(shí)現(xiàn),,所以粒子之間的信息共享方式對算法的性能有著至關(guān)重要的影響,,粒子之間的信息共享方式體現(xiàn)為粒子群的鄰域拓?fù)浣Y(jié)構(gòu),,因此,對粒子群的鄰城拓?fù)浣Y(jié)構(gòu)進(jìn)行研究也十分重要[5],。KENNEDY最早開始對PSO算法中的鄰域結(jié)構(gòu)進(jìn)行研究,,提出了幾種經(jīng)典的鄰域拓?fù)洌男∈澜缇W(wǎng)絡(luò)模型出發(fā),,對PSO算法中的鄰域拓?fù)溥M(jìn)行了初步的探索[6],。MENDES較為系統(tǒng)地分析了粒子群體中的拓?fù)浣Y(jié)構(gòu)對PSO性能的影響,并肯定了粒子群的拓?fù)浣Y(jié)構(gòu)對PSO算法的魯棒性和執(zhí)行性能有直接的作用[7],,其研究發(fā)現(xiàn),,粒子個(gè)體間社會(huì)交互的平均連接度越高,群體中的信息傳播速度就越快,,但是發(fā)生早熟收斂的風(fēng)險(xiǎn)也越大[7],。
2多層次粒子群算法
2.1中間結(jié)構(gòu)層
中間結(jié)構(gòu)層是處理復(fù)雜系統(tǒng)的一種方法。復(fù)雜系統(tǒng)中,,在組分和系統(tǒng)之間經(jīng)常會(huì)涌現(xiàn)出一些中間結(jié)構(gòu),,稱為“集體”,一個(gè)集體可能具有復(fù)雜的內(nèi)部結(jié)構(gòu),,但外表上呈現(xiàn)為一個(gè)整體單位,,作為一個(gè)單位與其他集體進(jìn)行相互作用。
集體具有強(qiáng)的內(nèi)聚和弱的外部耦合,,比單個(gè)組分更適合作為“個(gè)體”來處理,。借助集體,可能相互作用和不可能相互作用的組分之間有了一個(gè)確定的概念性區(qū)別,,而集體構(gòu)成的中間結(jié)構(gòu)層可將復(fù)雜系統(tǒng)問題分解為更簡單,、易處理的兩個(gè)部分:集體分析研究集體的內(nèi)部結(jié)構(gòu)和集體行為,系統(tǒng)分析研究集體對于系統(tǒng)整體行為的貢獻(xiàn),。
由于粒子群屬于一類復(fù)雜系統(tǒng),,本文將在粒子群系統(tǒng)中引入中間結(jié)構(gòu)層,構(gòu)成“基礎(chǔ)粒子層集體層系統(tǒng)”的多層次粒子群結(jié)構(gòu),,通過定義不同類型的集體達(dá)到增加粒子多樣性的目的,,并通過改進(jìn)集體之間的交流方式改善粒子群算法的性能。
2.2多層次PSO算法
2.2.1算法思想
傳統(tǒng)粒子群算法易于過早收斂,,其主要原因在于進(jìn)化過程中粒子的多樣性損失過快,所有的粒子依循相同的方式飛行,,很容易造成所有粒子搜尋方向雷同,,所以本文通過定義不同類型的集體,使屬于不同類型集體的粒子按照不同的搜索策略進(jìn)化,,來增強(qiáng)粒子的多樣性,,提升粒子的尋優(yōu)能力,。
首先定義F類集體,速度更新公式如下:
vk+1id=wFvkid+cF1rand()(pid-xkid)+cF2rand()(pFgbest-xkid)(3)
F類集體的目的是盡可能在解空間進(jìn)行大范圍的搜索,,慣性權(quán)重將保持固定的較大值,,為了避免過早陷入局部極值,F(xiàn)類集體的搜索策略注重于個(gè)體經(jīng)驗(yàn),,而削弱全局經(jīng)驗(yàn)的影響,,即它將僅受到自身經(jīng)驗(yàn)與集體內(nèi)部產(chǎn)生的全局最優(yōu)值的影響。
其次定義用于精細(xì)搜索的S類集體,,速度更新公式如下:
S類集體的目的是幫助算法更好地收斂,,慣性權(quán)重將保持固定的較小值,S類粒子參考所有類型的集體的社會(huì)經(jīng)驗(yàn)產(chǎn)生的較優(yōu)值,,并在其周圍進(jìn)行精細(xì)搜索,,最終得到全局最優(yōu)值。
算法思想:由F類集體進(jìn)行大范圍的較優(yōu)值搜索,,并產(chǎn)生初步最優(yōu)值FGBEST反饋給S類集體,;而S類集體則在初步最優(yōu)值周圍進(jìn)行精細(xì)搜索,并產(chǎn)生本次迭代的最終最優(yōu)值SGBEST,。之后的每次迭代中,,F(xiàn)類集體繼續(xù)尋找其他較優(yōu)值,而S類集體綜合考慮兩類集體粒子產(chǎn)生的最優(yōu)值,,并在其附近進(jìn)行精細(xì)搜索,。
2.2.2算法流程
(1)初始化一群隨機(jī)粒子(種群規(guī)模為m),,初始化的內(nèi)容包括粒子的速度和位置信息,、粒子所屬的集體類型;
?。?)計(jì)算每個(gè)粒子的適應(yīng)度(即目標(biāo)函數(shù)值),;
(3)對每個(gè)粒子,,將其適應(yīng)值與其經(jīng)過的最優(yōu)位置作比較,,適應(yīng)度高的成為個(gè)體的當(dāng)前Pbest;
?。?)對F類粒子,,將其適應(yīng)值與集體所經(jīng)過的最好位置作比較,適應(yīng)度高的作為當(dāng)前集體內(nèi)的最佳位置即Fgbest,,并反饋給S集體,;對S類粒子,將其適應(yīng)值與集體內(nèi)所經(jīng)過的最好位置比較,適應(yīng)度高的作為集體內(nèi)最佳位置即Sgbest,;
?。?)根據(jù)速度和位置更新公式調(diào)整粒子速度、位置,;
(6)未達(dá)到結(jié)束條件則轉(zhuǎn)(2),。
結(jié)束條件為最大迭代次數(shù)或Sgbest滿足預(yù)定最小適應(yīng)閾值。
3實(shí)驗(yàn)
3.1參數(shù)定義與測試函數(shù)
實(shí)驗(yàn)采用兩種標(biāo)準(zhǔn)測試函數(shù)即Sphere函數(shù),、Griewank函數(shù)對算法進(jìn)行性能測試,,其中Sphere函數(shù)是單峰函數(shù),主要用于測試算法的收斂速度和求解精度,;Griewank函數(shù)是典型的非線性多模態(tài)函數(shù),,是具有廣泛的搜索空間并且具有大量局部最優(yōu)點(diǎn)的多峰函數(shù),算法很容易陷入局部最優(yōu),,此函數(shù)通常被認(rèn)為是優(yōu)化算法很難處理的復(fù)雜多模態(tài)問題,,因此本文用Griewank函數(shù)測試算法的全局搜索能力。
Sphere函數(shù)表達(dá)式如下:
3.2集體內(nèi)粒子數(shù)對多層次PSO的影響
多層次粒子群算法中,,粒子分為在解空間內(nèi)迅速進(jìn)行大范圍搜索的F集粒子,、在初步較優(yōu)值周圍進(jìn)行精細(xì)搜索的S集粒子。本文在粒子群種群數(shù)目為30,、60,、90的情況下,對兩種類型粒子的數(shù)量對算法性能的影響做了實(shí)驗(yàn),。實(shí)驗(yàn)平臺(tái)為MATLAB2012,,S集體的w=0.9,c1=c2=0.5,;S集的w=0.4,,c1=c2=1.494 45;算法最大迭代次數(shù)為1 000次,;對每個(gè)函數(shù)的測試均運(yùn)行50次,,結(jié)果取平均值。實(shí)驗(yàn)結(jié)果如表1,、表2所示,。
實(shí)驗(yàn)結(jié)論:
(1)在種群規(guī)模不變的情況下,,用于快速搜索的F集粒子少于精細(xì)搜索的S集粒子時(shí),,尋優(yōu)精度較高,當(dāng)F集體粒子與S集體粒子數(shù)量之比為1:2時(shí),,算法精度達(dá)到最高,,但當(dāng)F集粒子數(shù)量繼續(xù)減少時(shí),尋優(yōu)能力會(huì)有所降低。
?。?)由于兩類集體內(nèi)粒子數(shù)量之比的變化不會(huì)影響粒子群總體規(guī)模,因此對運(yùn)行時(shí)間沒有顯著影響,。
?。?)當(dāng)粒子規(guī)模逐漸增大時(shí),解的質(zhì)量會(huì)有所提高,,但相應(yīng)運(yùn)行時(shí)間會(huì)有所增加,。
3.3與標(biāo)準(zhǔn)PSO的對比實(shí)驗(yàn)
圖1sphere函數(shù)對比實(shí)驗(yàn)中,種群規(guī)模取100,,F(xiàn)集體粒子數(shù)量與S集體粒子數(shù)量為1:2,;最大迭代次數(shù)為500次;其他參數(shù)設(shè)定如3.2,。實(shí)驗(yàn)結(jié)果如圖1和表3所示,。
從圖1可以看出,多層次PSO在迭代至200次左右時(shí)即找到了全局最優(yōu)值,,而標(biāo)準(zhǔn)PSO是在400次之后,,說明多層次PSO的收斂能力強(qiáng)于標(biāo)準(zhǔn)PSO,并且通過表3的實(shí)驗(yàn)數(shù)據(jù)可以看出多層次PSO的求解精度高于標(biāo)準(zhǔn)PSO,。
從圖2中可以看出,,多層次PSO在算法前期的尋優(yōu)精度和速度都強(qiáng)于標(biāo)準(zhǔn)PSO,并且由于多峰函數(shù)具有多個(gè)局部最優(yōu)點(diǎn),,因此標(biāo)準(zhǔn)版PSO在迭代至230代左右時(shí)陷入了局部極值,,而多層次PSO可以跳出局部極值繼續(xù)尋優(yōu),從表4實(shí)驗(yàn)數(shù)據(jù)可以得出多層次PSO最終得到的最優(yōu)值的質(zhì)量遠(yuǎn)遠(yuǎn)高于標(biāo)準(zhǔn)PSO,。
4結(jié)論
本文提出了一種多層次的粒子群算法,,通過引入中間結(jié)構(gòu)層構(gòu)造了不同類型的粒子,從而增加了粒子多樣性,。實(shí)驗(yàn)證明,,此改進(jìn)方法能使算法有效跳出局部極值,并在保證收斂速度的同時(shí)提高了求解精度,。
參考文獻(xiàn)
?。?] 黃少榮.粒子群優(yōu)化算法綜述[J].計(jì)算機(jī)工程與設(shè)計(jì), 2009, 30(8):19771980.
[2] 楊維,,李歧強(qiáng).粒子群優(yōu)化算法綜述[J].中國工程科學(xué),,2004,6(5):87-94.
?。?] 陳貴敏,,賈建援,韓琪.粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究[J].西安交通大學(xué)學(xué)報(bào),2006,,40(1):53-56.
?。?] 胡旺,李志蜀.一種更簡化而高效的粒子群優(yōu)化算法[J].軟件學(xué)報(bào),,2007,,18(4):861-868.
[5] 王偉,李枚毅,彭霞丹.一種雙層可變子群的動(dòng)態(tài)粒子群優(yōu)化算法[J].小型微型計(jì)算機(jī)系統(tǒng),2012, 33(1):145150.
?。?] 朱艷偉,石新春,但揚(yáng)清,等.粒子群優(yōu)化算法在光伏陣列多峰最大功率點(diǎn)跟蹤中的應(yīng)用[J].中國電機(jī)工程學(xué)報(bào), 2012, 32(4):42-48.
?。?] 王雪飛,王芳,邱玉輝.一種具有動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)的粒子群算法研究[J].計(jì)算機(jī)科學(xué),2007, 34(3):205-207.