【文章內(nèi)容簡介】 ),pg(t)與的變化之間存在著類似梯度信息的規(guī)律。那么當(dāng)搜索時間無限時， f(pi(t)),f(Pg(t))和pi(t),pg(t)在粒子群搜索的初期過程中會變化比較劇烈，隨后 pi(t),pg(t)將逐步逼近某個值，而 f(pi(t)), f(Pg(t))也將趨于穩(wěn)定或停滯，因此系統(tǒng)后期的輸入pi(t),pg(t)可以被看作是一個階躍函數(shù)，在不考慮隨機(jī)成分的情況下系統(tǒng)的輸出將能夠跟蹤上 粒子運動軌跡的分析（續(xù)） 粒子群在多數(shù)實際尋優(yōu)過程中無論是找到了最優(yōu)解或是陷入某個局部最優(yōu)解，還是算法停滯，整個過程中的 gBest變化將會逐步減小，最終趨于停止， pBest將逐步趨向 gBest。因此當(dāng)搜索時間無限時，所有粒子的位置將逐步靠近并停止于 處。粒子運動軌跡的分析（續(xù)） 在隨機(jī)啟發(fā)式優(yōu)化算法中隨機(jī)量的作用是非常重要的，正是隨機(jī)量所帶來的不確定性給整個粒子群帶來了多樣性和創(chuàng)新。去掉隨機(jī)量后，單個粒子的運動過程成為了一個二階線性系統(tǒng)，使得分析變得比較簡單，但這個便于分析的假設(shè)條件使得以上對粒子運動行為的分析具有很大的局限性。下面將進(jìn)一步討論隨機(jī)量對粒子運動行為的影響。粒子運動軌跡的分析（續(xù)） 為便于分析，式（ ）中初始值取 ，并對也取 Z變換可得到： （ ） 不考慮 與 之間存在的弱反饋關(guān)系，式（ ）所對應(yīng)的系統(tǒng)如圖。 粒子運動軌跡的分析（續(xù)）粒子運動軌跡的分析（續(xù)） 由仿真實例可以看出，當(dāng) PSO參數(shù)不滿足式（ ）的條件時，粒子的運動軌跡也可能收斂到 ；而當(dāng) PSO參數(shù)滿足式（ ）的條件時，粒子的運動軌跡卻不一定能保證收斂到一個固定位置。顯然，隨機(jī)性的存在使得粒子運動軌跡是否收斂到一個固定點并不完全遵照式（ ）所給出的規(guī)律。 粒子運動軌跡的分析（續(xù)） 實驗研究發(fā)現(xiàn)，粒子群中粒子運動軌跡收斂到固定點的概率與參數(shù)選擇存在著密切關(guān)系。當(dāng)參數(shù)不滿足式（ ）所給出條件時，絕大多數(shù)粒子的運動軌跡都是不收斂到一個固定點的，除了一些特例，例如粒子群中某個粒子找到全局最優(yōu)解，且當(dāng)前速度為 0，則該粒子運動軌跡肯定收斂。當(dāng)參數(shù)滿足式（ ）所給出條件時，參數(shù)越接近條件的邊界粒子運動軌跡收斂的幾率越小，反之越大。一般而言， w越大不收斂的概率越大， c c2越大不收斂的概率越大，其中 w的影響更大些。 另外，粒子運動軌跡不收斂到固定點時，其振蕩幅值與參數(shù)選擇也存在著密切關(guān)系。當(dāng)參數(shù)不滿足式（ ）時，振蕩幅值很大，甚至發(fā)散；滿足式（ ）時，振蕩幅值要小許多，且振蕩的幅值在一定范圍內(nèi)，在某種意義上粒子處于廣義穩(wěn)定狀態(tài)，這樣的狀態(tài)對粒子群的搜索是有益的。其中 w越大振蕩幅值越大， c c2越大振蕩幅值越大，其中的影響更大些。 粒子運動軌跡的分析（續(xù)） 粒子群中的粒子運動軌跡處于發(fā)散振蕩狀態(tài)顯然是對算法收斂無益的，而處于幅值有限的振蕩狀態(tài)對算法是有非常重要的作用。粒子運動軌跡振蕩幅值很大時可以看作是算法的開拓能力強(qiáng)，而當(dāng)粒子軌跡振蕩幅值較小時則是開掘能力強(qiáng)。是否能通過 PSO參數(shù)的選擇來調(diào)整粒子運動軌跡的振蕩幅值呢？ 粒子運動軌跡的分析（續(xù)）粒子運動軌跡的分析（續(xù)） 若 PSO參數(shù)一直滿足條件（ ） ,則粒子運動軌跡振蕩的幅值是有限的。這個二階振蕩環(huán)節(jié)的阻尼系數(shù)為： （ ） 二階振蕩系統(tǒng)的阻尼系數(shù)越小，系統(tǒng)振蕩的幅值越大。式（ ）表明，盡管存在隨機(jī)量，但通過選擇和調(diào)節(jié) PSO參數(shù)還是可以對粒子的振蕩幅值實現(xiàn)控制的。 粒子運動軌跡的分析（續(xù)） 以上討論說明，條件（ ）還是非常有意義的。針對優(yōu)化問題的特點，通過式（ ）和（ ）可以選擇合理的 PSO參數(shù)，調(diào)整粒子運動軌跡的振蕩幅值使得粒子群的開拓能力和開掘能力均能得到兼顧，從而可提高算法的成功率。另外，還可以在運算過程中動態(tài)地改變參數(shù)，使得粒子的運動的振蕩幅度由大到小，在搜索的前期粒子更多地體現(xiàn)開拓能力，而后期粒子更多地發(fā)揮開掘能力。因此，式（ ）和（ ）是有重要價值的，有助于實際應(yīng)用 PSO算法參數(shù)擇和使用的理論公式和條件。 粒子運動軌跡的分析（續(xù)）PSO算法收斂性分析 隨機(jī)算法收斂的標(biāo)準(zhǔn) 對于優(yōu)化問題 ，有隨機(jī)優(yōu)化算法 D，第 k次迭代的結(jié)果 XK，下一次迭代的結(jié)果為 ，其中 是算法 D這次迭代中曾經(jīng)搜索過的解。 條件 H1： ，且若 ，則有 。 條件 H1可保證隨機(jī)算法的正確性，其目的是希望能保證優(yōu)化算法的解的適應(yīng)度值是非遞增的。PSO算法 收斂性分析 (續(xù) )條件 H2： 對 ，有： 。 其中 為算法第 k次迭代的結(jié)果在集合 B上的概率測度。算法滿足條件 H2意味著， A中任意滿足 的子集 B，算法 D連續(xù)無窮次未搜索到 A中點的幾率為 0。因為 ，那么滿足條件的算法連續(xù)無窮次搜索不到近似全局最優(yōu)點的概率為 0。條件 H3： 對 ， 為緊集，且 ， 和 ，有：PSO算法 收斂性分析 (續(xù) ) 定理 （算法全局收斂）： 假設(shè) f是可測度的，可行解空間 A是 Rn上可測度的子集，算法 D滿足條件 (H1)(H2)， 是算法 D產(chǎn)生數(shù)列，則有： 定理 （算法局部收斂） ：假設(shè) f是可測度的，可行解空間 A是 Rn上可測度的子集，算法滿足條件 (H1)(H3)， 是算法D產(chǎn)生數(shù)列，則有：PSO算法 收斂性分析 (續(xù) ) 定義 （粒子狀態(tài)和粒子狀態(tài)空間） 粒子的位置 x，速度 v以及歷史最佳位置 p（ pBest）構(gòu)成粒子的狀態(tài)O=(x,v,p)，簡稱粒子，其中 x,p在可行解集 A中，且x,p∈ A,在速度范圍 [vmin,vmax]內(nèi)。所有可能的粒子狀態(tài)的集合構(gòu)成粒子狀態(tài)空間 簡稱粒子空間。 定義 （粒子群狀態(tài)和粒子群狀態(tài)空間） 粒子群中所有N個粒子的狀態(tài)的集合稱為粒子群狀態(tài)，簡稱粒子群 。所有可能的粒子群狀態(tài)的集合構(gòu)成粒子群狀態(tài)空間 。 PSO算法 收斂性分析 (續(xù) )定義 （粒子群等價） 對于 ，記 ，其中 表示事件 A的示性函數(shù)， 表示粒子群狀態(tài)中包含粒子狀態(tài)的數(shù)目。若有兩個粒子群 ，對于 ，若有 ，則稱 S1和 S2等價，記作～ 。定理 “～ ”是 S上的等價關(guān)系。 PSO算法 收斂性分析 (續(xù) )v 定義 （粒子群狀態(tài)等價類） 由等價關(guān)系“~”在 S上誘導(dǎo)的粒子群狀態(tài)等價類記作L=~/S，簡稱粒子群等價類。 v 定理 等價關(guān)系 “~”在 S上誘導(dǎo)的等價類劃分 L=~/S的個數(shù)為： PSO算法 收斂性分析 (續(xù) )v 定理 在數(shù)字計算機(jī)實現(xiàn)的標(biāo)準(zhǔn) PSO算法中，粒子群狀態(tài)序列 是有限齊次Markov鏈。v 定理 在數(shù)字計算機(jī)實現(xiàn)的標(biāo)準(zhǔn) PSO算法中，粒子群等價類狀態(tài)序列 是有限齊次 Markov鏈。PSO算法 收斂性分析 (續(xù) )v 定義 （最優(yōu)粒子狀態(tài)集） 設(shè)優(yōu)化問題 的全局最優(yōu)解為 ，定義粒子最優(yōu)狀態(tài)集 。v 定義 （最優(yōu)粒子群狀態(tài)集） 設(shè)優(yōu)化問題 的全局最優(yōu)解為 ，定義最優(yōu)粒子群狀態(tài)集 。 PSO算法 收斂性分析 (續(xù) )v 定理 PSO算法中，對粒子群狀態(tài)序列 而言，最優(yōu)粒子群狀態(tài)集合 G是狀態(tài)空間 S上的一個閉集。v 定理 當(dāng) 時，狀態(tài)空間 S中至少存在一個 G之外的閉集，即 PSO算法的收斂性分析（續(xù)）SGBPSO算法 收斂性分析 (續(xù) )v 定理 當(dāng) 時， PSO算法是無法保證全局收斂的。v 定理 時， PSO算法是無法保證局部收斂的。 盡管 PSO算法是無法保證收斂的，但這并不意味著 PSO算法的性能不好。本節(jié)研究結(jié)果的意義首先可用于指導(dǎo)算法的改進(jìn)。同時，本節(jié)所提出的方法更是為 PSO算法的理論分析和研究提供了一種新的思路，可在此基礎(chǔ)上對 PSO算法的進(jìn)一步的理論研究。 PSO理論分析的其它可能方法 目前，能對 PSO算法進(jìn)行理論分析的有效數(shù)學(xué)手段還很少，本文了提出的兩個新的分析手段，在微觀上采用差分方程，在宏觀上采用 Markov鏈。除此之外，是否還存在其它的分析方法和手段呢？根據(jù)對其它隨機(jī)算法討論和分析的經(jīng)驗以及 PSO算法的特點，下面對其它可能的分析方法和手段作簡單的討論。 隨機(jī)過程中的其它方法 本文采用了隨機(jī)過程中的 Markov鏈方法對PSO算法做分析。但如果獨立分析粒子群的位置轉(zhuǎn)換序列，它顯然不是一個 Markov鏈，是否可以采用隨機(jī)過程中的其它方法直接對進(jìn)行分析呢？例如，可以把粒子的運動看成一個隨機(jī)變量，它的變化都有著一定的確定性，也存在著一定的不確定性，能否用熵或相對熵來描述粒子運動離散分布的不確定性的大小，從而對算法的收斂率做分析呢？隨機(jī)過程中的其它可能方法（續(xù)） 另外，就 PSO算法迭代的隨機(jī)過程而言，總是希望這個過程在期望值意義下越來越好，這自然應(yīng)當(dāng)是一個下鞅序列，因此可利用鞅收斂定理就可對算法的收斂性進(jìn)行分析。同時也可以看到，要保證算法的收斂，有兩個參數(shù)很重要：一個是過程進(jìn)入滿意解之后下一步脫離滿意解的可能性；另一個是未進(jìn)入滿意解時下一步仍不能進(jìn)入滿意解的可能性。利用這種方法得到結(jié)果可能直觀而且簡練，也許對如何改進(jìn) PSO算法會有重要指導(dǎo)意義。 基于混沌動力學(xué)理論 一個好的 PSO系統(tǒng)既非穩(wěn)定態(tài)也非混沌態(tài)，而是一種處于兩者之間臨界態(tài)的自組織復(fù)雜系統(tǒng)。從系統(tǒng)工程的角度而言， PSO應(yīng)該是一個連續(xù)的非線性動態(tài)系統(tǒng)，因此將復(fù)雜系統(tǒng)的研究方法，將混沌理論中的非線性動力學(xué)引入 PSO的分析和改進(jìn)研究應(yīng)該是非常有前途的。 基于混沌動力學(xué)理論（續(xù)） 此類分析方法能充分體現(xiàn) PSO系統(tǒng)中粒子間的相互作用的意義和隨機(jī)性的價值。但如何采用混沌動力學(xué)理論來描述粒子群系統(tǒng)也存在一些困難，如何定義 PSO系統(tǒng)中的吸引子、軌道、分叉和穩(wěn)定性等概念都是要解決的問題。另外，非線性系統(tǒng)的穩(wěn)定性只能針對某個解來談的，而不能一般地討論系統(tǒng)的穩(wěn)定性，而且系統(tǒng)的