劉昕1,2,，皮建勇1,2

　　（1.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,，貴州 貴陽(yáng) 550025,；2.貴州大學(xué) 云計(jì)算與物聯(lián)網(wǎng)研究中心,，貴州 貴陽(yáng)550025）

        摘要：針對(duì)標(biāo)準(zhǔn)粒子群算法易陷入局部極值和優(yōu)化精度較低的缺點(diǎn)，結(jié)合復(fù)雜系統(tǒng)理論提出一種多層次粒子群算法,，通過(guò)在算法結(jié)構(gòu)中引入中間結(jié)構(gòu)層,，分別定義了進(jìn)行大范圍的較優(yōu)值搜索的粒子和在較優(yōu)值周?chē)M(jìn)行精細(xì)搜索的粒子，增加了粒子群的多樣性,，有效協(xié)調(diào)了粒子的尋優(yōu)能力,。采用了兩種標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)算法性能進(jìn)行了實(shí)驗(yàn),，結(jié)果表明，該算法可有效避免陷入局部最優(yōu),，并在保證運(yùn)行速度的同時(shí)提高了求解精度,。

　　關(guān)鍵詞：粒子群優(yōu)化算法；分層結(jié)構(gòu),；粒子群多樣性

　　中圖分類(lèi)號(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ī)制簡(jiǎn)單、清晰,、易于實(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í)際上是一類(lèi)復(fù)雜系統(tǒng),，這類(lèi)系統(tǒng)具有自適應(yīng)性、涌現(xiàn)性和開(kāi)放性,，研究者通常會(huì)引入中間結(jié)構(gòu)層來(lái)研究復(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）是人們?cè)谘芯盔B(niǎo)類(lèi)的群體行為基礎(chǔ)上提出的一種群智能算法，其基本思想是通過(guò)群體中個(gè)體之間的協(xié)作和信息共享來(lái)尋找最優(yōu)解［1］,。在算法中,，每個(gè)優(yōu)化問(wèn)題的潛在解被抽象成D維搜索空間上的一個(gè)點(diǎn),，稱(chēng)之為“粒子”，粒子通過(guò)跟蹤“個(gè)體極值（pbest）”和“全局極值(gbest)”來(lái)更新自己的位置,。算法流程如下：

　?。?）初始化一群隨機(jī)粒子(種群規(guī)模為m),，初始化內(nèi)容包括粒子的速度信息與位置信息；

　?。?）計(jì)算每個(gè)粒子的適應(yīng)值，即目標(biāo)函數(shù)值,；

　　（3）對(duì)每個(gè)粒子,，將其適應(yīng)值與其經(jīng)過(guò)的最優(yōu)位置作比較,，適應(yīng)度高的成為個(gè)體的當(dāng)前Pbest,；

　?。?）對(duì)每個(gè)粒子，將其適應(yīng)值與群體所經(jīng)過(guò)的最好位置作比較,，適應(yīng)度高的作為當(dāng)前的全局最優(yōu)解Gbest;

　?。?）根據(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ò)展搜索空間的趨勢(shì),，有能力探索新的區(qū)域,。第二部分來(lái)自于粒子個(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)對(duì)粒子的影響程度,。Rand是隨機(jī)數(shù),。m為種群規(guī)模，一般設(shè)置在20~100之間,，若側(cè)重于減少運(yùn)行時(shí)間,，則種群規(guī)模可設(shè)為40左右,，若偏向于高精度和高穩(wěn)定性,，則可設(shè)為60或80。

　　1.2相關(guān)研究

　　PSO算法既有深刻的智能背景,、適合科學(xué)研究,，又簡(jiǎn)單易實(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)等角度對(duì)傳統(tǒng)PSO進(jìn)行了研究與改進(jìn),。

　　1.2.1參數(shù)設(shè)置

　　粒子群算法所需參數(shù)少，但是對(duì)參數(shù)依賴性較大,，因此相關(guān)參數(shù)的設(shè)定對(duì)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,，算法開(kāi)始階段，大的慣性權(quán)重可以使算法不容易陷入局部最優(yōu),，到算法的后期,，小的慣性權(quán)重可以使收斂速度加快，使收斂更加平穩(wěn)［2］,。

　　加速系數(shù)方面：一般被設(shè)為相同的值,，最常見(jiàn)的是2，另一個(gè)常見(jiàn)的取值為1.494 45,。彭宇等人利用方差分析法分析了慣性權(quán)重和加速系數(shù)對(duì)算法性能的影響,，并給出了這兩種參數(shù)的設(shè)置參考原則［3］。ZHAN等提出了一種使用聚類(lèi)的方法對(duì)進(jìn)化狀態(tài)進(jìn)行判斷并且對(duì)加速系數(shù)進(jìn)行相應(yīng)調(diào)整的方案［4］,。

　　1.2.2拓?fù)浣Y(jié)構(gòu)研究

