智能單粒子優(yōu)化算法

1、智能單粒子優(yōu)化算法* 本文得到國家自然科學(xué)基金（批準(zhǔn)號：60572100，60673122）、國家自然科學(xué)基金委員會與英國皇家學(xué)會合作研究項目（60711130233）和深圳市科技三項經(jīng)費(fèi)(200704)資助。紀(jì)震為通信作者（jizhen）；地址：深圳大學(xué)計算機(jī)與軟件學(xué)院（辦公樓549）；電話 紀(jì)震1，周家銳1，廖惠連1，吳青華2（1深圳大學(xué)計算機(jī)與軟件學(xué)院德州儀器DSPs實驗室，深圳，518060）（2利物浦大學(xué)電氣電子工程系，利物浦，L69 3GJ, UK）摘要：本文在傳統(tǒng)粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法的基礎(chǔ)

2、上，提出了智能單粒子優(yōu)化算法（Intelligent Single Particle Optimizer, ISPO）。與傳統(tǒng)的PSO算法不同，該算法采用了一個粒子在解空間中搜索，粒子的位置矢量被分成一定數(shù)量的子矢量，并基于子矢量對粒子進(jìn)行更新。在子矢量更新過程中，通過分析之前的速度更新情況，引入一種新的學(xué)習(xí)策略，使粒子在搜索空間中能夠動態(tài)地調(diào)整速度和位置，從而向全局最優(yōu)靠近。實驗表明，此算法對大部分標(biāo)準(zhǔn)復(fù)合測試函數(shù)都具有很強(qiáng)的全局搜索能力，其尋優(yōu)能力超過了國際上最近提出的基于PSO的改進(jìn)算法。關(guān)鍵詞：智能單粒子優(yōu)化，粒子群優(yōu)化，子矢量，學(xué)習(xí)策略A Novel Intelligent Sing

3、le Particle Optimizer JI Zhen1, ZHOU Jiarui1, LIAO Huilian1, WU Qinghua2(1Texas Instruments DSPs Lab, School of Computer Science and Software Engineering, Shenzhen University, Shenzhen, 518060, China)(2Department of Electrical Engineering and Electronics, The University of Liverpool, Liverpool, L69

4、3GJ, UK)Abstract: Intelligent single particle optimizer (ISPO) is proposed based on conventional particle swarm optimization (PSO). ISPO applies a particle, which is different from conventional PSO, to search in the problem space. The whole position vector of particle is split into a certain number

5、of subvectors, and the particle is updated based on these subvectors. During the process of updating each subvector, a novel learning strategy is introduced based on the analysis of previous velocity subvectors, and the particle adjusts its velocity and position subvector dynamically. Experimental r

6、esults have demonstrated that ISPO has an outstanding ability to find the global optimum. ISPO performs much better than most recently proposed PSO-based algorithms on the optimization of most complicated composition test functions.Keywords: Intelligent single particle optimizer, Particle swarm opti

7、mization, Subvector, Learning strategy1 引言1995年Eberhart博士和Kennedy1博士基于鳥群覓食行為提出了粒子群優(yōu)化算法（Particle Swarm Optimization, PSO）。由于該算法概念簡明、實現(xiàn)方便、收斂速度快、參數(shù)設(shè)置少，是一種高效的搜索算法，近年來受到學(xué)術(shù)界的廣泛重視。但在優(yōu)化復(fù)雜函數(shù)時，PSO算法很容易陷入局部最優(yōu)，并出現(xiàn)早熟收斂現(xiàn)象。為了提高算法的收斂性能，隨后出現(xiàn)了各種基于不同思想的改進(jìn)算法。其中在對于基本粒子群算法進(jìn)化方程的改進(jìn)方面，Shi和Eberhart2于1998年對PSO算法的速度項引入了慣性權(quán)重，并提

