基于粒子群的混合智能優化算法收斂性分析

武警工程大學 高見文 葛衛麗

武警杭州士官學校 郭 程

基于粒子群的混合智能優化算法收斂性分析

武警工程大學 高見文 葛衛麗

武警杭州士官學校 郭 程

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

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

1.引言

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

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

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

圖1　混合算法流程圖

在初始化后，PSO算法和遺傳算法并行進化，并將各自最優解存儲于全局最有數據庫，當滿足結束條件時，算法終止，在種群全局最優數據庫中選取全局最優粒子輸出。

3.混合算法收斂性分析

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

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

準則1要求隨機搜索算法D是廣義單調非遞增的，從而保證適應度值f（x）是非遞增的。

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

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

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

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

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

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

定理：設混合算法優化的目標函數f是一個可測函數，其解空間S為Rn上可測子集，并且混合算法滿足隨機搜索算法全局收斂的準則1和準則2，設是混合算法所產生的解序列，則：

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

證明：

依據混合算法協同部分的流程，迭代函數F可定義為：

因為混合算法利用全局最優數據庫保留種群最優解，即采用適應度值非遞增的精英保留策略，可知算法滿足準則1。

如果混合算法滿足準則件2，則規模為n的混合種群樣本采樣空間的并集一定包含目標函數f的解向量空間S，即：

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

令Yk為遺傳算法在第k次迭代時搜索到的解。因為單獨執行云遺傳算法得到的解序列｛Yk｝以概率l全局收斂于最優區域Rε，M。因此，在混合算法中，對于有限個滿足f（Yk）〉f（Pg，k）的解Yk，可令其下一狀態為Pg，k，并將其存儲于全局最優數據庫中，而且該機制對云遺傳算法全局收斂性沒有影響，即在混合算法中恒有公式（6）成立，也就是說，當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）的超矩形。

當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。隨著迭代次數k增加，逐漸減少，從而存在整數k1，當k〉k1時，，但是因為有支撐集Mi0，k=S，所以。令S的Borel子集A=Mi，k，則v（A）〉0，且（18）式成立，從而混合算法滿足準則2。

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

4.結論

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

［1］張慧斌，王鴻斌，胡志軍.PSO算法全局收斂性分析［J］.計算機工程與應用，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］梁旭，黃明，寧濤，等.現代智能優化混合算法及其應用［M］.北京：電子工業出版社，2014：70-72.

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

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