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

　　（1.貴州大學(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；

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

　　（5）根據(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ī)模可設(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)容包括粒子的速度和位置信息、粒子所屬的集體類型；

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

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

　　（4）對(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；

　　（5）根據(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é)論：

　　（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ì)有所降低。

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

　　（3）當(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)

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

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

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

　　［4］ 胡旺，李志蜀.一種更簡(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.

　　［6］ 朱艷偉,石新春,但揚(yáng)清,等.粒子群優(yōu)化算法在光伏陣列多峰最大功率點(diǎn)跟蹤中的應(yīng)用［J］.中國電機(jī)工程學(xué)報(bào), 2012, 32(4):42-48.

　　［7］ 王雪飛,王芳,邱玉輝.一種具有動(dòng)態(tài)拓?fù)浣Y(jié)構(gòu)的粒子群算法研究［J］.計(jì)算機(jī)科學(xué),2007, 34(3):205-207.