劉 昕，皮建勇

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

一種基于中間結(jié)構(gòu)層的分層粒子群算法

劉 昕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í)提高了求解精度。

粒子群優(yōu)化算法；分層結(jié)構(gòu)；粒子群多樣性

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)是人們?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)

(2)

其中i=1,2,…,m；d=1,2,…D。

式(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é)研究，又簡單易實(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ǎ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)問題分解為更簡單、易處理的兩個(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類集體，速度更新公式如下：

(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類集體，速度更新公式如下：

(4)

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á)式如下：

(5)

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

(6)

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所示。

表1 Sphere函數(shù)

注：F集粒子數(shù)量為：mF，S集粒子數(shù)量為：mS

表2 Griewank函數(shù)

實(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)

圖1 sphere函數(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所示。

表3 Sphere函數(shù)實(shí)驗(yàn)結(jié)果

從圖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。

圖2 Griewank函數(shù)

算法最優(yōu)解運(yùn)行時(shí)間/s標(biāo)準(zhǔn)PSO1．31E?014．046E?01改進(jìn)多層次PSO1．21E?034．255E?01

4 結(jié)論

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

[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] 胡旺，李志蜀.一種更簡化而高效的粒子群優(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.

Hierarchic particle swarm algorithm based on layer of intermediate structure

Liu Xin1,2，Pi Jianyong1,2

(1.College of Computer Science and Technology，Guizhou University，Guiyang 550025，China ；2.Research Centre of Cloud Computing and Internet of Things，Guizhou University，Guiyang 550025，China )

A hierarchic particle swarm algorithm(PSO) is proposed in order to overcome the weak ability of local search of standard PSO algorithm. The proposed algorithm based on layer of intermediate structure and the particles is divided into two types. One type is used to search optimum solution fast,the other type is used to search optimum solution carefully. This method can increase diversity of particles and reduce the possibility of local minimum. The experiment performance of the propose algorithm is compared with the performance of the standard PSO using two benchmark functions.The experimental simulation results indicates that the hierarchic particle swarm algorithm can escape from local optimal solutions efficiently and the global search ability is better than standard PSO.

particle swarm algorithm; layered structure; diversity of particle swarm

TP301

A

10.19358/j.issn.1674- 7720.2017.04.008

劉昕，皮建勇.一種基于中間結(jié)構(gòu)層的分層粒子群算法[J].微型機(jī)與應(yīng)用，2017,36(4)：25-28.

2016-09-22)

劉昕(1992-)，女，碩士研究生，主要研究方向：群智能理論。

皮建勇(1973-)，男，博士，副教授，主要研究方向：數(shù)據(jù)挖掘、人工智能、分布式并行計(jì)算。