基于粒子群的混合智能優(yōu)化算法收斂性分析

武警工程大學(xué) 高見文 葛衛(wèi)麗

武警杭州士官學(xué)校 郭 程

基于粒子群的混合智能優(yōu)化算法收斂性分析

武警工程大學(xué) 高見文 葛衛(wèi)麗

武警杭州士官學(xué)校 郭 程

本文針對粒子群算法（PSO）存在的不能以概率1全局收斂以及易陷入早熟收斂等問題，提出將PSO算法和遺傳算法（GA）相結(jié)合的混合算法，采用并聯(lián)模式實現(xiàn)了兩種算法的協(xié)同進化，并證明了算法能夠以概率1全局收斂。

粒子群算法；遺傳算法；混合算法

1.引言

PSO算法是一種得到廣泛應(yīng)用的智能優(yōu)化算法，因其算法簡單、收斂性快等優(yōu)點，在復(fù)雜優(yōu)化問題、人工智能以及聚類分析等領(lǐng)域都有廣泛的應(yīng)用。但是PSO算法也存在著易陷入早熟收斂、不能以概率1全局收斂的問題［1］。而采用最優(yōu)保留策略的遺傳算法雖然存在著收斂速度慢等問題，但是其具有全局收斂性，能夠以概率1全局收斂。因此將兩種算法結(jié)合起來組成混合算法，能夠有效利用兩者的優(yōu)點，優(yōu)勢互補，彌補不足。

2.PSO算法和GA算法的混合模式

PSO算法和GA算法的混合算法流程圖如下：

圖1　混合算法流程圖

在初始化后，PSO算法和遺傳算法并行進化，并將各自最優(yōu)解存儲于全局最有數(shù)據(jù)庫，當(dāng)滿足結(jié)束條件時，算法終止，在種群全局最優(yōu)數(shù)據(jù)庫中選取全局最優(yōu)粒子輸出。

3.混合算法收斂性分析

Solis和Wets［2］給出了一般隨機搜索算法收斂性判定準(zhǔn)則及相關(guān)定理，一般最優(yōu)化問題可記為〈A，f〉，對于隨機搜索算法D，其第k次尋優(yōu)結(jié)果為Xk，下一次迭代尋優(yōu)結(jié)果為Xk+1=D（Xk，ζk）。其中，A為Rn上某個子集的σ-域，f為適應(yīng)度函數(shù)，ζk為算法D尋優(yōu)過程中找到的解。

準(zhǔn)則1：算法D滿足f（D（x，ζ））≤f（x），若ζ∈A，則f（D（x，ζ））≤f（ζ）。

準(zhǔn)則1要求隨機搜索算法D是廣義單調(diào)非遞增的，從而保證適應(yīng)度值f（x）是非遞增的。

準(zhǔn)則2：對于A的任意Borel子集P，若滿足v（P）〉0，則有：

其中，μk（P）為算法D在第k次迭代中搜索到的解在集合P上的概率測度。準(zhǔn)則2說明，只要是可行解空間A中概率測度大于零的子集P，算法D連續(xù)無窮次搜索不到集合P中解的概率為0。

引理：若函數(shù)f可測，可測空間A是Rn上可測子集，且算法D滿足條件1和條件2，是算法D產(chǎn)生的解序列，則：

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

文獻(xiàn)［1］指出PSO算法不能以概率1收斂于全局最優(yōu)解，利用K-means算法原理計算適應(yīng)度的過程不影響混合算法的收斂性，文獻(xiàn)［3］證明種群初始化不會直接影響算法收斂性，因此證明混合算法的全局收斂性，僅需證明PSO算法和云遺傳算法的協(xié)同過程的全局收斂性。

文獻(xiàn)［4］應(yīng)用齊次有限馬爾科夫鏈分析并證明了保留最優(yōu)個體的遺傳算法以概率1全局收斂。

定理：設(shè)混合算法優(yōu)化的目標(biāo)函數(shù)f是一個可測函數(shù)，其解空間S為Rn上可測子集，并且混合算法滿足隨機搜索算法全局收斂的準(zhǔn)則1和準(zhǔn)則2，設(shè)是混合算法所產(chǎn)生的解序列，則：

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

證明：

依據(jù)混合算法協(xié)同部分的流程，迭代函數(shù)F可定義為：

因為混合算法利用全局最優(yōu)數(shù)據(jù)庫保留種群最優(yōu)解，即采用適應(yīng)度值非遞增的精英保留策略，可知算法滿足準(zhǔn)則1。

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

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

令Yk為遺傳算法在第k次迭代時搜索到的解。因為單獨執(zhí)行云遺傳算法得到的解序列｛Yk｝以概率l全局收斂于最優(yōu)區(qū)域Rε，M。因此，在混合算法中，對于有限個滿足f（Yk）〉f（Pg，k）的解Yk，可令其下一狀態(tài)為Pg，k，并將其存儲于全局最優(yōu)數(shù)據(jù)庫中，而且該機制對云遺傳算法全局收斂性沒有影響，即在混合算法中恒有公式（6）成立，也就是說，當(dāng)f（Yk）〈f（Pg，k）時，存在一個粒子i0，其支撐集Mi0，k=S。

而對于其它粒子i，

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

當(dāng)max｛c1|Pi-X（t-1）|，c2|Pg-X（t-1）|｝〈0.5diameterj（S）時，有：v（Mi，k∩S）〈v（S），其中，diameterj（S）表示解向量空間S在第j維分量的長度。因xi收斂到平衡點（φ1Pi+φ2Pg）/（φ1+φ2），所以Mi，k長度趨于0。隨著迭代次數(shù)k增加，逐漸減少，從而存在整數(shù)k1，當(dāng)k〉k1時，，但是因為有支撐集Mi0，k=S，所以。令S的Borel子集A=Mi，k，則v（A）〉0，且（18）式成立，從而混合算法滿足準(zhǔn)則2。

綜上所述，混合算法的PSO算法和遺傳算法的協(xié)同部分，滿足隨機搜索算法全局收斂的判定準(zhǔn)則1和判定準(zhǔn)則2。因此混合算法的搜索序列以概率1收斂于全局最優(yōu)解，即混合算法具有全局收斂性。

4.結(jié)論

本文首先對PSO算法和GA算法的優(yōu)缺點進行了介紹，在此基礎(chǔ)上介紹了二者混合協(xié)同進化的模型，并對混合算法的收斂性進行了分析，證明了混合算法能夠以概率1收斂到全局最優(yōu)解。

［1］張慧斌，王鴻斌，胡志軍.PSO算法全局收斂性分析［J］.計算機工程與應(yīng)用，2011，47（34）：61-63.

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

［3］梁旭，黃明，寧濤，等.現(xiàn)代智能優(yōu)化混合算法及其應(yīng)用［M］.北京：電子工業(yè)出版社，2014：70-72.

［4］惲為民，席裕庚.遺傳算法的全局收斂性和計算效率分析［J］.控制理論與應(yīng)用，1996，13（4）：455-459.

高見文（1991—），山東臨沂人，碩士研究生，現(xiàn)就讀于武警工程大學(xué)。