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

劉 昕，皮建勇

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

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

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

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

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

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

0 引言

粒子群算法是基于群體智能理論的優(yōu)化算法，其原理和機制簡單、清晰、易于實現(xiàn)，并且所需參數(shù)少、收斂速度快、魯棒性強，是智能優(yōu)化算法中的一個研究熱點，目前已廣泛應用于函數(shù)尋優(yōu)、系統(tǒng)建模、決策支持以及模糊系統(tǒng)控制等諸多領(lǐng)域。

粒子群算法是典型的群智能算法，而群智能系統(tǒng)實際上是一類復雜系統(tǒng)，這類系統(tǒng)具有自適應性、涌現(xiàn)性和開放性，研究者通常會引入中間結(jié)構(gòu)層來研究復雜系統(tǒng)。中間結(jié)構(gòu)層屬于一種模塊化和損害控制策略，借助中間結(jié)構(gòu)層可以更容易研究復雜系統(tǒng)中各組成部分之間相互作用所涌現(xiàn)出的特性與規(guī)律。

本文基于復雜系統(tǒng)理論，在粒子群算法中引入中間結(jié)構(gòu)層，提出了一種多層次粒子群算法，此算法改進了粒子間信息的共享方式，增強了粒子多樣性。實驗證明，該算法在保證收斂速度的同時，可以有效跳出局部極值，并提高算法的全局搜索能力和求解精度。

1 標準粒子群算法

1.1 標準PSO

粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)是人們在研究鳥類的群體行為基礎(chǔ)上提出的一種群智能算法，其基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解[1]。在算法中，每個優(yōu)化問題的潛在解被抽象成D維搜索空間上的一個點，稱之為“粒子”，粒子通過跟蹤“個體極值(pbest)”和“全局極值(gbest)”來更新自己的位置。算法流程如下：

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

(2)計算每個粒子的適應值，即目標函數(shù)值；

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

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

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

(6)未達到結(jié)束條件則轉(zhuǎn)(2)。

算法終止條件一般為最大迭代次數(shù)或粒子群搜索到的最優(yōu)位置，滿足預定最小適應閾值。

在PSO中，速度決定了粒子運動的方向和速率，位置則是粒子所代表的解在解空間的位置，是評估該解質(zhì)量的基礎(chǔ)。

速度更新公式和位置更新公式如下:

(1)

(2)

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

式(1)的第一部分表示上次速度的影響，w是慣性權(quán)重，它使粒子保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區(qū)域。第二部分來自于粒子個體的經(jīng)驗，是從當前點指向粒子歷史最好點的一個矢量；第三部分是一個從當前點指向種群最好點的矢量，反映了粒子間的全局協(xié)同合作和知識共享。其中c1和c2代表加速系數(shù)，即個體經(jīng)驗與社會經(jīng)驗對粒子的影響程度。Rand是隨機數(shù)。m為種群規(guī)模，一般設(shè)置在20～100之間，若側(cè)重于減少運行時間，則種群規(guī)?？稍O(shè)為40左右，若偏向于高精度和高穩(wěn)定性，則可設(shè)為60或80。

1.2 相關(guān)研究

PSO算法既有深刻的智能背景、適合科學研究，又簡單易實現(xiàn)、適合工程應用。因此一經(jīng)提出便引起信息和進化計算科學領(lǐng)域?qū)W者們的廣泛關(guān)注，形成了一個新的熱點，目前已有大量研究者從參數(shù)設(shè)置、拓撲結(jié)構(gòu)等角度對傳統(tǒng)PSO進行了研究與改進。

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

粒子群算法所需參數(shù)少，但是對參數(shù)依賴性較大，因此相關(guān)參數(shù)的設(shè)定對PSO的優(yōu)化性能有著重要影響。

