混合粒子群優(yōu)化算法及其收斂性分析

董　航，高志強，李姝湲，郭紅霞，程　川

（武警工程大學(xué)，西安　710086）

混合粒子群優(yōu)化算法及其收斂性分析

董航，高志強，李姝湲，郭紅霞，程川

（武警工程大學(xué)，西安710086）

為解決標(biāo)準(zhǔn)粒子群優(yōu)化算法不能保證全局收斂，尋優(yōu)精度低，尤其在高維函數(shù)優(yōu)化方面易陷入局部極小值等問題，提出一種融合Kent混沌映射、云模型理論和布谷鳥搜索的混合粒子群優(yōu)化算法（CPSO）；CPSO算法采用混沌初始化種群位置、全局開發(fā)及局部開采的均衡搜索、多子種群協(xié)同進化等改進策略，同時從隨機優(yōu)化算法的全局收斂準(zhǔn)則角度對CPSO算法的全局收斂性進行證明，并給出了CPSO算法的時間復(fù)雜度分析；經(jīng)典的benchmark測試函數(shù)的實驗統(tǒng)計結(jié)果表明，CPSO算法在收斂性、尋優(yōu)精度、穩(wěn)定性等方面均優(yōu)于經(jīng)典算法。

混合粒子群優(yōu)化算法；云模型；混沌映射；布谷鳥搜索；收斂性分析

0　引言

作為群體智能的優(yōu)秀范例，粒子群優(yōu)化算法（PSO）［1］具有收斂速度快，調(diào)節(jié)參數(shù)少和尋優(yōu)能力強等特點，但也存在現(xiàn)代智能優(yōu)化算法普遍的缺陷，如易陷入局部極小值、尋優(yōu)精度不高，尤其是在高維函數(shù)優(yōu)化方面尤為明顯。目前，混合粒子群優(yōu)化算法［2］已成為新的研究熱點。劉洪波［3］融合了一種非線性反饋的混沌神經(jīng)元映射算法，提高了種群的多樣性和搜索空間的遍歷性，在多模態(tài)、高維函數(shù)優(yōu)化方面取得良好效果。彭智［4］從廣義單調(diào)有界數(shù)列極限的角度，給出混合優(yōu)化算法全局收斂的充分條件，為混合算法設(shè)計提供基本準(zhǔn)則。朱奇光［5］提出了引入人工免疫克隆方法的PSO算法，并成功將其應(yīng)用到偏振模色散補償中。方偉［6］用量子空間和量子勢能場模型描述PSO算法，證明了融合算法的全局收斂性。

目前，混合算法的研究主要集中在多次重新啟動、全局及局部均衡搜索策略、多子種群協(xié)同進化等方面［2，4］。本文采用Kent混沌映射引入隨機因素，為種群提供具有均勻分布特性的初始位置；在兩個子種群的基礎(chǔ)上，利用由PSO算法和布谷鳥搜索共享的種群最優(yōu)資源檔案池來記憶和共享種群迭代中的最優(yōu)歷史信息，并指導(dǎo)兩個子種群在整個解向量空間協(xié)同進化、全面搜索；當(dāng)種群收斂到一定程度時，啟動云模型搜索，引入隨機和模糊因素，在種群最優(yōu)個體周圍重新挖掘歷史信息，進而得到最終的全局最優(yōu)解。

1　混合粒子群優(yōu)化算法的設(shè)計與實現(xiàn)

1.1Kent混沌映射

混沌現(xiàn)象存在于非線性動力系統(tǒng)中，具有初值敏感性、規(guī)律性、普適性、遍歷性等優(yōu)點。Kent映射［7］是一種典型的離散混沌系統(tǒng)，是二對一型的線性迭代函數(shù)，其系統(tǒng)方程如下：

其中：β∈［0，1］，x∈［0，1］。由Perron-Frobenious方程得到Kent映射概率密度函數(shù)服從在（0，1）上的均勻分布。另外，在游程、互相關(guān)均方根值、平衡性、自相關(guān)旁瓣等［8］特征方面，Kent映射均展現(xiàn)出優(yōu)越的性能。因此，本文采用均勻性更優(yōu)的Kent映射產(chǎn)生初始隨機數(shù)序列randi。設(shè)種群中粒子位置變量X的取值范圍為［xmin，xmax］，采用下式對種群粒子的各維進行初始化。

