交互學習的粒子群優化算法

秦全德，李麗，程適，李榮鈞

(1.深圳大學管理學院，廣東 深圳518060;2.英利利物浦大學電氣電子工程系，英國利物浦L69 3GJ;3.西交利物浦大學電氣電子工程系，江蘇蘇州215123;4.華南理工大學工商管理學院，廣東廣州510640)

粒子群優化(particle swarm optimization，PSO)算法是一種基于種群搜索的隨機優化技術，其模擬了鳥群覓食過程中的遷徙和群集行為[1].PSO算法具有概念簡單、控制參數少、收斂速度快和易于編程實現的優點[2]，自提出以來受到廣大學者的關注.但PSO算法同其他的隨機搜索方法類似，在求解復雜多峰函數時，容易陷入局部最優[3].為了提高算法性能，較多學者提出了基于不同思想的改進算法，可以簡單歸納為以下幾類:1)調節算法的參數[4-5];2)群體拓撲結構的改進[6-7];3)與其他優化算法混合[8-9];4)嵌入生物行為機制[10-11];5)設計新的學習策略[12-13].

在基本PSO算法中，粒子通過向個體最優位置和群體最優位置學習并不斷調整其飛行速度和所在位置，從而實現在搜索空間尋優.這樣的學習策略使得群體內的信息交流速度快，但由于學習方向的單一性，容易產生“趨同”現象，在算法性能上表現為迭代后期搜索緩慢甚至停滯，容易陷入局部最優[14].因此，設計新的粒子學習策略是提高PSO算法性能的一個重要途徑.目前，國內外學者已經在這方面開展了一些研究.Liang等提出了廣泛學習的PSO算法，其每個粒子根據學習概率來決定向自身個體最優位置還是其他的個體最優位置進行學習[12].實驗結果表明，采用廣泛學習策略能夠探索更大的搜索空間，保持了群體多樣性，算法在搜索過程中不容易陷入局部最優，適合于多峰函數的求解.根據多精英比單精英更能夠引導群體學習的社會現象，Huang等提出了基于榜樣學習的改進PSO算法[13].文獻[15]引入了超球坐標的方式來更新粒子速度，設計了一種集成學習PSO算法.Wang等提出了一種自適應學習的PSO算法，該算法依據搜索的進程進行調整學習概率，在具有不同優點的4種學習策略中進行自適應選擇[16].Peram等提出了適應度值－距離－比例的PSO算法，此算法中每個粒子的每一維根據適應度值－距離－比例原則確定一個新的學習對象[17].

人類社會中不同群體之間存在資源和特質的差異性，個體不但會吸收所在群體的經驗，而且還會同其他群體進行信息交流.因此，人類社會的學習行為可以發生在個體與個體、個體與群體以及群體與群體之間.啟發于人類社會的學習行為特點，本文提出了一種由2個種群組成的交互學習的粒子群優化算法(interactive learning particle swarm optimization，ILPSO).當2個種群中最佳的全局最優位置在連續一定的迭代次數內沒有改善時，開始實施交互學習策略.交互學習的策略使得粒子學習的方向具有了多樣性，為算法擺脫局部最優提供了新的額外動力.仿真實驗結果表明，ILPSO在搜索的過程中能夠較好地保持群體的多樣性，具有較好的全局尋優能力，是一種求解復雜問題的有效方法.

1 粒子群優化算法框架

PSO算法中的每個粒子視為問題的一個可行解.在D維的搜索空間中，粒子i在t次迭代時的狀態屬性由位置向量和速度向量進行描述其中 ld和 ud分別為搜索空間的下限和上限，d=1，2，…，D，vmin和 vmax是由用戶設定的粒子飛行的最小和最大速度.粒子的好壞由一個事先設定的適應度函數來確定.在算法的迭代過程中，每一個粒子通過向個體最優位置和群體最優位置進行學習，按照式(1)和式(2)更新飛行速度和位置，從而在搜索空間內尋優.

式中:tmax和t分別表示最大迭代次數和當前的迭代次數，ωs和ωe分別表示算法初始和停止時的慣性權重.文獻[4]的研究結果表明當 ωs=0.9，ωe=0.4時，算法具有較好的性能.將文獻[4]這種慣性權重按照式(3)遞減的PSO算法稱為標準粒子群優化算法(SPSO).

2 交互學習的粒子群優化算法

2.1 交互學習策略

