多模型切換分段混沌粒子群優(yōu)化算法

段磊

（遼寧大學(xué)經(jīng)濟(jì)學(xué)院，遼寧錦州110044）

眾所周知，粒子群優(yōu)化算法（PSO）[1]主要用于求解一些復(fù)雜的多維方程，或者優(yōu)化一些非線性問題。到目前為止，這種算法以及它的改進(jìn)型算法都被廣泛的應(yīng)用于各種領(lǐng)域中去，如PID控制優(yōu)化[2]，電力系統(tǒng)調(diào)度等[3]。在這些實際系統(tǒng)中，被優(yōu)化的目標(biāo)的方程往往具有離散性，多峰值性等特征，因此，我們需要一種魯棒性很強(qiáng)的算法能夠適應(yīng)求解或優(yōu)化不同的問題。

PSO算法的慣性權(quán)重是平衡粒子群探索和開發(fā)能力的主要參數(shù)，如果慣性權(quán)重變大，那么粒子群的探索能力變強(qiáng)，如果變小，那么開發(fā)能力變強(qiáng)[4]。為了避免早熟收斂導(dǎo)致粒子落入局部極值，一種引入混沌序列來進(jìn)行全局搜素的方法出現(xiàn)了[5]，即混沌粒子群算法（HCPSO）。本文主要是吸收了這兩種方法的優(yōu)點，運用多模型切換的手段，使算法既能快速的收斂，又能比較好的跳出局部極值。為了公平的評價這種算法的性能，在數(shù)值實驗中，我們用運算時間和迭代次數(shù)兩個指標(biāo)來進(jìn)行評估，結(jié)果表明，在相同的迭代次數(shù)下，這種算法具有較短的運算時間和較高的收斂精度。

1 PSO及其改進(jìn)

1.1 PSO算法

設(shè)優(yōu)化問題為

設(shè)第i個微粒表示為Xi=(xi1,xi2,…,xiD)，它經(jīng)歷過的最好位置（即有最好的適應(yīng)值）記為Pi=(pi1,pi2,…,piD)，也稱為pbest，在群體所有的微粒經(jīng)歷過的最好位置的索引號用符號g表示，即Pg，或者稱為gbest。微粒i的速度用Vi=(vi1,vi2,…,viD)表示，對每一代，其第d維(1≤d≤D)根據(jù)如下方程迭代：

式中，c1和c2都是正常數(shù)，稱為學(xué)習(xí)因子，r1和r2為介于0到1的隨機(jī)數(shù)，t，t+1為迭代數(shù)，vid為每一個Particle在第d維的速度，i為Particle的編號，d為維數(shù)，pid為每一個Particle到目前為止所出現(xiàn)的最優(yōu)位置，pgd為所有Particle到目前為止，所出現(xiàn)的最優(yōu)位置，xid為Particle目前所在的位置。ω是慣性權(quán)重，決定了算法的開發(fā)與探索能力。

1.2 PSO改進(jìn)算法

到目前為止，出現(xiàn)了很多PSO改進(jìn)算法。其中一些主要把改進(jìn)的焦點放在慣性權(quán)重上，如線性遞減慣性權(quán)重[4]，模糊慣性權(quán)重[6]和隨機(jī)慣性權(quán)重[7]。因為混沌序列具有良好的歷遍性，因此這種序列被引入到粒子群算法中來，主要用于全局搜索，來防止粒子落入局部極值[5]。后來又出現(xiàn)了基于Tent映射的分段混沌方法來替代傳統(tǒng)的混沌映射[8-9]，其中，文獻(xiàn)[9]指出，實驗證明分段混沌映射具有更好的隨機(jī)性能和初值敏感性。此外，一些學(xué)者通過以一定的概率交換不同粒子的歷史最優(yōu)值來解決粒子早熟收斂的問題，如CLPSO[10]，混合和聲搜索粒子群算法（HHSPSO）[12]，具有全局優(yōu)化問題信息共享機(jī)制的競爭與合作粒子群算法（CCPSO-ISM）[13]，一種可擴(kuò)展優(yōu)化的社會學(xué)習(xí)粒子群優(yōu)化算法（SL-PSO）[14]，混合無參數(shù)粒子群算法（HNPPSO）[15]。

但是，到目前為止，大多數(shù)改進(jìn)PSO都具有其局限性。比如慣性權(quán)重的方法雖然擴(kuò)大了粒子在前期的搜索空間，并且也能在后期加速收斂，但是這并不能保證粒子經(jīng)歷所有的空間，并且，當(dāng)出現(xiàn)某個全局極值附近粒子的當(dāng)前值小于某個局部極值附近粒子的當(dāng)前值的時候，粒子將陷入局部極值。CLSPO和SAPSO搜索方法相對能很好的避免落入局部極值這種情況，但是對于單峰值函數(shù)，它們的收斂速度慢。

2 多模型切換分段混沌粒子群優(yōu)化算法（MMSPCPSO）

2.1 分段混沌公式

根據(jù)文獻(xiàn)[13]，提出了一種分段Logistic映射，這種映射具有更好的初值敏感性和歷遍性。定義為：

其中 3.569 945 6…≤u≤4。當(dāng)u=4時，取1 000個點，分段Logistic混沌映射如圖1所示，之后，利用公式4生成定義域內(nèi)地混沌序列。

圖1 當(dāng)U=4時，分段混沌映射圖

其中，xi為將要生成的定義域內(nèi)的變量，ai為已經(jīng)產(chǎn)生的分段混沌序列，Ui為定義域的上界，Li為定義域的下界。

2.2 混沌粒子群算法