8、出在進(jìn)化過程中動態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度。后來Shi和Eberhart3又提出了基于模糊系統(tǒng)的慣性權(quán)重的動態(tài)調(diào)整，從而實現(xiàn)對慣性權(quán)重的非線性控制。此外Clerc45提出帶收縮因子的粒子群算法，以確保算法收斂。在借鑒其它優(yōu)化方法的思想方面，也出現(xiàn)了各類的改進(jìn)粒子群算法，如Angeline6于1999年借鑒進(jìn)化計算中的選擇概念，將其引入到PSO算法中，從而淘汰差的粒子，將具有較高適應(yīng)值的粒子進(jìn)行復(fù)制以產(chǎn)生等數(shù)額的粒子來提高算法的收斂性，隨后Angeline7又提出了借鑒雜交的改進(jìn)粒子群算法。在利用小生境思想方面，P. N. Suganthan8于1999年提出一種基于領(lǐng)域思想的粒

9、子群算法，其基本思想是在算法開始階段，每個個體的領(lǐng)域為其自身，隨著進(jìn)化代數(shù)的增長，其領(lǐng)域范圍也在不斷增大直至整個種群。為進(jìn)一步改善算法性能，避免過早收斂的現(xiàn)象，J. Kennedy9于1999年提出幾種基本的領(lǐng)域結(jié)構(gòu)，如環(huán)形結(jié)構(gòu)和輪形結(jié)構(gòu)及它們的推廣。近來性能較為顯著的基于PSO算法的改進(jìn)算法有Thanmaya Peram10等人于2003年提出的基于粒子群優(yōu)化的適應(yīng)值-距離-比例算法(Fitness-Distance-Ratio based Particle Swarm Optimization, FDR-PSO)，在此算法中每個粒子根據(jù)一定的適應(yīng)值-距離-比例原則，向附近具有較好適應(yīng)值的多

10、個粒子進(jìn)行不同程度的靠近，而不僅僅只向當(dāng)前所發(fā)現(xiàn)的最好粒子靠近。此算法改善了PSO算法的早熟收斂問題，在優(yōu)化復(fù)雜函數(shù)方面，其性能得到了較大改善。F. Bergh11等人于2004年提出了協(xié)同粒子群優(yōu)化算法(Cooperative Particle Swarm Optimizer, CPSO)，采用多個協(xié)同工作的子粒子群對解向量的不同部分分別進(jìn)行優(yōu)化，達(dá)到較好的尋優(yōu)結(jié)果。為防止PSO算法陷入局部最優(yōu)，J. J. Liang12等人于2006年提出了綜合學(xué)習(xí)粒子群優(yōu)化算法(Comprehensive Learning Particle Swarm Optimizer, CLPSO)，使得每個粒子的

11、速度更新基于所有其它粒子的歷史最優(yōu)位置，從而達(dá)到綜合學(xué)習(xí)的目的。但上述算法在優(yōu)化復(fù)雜高維多模函數(shù)時，容易陷入局部最優(yōu)，且解與全局最優(yōu)值相差較大。本文基于傳統(tǒng)粒子群算法，提出了智能單粒子優(yōu)化算法(Intelligent Single Particle Optimizer, ISPO)。在ISPO算法的優(yōu)化過程中，算法不是對整個速度矢量或位置矢量同時進(jìn)行更新，而是先把整個矢量分成若干子矢量，并按順序循環(huán)更新每個子矢量。在子矢量的更新過程中，此算法通過引入一種新的學(xué)習(xí)策略，使得粒子在更新過程中能夠分析之前的速度更新情況，并決定子矢量在下一次迭代中的速度。而在傳統(tǒng)粒子群算法中，粒子只是簡單的個體，不具

12、備分析之前速度更新情況的能力。實驗結(jié)果表明，此算法在優(yōu)化復(fù)雜的具有大量局部最優(yōu)點(diǎn)的高維多模函數(shù)方面具有一定的優(yōu)勢，其性能顯著優(yōu)于最近提出的粒子群改進(jìn)算法的性能，且其解非常接近全局最優(yōu)點(diǎn)。2 PSO算法在一個D維的目標(biāo)搜索空間中，由n個粒子構(gòu)成一個群體，其中第i個粒子(i=1,2, n)的位置可表示為D維的位置矢量。n也被稱為群體規(guī)模，過大的n會影響算法的運(yùn)算速度和收斂性。根據(jù)一定標(biāo)準(zhǔn)計算當(dāng)前的適應(yīng)值，即可衡量粒子位置的優(yōu)劣。每次迭代中粒子i移動的距離為粒子的飛行速度或者速度矢量，表示為，粒子迄今為止搜索到的最優(yōu)位置為，整個粒子群迄今為止搜索到的最優(yōu)位置為。每次迭代中，粒子根據(jù)以下式子更新速度和