在ILPSO中，粒子分成Swarm1和Swarm22個種群.算法初始運行時，2個種群均按照式(1)更新速度.Swarm1中粒子i在t次迭代的位置向量、速度向量、個體最優位置和群體最優位置分別記為將上述 4 個向量的下標“1”改成“2”就代表Swarm2相對應的向量.設的適應度表示為表示 t次迭代時 2 個種群中最佳的全局最優位置，其適應度表示為在連續的k次迭代中如果沒有改善時，即，表明算法陷入了局部最優，2個種群開始實施交互學習策略，其主要步驟如下:

1)確定學習種群和被學習種群.啟動交互學習策略時，其中一個種群將仍然維持原有的方式進行尋優，稱之為被學習種群;改變原有的學習方式的種群稱為學習種群.根據的值，采用模擬退火的方法確定Swarm1和Swarm2作為被學習種群的概率.這樣的方式使得群體最優位置相對較差的種群將以一定的概率作為被學習種群，從而增加了算法的全局搜索能力.用ps表示Swarm1被選擇作為被學習種群的概率，依據模擬退火算法的原理易有式(4):

式中:T表示模擬退火的溫度.依據ps的大小，采用輪盤賭的抽樣方法確定學習種群和被學習種群.抽取在[0，1]均勻分布的隨機數，小于 ps時，Swarm1為被學習種群，反之Swarm2將作為被學習種群.

2)確定學習種群中每個粒子向被學習種群學習的概率.在ILPSO中，根據學習種群中單個粒子適應度值的排序來決定學習概率的大小.學習種群中適應度好的粒子向被學習種群學習的概率相對較小，以盡量維持目前良好的搜索形態;反之學習種群中適應度值較差的粒子，學習概率較大.依據經驗公式(5)確定學習種群中粒子i向被學習種群的學習概率 pci.

式中:orderi表示按粒子i在學習種群內適應度的排序;m表示學習種群的規模.

3)更新每個種群的速度和位置.被學習種群的粒子按照式(1)更新速度;在學習種群中，如果產生的隨機數小于pci，粒子i同時向個體最優位置、群體最優位置和被學習種群的群體最優位置學習更新速度;反之仍然根據式(1)更新速度.當Swarm1是學習種群時，向Swarm2學習的粒子速度按照式(6)更新.而當Swarm2是學習種群時，向Swarm1學習的粒子速度按照式(7)更新.

式中:rij(i=1，2，j=1，2，3)表示在[0，1]內均勻分布的隨機數.

2.2 變異算子

如果Swarm1和Swarm2的群體最優位置的適應度值相差較大時，式(4)會給算法帶來較大的選擇壓力，不利于全局搜索.基于這樣的考慮，本文采用在任意一個種群中隨機選擇一個粒子在任一維上的速度按式(8)發生變異:

式中:vmax表示粒子飛行的最大速度，r3和r4表示均勻分布在[0，1]的隨機數.由于只選擇一個種群中的一個粒子一維的速度發生變異，因此幾乎不會破壞群體的結構.但每一個種群、每一個粒子和其每一維速度從統計意義上來說是以同樣的概率被選擇發生變異.

2.3 ILPSO 主要步驟

ILPSO的主要步驟如下:

1)置t=0;初始化2個種群粒子的位置和速度，并設定相應的參數;

2)計算粒子適應度值，確定個體最優位置和群體最優位置;

4)確定學習種群和被學習種群;

5)計算學習種群中每個粒子向被學習種群學習的概率;

6)更新2個種群的粒子速度和位置;

7)執行變異算子;

8)t=t+1;計算粒子適應度，更新每個粒子的個體最優位置和群體最優位置;

9)判斷程序終止條件是否滿足，若滿足則算法終止，輸出最優解，否則轉到3).

3 仿真實驗

3.1 測試函數

本文選取了11個常用的測試函數進行仿真實驗.其中基本測試函數包括f1、f22個單峰函數和f3、f64個多峰函數，f7、f8和 f9、f11分別是偏移測試函數和旋轉測試函數.基本測試函數的局部極值點多沿著平行的坐標軸，且全局最優位于原點，不能較好地反映現實中優化問題的復雜性.Suganthan等對基本測試函數進行了偏移和旋轉[18].f7、f8是將基本測試函數f2和f3的全局最優點隨機移動到每一維具有不同數值的新位置，并且加上了一個偏置值O.本文依據文獻[18]的方法進行偏移.旋轉測試函數f9～f11是通過將一個正交矩陣左乘f2、f3和f5而得到的，其各個變量之間變得都不可分.其中正交矩陣的產生采用Salomon在1996年提出的方法[19].表1給出了每個函數的名稱、數學表達式、搜索范圍和最優值.