xid（0）=xmin+randi（xmax-xmin），i=1，2，…，n（2）

1.2布谷鳥搜索

英國學(xué)者Yang［9］于2009年模擬布谷鳥尋窩產(chǎn)蛋行為，并結(jié)合萊維飛行 （Levy Flights），提出一種元啟發(fā)式算法——布谷鳥搜索 （Cuckoo Search，CS）。該算法是一種簡單、易于實現(xiàn)、且具有全局收斂性［107］的群體智能優(yōu)化方法。在布谷鳥搜索中，鳥巢代表候選解，利用Levy飛行來更新最好解。然后按發(fā)現(xiàn)概率對現(xiàn)有候選解進行舍棄。最后，以隨機偏好的方式產(chǎn)生與淘汰等量的解，再次評價解的質(zhì)量?；贚evy飛行的布谷鳥搜索采用如下方式產(chǎn)生新解：xi（t+1）=xi（t）+α⊕Levy（β）（3）

其中，xi（t+1）表示第t+1次迭代產(chǎn)生的第i個候選解，α是用來控制算法在搜索空間中尋優(yōu)范圍的最優(yōu)步長，⊕是點乘，本文采用Mantegna算法來實現(xiàn)Levy飛行模式，布谷鳥搜索產(chǎn)生新解xi（t+1）的一種具體實現(xiàn)方式為：

其中，α0為常量（通常α0=0.01），xbest（t）表示截至第t次迭代產(chǎn)生的最優(yōu)解。另外，按發(fā)現(xiàn)概率Pa丟棄一定數(shù)量的解后，采用如下偏好方式產(chǎn)生等量的新解：

xi（t+1）=xi（t）+rand（xj（t）-xk（t））（5）

其中，rand 為 （0，1）區(qū)間的隨機數(shù)，xj（t）、xk（t）為第t次迭代中的兩個隨機解。

1.3云模型

中國工程院院士李德毅于1995年首次提出了云模型理論［10］。它是一種用自然語言描述定性概念與定量概念的雙向認(rèn)知轉(zhuǎn)換模型。設(shè)U是一個用精確數(shù)值表示的定量論域，C是U上的定性概念，若定量值x∈U，且x是定性概念C的一次隨機實現(xiàn)，x對C的隸屬度μ（x）∈［0，1］是具有穩(wěn)定傾向的隨機數(shù)，則x在論域U上的分布稱作云，每一個x稱作一個云滴。云模型具有3個數(shù)字特征，即Ex（Expected value），En（Entropy）和He（Hyper entropy）。

本文采用的一維逆向正態(tài)云發(fā)生器算法（1-D Backward Normal Cloud Generator，BNCF）［11］充分考慮云模型的霧化特性，對定性概念的數(shù)字特征具有更高的矩估計準(zhǔn)確性和有效性。采用的一維正向正態(tài)云發(fā)生器算法（1-D Forward Normal Cloud Generator，F(xiàn)NCG）［12］實現(xiàn)由定性概念向定量數(shù)值的轉(zhuǎn)換。

1.4混合粒子群優(yōu)化算法流程

為克服PSO算法易早熟，不具備全局收斂性等缺點，本文提出一種混合粒子群優(yōu)化算法（Composite Particle Swarm Optimization，CPSO），混合算法采用“并行加串行”的算法結(jié)構(gòu)，可具體分為以下3個部分，具體算法流程如圖1所示。

1）初始化及種群分類：首先，根據(jù)式（1）和式（2），利用在遍歷過程中均勻性更具優(yōu)勢的Kent混沌映射，產(chǎn)生混沌序列并映射到種群的搜索空間，實現(xiàn)種群初始化。然后，將種群隨機等容量地分成種群1和種群2，并行執(zhí)行以PSO算法為主子群和CS算法為輔助子種群的進化策略。

