寧必鋒，蘇 琪

（1.吉林化工學(xué)院 理學(xué)院，吉林 吉林 132022；2.吉林市第五中學(xué) 吉林 吉林 132022）

在工程設(shè)計(jì)、機(jī)械制造等許多領(lǐng)域中，求解全局優(yōu)化問題的智能優(yōu)化算法有粒子群優(yōu)化算法、遺傳算法等，筆者考慮使用粒子群優(yōu)化算法。1995年，粒子群優(yōu)化算法被美國的Kennedy和Eberhart首次提出后[1]在各個(gè)領(lǐng)域得到廣泛的應(yīng)用。目前產(chǎn)生了許多改進(jìn)的粒子群優(yōu)化算法。由于混沌具有遍歷性、隨機(jī)性等特點(diǎn)，許多學(xué)者提出了嵌入混沌序列的混合粒子群優(yōu)化算法[2]，這些算法在不同程度上改進(jìn)了粒子群優(yōu)化算法的收斂速度和解的精度。

筆者主要做了如下工作：1）首先將混沌序列初始化與粒子群優(yōu)化算法充分結(jié)合，即在混沌初始化后，繼續(xù)使用混沌序列產(chǎn)生新的粒子位置，使混沌序列遍歷性得以充分利用。2）然后采用離差平方和法對(duì)粒子群進(jìn)行聚類，同時(shí)根據(jù)粒子更新位置的目標(biāo)函數(shù)適應(yīng)值與個(gè)體和全局歷史最好位置目標(biāo)函數(shù)適應(yīng)值進(jìn)行比較，不同的類速度更新公式不同。提出基于離差平方和法的粒子群優(yōu)化算法簡(jiǎn)稱（CPSOW），并且給出了算法流程，通過3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的數(shù)值模擬實(shí)驗(yàn)，結(jié)果表明所提出的算法優(yōu)于其它算法。

1 基于離差平方和法的粒子群優(yōu)化算法

文中所要解決的全局連續(xù)優(yōu)化問題[3]是

其中f（x）是一個(gè)實(shí)函數(shù)，x是一個(gè)實(shí)數(shù)向量。S={x∈S?Rn，aj≤xj≤bj； j=1…n}。

1.1 充分運(yùn)用混沌序列遍歷性質(zhì)

筆者在算法的前期充分利用混沌序列均勻性、遍歷性和隨機(jī)性，避免了在算法后期搜索速度慢。文章采用的混沌序列迭代公式是典型的混沌動(dòng)力學(xué)系統(tǒng)Logistic方程

μ=4，x0∈（0，1） 隨機(jī)數(shù)， 這里 x0是混沌序列的初始值，x0≠{0，0.25，0.5，0.75，1.0}。

事實(shí)上，首先根據(jù)Logistic方程迭代產(chǎn)生大量混沌序列后擇優(yōu)出初始化群體，其次混沌序列隨著算法的循環(huán)繼續(xù)根據(jù)Logistic方程進(jìn)行迭代產(chǎn)生新的混沌序列，根據(jù)混沌序列遍歷性和不重復(fù)性質(zhì)，若是混沌序列產(chǎn)生的最優(yōu)解位置比迄今為止粒子群搜索到的最優(yōu)解位置還要好，就用這個(gè)位置替代粒子群中某一個(gè)粒子的位置。

1.2 離差平方和法

離差平方和法[4]是Ward在1936提出來的，也稱為Ward法。它基于方差分析思想，如果類分的正確，則同類樣品之間的離差平方和法應(yīng)當(dāng)較小，不同類的樣品之間的離差平方和應(yīng)當(dāng)較大。

假定已將 n 個(gè)樣品分為 m 類，記為 G1，G2，…，Gm，nw表示Gw類的樣品個(gè)數(shù)，表示Gw的重心 （重心就是屬于該類樣品的均值）。 Xwi表示 Gw中第 i個(gè)樣品（i=1，…，nw），則 Gw中樣品的離差平方和為