表1 測試函數及其參數設置Table 1 Benchmark function and their settings

3.2 實驗參數設置

將ILPSO 同 SPSO、PSOPC、FDR-PSO 和 HPSOTVAC的性能進行比較.為公平起見，各種比較算法的粒子數量設置為 60，在 ILPSO中 Swarm1和Swarm2的粒子數量分別設置為30.SPSO、PSOPC、FDR-PSO、HPSO-TVAC和ILPSO的詳細參數根據文獻[4、10、17、20]進行設置，具體見表 2，其中 Range表示搜索范圍的大小.式(4)中初始溫度T0和退溫方式根據文獻[21]提出的如式(9)、(10)確定:

式中:λ稱為退溫速率，本文取λ=0.9.

表2 參數設置Table 2 Parameter settings of involved algorithms

3.3 實驗結果與分析

將ILPSO和其他的4種PSO算法在11個測試函數上分別獨立運行25次，最大迭代次數為6 000次.比較的5種PSO算法的實驗結果(平均值和標準差)如表3，其中最好的實驗結果加粗表示.圖1描述了比較的5種PSO算法求解f1～f3，f5～f10平均最優值的變化曲線.

表3 各種算法的測試結果比較Table 3 Comparisons of experimental results

對于f1，ILPSO的求解結果都優于其他4種算法.在對“香蕉函數”f2的優化中，相較于 SPSO、PSOPC和 FDR-PSO，ILPSO和 HPSO-TVAC在搜索過程中沒有陷入局部最優.雖然ILPSO實驗結果的平均值稍差于 HPSO-TVAC，但標準差較小，表明ILPSO具有較好的魯棒性.對于具有大量局部最優點的復雜多峰函數f3和f6，ILPSO體現了很好的優化效果，在搜索過程中一直沒有陷入局部最優，說明了交互學習策略能夠擺脫局部最優的有效性.比較的各算法在求解函數f4的性能差別不大，都搜索到比較滿意的結果.在求解 f5中，SPSO、PSO-FDR和HPSO-TVAC的搜索精度只能達到 10－2數量級，PSOPC的搜索精度為10－3數量級，而ILPSO的搜索精度達到了10－4數量級且標準差最小.對于偏移測試函數f7和f8，ILPSO求解結果的平均值和標準差都明顯好于其他算法.將函數的坐標軸進行旋轉后，求解的難度將會提高.ILPSO對旋轉測試函數f9～f11的實驗結果仍表現出了好的搜索精度和魯棒性，表明了其具有很好的適應性.綜上分析，ILPSO在對基本測試函數、偏移測試函數和旋轉測試函數的求解中都表現了搜索精度高和魯棒性好的特點，特別對復雜的函數，其優秀的搜索性能更加突出.

在ILPSO中，由于交互學習策略的作用，每個粒子群體的多樣性得到維護，從而提高了全局搜索能力，不容易陷入局部最優.根據“沒有免費午餐定理”，在維護粒子群體多樣性的同時也帶來了收斂速度相對不夠快的成本.從圖1中可以看出，ILPSO的收斂速度雖然快于SPSO和HPSO-TVAC，但在一些測試函數的優化上比PSOPC和FDR-PSO的收斂速度稍慢.

圖1 各種算法實驗結果的平均最優值變化Fig.1 The convergence curve of invdved algorithms

4 結束語

在分析基本PSO算法學習策略缺陷的基礎上，啟發于人類社會學習的特點，本文提出了一種交互學習的PSO算法——ILPSO.交互學習策略中學習種群和被學習種群在搜索的過程中能夠相互轉換，且改善了粒子學習方向“單一性”的缺陷，保證了群體的多樣性，從而提高了算法的全局搜索能力.多個測試函數的實驗結果表明ILPSO具有較高的搜索精度和魯棒性，特別在求解復雜的問題中，體現的優化性能更加突出.如何在保證ILPSO搜索精度和魯棒性的同時，并進一步提高收斂速度，以及將ILPSO應用到實際問題的求解中是未來研究的重點.

