PSO算法收斂性分析研究綜述

陸偉峰

摘要：粒子群算法是當(dāng)前群智能計算中的一個熱點(diǎn)。系統(tǒng)介紹了當(dāng)前PSO算法收斂性分析中的一些重要研究方法，如常微分方程、Lyapunov穩(wěn)定性理論、凸化理論、Markov鏈和隨機(jī)逼近等方法。并指出未來研究的方向。

關(guān)鍵詞：粒子群算法；收斂性分析

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）29-0181-02

粒子群算法（Particle Swarm Optimization，PSO）是模仿鳥類捕食行為的一種仿生算法.由于PSO收斂速度快、參數(shù)少簡潔易操作，是求解連續(xù)優(yōu)化問題的重要方法。但也存在著易陷入局部最優(yōu)值、迭代后期搜索能力不強(qiáng)等缺陷。

為提高PSO的搜索效率，眾多學(xué)者進(jìn)行了研究，提出了各種改進(jìn)方法。遇到的一個難題便是如何保證算法的收斂性。本文系統(tǒng)總結(jié)了近幾年P(guān)SO收斂性分析方面的研究成果，指出了各種算法的特點(diǎn)。并對未來的研究進(jìn)行了展望。

1PSO算法的原理

標(biāo)準(zhǔn)粒子群算法可以表述為：在，J維搜索空間中，m個粒子組成一個種群，t時刻第i個粒子的位置可以表示為Xⁱ_t=（Xⁱ¹_t，Xⁱ²_t，…，X^iD_t），飛行速度可以表示為vⁱ_t=（vⁱ¹_t，vⁱ²_t，…v^iD_t），（i=1，2，…，m）。第i個粒子的歷史最好位置記為Pⁱ_b，整個種群的歷史最優(yōu)位置記為P_g。由于每個粒子是地位均等的，我們省略標(biāo)號i得到每一代粒子的位置X_t和速度v_t的迭代方程為：

其中ω為慣性系數(shù)，c₁，c₂為常數(shù)，通常記c₁+c₂=c，r₁，r₂為[0，1]之間的隨機(jī)數(shù)。

c₁r₁（p_b-X_t）是粒子的認(rèn)知部分，體現(xiàn)了自身的經(jīng)驗(yàn)。c₂r₂（p_g-X_t）是粒子的社會部分，體現(xiàn)了粒子的交互能力。通過這兩項(xiàng)，粒子協(xié)調(diào)局部與全局探索能力，從而達(dá)到全局最優(yōu)值。

2PSO算法的收斂性分析研究進(jìn)展

由于PSO算法是一個隨機(jī)系統(tǒng)，受到隨機(jī)系數(shù)的影響很大，分析比較困難。許多學(xué)者使用各種不同的方法對其進(jìn)行收斂性分析，確定收斂的條件，指導(dǎo)算法的改進(jìn)工作。

2.1基于定常線性系統(tǒng)的收斂性分析

最早并且最廣泛采用的方法是將隨機(jī)數(shù)看做常數(shù)，使用確定性線性系統(tǒng)的穩(wěn)定性分析方法進(jìn)行分析。

Clerc和Kennedy首先采用這一方法，假設(shè)P_b，P_g保持不變，r₁，r₂為常數(shù)，將基本粒子群算法表示為定常線性系統(tǒng)：

其中y_t=p-x_t。

通過計算特征系數(shù)矩陣的特征值小于1，確定收斂條件下參數(shù)的取值范圍。

孫湘等在文獻(xiàn)中不考慮隨機(jī)分量，將帶慣性權(quán)重的粒子群算法表示為一個線性系統(tǒng)：

根據(jù)動力系統(tǒng)穩(wěn)定性理論，系統(tǒng)穩(wěn)定的一個充分條件是系數(shù)矩陣的特征值λ₁，λ₂滿足max{|λ₁|，|λ₂|}<1，由此得到系統(tǒng)穩(wěn)定收斂的條件是0<ω<1且0

這一方法將隨機(jī)系統(tǒng)轉(zhuǎn)化為定常線性系統(tǒng)，簡化了問題，但沒有考慮隨機(jī)分量，削弱了結(jié)論的適用范圍。這些結(jié)論既不是充分條件也不是必要條件。

2.2基于隨機(jī)過程的收斂性分析

文獻(xiàn)將PSO算法化為

2.4基于凸化理論和概率收斂理論的收斂性分析

文獻(xiàn)則使用凸性理論和概率收斂理論，分析得到在不考慮隨機(jī)性的條件下，對于單峰值函數(shù)，粒子群收斂于全局最優(yōu)位置，而對多峰值函數(shù)，未必能最終收斂于全局最優(yōu)位置。在考慮隨機(jī)性后，無論單峰值還是多峰值函數(shù)，粒子群都能依概率收斂于最優(yōu)位置。

該方法較好的給出了收斂條件、收斂速度及誤差估計。但是假設(shè)的前提條件比較多，需要進(jìn)一步研究更一般的條件下的收斂性。

3總結(jié)與展望

本文對粒子群算法近幾年有關(guān)收斂性分析方面的研究進(jìn)展進(jìn)行了概況和總結(jié)。由于粒子群算法是一個復(fù)雜的非線性隨機(jī)系統(tǒng)，對其收斂性分析的研究還在不斷深入。通過分析現(xiàn)有研究成果，對PS0收斂性分析的工作總體呈現(xiàn)以下趨勢：

1）研究方法的不斷拓展。目前的研究主要是常系數(shù)微分方程（差分方程）方法和基于隨機(jī)過程的分析、基于Markov鏈的分析等隨機(jī)分析方法。針對IX50算法的特點(diǎn)，隨機(jī)逼近等隨機(jī)方法將可能繼續(xù)深入研究，Mann迭代序列等迭代算法可能用于PSO的收斂性分析。

2）從單粒子的收斂性分析，轉(zhuǎn)向?qū)φ麄€粒子群的收斂性分析?；诙ǔ＞€性系統(tǒng)、隨機(jī)過程、Lvapunov等方法的分析，是對單個粒子的分析，雖然比較成熟，但無法反映整個種群的狀況。而基于Markov鏈、基于隨機(jī)逼近等方法分析了整個種群的收斂性，得到的結(jié)果更具一般性。

3）從基本PSO算法的收斂性分析，延伸到對PSO改進(jìn)算法的收斂性分析，并用于指導(dǎo)算法的改進(jìn)。從PSO算法誕生到現(xiàn)在，眾多學(xué)者投入研究，引入量子行為、混沌等新的尋優(yōu)機(jī)制，提出眾多新穎有效的改進(jìn)算法。這些改進(jìn)算法的收斂性分析也必將成為研究的重點(diǎn)。而分析的結(jié)果也為提高算法的性能提供了理論依據(jù)，指導(dǎo)算法進(jìn)一步提高收斂速度與精度。