其中，Xwi，為 s維向量，Qw為一數(shù)值（w=1，2，…，m）。m個(gè)類的總離差平方和為

當(dāng)m固定時(shí)，要選擇使Q達(dá)到極小的分類。

Ward法的基本思想是，先將n個(gè)樣品各自成一類，此時(shí)Q=0；然后每次將其中某兩類合并為一類，因每縮小一類離差平方和就要增加，每次選擇使Q增加最小的兩類進(jìn)行合并，直至所有的樣品合并為一類為止。

1.3 粒子目標(biāo)函數(shù)值分類過程

根據(jù)新粒子位置的目標(biāo)函數(shù)值[5]，可以將粒子分成3類，并由此改變粒子更新速度公式。

第一步：當(dāng)搜索更新的粒子的目標(biāo)函數(shù)適應(yīng)值不如先前粒子最好個(gè)體的目標(biāo)函數(shù)適應(yīng)值時(shí)，符合以上條件的粒子用公式（5）來進(jìn)行速度更新。用pbesti表示粒子本身所找到的最好解，叫做個(gè)體極值點(diǎn)。用gbesti表示整個(gè)種群目前找到的最好解，稱為全局極值點(diǎn)。其中r1和r2是隨機(jī)數(shù)，0≤r1≤1，0≤r2≤1；1≤i≤N，1≤j≤N；c1和 c2是加速因子，0

第二步：當(dāng)搜索更新的粒子的目標(biāo)函數(shù)適應(yīng)值好于先前粒子最好個(gè)體的目標(biāo)函數(shù)適應(yīng)值，但是不如整個(gè)粒子群迄今為止搜索到的最優(yōu)解的目標(biāo)函數(shù)值時(shí)。用更新的粒子位置代替自己先前最好位置，符合以上條件的粒子用公式（6）來進(jìn)行速度更新。，而且還要比較出這一類中目標(biāo)函數(shù)適應(yīng)值最好的粒子位置設(shè)為:pklc。

其中pklc表示第k代這個(gè)類中最優(yōu)解的位置。

第三步：當(dāng)搜索更新的粒子的目標(biāo)函數(shù)適應(yīng)值好于整個(gè)粒子群迄今為止搜索到的最優(yōu)解的目標(biāo)函數(shù)適應(yīng)值時(shí)，并且在迭代公式（6）中粒子先前個(gè)體最好位置項(xiàng)依然應(yīng)用，符合以上條件的粒子用公式（7）來進(jìn)行速度更新，而且還要繼續(xù)比較出這一類中目標(biāo)函數(shù)適應(yīng)值最好的粒子位置設(shè)為:pkgc。

其中pkgc表示第k代這個(gè)類中最優(yōu)解的位置。

2 文中提出的算法流程

CPSOW算法步驟[3]如下：

1）初始化：

步驟1初始化迭代次數(shù)k=0、最大迭代次數(shù)kmax=3 000、維數(shù)n=50、種群個(gè)數(shù)N=30，利用混沌序列在n維問題空間中初始化N粒子的位置（xki，i=1，2…N）利用混沌序列在n維問題空間中初始化N粒子的速度（vki，i=1，2…N）

步驟2利用公式（1）計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值f（xki）。

步驟3初始化粒子的各自最好位置，預(yù)分配個(gè)體最好位置 pki=xki且 f（pki）=f（xki）（i=1，…N），初始化當(dāng)前代全局最優(yōu)解的位置，尋找

并且初始化pkg=pgkbest和 f（pkg）=f（pgkbest）。

2）優(yōu)化過程（重復(fù)迭代直到滿足停止循環(huán)的條件）

步驟1在當(dāng)前代中繼續(xù)計(jì)算初始化的混沌序列并且轉(zhuǎn)化混沌序列為粒子的位置和速度。

步驟2執(zhí)行離差平方和法聚類過程和粒子目標(biāo)函數(shù)值分類過程，然后進(jìn)行速度更新。