13、位置：（1） （2） 其中，是迭代次數(shù)，和為0,1之間的隨機(jī)數(shù)構(gòu)成的矢量。和為學(xué)習(xí)因子，也稱加速因子，其使粒子具有自我總結(jié)和向群體中優(yōu)秀個體學(xué)習(xí)的能力，從而向自己的歷史最優(yōu)點(diǎn)以及群體內(nèi)歷史最優(yōu)點(diǎn)靠近。速度取值范圍為,，位置的取值范圍為,。3 智能單粒子優(yōu)化算法在ISPO算法的優(yōu)化過程中，算法并不是對整個速度矢量或位置矢量(即所有維的數(shù)值)同時進(jìn)行更新，而是先把整個矢量分成若干個子矢量，并基于子矢量進(jìn)行粒子更新。在子矢量的更新過程中，通過引入一種新的學(xué)習(xí)策略，使其對之前的速度更新情況進(jìn)行分析，并決定下一次迭代的速度，從而實現(xiàn)對速度的動態(tài)調(diào)整。3.1 子矢量大部分隨機(jī)優(yōu)化算法(包括粒子群算法和遺傳

14、算法等)的性能隨維數(shù)增加而變差。在更新過程中，傳統(tǒng)的PSO算法往往同時改變整個解矢量中各維的數(shù)值，并根據(jù)更新后的解矢量得到一個適應(yīng)值（Fitness value），從而判斷解矢量的適應(yīng)程度。此適應(yīng)值能夠判斷解矢量的整體質(zhì)量，但不能判斷部分維是否向最優(yōu)方向移動。例如，在解決三維函數(shù)問題中，其全局最優(yōu)為0,0,0，解的初始值設(shè)為1,1,1，給其一個隨機(jī)擾動0.2,-0.5,0.3，可得到更新后的解為1.2,0.5,1.3。假設(shè)更新后的解的適應(yīng)值比初始值對應(yīng)的適應(yīng)值有所提高，則在下一次迭代中解將會在某種程度上向0.2,-0.5,0.3方向移動。此時，雖然第二維的數(shù)值向全局最優(yōu)靠近，但第一維和第三維的

15、數(shù)值卻遠(yuǎn)離了全局最優(yōu)。因此，對于高維函數(shù)，一般PSO算法很難兼顧所有維的優(yōu)化方向。為解決這個問題，在保證粒子能夠搜索到空間中的每個區(qū)域的同時，可把搜索空間分解成若干個低維小空間進(jìn)行搜索。在本文提出的ISPO算法中，一個粒子代表著整個位置矢量。在更新過程中，把整個D維的解空間分成m部分，即把整個位置矢量分成m個位置子矢量，其中每一位置子矢量與其對應(yīng)的速度子矢量分別表示為和,。為簡單起見，設(shè)D剛好被m整除，則每個子矢量包括了l (l=D/m) 維，如圖1所示。1(j-1)l+1 jlD-+1D子矢量1子矢量j子矢量m圖1 位置子矢量示意圖對于維之間相關(guān)性較大的函數(shù)，需根據(jù)函數(shù)特征來決定子矢量的個數(shù)

16、。如圖2所示，假設(shè)全局最優(yōu)點(diǎn)為(0,0)，而(k1,k2)為直線x=k1和y=k2上的最優(yōu)解。把初始值設(shè)在 (k1,k2)，并在更新過程中輪流更新每一維。在更新其中一維的數(shù)值時需保持另一維的數(shù)值不變。由于(k1,k2)為兩直線上的最優(yōu)解，所以對這兩維數(shù)值進(jìn)行輪流更新將會導(dǎo)致解跳不出局部最優(yōu)(k1,k2)。此時，如果同時改變兩維的數(shù)值，解有可能會跳出局部最優(yōu)點(diǎn)，并到達(dá)全局最優(yōu)。因此在解決不同問題時，需根據(jù)維之間的相關(guān)性來決定每個子矢量所包含的維數(shù)。k1k200(k1,k2)xy圖2 維相關(guān)性示意圖3.2 子矢量的更新過程ISPO的更新過程是基于子矢量，按先后順序（從到）進(jìn)行循環(huán)更新。在更新第個子