2）全局開發(fā)（explore）：PSO算法和CS算法并行協(xié)同演進。其中，為擴大全局搜索范圍，提高變異概率，CS算法的發(fā)現(xiàn)概率Pa定為黃金分割率（0.618），同時將搜索到的最優(yōu)解存入種群最優(yōu)資源檔案池，并與PSO算法共同更新種群最優(yōu)資源檔案池中存儲的最優(yōu)個體，優(yōu)勢互補，以擴大PSO算法和CS算法中最優(yōu)個體的選擇范圍。當(dāng)PSO算法達到終止條件，結(jié)束以PSO算法為主體，CS算法協(xié)同的全局開發(fā)過程。

3）局部開采 （exploit）：通過種群密度判定體現(xiàn)種群的進化狀態(tài)情況。當(dāng)種群密度小于預(yù)設(shè)值時，結(jié)束算法輸出結(jié)果；當(dāng)種群密度大于預(yù)設(shè)值時，啟動云模型深度搜索模式（相當(dāng)于重啟動策略或再次引入隨機個體策略）。利用啟動逆向云發(fā)生器 （BNCG），得到定性概念的數(shù)字特征，然后啟動正向云發(fā)生器（FNCG），生成代表新的搜索粒子的云滴，進行深度開采，直至達到算法結(jié)束條件。

圖1　CPSO算法流程圖

2　混合粒子群優(yōu)化算法性能分析

本節(jié)從隨機算法全局收斂性準(zhǔn)則［13］的角度出發(fā)，對CPSO算法收斂性進行證明和分析。在CPSO算法中，混沌初始化增加種群均勻性，云模型搜索是在已收斂情況下增加開發(fā)深度。只有PSO算法和CS算法的子種群協(xié)同進化部分影響整個算法的全局收斂性，所以只需證明該部分的收斂性即可。

定理1：假設(shè)CPSO算法優(yōu)化的目標(biāo)函數(shù)f是一個可測函數(shù)，其解空間S為Rn上的可測子集，并且CPSO算法同時滿足隨機搜索算法全局收斂的條件1和條件2，設(shè)｛xk｝∞k=0是CPSO算法所產(chǎn)生的解序列，則k→∞

其中，P（xk∈Rε，M）是CPSO算法第k步搜索到的解xk在最優(yōu)區(qū)域Rε，M中的概率測度。

證明：依據(jù)CPSO算法流程（只針對兩個子種群協(xié)作部分），迭代函數(shù)F可定義為

因為CPSO算法利用種群最優(yōu)資源檔案池保留種群最優(yōu)解，即采用適應(yīng)度值非遞增的精英保留策略，可知算法滿足文獻［13］中條件1。

如果CPSO算法滿足文獻［13］中條件2，則規(guī)模為n的混合種群的樣本采樣空間的并集一定包含目標(biāo)函數(shù)f的解向量空間S，即

其中，Mi，k為第k次迭代種群中粒子i的樣本空間的支撐，即概率測度為1的最小閉子集。

令Yk為CS算法在第k次迭代時搜索到的解。因為，單獨執(zhí)行CS算法得到的解序列｛Yk｝以概率l全局收斂于最優(yōu)區(qū)域Rε，M［14］。因此，在CPSO算法中，對于有限個滿足f（Yk）＞f（Pg，k）的解Yk，可令其下一狀態(tài)為Pg，k，并將其存儲于種群最優(yōu)資源檔案池中，而且該機制對CS算法的全局收斂性沒有影響，即在CPSO算法中恒有l(wèi)i mP（Yk∈Rε，M）=

k→∞1，也就是說，當(dāng)f（Yk）＜f（Pg，k）時，存在一個粒子i0，其支撐集Mi0，k=S，而對于其它的粒子i，由文獻［15］中推導(dǎo)得到的二階非齊次遞歸公式有

其中，0≤φ1≤c1，0≤φ2≤c2，可知Mi，k為一個頂點為（φ1，φ2）=（0，0），另一個頂點為（φ1，φ2）=（c1，c2）的超矩形。

綜上所述，CSPO算法的兩個子種群協(xié)作部分，滿足隨機搜索算法全局收斂的條件1和條件2，并結(jié)合初始化和云模型深度搜索兩個策略，CPSO算法的搜索序列依概率1收斂于全局最優(yōu)解，即CSPO算法具有全局收斂性。