　　在PSO算法中,粒子之間通過(guò)相互學(xué)習(xí)尋找最優(yōu)解,，這種學(xué)習(xí)通過(guò)共享粒子所發(fā)現(xiàn)的最優(yōu)解來(lái)實(shí)現(xiàn),，所以粒子之間的信息共享方式對(duì)算法的性能有著至關(guān)重要的影響，粒子之間的信息共享方式體現(xiàn)為粒子群的鄰域拓?fù)浣Y(jié)構(gòu),，因此,，對(duì)粒子群的鄰城拓?fù)浣Y(jié)構(gòu)進(jìn)行研究也十分重要［5］。KENNEDY最早開(kāi)始對(duì)PSO算法中的鄰域結(jié)構(gòu)進(jìn)行研究,，提出了幾種經(jīng)典的鄰域拓?fù)?，并從小世界網(wǎng)絡(luò)模型出發(fā)，對(duì)PSO算法中的鄰域拓?fù)溥M(jìn)行了初步的探索［6］,。MENDES較為系統(tǒng)地分析了粒子群體中的拓?fù)浣Y(jié)構(gòu)對(duì)PSO性能的影響,，并肯定了粒子群的拓?fù)浣Y(jié)構(gòu)對(duì)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),，稱(chēng)為“集體”，一個(gè)集體可能具有復(fù)雜的內(nèi)部結(jié)構(gòu),，但外表上呈現(xiàn)為一個(gè)整體單位,，作為一個(gè)單位與其他集體進(jìn)行相互作用。

　　集體具有強(qiáng)的內(nèi)聚和弱的外部耦合,，比單個(gè)組分更適合作為“個(gè)體”來(lái)處理,。借助集體，可能相互作用和不可能相互作用的組分之間有了一個(gè)確定的概念性區(qū)別,，而集體構(gòu)成的中間結(jié)構(gòu)層可將復(fù)雜系統(tǒng)問(wèn)題分解為更簡(jiǎn)單,、易處理的兩個(gè)部分：集體分析研究集體的內(nèi)部結(jié)構(gòu)和集體行為，系統(tǒng)分析研究集體對(duì)于系統(tǒng)整體行為的貢獻(xiàn),。

　　由于粒子群屬于一類(lèi)復(fù)雜系統(tǒng),，本文將在粒子群系統(tǒng)中引入中間結(jié)構(gòu)層，構(gòu)成“基礎(chǔ)粒子層集體層系統(tǒng)”的多層次粒子群結(jié)構(gòu),，通過(guò)定義不同類(lèi)型的集體達(dá)到增加粒子多樣性的目的,，并通過(guò)改進(jìn)集體之間的交流方式改善粒子群算法的性能。

　　2.2多層次PSO算法

　　2.2.1算法思想

　　傳統(tǒng)粒子群算法易于過(guò)早收斂,，其主要原因在于進(jìn)化過(guò)程中粒子的多樣性損失過(guò)快,，所有的粒子依循相同的方式飛行，很容易造成所有粒子搜尋方向雷同,，所以本文通過(guò)定義不同類(lèi)型的集體,，使屬于不同類(lèi)型集體的粒子按照不同的搜索策略進(jìn)化,，來(lái)增強(qiáng)粒子的多樣性，提升粒子的尋優(yōu)能力,。

　　首先定義F類(lèi)集體,，速度更新公式如下：

　　vk+1id=wFvkid+cF1rand()(pid-xkid)+cF2rand()(pFgbest-xkid)(3)

　　F類(lèi)集體的目的是盡可能在解空間進(jìn)行大范圍的搜索，慣性權(quán)重將保持固定的較大值,，為了避免過(guò)早陷入局部極值,，F(xiàn)類(lèi)集體的搜索策略注重于個(gè)體經(jīng)驗(yàn)，而削弱全局經(jīng)驗(yàn)的影響,，即它將僅受到自身經(jīng)驗(yàn)與集體內(nèi)部產(chǎn)生的全局最優(yōu)值的影響,。

　　其次定義用于精細(xì)搜索的S類(lèi)集體，速度更新公式如下：

　　S類(lèi)集體的目的是幫助算法更好地收斂,，慣性權(quán)重將保持固定的較小值,，S類(lèi)粒子參考所有類(lèi)型的集體的社會(huì)經(jīng)驗(yàn)產(chǎn)生的較優(yōu)值，并在其周?chē)M(jìn)行精細(xì)搜索,，最終得到全局最優(yōu)值,。

　　算法思想：由F類(lèi)集體進(jìn)行大范圍的較優(yōu)值搜索，并產(chǎn)生初步最優(yōu)值FGBEST反饋給S類(lèi)集體,；而S類(lèi)集體則在初步最優(yōu)值周?chē)M(jìn)行精細(xì)搜索,，并產(chǎn)生本次迭代的最終最優(yōu)值SGBEST。之后的每次迭代中,，F(xiàn)類(lèi)集體繼續(xù)尋找其他較優(yōu)值,，而S類(lèi)集體綜合考慮兩類(lèi)集體粒子產(chǎn)生的最優(yōu)值，并在其附近進(jìn)行精細(xì)搜索,。