17、矢量的過程中，將按以下的速度和位置更新公式迭代執(zhí)行N次：(3) (4) (5)其中；。參數(shù)為學(xué)習(xí)變量，用于分析之前速度的更新情況，從而決定下一次迭代的速度；隨機(jī)矢量在-0.5,0.5范圍內(nèi)服從均勻分布；多樣性因子、下降因子、收縮因子和加速度因子為常數(shù)；為評估算法性能的適應(yīng)值。在子矢量更新過程中，位置子矢量由速度子矢量決定。速度子矢量由兩部分組成：多樣性部分和學(xué)習(xí)部分。在多樣性部分中，控制隨機(jī)矢量的幅度，而控制幅度的下降梯度。由于是隨迭代次數(shù)增加而下降的冪函數(shù)，所以粒子在優(yōu)化前期更趨向于全局搜索，并隨更新過程逐漸從全局搜索向局部搜索轉(zhuǎn)換。學(xué)習(xí)部分完成一種新的學(xué)習(xí)策略，其中學(xué)習(xí)變量能夠根據(jù)之前的速

18、度更新情況而動態(tài)地調(diào)整速度子矢量。學(xué)習(xí)部分在更新過程中所起的作用主要為如下三點(diǎn)：l 在每次迭代中，如果一個粒子找到比歷史最好位置更優(yōu)的位置時，它將會把這次迭代的速度增加到倍，并決定下一次迭代的速度，如公式（4）（5）所示。l 如果在第一次迭代中，適應(yīng)值得到改善，但在第二次迭代中適應(yīng)值沒有得到改善。這是因為第二次迭代的速度子矢量是第一次迭代的速度子矢量的倍，其速度太大以至于位置子矢量跳過了最優(yōu)點(diǎn)。在這種情況下，如果，降低速度將會有助于搜索全局最優(yōu)點(diǎn)，因此第三次迭代中的學(xué)習(xí)子矢量將減小為原值的。l 如果粒子經(jīng)過幾次迭代后適應(yīng)值仍然沒有得到改善，將會被減到一個很小的值，當(dāng)其小于時將被設(shè)為0，此時只有

19、多樣性部分決定著速度子矢量。這意味著此時的速度會具有更大的多樣性，更容易跳出局部最優(yōu)。從上述幾點(diǎn)可見此粒子的智能性。ISPO的偽代碼如下，其中為函數(shù)計算（Function Evaluations, FEs）的次數(shù)，Nmax為的最大次數(shù)。開始初始位置矢量;計算適應(yīng)值, 即;1 初始FEs的次數(shù)為;2 初始子矢量的個數(shù);初始學(xué)習(xí)變量;3 初始子矢量中的迭代次數(shù);計算;計算; 計算;=;如果，設(shè)置; ;如果，設(shè)置; ;如果, 設(shè)置學(xué)習(xí)變量;如果<N, 跳至步驟3;如果j<m, 跳至步驟2;如果< Nmax, 跳至步驟1;結(jié)束4 實驗結(jié)果實驗仿真平臺為WindowsXP，Matlab

20、 6.5。本實驗把ISPO算法與帶慣性的粒子群算法(Particle Swarm Optimizer with inertia weight w, PSO-w) 2、協(xié)同粒子群優(yōu)化算法(Cooperative Particle Swarm Optimizer, CPSO)11和綜合學(xué)習(xí)粒子群優(yōu)化算法(Comprehensive Learning Particle Swarm Optimizer , CLPSO) 12進(jìn)行比較*各算法的程序可從。本實驗采用了國際上通用的6個標(biāo)準(zhǔn)復(fù)合測試函數(shù)13：CF1-CF6。這些測試函數(shù)為高維多模函數(shù)，具有大量的局部最優(yōu)點(diǎn)，是優(yōu)化領(lǐng)域中公認(rèn)的較難優(yōu)化的函數(shù)。大