另外，本文提出的混合粒子群算法（CPSO）的時間復(fù)雜度和空間復(fù)雜度都是多項式時間階，且與PSO算法的復(fù)雜度在同一數(shù)量級上，因此，無論是從算法的執(zhí)行效率還是數(shù)據(jù)的存儲結(jié)構(gòu)等方面均簡單方便，易于計算機編程實現(xiàn)。

3　混合粒子群優(yōu)化算法的benchmark測試函數(shù)實驗

實驗相關(guān)參數(shù)設(shè)置如下：初始化種群規(guī)模為40，兩個子種群規(guī)模各為20，慣性權(quán)重ω從0.9線性遞減至0.4，學(xué)習(xí)因子c1=c2=1.494，最大迭代次數(shù)為1 000。對比算法PSO［16］和CSPSO［17］參數(shù)設(shè)置均與參考文獻相同。

為便于驗證分析，實驗結(jié)果中，均以“平均誤差+標(biāo)準(zhǔn)差”形式表示每個解，同時，給出了0.05顯著水平下的雙側(cè)t -檢驗結(jié)果?！啊帧北硎緦Ρ人惴ㄅc本章算法解的質(zhì)量相似；“++”表示對比算法解的質(zhì)量比本章算法性能差；“+|”表示對比算法解的質(zhì)量比本章算法性能好。對維數(shù)為30的測試函數(shù)（f1～f4）分別獨立進行20次實驗，算法性能測試的最終結(jié)果如表1所示。

從表1可以看出，就單峰函數(shù)（f1、f2）而言，CPSO算法與標(biāo)準(zhǔn)PSO算法、CSPSO算法相比，在具有更高精度的同時，解的穩(wěn)定性顯著提高，而且可以很輕易的找到全局最優(yōu)解；其中，標(biāo)準(zhǔn)PSO算法和CSPSO算法也均可收斂到相應(yīng)容忍度下限，且CSPSO算法優(yōu)于標(biāo)準(zhǔn)PSO算法。在有眾多局部極值點的多峰函數(shù)（f3、f4）中，CPSO算法同樣顯著提高了解的質(zhì)量，并且在f3函數(shù)上獲得全局最優(yōu)解；對多峰函數(shù)f4而言，子種群并行協(xié)作和基于種群最優(yōu)資源檔案池深度搜索策略能夠有效提高算法解的質(zhì)量，得到了精度較好的解。CPSO算法之所以能在大多數(shù)的函數(shù)上改善解的質(zhì)量，是因為采用子種群并行策略使算法避免了算法陷入局部最優(yōu)，擴大全局尋優(yōu)空間；云模型的深度搜索充分利用歷史信息加強算法局部搜索性能。

表1　算法性能測試結(jié)果

上述結(jié)果表明，通過布谷鳥群、共享種群最優(yōu)資源檔案池、云模型等機制的引入，提高了全局開發(fā)和局部開采的性能。粒子群和布谷鳥共享尋優(yōu)信息，提高了開發(fā)范圍；云模型更加精確的完善了局部開采機制。總之，新機制的引入解決了粒子群算法在高維復(fù)雜函數(shù)尋優(yōu)中，容易早熟收斂、尋優(yōu)精度不高的問題。通過實驗與分析，為達到更優(yōu)的算法效能，推薦布谷鳥種群大小適宜設(shè)置為30，此時尋優(yōu)效果和算法復(fù)雜度都可滿足實際應(yīng)用的要求。

4　結(jié)論

本文提出的混合粒子群優(yōu)化算法（CPSO），解決了標(biāo)準(zhǔn)PSO算法易陷入局部最優(yōu)解、不能保證全局收斂的問題。采用Kent混沌初始化，并結(jié)合CS算法和PSO算法的特性，在云模型的基礎(chǔ)上，提出了在函數(shù)優(yōu)化方面具有全局收斂性的CPSO算法。實驗證明，CPSO比其他算在搜索精度、解的質(zhì)量及收斂性能上都更具優(yōu)勢，尤其在求解多維函數(shù)優(yōu)化問題上是具有競爭力的，因此，將CPSO算法應(yīng)用到工程優(yōu)化、智能調(diào)度、信息融合、態(tài)勢感知、聚類分析等諸多領(lǐng)域是具有廣闊前景的。