　　2.2.2算法流程

　?。?）初始化一群隨機(jī)粒子(種群規(guī)模為m)，初始化的內(nèi)容包括粒子的速度和位置信息,、粒子所屬的集體類(lèi)型,；

　　（2）計(jì)算每個(gè)粒子的適應(yīng)度（即目標(biāo)函數(shù)值）,；

　?。?）對(duì)每個(gè)粒子，將其適應(yīng)值與其經(jīng)過(guò)的最優(yōu)位置作比較,，適應(yīng)度高的成為個(gè)體的當(dāng)前Pbest,；

　　（4）對(duì)F類(lèi)粒子,，將其適應(yīng)值與集體所經(jīng)過(guò)的最好位置作比較,，適應(yīng)度高的作為當(dāng)前集體內(nèi)的最佳位置即Fgbest，并反饋給S集體；對(duì)S類(lèi)粒子,，將其適應(yīng)值與集體內(nèi)所經(jīng)過(guò)的最好位置比較,，適應(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ù)定義與測(cè)試函數(shù)

　　實(shí)驗(yàn)采用兩種標(biāo)準(zhǔn)測(cè)試函數(shù)即Sphere函數(shù)、Griewank函數(shù)對(duì)算法進(jìn)行性能測(cè)試,，其中Sphere函數(shù)是單峰函數(shù),，主要用于測(cè)試算法的收斂速度和求解精度；Griewank函數(shù)是典型的非線性多模態(tài)函數(shù),，是具有廣泛的搜索空間并且具有大量局部最優(yōu)點(diǎn)的多峰函數(shù),，算法很容易陷入局部最優(yōu)，此函數(shù)通常被認(rèn)為是優(yōu)化算法很難處理的復(fù)雜多模態(tài)問(wèn)題,，因此本文用Griewank函數(shù)測(cè)試算法的全局搜索能力,。

　　Sphere函數(shù)表達(dá)式如下：

　　3.2集體內(nèi)粒子數(shù)對(duì)多層次PSO的影響

　　多層次粒子群算法中，粒子分為在解空間內(nèi)迅速進(jìn)行大范圍搜索的F集粒子,、在初步較優(yōu)值周?chē)M(jìn)行精細(xì)搜索的S集粒子,。本文在粒子群種群數(shù)目為30、60,、90的情況下,，對(duì)兩種類(lèi)型粒子的數(shù)量對(duì)算法性能的影響做了實(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次,；對(duì)每個(gè)函數(shù)的測(cè)試均運(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ì)有所降低。

　?。?）由于兩類(lèi)集體內(nèi)粒子數(shù)量之比的變化不會(huì)影響粒子群總體規(guī)模,，因此對(duì)運(yùn)行時(shí)間沒(méi)有顯著影響。

　?。?）當(dāng)粒子規(guī)模逐漸增大時(shí),，解的質(zhì)量會(huì)有所提高，但相應(yīng)運(yùn)行時(shí)間會(huì)有所增加,。

　　3.3與標(biāo)準(zhǔn)PSO的對(duì)比實(shí)驗(yàn)

　　圖1sphere函數(shù)對(duì)比實(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次之后,，說(shuō)明多層次PSO的收斂能力強(qiáng)于標(biāo)準(zhǔn)PSO,，并且通過(guò)表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é)論

　　本文提出了一種多層次的粒子群算法,，通過(guò)引入中間結(jié)構(gòu)層構(gòu)造了不同類(lèi)型的粒子,，從而增加了粒子多樣性。實(shí)驗(yàn)證明,，此改進(jìn)方法能使算法有效跳出局部極值,，并在保證收斂速度的同時(shí)提高了求解精度。

　　參考文獻(xiàn)

　?。?］ 黃少榮.粒子群優(yōu)化算法綜述［J］.計(jì)算機(jī)工程與設(shè)計(jì), 2009, 30(8):19771980.

　?。?］ 楊維，李歧強(qiáng).粒子群優(yōu)化算法綜述［J］.中國(guó)工程科學(xué),，2004,，6（5）：87-94.

　　［3］ 陳貴敏，賈建援,，韓琪.粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究［J］.西安交通大學(xué)學(xué)報(bào),，2006，40（1）：53-56.

　?。?］ 胡旺,，李志蜀.一種更簡(jiǎn)化而高效的粒子群優(yōu)化算法［J］.軟件學(xué)報(bào)，2007,，18（4）：861-868.

　?。?］ 王偉,李枚毅,彭霞丹.一種雙層可變子群的動(dòng)態(tài)粒子群優(yōu)化算法［J］.小型微型計(jì)算機(jī)系統(tǒng),2012, 33(1):145150.

　　［6］ 朱艷偉,石新春,但揚(yáng)清,等.粒子群優(yōu)化算法在光伏陣列多峰最大功率點(diǎn)跟蹤中的應(yīng)用［J］.中國(guó)電機(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.