21、部分優(yōu)化算法在對其進(jìn)行尋優(yōu)的過程中往往會陷入局部最優(yōu)點(diǎn)。近年來，優(yōu)化高維多模函數(shù)已成為優(yōu)化算法領(lǐng)域的研究熱點(diǎn)。在實驗中，適應(yīng)值函數(shù)的值為當(dāng)前位置對應(yīng)的函數(shù)值。PSO-w算法的參數(shù)設(shè)置為：2。CPSO和CLPSO的參數(shù)設(shè)置參考文獻(xiàn)13。ISPO算法的參數(shù)設(shè)置如表1所示。表1 ISPO算法的參數(shù)設(shè)置函數(shù)C00e+00CF25240141.00e+00CF330020.1141.00e+00CF4400021141.00e+00CF5102100140.00e+00CF6400021141.00e+00各算法對6個標(biāo)準(zhǔn)復(fù)合測試函數(shù)分別執(zhí)行10次，在每次執(zhí)行中函數(shù)的總計算次數(shù)

22、FEs設(shè)置為5×104，其平均結(jié)果和標(biāo)準(zhǔn)方差如表2所示。在優(yōu)化這6個標(biāo)準(zhǔn)復(fù)合測試函數(shù)時，ISPO算法都能夠到達(dá)距全局最優(yōu)點(diǎn)較近的位置，其算法穩(wěn)定性較好。與PSO-w、CPSO和CLPSO算法相比，ISPO算法在測試函數(shù)CF1、CF2、CF3和CF5上所得到的最終位置比其它三個算法更接近于全局最優(yōu)點(diǎn)。特別是對于CF1和CF5，ISPO算法的適應(yīng)值明顯優(yōu)于其它三個算法。ISPO的優(yōu)化結(jié)果的標(biāo)準(zhǔn)方差也相對較低，從而證明其算法的穩(wěn)定性。表2 各算法對6個標(biāo)準(zhǔn)復(fù)合測試函數(shù)進(jìn)行優(yōu)化的結(jié)果函數(shù)PSO-wCPSOCLPSOISPOCF12.32e+02±1.17e+021.39e+02&#

23、177;2.79e+011.41e+02±2.13e+022.47e+01±7.79e+01CF22.29e+02±1.61e+021.15e+02±3.48e+011.12e+02±1.40e+026.54e+01±6.03e+01CF33.42e+02±1.52e+022.27e+02±6.45e+013.01e+02±1.95e+022.12e+02±6.06e+01CF44.71e+02±1.51e+023.77e+02±4.79e+013.32e+02±1

24、.26e+024.11e+02±5.87e+01CF52.69e+02±2.41e+021.11e+02±2.47e+011.95e+02±2.36e+023.37e+01±2.88e+01CF69.05e+02±3.10e+006.71e+02±1.58e+028.39e+02±1.44e+026.95e+02±2.07e+02圖3給出了各算法在優(yōu)化復(fù)合測試函數(shù)時的收斂特性，圖中橫坐標(biāo)顯示FEs的范圍為05×104，縱坐標(biāo)為適應(yīng)值的對數(shù)。ISPO在CF1、CF2和CF5上收斂速度明顯快于其它三

25、個算法。 (a) 函數(shù)CF1 (b) 函數(shù)CF2 (c) 函數(shù)CF3 (d) 函數(shù)CF4 (e) 函數(shù)CF5 (f) 函數(shù)CF6 圖3 各算法對標(biāo)準(zhǔn)復(fù)合測試函數(shù)進(jìn)行優(yōu)化的收斂曲線5 結(jié)論本文在粒子群優(yōu)化算法的基礎(chǔ)上，針對復(fù)雜高維多模函數(shù)很難極小化的問題，提出了智能單粒子優(yōu)化算法,并給出了一種確定算法參數(shù)的方法。智能單粒子優(yōu)化算法先把整個矢量分成若干子矢量，并按順序循環(huán)更新每一子矢量。在更新每一子矢量的過程中，此算法通過引入一種新的學(xué)習(xí)策略，使粒子能夠根據(jù)之前的速度更新情況進(jìn)行動態(tài)地調(diào)整子矢量速度。粒子在陷入局部最優(yōu)點(diǎn)時會增加速度的多樣性，從而跳出局部最優(yōu)，并向全局最優(yōu)靠近。實驗表明，此算法對大

