多模型切換分段混沌粒子群優化算法

段磊

（遼寧大學經濟學院，遼寧錦州110044）

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

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

1 PSO及其改進

1.1 PSO算法

設優化問題為

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

式中，c1和c2都是正常數，稱為學習因子，r1和r2為介于0到1的隨機數，t，t+1為迭代數，vid為每一個Particle在第d維的速度，i為Particle的編號，d為維數，pid為每一個Particle到目前為止所出現的最優位置，pgd為所有Particle到目前為止，所出現的最優位置，xid為Particle目前所在的位置。ω是慣性權重，決定了算法的開發與探索能力。

1.2 PSO改進算法

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

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

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

2.1 分段混沌公式

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

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

圖1 當U=4時，分段混沌映射圖

其中，xi為將要生成的定義域內的變量，ai為已經產生的分段混沌序列，Ui為定義域的上界，Li為定義域的下界。

2.2 混沌粒子群算法

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

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

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

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

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

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

2.3 多模型切換策略

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

文中提出3種運算模型：

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

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

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

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

3 實驗與結果分析

3.1 魯棒性與效率分析

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

圖2 MMSPCPS算法流程圖

3.2 維數比較分析

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

4 結 論

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

表1 基準函數

表2 魯棒性對比

表3 優化Ackley函數對比