[1]EBERHART R C，KENNEDY J.Particle swarm optimiza-tion[C]//IEEE International Conference on Neural Networks.Perth，Australia，1995:1942-1948.

[2]KENNEDY J，EBERHART R C.Empirical study of particle swarm optimization[C]//Proc of Congress on Evolutionary Computation.Washington，DC，USA，1999:1945-1949.

[3]ANGELINE P J.Evolutionary optimization versus particle swarm optimization and philosophy and performance difference[C]//Proc of 7th Annual Conference on Evolutionary Programming.San Diego，USA，1998:601-610.

[4]SHI Y，EBERHART R C.A modified particle swarm optimizer[C]//IEEE Congress on Evolutionary Computation Anchorage.AK，NJ，1998:69-73.

[5]FAN S K S，LIANG Y C，ZAHARA E.Hybrid simplex search and particle swarm optimization for the global optimization of multimodal functions[J].Engineering Optimization，2004，36:401-418.

[6]SUGANTHAN P N.Particle swarm optimizer with neighborhood operator[C]//Proc of the IEEE Congress of Evolutionary Computation.Washington DC，USA，1999:1958-1961.

[7]楊雪榕，梁加紅，陳凌，等.多鄰域改進粒子群算法[J].系統工程與電子技術，2010，32(11):2453-2458.YANG Xuerong，LIANG Jiahong，CHEN Ling，et al.Multineighbourhood improved particle swarm optimization algorithm[J].Systems Engineering and Electronics，2010，32(11):2453-2558.

[8]楊帆，胡春平，顏學峰.基于蟻群系統的參數自適應粒子群算法及其應用[J].控制理論與應用，2010，27(11):1479-1488.YANG Fan，HU Chunping，YAN Xuefeng.Particle swarm optimization algorithm of self-adaptive parameter based on ant system and its application[J].Control Theory ＆ Applications，2010，27(11):1479-1488.

[9]ZHANG W J，XIE X F.DEPSO:hybrid particle swarm with differential evolution operator[C]//Proc of IEEE International Conference on System，Man and Cybernetic.Washington DC，USA，2003:3816-3821.

[10]HE S，WU Q H，WEN J Y，et al.A particle swarm optimizer with passive congregation[J].BioSystems，2004，78:135-147.

[11]秦全德，李榮鈞.基于生物寄生行為的雙種群粒子群算法[J].控制與決策，2011，26(4):548-552.QIN Quande，LI Rongjun.Two-population particle swarm optimization algorithm based bio-parasitic behaviour[J].Control and Decision，2011，26(4):548-552.

[12]LIANG J J，QIN K，SUGANTHAN P N.Comprehensive learning particle swarm optimization for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation，2006，6(3):281-295.

[13]HUANG H，QIN H，HAO Z F，et al.Exampled-based learning swarm optimization for continuous optimization[J].Information Sciences，2011，182(1):125-138.

[14]CLERC M，KENNEDY J.The particle swarm:explosion，stability，and convergence in multi dimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6:58-73.

[15]SABAT S L，UDGATA S K.Integrated learning particle swarm optimizer for global optimization[J].Applied Soft Computing，2011，11(1):574-584.

[16]WANG Y，LI B，WEISE T，et al.Self-adaptive learning based particle swarm optimization[J].Information Sciences，2011，182(20):4515-4538.

[17]PERAM T，VEERAMACHANENI K，MOHAN C K.Fitness-distance-ratio based particle swarm optimization[C]//Proc of the Swarm Intelligence Symposium.Indianapolis，USA，2003:174-181.

[18]SUGANTHAN P N，HANSEN N，LIANG J J，et al.Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[R/OL].http://www.ntu.edu.sg/home/EPNSugan.

[19]SALOMON R.Reevaluating genetic algorithm performance under coordinate rotation of benchmark functions[J].Biosystems，1996，39:263-278.

[20]RATNAWEERA A，HALGAMUGE S K，WATSON H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].IEEE Transactions on Evolutionary Computation，2004，8(3):240-255.

[21]王凌，李令萊，鄭大鐘.非線性系統參數估計的一類有效搜索策略[J].自動化學報，2003，29:953-958.WANG Ling，LI Lingtai，ZHENG Dazhong.A class of effective search strategies for parameter estimation of nonlinear systems[J].Acta Automatica Sinica，2003，29:953-958.