基于聚類的多子群粒子群優(yōu)化算法

基于聚類的多子群粒子群優(yōu)化算法

受人工生活研究結(jié)果的啟發(fā)，kneya和berry在1995年提出了隨機排列優(yōu)化算法。由于粒子群優(yōu)化算法簡單、容易實現(xiàn),因此粒子群優(yōu)化算法一提出,立刻引起了演化計算等領域的學者們的廣泛關(guān)注,在短短幾年時間里出現(xiàn)大量的研究成果,并已廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模式分類、模糊系統(tǒng)控制以及其他的應用領域。本文在基本粒子群優(yōu)化算法基礎上,提出了基于聚類的粒子群優(yōu)化算法。1基于約束的d維的建立粒子群優(yōu)化算法最先由Eberhart博士和Kennedy博士在文獻中提出,它是一種基于群體的具有全局尋優(yōu)能力的優(yōu)化工具。它通過迭代搜尋最優(yōu)值,系統(tǒng)初始化為一組隨機解,而粒子(潛在的解)在解空間追隨最優(yōu)的粒子進行搜索。假設在一個D維的目標搜索空間中,有N個粒子組成一個群體,其中第i個粒子表示為一個D維的向量xi,i=1,2,…,N,即第i個粒子在D維的搜索空間中的位置是xi。每個粒子的位置就是一個潛在的解。將xi帶入一個目標函數(shù)就可以計算出其適應值,根據(jù)適應值的大小衡量xi的優(yōu)劣。第i個粒子的“飛行”速度也是一個D維的向量,記為vi,i=1,2,…,N。粒子群優(yōu)化算法采用下列公式對粒子操作:v(t+1)i(t+1)i=v(t)i(t)i+c1r1(p(t)i(t)i-x(t)i)+c2r2(p(t)g-x(t)i)(1)x(t+1)i=x(t)i+v(t+1)i(2)其中,p(t)i(i=1,2,…,N),為第i個粒子迄今為止搜索到的最優(yōu)位置,用式(3)更新:p(t+1)i={p(t)i,f(x(t+1)i≥f(p(t)i)x(t+1)i,f(x(t+1)i)＜f(p(t)i)(3)p(t)g為整個粒子群迄今為止搜索到的最優(yōu)位置,即p(t)g∈{p(t)1,p(t)2,…,p(t)Ν|f(p(t)g)=min{f(p(t)1),f(p(t)2),…,f(p(t)N)}}(4)其中,學習因子c1和c2是非負常數(shù);r1和r2是介于之間的隨機數(shù)。迭代中止條件根據(jù)具體問題一般選為最大迭代次數(shù)或(和)粒子群迄今為止搜索到的最優(yōu)位置滿足預定最小適應閾值。2求解系統(tǒng)方程穩(wěn)定設G={x1,x2,…,xN}表示N個粒子xi(i=1,2,…,N)組成的數(shù)據(jù)集,被分為K個聚類區(qū)Ci(i=1,2,…,K),記qi(i=1,2,…,K)為每個聚類區(qū)Ci(i=1,2,…,K)中的粒子迄今為止搜索到的最優(yōu)位置。我們采用下式對粒子群中的粒子進行更新:v(t+1)i=v(t)i+c0r0(p(t)i-x(t)i)+Κ∑j=1cjrj(q(t)j-x(t)i)(5)x(t+1)i=x(t)i+v(t+1)i(6)其中,學習因子cj(j=0,1,…,K)是非負常數(shù);rj(j=0,1,…,K)是介于之間的隨機數(shù)。由此得基于聚類的粒子群優(yōu)化算法步驟如下:(1)隨機產(chǎn)生N個粒子及其初始飛行速度的粒子群G={x1,x2,…,xN},確定學習因子cj(j=0,1,…,K);(2)根據(jù)聚類算法確定聚類區(qū)Ci(i=1,2,…,K);(3)求出每個粒子迄今為止搜索到的最優(yōu)位置p(t)i(i=1,2,…,N)和每個聚類區(qū)Ci(i=1,2,…,K)中的粒子迄今為止搜索到的最優(yōu)位置qi(i=1,2,…,K);(4)采用式(5)、式(6)對粒子群中的粒子進行操作;(5)若當前最優(yōu)粒子不滿足收斂條件,則對當前粒子群重新進行聚類確定聚類區(qū)Ci(i=1,2,…,K),轉(zhuǎn)步驟(3);否則迭代過程結(jié)束,返回全局最優(yōu)解。與基本粒子群優(yōu)化算法比較可知:基于聚類的粒子群優(yōu)化算法首先根據(jù)聚類算法把粒子群分為若干“子群”,求出每一“子群”的最優(yōu)位置qi(i=1,2,…,K);然后粒子群中的粒子根據(jù)其個體極值和每個“子群”中的最優(yōu)位置qi(i=1,2,…,K)更新自己的速度和位置值。該算法通過對粒子群的聚類,使粒子之間的信息得以交換,并利用了更多粒子在迭代尋優(yōu)過程中包含的信息,算法的全局收斂性更強?；玖Ｗ尤簝?yōu)化算法僅為基于聚類的粒子群優(yōu)化算法中聚類區(qū)個數(shù)K為1時的一個特例。將式(5)和式(6)整理可得:v(t+1)i=v(t)i-(Κ∑j=0cjrj)x(t)i+c0r0p(t)i+Κ∑j=1cjrjq(t)j(7)x(t+1)i=v(t)i+(1-Κ∑j=0cjrj)x(t)i+c0r0p(t)i+Κ∑j=1cjrjq(t)j(8)即其中,φ=Κ∑j=0cjrj,記則式(9)變?yōu)槭?10)即是一離散時間線性系統(tǒng)方程,該系統(tǒng)方程穩(wěn)定的充要條件是矩陣A的特征值的模均小于1。矩陣A的特征值為λ1,2=2-φ±√(φ-2)2-42(11)當|φ-2|≥2時,其特征值為實值,小于1意味著:-2＜2-φ+√(φ-2)2-4＜2(12)-2＜2-φ-√(φ-2)2-4＜2(13)兩式相加得-2<2-φ<2,這與|φ-2|≥2矛盾,此時該系統(tǒng)方程不穩(wěn)定。當|φ-2|<2時,其特征值為兩個復值,其模小于1即√(2-φ)2+(φ-2)2-4/2=√2(2-φ)2-4/2＜2局勢(14)化簡即0<φ<4,此時該系統(tǒng)方程穩(wěn)定。故,當0<φ<4時,式(10)描述的系統(tǒng)是漸進穩(wěn)定的,亦即基于聚類的粒子群優(yōu)化算法收斂。3算法性能我們以求兩個函數(shù)的最小值為例,通過計算機仿真來說明基于聚類的粒子群優(yōu)化算法的性能,兩個函數(shù)表達式如下:(1)f1(x1,x2)=100(x21-x2)2+(1-x1)2,-2.048≤x1,x2≤2.048,在區(qū)間內(nèi)有一個全局最小值點(1,1),全局最小值為0。(2)f2(x1,x2,x3,x4)=1/4000(x21+x22+x23+x24)-cos(x1)cos(x2/√2)cos(x3/√3)cos(x4/√4)+1?-600≤x1,x2,x3,x4≤600,在區(qū)間內(nèi)有一個全局最小值點(0,0,0,0),全局最小值為0。算法的初始化參數(shù)為粒子群規(guī)模30,聚類數(shù)目即K為3,學習因子c0=0.5,c1=0.5,c2=0.5,c3=0.5。為評價算法的收斂性能,進化次數(shù)設為500,連續(xù)運行10次所得函數(shù)全局最小值點的平均值和全局最小值的平均值作為算法的衡量指標。圖1和圖2分別是函數(shù)f1和f2適應度值的對數(shù)(即每次進化所得全局最小值的對數(shù))隨進化次數(shù)變化的曲線圖(10次獨立運行的平均),每幅圖中,上面一條曲線對應于基本粒子群優(yōu)化算法,而下面一條曲線對應于基于聚類的粒子群優(yōu)化算法。從圖1、圖2中可以看出,基于聚類的粒子群優(yōu)化算法的收斂性能明顯優(yōu)于基本粒子群優(yōu)化算法的