文獻(xiàn)[5]提出先對粒子群做混沌化，經(jīng)過PSO公式的計算之后，根據(jù)函數(shù)的適應(yīng)值將粒子群分類分析，對好的部分做進(jìn)一步的混沌比較以此來跳出局部極值。其程序流程是：

Step1，根據(jù)本文引用的混沌公式（3），（4）將粒子群做混沌化；

Step2，根據(jù)粒子群公式（1），（2）運行，得到新的粒子群；

Step3，根據(jù)粒子的適應(yīng)度函數(shù)值排序，對適應(yīng)度相對好的一部分粒子重新做混沌化，重新與PSO步驟所得的結(jié)果比較，如果比原來的好，就替代粒子，否則放棄。

Step4，檢測結(jié)果是否滿足收斂條件，如果是，則結(jié)束程序，否則返回Step2.

以上的算法是以粒子群最優(yōu)的部分作為下一次混沌的起始點，我們稱為PCPSO-HB算法；那么，相應(yīng)的，以粒子群最差的部分為下一次混沌起始點的算法就稱為PCPSO-HW算法；以粒子群的全部點為下一次混沌起始點的算法稱為PCPSO-T算法；以粒子群最佳位置為下一次混沌起始點的算法稱為PCPSO-PG算法。

2.3 多模型切換策略

文中在前面已有算法的基礎(chǔ)上，提出一個新的混沌粒子群算法，它是以每次更新粒子群的全部粒子作為下一次混沌運算的起始點，并且每個粒子做n（n＞=2）次混沌運算，我們稱之為PCPSO-TN算法。由于混沌運算的比重相對較大，這種算法具有很強(qiáng)歷遍性。可以應(yīng)用到下面的多模型切換算法中去。

文中提出3種運算模型：

模型1（flag1）：采用PCPSO-T算法，即PSO運算與分段混度運算（PC）相混合，等比重前進(jìn)搜索。其中PSO算法的慣性權(quán)重ω取常用的0.7，學(xué)習(xí)因子c1=c2=1.496 2。

模型2（flag2）：采用PSO算法，由于選取很小的慣性權(quán)重ω=0.1，此算法具有很快的收斂能力，但是幾乎放棄了全局搜索能力。

模型3（flag3）：采用PCPSO-TN算法。選取合適的慣性權(quán)重ω和學(xué)習(xí)因子。n＞2，特點是具有較強(qiáng)的搜索能力。

模型之間的切換策略：隨著粒子群經(jīng)PSO公式更新，如果全局最優(yōu)點連續(xù)更新2次以上，那么采用模型2的算法；如果連續(xù)2次不更新，懷疑粒子群有可能落入局部極值點，則采用模型3的算法；其余采用模型1的算法。

3 實驗與結(jié)果分析

3.1 魯棒性與效率分析

實驗中選取多個多維多峰值函數(shù)做為基準(zhǔn)函數(shù)，其函數(shù)名稱和函數(shù)表達(dá)式表1所示。我們將MMSPCPSO 與 HNPPSO[15]，SRPSO[13]，HHSPSO[12]，SLPSO[14]和上文模型3中的PCPSO-T和PCPSO-TN算法相比較。設(shè)置種群大小為50，迭代次數(shù)為100次，PCPSO-TN中的混沌運算比例N=3，每種算法都運行50次，結(jié)果如表2所示。其中，F(xiàn)代表粒子落入局部極值的次數(shù)；T代表一共運行了50次；所用電腦的CPU頻率是2.6 GHz，內(nèi)存4 GB，軟件為MATLAB 7.0?？梢钥闯觯琍CPSO-TN與MMSPCPSO粒子落入局部極值的概率幾乎是相同的，也是最小的，這說明這兩種算法都具有很強(qiáng)的全局搜索能力；PCPSO-TN所花費的時間幾乎是PCPSO-T的2倍，PSO的3倍，而MMSPCPSO所花費的時間接近于PSO，這說明MMSPCPSO具有很高的運行效率。可以推斷，如果增加混沌運算的比重N，PCPSO-TN所花費的時間將線性增加，但是MMSPCPSO卻不需要線性增加。

圖2 MMSPCPS算法流程圖

3.2 維數(shù)比較分析

函數(shù)Ackley是一個多峰值函數(shù)，它具有一個全局最優(yōu)點（0，0）D，以及很多局部極值。設(shè)粒子群數(shù)為100，分別測試各個算法在其高維度的收斂情況（100～1000），每種算法運算50次后取平均值，其結(jié)果如表3所示，可以看出，隨著維數(shù)的增加，PCPSOTN收斂的結(jié)果最小，MMSPCPSO具有第二小的平均收斂結(jié)果，然而，相比較之前表2的運算時間，MMSPCPSO是性價比最好的算法。

4 結(jié) 論

文中提出了一種新的多模型切換的算法MMSPCPSO，加強(qiáng)了粒子群全局搜索和快速收斂能力。在這個算法中，引入了3種模型，一種是通過改變慣性權(quán)重來增加收斂速度，另一種是通過增加混沌搜索運算來增強(qiáng)全局搜索能力，第三種則是兩者之間的平衡。提出了根據(jù)最優(yōu)粒子的更新情況來判斷切換那一種模型的策略。數(shù)值實驗的結(jié)果表明，這種策略極大提高了粒子搜索的效率，縮短了運算所需時間，相比其他的改進(jìn)PSO算法，這種算法不僅具有更好的魯棒性，而且也具有很快的收斂速度。

表1 基準(zhǔn)函數(shù)

表2 魯棒性對比

表3 優(yōu)化Ackley函數(shù)對比