［1］李洪明.多域光網(wǎng)絡(luò)中基于博弈論的智能優(yōu)化生存性算法設(shè)計與仿真實現(xiàn)［D］.沈陽：東北大學(xué)，2010.

［2］李寶磊，施心陵，茍常興，等.多元優(yōu)化算法及其收斂性分析［J］.自動化學(xué)報，2015，41（5）：949-959.

［3］劉洪波，王秀坤，譚國真.粒子群優(yōu)化算法的收斂性分析及其混沌改進算法［J］.控制與決策，2006，21（6）：636-645.

［4］彭智，謝玲.混合優(yōu)化算法的全局收斂性分析［J］.北京理工大學(xué)學(xué)報，2012，32（4）：435-440.

［5］朱奇光，王洪瑞.IC-PSO算法的收斂性分析及應(yīng)用研究［J］.光電工程，2010，37（4）：108-112.

［6］方偉，孫俊，謝振平，等.量子粒子群優(yōu)化算法的收斂性分析及控制參數(shù)研究 ［J］.物理學(xué)報，2010，59（6）：3686-3694.

［7］梁瑞鑫，鄭德玲.基于區(qū)間套混沌搜索的混合優(yōu)化方法［J］.北京科技大學(xué)學(xué)報，2002，24（3）：342-344.

［8］張勇，單承贛.Kent混沌偽隨機碼的性能研究［J］.合肥工業(yè)大學(xué)（自然科學(xué)版），2003，26（2）：227-231.

［9］Yang X S，Deb S.Cuckoo search via Lévy flights［C］.In：Proc.of the World Congress on Nature and Biologically Inspired Computing. 2009：210214.

［10］李德毅.不確定性人工智能［M］.北京：國防工業(yè)出版社，2005.

［11］高溥，王寅杰，李宗剛，等.無確定度逆向云模型新算法［J］.計算機應(yīng)用研究，2013，30（8）：2262-2265.

［12］代勁，宋娟，胡娟，等.云模型與文本挖掘［M］.北京：人民郵電出版社，2013.

［13］Solis F，Wets R.Minimization by Random Search Techniques［J］. Mathematics of Operations Research，1981，6：19-30.

［14］王凡，賀興時，王燕，等.基于CS算法的Markov模型及收斂性證明［J］.計算機工程，2012，38（11）：180-185.

［15］王麗芳，曾建潮.基于微粒群算法與模擬退火算法的協(xié)同進化方法 ［J］.自動化學(xué)報，2006，32（4）：630-635.

［16］Kennedy J，Eberhart R.Particle swarm optimization［A］.Proc. of the IEEE Int'l Conf.on Neural Networks［C］.1995：1942 1948.

［17］Wang F，He X S，Luo L G，et al.Hybrid optimization algorithm of PSO and cuckoo search［A］.Proc.of the 2nd Int'l Conf.on Artificial Intelligence，Management Science and Electronic Commerce（AIMSEC）［C］.2011.1172-1175.

Composite Particle Swarm Optimization and Analysis of Convergence

Dong Hang，Gao Zhiqiang，Li Shuyuan，Guo Hongxia，Cheng Chuan
（University of CAPF，Xi'an710086，China）

In order to cope with low accuracy and disability in convergence of PSO，a composite PSO algorithm is proposed，combined with Kent mapping，cloud model and cuckoo search.Furthermore，chaotic initialization，exploration and exploitation as well as multi-swarm strategies are adopted.In addition，convergence analysis and time complexity of CPSO are conducted.Finally，experiment results of standard benchmark function show that compared with traditional methods，our proposed algorithm is excellent in both convergence，accuracy and robustness.

composite particle swarm optimization；cloud model；chaos mapping；cuckoo search；convergence analysis

1671-4598（2016）05-0146-04

10.16526/j.cnki.11-4762/tp.2016.05.042

TP393

A

2015-09-08；

2015-12-15。

國家自然科學(xué)基金項目（61309008）。

董航（1992-），男，黑龍江哈爾濱人，碩士研究生，主要從事統(tǒng)計學(xué)和智能優(yōu)化算法方向的研究。

高志強（1989-），男，黑龍江齊齊哈爾人，碩士研究生，主要從事智能優(yōu)化算法方向的研究。