26、部分函數(shù)都具有很強(qiáng)的全局搜索能力，特別在優(yōu)化復(fù)雜的高維多模函數(shù)時，其性能比起PSO-w、FEP和CLPSO算法有著很大的改善，且其解非常接近全局最優(yōu)點(diǎn)。參考文獻(xiàn)：1 Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ, IEEE Service Center, 1995: 19421948.2 Shi Y, Eberhart R C. A modified particle

27、 swarm optimizer. In: Proceedings of the IEEE International Conference on Evolutionary Computation, Piscataway, NJ, IEEE Press, 1998: 6973.3 Shi Y, Eberhart R C. Fuzzy adaptive particle swarm optimization. In: Proceedings of the IEEE Congress on Evolutionary Computation, Seoul, Korea, 2001: 1011 106

28、.4 Clerc M. The swarm and the queen: toward a deterministic and adaptive particle swarm optimization. In: Proceedings of the Congress on Evolutionary Computation, 1999: 19511957.5 Corne D, Dorigo M, Glover F. New ideas in optimization. McGraw Hill, 1999: 379387.6 Angeline P J. Using selection to imp

29、rove particle swarm optimization. In: Proceedings of IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, USA, 1998: 8489.7 Angeline P J. Evolutionary optimization versus particle swarm optimization: philosophy and performance differences. In: Proceedings of 7th Annual Confe

30、rence on Evolutionary Programming, Germany, 1998: 601610.8 Suganthan P N. Particle swarm optimizer with neighborhood topology on particle swarm performance. In: Proceedings of the 1999 Congress on Evolutionary Computation, Piscataway, NJ: IEEE Press, 1999: 19581962.9 Kennedy J. Small worlds and Mega

31、-minds: effects of neighborhood topology on particle swarm performance. In: Proceedings Congress on Evolutionary Computation, Piscataway, NJ: IEEE Press, 1999: 19311938.10 Peram T, Veeramachaneni K, Mohan C K. Fitness-distance-ratio based particle swarm optimization. In: Proceedings Swarm Intelligen

32、ce Symposium, Indianapolis, Indiana, USA, 2003: 174181. 11 Bergh F, Engelbrecht A P. A cooperative approach to particle swarm optimization. IEEE Transactions on Evolutionary Computation, 2004, 8, (3): 225239.12 Liang J J, Qin A K, Suganthan P N et al. Comprehensive learning particle swarm optimizer

33、for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 2006, 10, (3): 281295.13 Liang J J, Suganthan P N, Deb K. Novel composition test functions for numerical global optimization. In : Proceedings of IEEE International Swarm Intelligence Symposium, Mess

34、ina, Italy, 2005: 6875.BackgroundParticle Swarm Optimization (PSO), proposed by Kennedy and Eberhart in 1995, has been widely used for optimization problems. Since PSO was proposed, research on its improvement and application in engineering optimization becomes a hot spot in the area of evolutionary

35、 computation and swarm intelligence. Recently, IEEE Transactions on Evolutionary Computation published a special issue on PSO. PSO has a lot of advantages compared with other evolutionary algorithms, due to its simplicity of implementation, fast convergence rate and easy selection of parameters.Howe

36、ver, for most stochastic optimization algorithms, including PSO, their performance deteriorates as the dimensionality of the search space increases. Many existing PSO-based algorithms are easily trapped into local optima on solving complicated multi-modal functions. In this paper, the new algorithm

37、ISPO, proposed as the improvement of PSO, aims to optimize complicated multimodal functions. ISPO uses a single particle instead of a particle swarm, and applies a novel learning strategy to update the particles velocity and position. Experimental results have shown that: on solving some widely used multimodal benchmark