慣性權(quán)重方面：研究表明較大的慣性權(quán)重有利于粒子群在更大的解空間內(nèi)進行搜索，從而跳出局部最優(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，另一個常見的取值為1.494 45。彭宇等人利用方差分析法分析了慣性權(quán)重和加速系數(shù)對算法性能的影響，并給出了這兩種參數(shù)的設(shè)置參考原則[3]。ZHAN等提出了一種使用聚類的方法對進化狀態(tài)進行判斷并且對加速系數(shù)進行相應調(diào)整的方案[4]。

1.2.2 拓撲結(jié)構(gòu)研究

在PSO算法中,粒子之間通過相互學習尋找最優(yōu)解，這種學習通過共享粒子所發(fā)現(xiàn)的最優(yōu)解來實現(xiàn)，所以粒子之間的信息共享方式對算法的性能有著至關(guān)重要的影響，粒子之間的信息共享方式體現(xiàn)為粒子群的鄰域拓撲結(jié)構(gòu)，因此，對粒子群的鄰城拓撲結(jié)構(gòu)進行研究也十分重要[5]。KENNEDY最早開始對PSO算法中的鄰域結(jié)構(gòu)進行研究，提出了幾種經(jīng)典的鄰域拓撲，并從小世界網(wǎng)絡(luò)模型出發(fā)，對PSO算法中的鄰域拓撲進行了初步的探索[6]。MENDES較為系統(tǒng)地分析了粒子群體中的拓撲結(jié)構(gòu)對PSO性能的影響，并肯定了粒子群的拓撲結(jié)構(gòu)對PSO算法的魯棒性和執(zhí)行性能有直接的作用[7]，其研究發(fā)現(xiàn)，粒子個體間社會交互的平均連接度越高，群體中的信息傳播速度就越快，但是發(fā)生早熟收斂的風險也越大[7]。

2 多層次粒子群算法

2.1 中間結(jié)構(gòu)層

中間結(jié)構(gòu)層是處理復雜系統(tǒng)的一種方法。復雜系統(tǒng)中，在組分和系統(tǒng)之間經(jīng)常會涌現(xiàn)出一些中間結(jié)構(gòu)，稱為“集體”，一個集體可能具有復雜的內(nèi)部結(jié)構(gòu)，但外表上呈現(xiàn)為一個整體單位，作為一個單位與其他集體進行相互作用。

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

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

2.2 多層次PSO算法

2.2.1 算法思想

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

首先定義F類集體，速度更新公式如下：

(3)

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

其次定義用于精細搜索的S類集體，速度更新公式如下：

(4)

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

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

2.2.2 算法流程

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

(2)計算每個粒子的適應度(即目標函數(shù)值)；

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

(4)對F類粒子，將其適應值與集體所經(jīng)過的最好位置作比較，適應度高的作為當前集體內(nèi)的最佳位置即Fgbest，并反饋給S集體；對S類粒子，將其適應值與集體內(nèi)所經(jīng)過的最好位置比較，適應度高的作為集體內(nèi)最佳位置即Sgbest；

(5)根據(jù)速度和位置更新公式調(diào)整粒子速度、位置；

(6)未達到結(jié)束條件則轉(zhuǎn)(2)。

結(jié)束條件為最大迭代次數(shù)或Sgbest滿足預定最小適應閾值。

3 實驗

3.1 參數(shù)定義與測試函數(shù)

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

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

(5)

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

(6)

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

多層次粒子群算法中，粒子分為在解空間內(nèi)迅速進行大范圍搜索的F集粒子、在初步較優(yōu)值周圍進行精細搜索的S集粒子。本文在粒子群種群數(shù)目為30、60、90的情況下，對兩種類型粒子的數(shù)量對算法性能的影響做了實驗。實驗平臺為MATLAB2012，S集體的w=0.9，c1=c2=0.5；S集的w=0.4，c1=c2=1.494 45；算法最大迭代次數(shù)為1 000次；對每個函數(shù)的測試均運行50次，結(jié)果取平均值。實驗結(jié)果如表1、表2所示。

表1 Sphere函數(shù)

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

表2 Griewank函數(shù)

實驗結(jié)論：

(1)在種群規(guī)模不變的情況下，用于快速搜索的F集粒子少于精細搜索的S集粒子時，尋優(yōu)精度較高，當F集體粒子與S集體粒子數(shù)量之比為1：2時，算法精度達到最高，但當F集粒子數(shù)量繼續(xù)減少時，尋優(yōu)能力會有所降低。

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

(3)當粒子規(guī)模逐漸增大時，解的質(zhì)量會有所提高，但相應運行時間會有所增加。

3.3 與標準PSO的對比實驗

圖1 sphere函數(shù)

對比實驗中，種群規(guī)模取100，F(xiàn)集體粒子數(shù)量與S集體粒子數(shù)量為1:2；最大迭代次數(shù)為500次；其他參數(shù)設(shè)定如3.2。實驗結(jié)果如圖1和表3所示。

表3 Sphere函數(shù)實驗結(jié)果

從圖1可以看出，多層次PSO在迭代至200次左右時即找到了全局最優(yōu)值，而標準PSO是在400次之后，說明多層次PSO的收斂能力強于標準PSO，并且通過表3的實驗數(shù)據(jù)可以看出多層次PSO的求解精度高于標準PSO。

從圖2中可以看出，多層次PSO在算法前期的尋優(yōu)精度和速度都強于標準PSO，并且由于多峰函數(shù)具有多個局部最優(yōu)點，因此標準版PSO在迭代至230代左右時陷入了局部極值，而多層次PSO可以跳出局部極值繼續(xù)尋優(yōu)，從表4實驗數(shù)據(jù)可以得出多層次PSO最終得到的最優(yōu)值的質(zhì)量遠遠高于標準PSO。

圖2 Griewank函數(shù)

算法最優(yōu)解運行時間/s標準PSO1．31E?014．046E?01改進多層次PSO1．21E?034．255E?01

4 結(jié)論

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

[1] 黃少榮.粒子群優(yōu)化算法綜述[J].計算機工程與設(shè)計, 2009, 30(8):1977-1980.

[2] 楊維，李歧強.粒子群優(yōu)化算法綜述[J].中國工程科學，2004，6(5)：87-94.

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

[4] 胡旺，李志蜀.一種更簡化而高效的粒子群優(yōu)化算法[J].軟件學報，2007，18(4)：861-868.

[5] 王偉,李枚毅,彭霞丹.一種雙層可變子群的動態(tài)粒子群優(yōu)化算法[J].小型微型計算機系統(tǒng),2012, 33(1):145-150.

[6] 朱艷偉,石新春,但揚清,等.粒子群優(yōu)化算法在光伏陣列多峰最大功率點跟蹤中的應用[J].中國電機工程學報, 2012, 32(4):42-48.

[7] 王雪飛,王芳,邱玉輝.一種具有動態(tài)拓撲結(jié)構(gòu)的粒子群算法研究[J].計算機科學,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].微型機與應用，2017,36(4)：25-28.

2016-09-22)

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

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