步驟3根據(jù)公式xki+1=xki+vki+1來更新粒子位置xki，根據(jù)公式（1）來計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值 f（xki）。

步驟4更新個(gè)體最好目標(biāo)函數(shù)適應(yīng)值：若是粒子的當(dāng)前代目標(biāo)函數(shù)適應(yīng)值優(yōu)于自己歷史最好值，那么就用當(dāng)前代粒子的位置代替先前粒子的位置；并且更新迄今為止全局最好目標(biāo)函數(shù)適應(yīng)值：比較所有粒子適應(yīng)值，選取優(yōu)于歷史全局最好適應(yīng)值的粒子位置替代先前全局最優(yōu)解的粒子位置。

步驟5增加迭代步數(shù) k=k+1。

3）停止迭代的條件被滿足。全局最優(yōu)解pkgbest和目標(biāo)函數(shù)值 f（Pkgbest）。

3 算法仿真實(shí)驗(yàn)與比較研究

文中采用文獻(xiàn)[6]中3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)：Sphere函數(shù)、Rosenbrock函數(shù)、Rastrigin函數(shù)來驗(yàn)證算法的性能，算法停止的兩個(gè)標(biāo)準(zhǔn)：達(dá)到迭代的最大步數(shù)或者是達(dá)到最小誤差限。為了評(píng)價(jià)基于混沌的聚類粒子群優(yōu)化算法（CPSOW）的性能，采用了4種統(tǒng)計(jì)參數(shù)：最好值（最優(yōu)解）、最優(yōu)解的平均值、最優(yōu)解的標(biāo)準(zhǔn)差、最優(yōu)解滿足精度所需要的步數(shù)，并且與標(biāo)準(zhǔn)粒子群優(yōu)化算法（SPSO）、混沌粒子群優(yōu)化算法（CPSO）、慣性權(quán)重線性遞減粒子群優(yōu)化算法 (LDIWPSO）進(jìn)行比較分析。對(duì)于SPSO，CPSO，LDIWPSO 的參數(shù)設(shè)置分別參照了文獻(xiàn) [7]、[8]。運(yùn)用軟件MATLAB(Version7.4）進(jìn)行模擬數(shù)值實(shí)驗(yàn)，實(shí)驗(yàn)進(jìn)行100次，表中粗體數(shù)值表示同類別數(shù)據(jù)中最好者。

4 實(shí)驗(yàn)結(jié)果分析

根據(jù)表1~表3主要的分析和比較如下：

表1 Sphere函數(shù)各算法的比較結(jié)果Tab.1 Resu lts com parision of four algorithm s for Sphere function

表2 Rosenbrock函數(shù)各算法的比較結(jié)果Tab.2 Results comparision of four algorithms for Rosenbrock function

表3 Rastrigin函數(shù)各算法的比較結(jié)果Tab.3 Results comparision of four algorithms for Rastrigin function

圖1 Sphere函數(shù)最好解函數(shù)適應(yīng)值變化趨勢(shì)圖Fig.1 Comparison of best fitness trendlines for the Sphere function

圖3 Rastrigin函數(shù)最好解函數(shù)適應(yīng)值變化趨Fig.3 Comparison of best fitness trendlines for the Rastrigin function

圖2 Rosenbrock函數(shù)最好解函數(shù)適應(yīng)值變化趨勢(shì)圖Fig.2 Comparison of best fitness trendlines for the Rosenbrock function

1）在所有函數(shù)優(yōu)化問題測(cè)試中，CPSOW算法都提高了最優(yōu)解的精度，在函數(shù)Sphere，Rastrigin比較中CPSOW算法最優(yōu)解的精度提高的均很顯著，已經(jīng)達(dá)到10-29~10-9之間，這說明所提算法的搜索能力強(qiáng)，并能夠使算法收斂到目標(biāo)函數(shù)的理論極值點(diǎn)。

2）在最優(yōu)解的標(biāo)準(zhǔn)差比較中，在函數(shù)Sphere，Rastrigin中CPSOW算法的結(jié)果相當(dāng)好，精度已經(jīng)分別達(dá)到10-27~10-9。由此驗(yàn)證了在算法中，根據(jù)粒子位置采用不同速度更新公式，由此不斷靠近全局最優(yōu)解，因此從數(shù)據(jù)結(jié)果來看，所提出的CPSOW算法，實(shí)驗(yàn)結(jié)果波動(dòng)性比較小。

3）從圖1到圖3可知：CPSOW算法在所有測(cè)試函數(shù)中，最優(yōu)解函數(shù)適應(yīng)值均始終保持最好，而在Sphere函數(shù)和Rosenbrock函數(shù)中搜索最優(yōu)解速度極快，百步之內(nèi)就能迅速定位全局最優(yōu)解的所在空間區(qū)域，這說明在CPSOW算法中充分利用混沌序列的均勻性和遍歷性，為粒子發(fā)現(xiàn)全局最優(yōu)解位置提供重要的信息，致使粒子快速靠近全局最優(yōu)解，從而CPSOW算法始終保持最好的結(jié)果。

5 結(jié)束語

文中提出了基于離差平方和法的粒子群優(yōu)化算法，該算法在應(yīng)用混沌序列的遍歷性和隨機(jī)性，使得CPSOW算法能夠避免無用的搜索，縮短尋優(yōu)時(shí)間。然后采用離差平方和法進(jìn)行聚類提高尋找最優(yōu)解的能力。同時(shí)根據(jù)粒子更新位置的目標(biāo)函數(shù)適應(yīng)值與個(gè)體和全局歷史最好位置目標(biāo)函數(shù)適應(yīng)值進(jìn)行比較分類，進(jìn)行速度更新。應(yīng)用所提出的算法處理3個(gè)典型優(yōu)化函數(shù)，并與3種算法SPSO，CPSO，LDIWPSO進(jìn)行比較分析。實(shí)驗(yàn)數(shù)據(jù)結(jié)果表明：CPSOW算法不易受早熟影響，幾乎不陷入局部最優(yōu)解中，不論是算法搜索最優(yōu)解的速度，還是在最優(yōu)解的精度，CPSOW算法都有所的提高。

[1]Kennedy J，Eberhart R C.Particle swarm optimization[C]//In:Proceedings of IEEE International Conference on Neural Networks，Piscataway:IEEE Service Center，1995:1942-1948.

[2]LIU Bo，WANG Ling，JIN Yi-hui，et al.Improve particle swarm optimization combined with chaos[J].Chaos Solitons and Fractals，2005（25）：1 261-1 271.

[3]錢偉懿，寧必鋒.基于混沌的聚類粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì)：2011，32（2）：685-688.QIAN Wei-yi，NING Bi-feng.Clustering particle swarm optimization algorithm based on chaos[J].Computer Engineering and Design，2011，32（2）:685-688.

[4]高惠璇.應(yīng)用多元統(tǒng)計(jì)分析 [M].北京：北京大學(xué)出版社，2009.

[5]寧必鋒，褚國娟，馬春麗，等.一種改進(jìn)的混合粒子群優(yōu)化算法[J].渤海大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，31（1）：37-43.NING Bi-feng，CHU Guo-juan，MA Cun-li，et al.An improved hybrid particle swarm optimization algorithm[J].Journal of Bohai University:Natural Science Edition，2010，31（1）:37-43.

[6]Arumugam MS，Rao MV C，Chandramohan A.A new and improved version of particle swarm optimization algorithm with global-local best parameters[C]//Knowl Inf Syst，2008:331-357.

[7]紀(jì)震，廖惠連，吳青華.粒子群算法及應(yīng)用[M].北京：科學(xué)出版社，2009.

[8]Alatas B，Akin E，Ozer A B.Chaos embedded particle swarm optimization algorithms[J].Chaos，Solitons and Fractals，2009，40（4）：1715-1734.