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

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

        摘要：針對(duì)標(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)測(cè)試函數(shù)對(duì)算法性能進(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ī)制簡(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í)際上是一類復(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）是人們?cè)谘芯盔B類的群體行為基礎(chǔ)上提出的一種群智能算法，其基本思想是通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解［1］,。在算法中,，每個(gè)優(yōu)化問題的潛在解被抽象成D維搜索空間上的一個(gè)點(diǎn)，稱之為“粒子”,，粒子通過跟蹤“個(gè)體極值（pbest）”和“全局極值(gbest)”來更新自己的位置,。算法流程如下：

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

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

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

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

　?。?）根據(jù)速度和位置更新公式調(diào)整粒子速度和位置,；

　　（6）未達(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ū)域。第二部分來自于粒子個(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ī)?？稍O(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，算法開始階段,，大的慣性權(quán)重可以使算法不容易陷入局部最優(yōu),，到算法的后期，小的慣性權(quán)重可以使收斂速度加快,，使收斂更加平穩(wěn)［2］,。

　　加速系數(shù)方面：一般被設(shè)為相同的值，最常見的是2,，另一個(gè)常見的取值為1.494 45,。彭宇等人利用方差分析法分析了慣性權(quán)重和加速系數(shù)對(duì)算法性能的影響，并給出了這兩種參數(shù)的設(shè)置參考原則［3］,。ZHAN等提出了一種使用聚類的方法對(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算法中,粒子之間通過相互學(xué)習(xí)尋找最優(yōu)解,，這種學(xué)習(xí)通過共享粒子所發(fā)現(xiàn)的最優(yōu)解來實(shí)現(xiàn)，所以粒子之間的信息共享方式對(duì)算法的性能有著至關(guān)重要的影響,，粒子之間的信息共享方式體現(xiàn)為粒子群的鄰域拓?fù)浣Y(jié)構(gòu),，因此，對(duì)粒子群的鄰城拓?fù)浣Y(jié)構(gòu)進(jìn)行研究也十分重要［5］,。KENNEDY最早開始對(duì)PSO算法中的鄰域結(jié)構(gòu)進(jìn)行研究,，提出了幾種經(jīng)典的鄰域拓?fù)洌男∈澜缇W(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)，稱為“集體”,，一個(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)問題分解為更簡(jiǎn)單、易處理的兩個(gè)部分：集體分析研究集體的內(nèi)部結(jié)構(gòu)和集體行為,，系統(tǒng)分析研究集體對(duì)于系統(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）對(duì)每個(gè)粒子,，將其適應(yīng)值與其經(jīng)過的最優(yōu)位置作比較,，適應(yīng)度高的成為個(gè)體的當(dāng)前Pbest；

　?。?）對(duì)F類粒子,，將其適應(yīng)值與集體所經(jīng)過的最好位置作比較，適應(yīng)度高的作為當(dāng)前集體內(nèi)的最佳位置即Fgbest,，并反饋給S集體,；對(duì)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ù)定義與測(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)問題,，因此本文用Griewank函數(shù)測(cè)試算法的全局搜索能力,。

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

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

　　多層次粒子群算法中,，粒子分為在解空間內(nèi)迅速進(jìn)行大范圍搜索的F集粒子、在初步較優(yōu)值周圍進(jìn)行精細(xì)搜索的S集粒子,。本文在粒子群種群數(shù)目為30,、60、90的情況下,，對(duì)兩種類型粒子的數(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é)論：

　?。?）在種群規(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ī)模，因此對(duì)運(yùn)行時(shí)間沒有顯著影響,。

　?。?）當(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次之后,，說明多層次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):19771980.

　　［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.

　?。?］ 胡旺，李志蜀.一種更簡(jiǎn)化而高效的粒子群優(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):145150.

　?。?］ 朱艷偉,石新春,但揚(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.