融合Rosenbrock搜索法的混合粒子群算法

黃卓超 張偉 王亞剛

摘 要：為克服粒子群算法在處理復雜高維問題時易陷入局部最優(yōu)及尋優(yōu)精度低等缺陷，提出一種融合Rosenbrock搜索法的混合粒子群算法。首先，利用Tent混沌序列進行種群初始化;其次，采用去速度項的簡化粒子群公式提高收斂速度并對個體極值加入擾動，增強粒子種群多樣性;最后，當全局最優(yōu)個體更新停滯時，利用Rosenbrock搜索法對全局最優(yōu)個體進行局部搜索，提高解的精度。利用8個常用基準測試函數分別對30維和50維問題進行實驗，證實該算法可尋到病態(tài)函數Rosenbrock全局最優(yōu)值，且比其它7個函數的尋優(yōu)精度提高[10-2]數量級。實驗證明該算法收斂速度快，解的精度高，全局搜索能力強，尋優(yōu)能力明顯提高。

關鍵詞：粒子群算法;Tent混沌;極值擾動;Rosenbrock搜索法

DOI：10. 11907/rjdk. 192513 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）007-0060-06

Hybrid Particle Swarm Optimization Algorithm Combining

Rosenbrock Search Method

HUANG Zhuo-chao， ZHANG Wei， WANG Ya-gang

（School of Optical-Electrical and Computer Engineering， University of Shanghai for Science and Technology，

Shanghai 200093， China）

Abstract：For the particle swarm algorithm， it is easy to fall into local optimum and low precision in processing when dealing with complex and high-dimensional problems. A hybrid particle swarm optimization algorithm combining Rosenbrock search is proposed. Firstly， the improved algorithm uses the Tent chaotic sequence to initialize the population， so that the initial particles are well distributed in the solution space. Secondly， the simplified particle swarm optimization algorithm with the velocity term removed is used and the disturbance is added to the individual extremum to enhance the particle population diversity， so that the algorithm is not easy to premature. Finally， the global optimal individuals stagnation update times is used to judge whether the algorithm falls into local optimum， and the Rosenbrock search method is used to locally search the global optimal individual to improve the solution quality. Experiments were performed on 30-D and 50-D problems using eight common benchmark functions. Compared with some improved particle swarm optimization algorithms proposed in other literatures， the proposed algorithm can find the global optimal value of the ill-conditioned function Rosenbrock， and the optimization accuracy of the other seven functions has an improve of magnitude of [10-2]. The proposed algorithm has fast convergence speed， high precision of the solution， strong global search ability and obvious improvement ability.

0 引言

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法是1995年Eberhart &Kenney[1]受飛鳥集群活動規(guī)律性啟發(fā)提出的一種隨機智能群優(yōu)化算法。由于算法需調整的參數少、運行速度快及實現簡單等特點，已在多個科學和工程領域得到廣泛應用[2-4]。但該算法在處理高維多峰問題時存在早熟收斂、容易陷入局部最優(yōu)等不足。

針對這些問題，許多學者對經典粒子群算法提出了不同的優(yōu)化策略。如文獻[5]中，shi等以算法復雜度為代價，利用模糊規(guī)則確定慣性權重;文獻[6]提出一種新的慣性參數自適應策略，主要利用貝葉斯技術更新粒子速度和位置，并利用柯西變異防止算法陷入局部最優(yōu);文獻[7]引入Sigmoid函數，并根據粒子當前適應度優(yōu)劣自適應地調整慣性參數，讓適應度好的粒子進行小范圍局部搜索，適應度差的粒子進行大范圍全局搜索，增強了算法尋優(yōu)能力;文獻[8]研究了PID控制與粒子群算法相似性，并利用閉環(huán)反饋控制的思想改進粒子群算法;文獻[9]采用去掉速度項的簡化粒子群算法，并證明了改進算法的收斂性;文獻[10]也采用除去速度項的簡化公式進行迭代更新，并利用個體最優(yōu)均值和群體最優(yōu)值對加速因子進行動態(tài)更新，使算法具有較好的性能，但在一些病態(tài)測試函數中未能取得較好的效果;文獻[11]在位置更新公式中引入了正弦函數因子，利用正弦函數振蕩特性，保持算法在迭代過程中種群多樣性。一些學者還采用算法結合策略，如文獻[12]結合粒子群算法與模擬退火算法，模擬退火算法防止粒子群算法早熟，幫助粒子概率跳出局部最優(yōu)解;文獻[13]結合PSO算法與人工魚群算法，利用人工魚群公告板、群聚和隨行策略的模式改進PSO更新公式，提高了算法性能;文獻[14]將序貫二次規(guī)劃（SQP）法作為局部搜索算法，通過與PSO結合，提高了收斂速度，但對一些高維多極點問題難以獲得全局最優(yōu)解。

對于復雜多峰問題，現有算法很難實現算法全局收斂和收斂速度的平衡。因此本文提出一種融合Rosenbrock搜索的混合粒子群算法（Hybrid Particle Swarm Optimization Algorithm Combining Rosenbrock Search，RHPSO）， 改進算法利用Tent混沌序列確定粒子種群初始位置，采用除去速度項的位置更新公式，有效提高算法收斂速度，并在迭代公式中的個體最優(yōu)位置加入擾動，增加種群多樣性，可有效避免算法早熟，在全局最優(yōu)個體更新陷入停滯時，采用Rosenbrock搜索法進行有效的局部搜索，提高解的質量。實驗結果表明，本文算法在收斂速度和全局收斂性上均優(yōu)于已有的粒子群改進算法。

1 標準粒子群算法原理

粒子群算法在解決最優(yōu)化問題時，一般假定問題的解為搜索空間中的一個粒子。粒子在迭代過程中只根據粒子個體當前發(fā)現的歷史最優(yōu)解pbest及粒子群體當前全局最優(yōu)解gbest更新自己的位置，持續(xù)更新直到滿足迭代終止條件，最后得出最優(yōu)解。

標準粒子群算法數學描述為：在D維問題可行域搜索空間中，有N個粒子組成的一個粒子群體，每一粒子均有位置和速度兩個屬性。例如，第i個粒子的位置和速度分別為[xi=（xi1，xi2，？，xiD）]：[xi=（xi1，xi2，？，xiD）]和[vi=（vi1，vi2，][？，viD）]，均為D維向量[vi=（vi1，vi2，？，viD）];第i個粒子的個體歷史最優(yōu)值為pbest，位置為：[pi=（pi1，pi2，？，piD）];種群全局最優(yōu)值為gbest，位置為[pg=（pg1，pg2，？，pgD）]。

在尋優(yōu)過程中，第i個粒子通過式（1）、式（2）更新位置和速度。

其中，[i=1，2，？，M];[d=1，2，？，D]。[ω]為慣性權重因子，可調節(jié)算法全局和局部搜索能力，一般取值在[0.1～0.9]之間。t為當前迭代次數;[c1]是粒子向自我歷史最優(yōu)位置學習的權重系數，[c2]是粒子向全局最優(yōu)位置學習的權重參數;[r1]和[r2]是服從[U（0，1）]分布的隨機數;[v（t+1）id]和[x（t+1）id]表示第i個粒子更新后的速度與位置;為防止粒子在迭代過程中跑出搜索空間，一般通過設定位置范圍[[xmin，xmax]]和速度范圍[[vmin，vmax]]限制粒子移動。

2 算法描述

本文按照文獻[9]中除去速度項的位置更新公式，具體如下：

迭代公式由原來的二階變?yōu)橐浑A，算法更簡單高效，避免了速度項引起的粒子發(fā)散，使粒子在搜索過程中收斂速度更快[9]。

2.1 混沌序列初始化種群

混沌序列具有隨機性、遍歷性和規(guī)律性，利用這些性質進行優(yōu)化搜索，可有效保持種群多樣性，盡可能降低算法陷入局部最優(yōu)的可能性。已有很多學者將混沌的思想引入啟發(fā)式算法，較多文獻使用的是Logistic混沌映射，文獻[15]表明Tent映射比Logistic映射有更好的遍歷均勻性，并針對Tent混沌序列在迭代過程中存在小周期點和不穩(wěn)定周期點的不足，提出一種改進的Tent混沌映射表達式，具體為：

變換后表達式為：

其中[N]為序列長度，[rand0，1]是[[0，1]]內的隨機數，加入隨機量[rand0，1*1N]不僅可以保持Tent映射的隨機性、遍歷性和規(guī)律性，還可避免迭代過程中陷入小周期點和不穩(wěn)定周期點內。鑒于上述優(yōu)點，本文采用改進的Tent映射表達式在可行域內產生一組優(yōu)秀的初始種群，步驟如下：

Step1：利用隨機數發(fā)生器產生一個（0，1）之間的隨機數，并利用式（5）對該隨機數產生長度為L（L>N）的序列。

Step2：對序列中L個元素分別進行D次Tent變換，產生L個長度為D的向量。

Step3：對L個向量進行函數適應度評估，選擇N個適應度最優(yōu)的向量作為初始種群。

利用改進Tent混沌方法產生一組較大的點庫，該點庫中的點均勻分布在問題解空間中，本文從中選取適應度最優(yōu)的前N個粒子作為初始種群，按照該選取方式使部分初始解分布在全局最優(yōu)點附近的概率較大，可有效幫助算法找到最優(yōu)解，并減少發(fā)現最優(yōu)解所需的迭代次數。

2.2 個體極值擾動

粒子群算法中粒子由個體最優(yōu)和全局最優(yōu)引導飛行，當個體最優(yōu)位置和全局最優(yōu)位置長時間停止更新時，粒子群算法陷入局部最優(yōu)，粒子會被聚集在一個很小的區(qū)域，由于速度很小，粒子難以找到更優(yōu)位置，此時需要擴大粒子搜索范圍，有利于讓粒子跳出局部最優(yōu)解，探索新區(qū)域。所以，個體最優(yōu)位置引入極值擾動以擴大粒子搜索范圍，避免粒子陷入局部最優(yōu)，常見方法為添加一個高斯擾動[18]。本文選擇添加一個簡單隨機擾動，亦能到達較好效果，將位置更新公式改為：

其中，[r3]是服從[U（0，1）]分布的隨機數，個體最優(yōu)值會隨著[r3]取值不同而發(fā)生范圍擾動，速度大小和方向也會發(fā)生改變。這種改進策略主要作用在迭代前期，種群搜索范圍擴大，粒子會飛向更多新位置，粒子容易發(fā)現更優(yōu)值，通過粒子間的相互學習，粒子會向更優(yōu)位置移動，減少粒子陷入局部最優(yōu)的可能。

2.3 Rosenbrock搜索法

Rosenbrock方法又稱為轉軸法，于1960年由Rosenbrock[16]提出，后由Bazaraa等改進，是一種解決無約束最優(yōu)化問題時無需函數導數信息的直接方法，該算法每次迭代包含探測階段和構造搜索方向兩部分，具體步驟[17]如下：

（1）探測階段。

Step1：給定一個初始可行解[x（1）∈Rn]，單位正交的n個方向[d（1），d（2），？，d（n）]，一般為坐標軸方向，搜索步長[δ（0）1，δ（0）2，？，δ（0）n，]放大因子[α>1]，縮小因子[β∈（-1，0）]和允許誤差[ε>0]。置[y（1）=x（1）]，[δi=δ（0）i，i=1，2，？，n]，置k=1，j=1。

Step2：如果[fy（j）+δjd（j）

Step3：如果[j

Step4：[fy（n+1）

Step5：[fy（n+1）

Step6：令[x（k+1）=y（n+1）]。如果[x（k+1）-x（k）<ε]，則取[x（k+1）]作為極小點的估計，停止計算;否則，進入構造新的搜索方向階段。

（2）構造新的搜索方向。

Step7： 根據上一階段探測結果，有[x（k+1）=x（k）+][i=1nλid（i）]，其中[λi]是探測階段中所有沿[d（i）]方向的步長代數和，向量[p=x（k+1）-x（k）]可能是有利于函數值下降的方向，為此定義一組向量[p（1），p（2），？，p（n）]為：

再利用施密特正交化，把向量組[p（j）]正交化，得：

再單位化，令：

由此得到n個新單位正交的搜索方向。

當粒子陷入局部最優(yōu)后，常利用高斯變異或混沌變異[19-20]幫助粒子跳出局部最優(yōu)，但由于缺乏一定的引導性，很多變異是無效的，并沒有讓粒子跳出局部最優(yōu)。Rosenbrock搜索算法增強了PSO算法局部搜索能力，可有效提高最優(yōu)解精度。另一方面，當粒子陷入局部最優(yōu)難以跳出時，一般情況下是粒子部分維度處于極差狀態(tài)。在合理選擇搜索步長[δ]及放大因子[α]和縮小因子[β]的情況下，Rosenbrock搜索可有效改善單個維度或幾個維度陷入較差值的情況，即增強粒子跳出局部最優(yōu)的能力。與極值擾動相比，該方法主要作用在粒子迭代后期，因為此時粒子速度較低，種群多樣性降低，跳出局部最優(yōu)的能力變差。

綜上所述，改進算法具體步驟如下：

Step1：設定混合粒子群算法及Rosenbrock搜索法的各項參數，并利用tent混沌映射初始化粒子的位置。

Step2：評價所有粒子的適應度，將個體粒子當前最優(yōu)位置設為[pi]，種群最優(yōu)位置設為[pg]。

Step3：按（6）式更新所有粒子的位置，評價所有粒子的適應度，并更新[pi]和[pg]。

Step4：若全局最優(yōu)粒子在T次迭代中未得到改變，則全局最優(yōu)粒子執(zhí)行Rosenbrock搜索，直到RosenBrock算法收斂或者Rosenbrock搜索次數達到設定值，更新[pg];否則，轉Step3。

Step5：若算法到達終止條件，則輸出全局最優(yōu)粒子的位置及其適應值，并停止迭代;否則，轉Step3。

3 仿真實驗及結果分析

3.1 基準測試函數

本文選取3個改進PSO算法與本文提出的改進算法共4個算法，分別對8個基準測試函數在30維和50維問題上進行性能比較。3個改進算法分別為：慣性權重線性遞減粒子群算法（PSO-W）、自適應擴展簡化粒子群算法（AESPSO）[6]和帶正弦函數因子的粒子群算法（TFPSO）[7]。

對不同的改進PSO算法設置相同的群體數量N=20，最大迭代次數T=1 000， PSO-w中[c1=c2=1.496 18]，[ωmax=0.9，ωmin=0.4]，AESPSO和TFPSO算法參數與對應文獻中的設置相同。

在本文RHPSO算法中，c1=c2=1.496 18，[ω=0.729 84]，混沌序列長度L=10 000，全局最優(yōu)值停滯更新的最大容忍次數M = 5，在Rosenbrock搜索中，初始搜索步長[δ]為半搜索區(qū)間的10%（如一維搜索區(qū)間為[-10，10，]則初始[δ=1]），放大因子[α=1.7]，縮小因子[β=-0.65]， 允許誤差[ε=10-6]，最大搜索次數[kmax=50]，即到達最大搜索次數，即使步長未達到允許誤差也會跳出搜索。

8個基準測試函數信息如表1所示。其中[f7x]中[ωi=1+xi4，i=1，？]。實驗測試函數主要分為兩類，第一類是[f1]～[f3]類的單峰函數，[f1]曲面規(guī)則一般用來測試算法尋優(yōu)精度的能力，[f3]是一個典型的病態(tài)函數，在高維時表現出多模態(tài)性質，由于其存在一條極細的溝壑，算法跳出局部最優(yōu)的機會很小，很難尋到全局最優(yōu)值點;第二類屬于非線性多模態(tài)函數，函數[f4]～[f8]屬于該類函數，由于三角函項的引入，使該類函數存在大量波峰波谷，在尋優(yōu)過程中極易陷入局部最優(yōu)，且當問題維數增大時，尋優(yōu)難度也隨之增加。

3.2 仿真實驗結果及分析

為檢驗改進算法性能，實驗分為兩組進行，問題維度分別為30和50，4種算法獨立運行30次以消除隨機性，并將30次結果求取的平均值、標準差和最優(yōu)值作為評估標準，4種算法中的最佳實驗結果加粗表示，實驗結果如表2、表3所示。

從表2可以看出本文提出的RHPSO算法在解決高維單峰和多峰問題上均有優(yōu)秀表現。與PSO-w算法相比，在8個函數中尋優(yōu)能力和穩(wěn)定性更好;TFPSO算法除在函數[f5]上可到達最優(yōu)值外，在其它7個函數上優(yōu)化結果均不如本文改進算法;與ASEPSO算法相比，本文改進算法主要在[f3]，[f7]，[f8]表現出明顯優(yōu)勢。[f3]是一個病態(tài)函數，在低維時表現出單峰特性，在高維時表現出多峰特性，在搜索過程中極易陷入局部最優(yōu)且難以跳出局部最優(yōu)。

由表2可看出PSO-w、TFPSO和ASEPSO算法在該函數上陷入局部最優(yōu)，從最優(yōu)值指標也可看出，這兩種改進算法在30次實驗中全部陷入局部最優(yōu)，本文算法在[f3]的尋優(yōu)過程中表現優(yōu)異，尋優(yōu)精度達到了[10-4]，在處理該函數時本文算法基本不會陷入局部最優(yōu)。對于[f7]和[f8]兩個多峰函數，3種已有的改進算法基本陷入了局部最優(yōu)，本文算法在處理[f7]函數時能尋得全局最優(yōu)點，在處理[f8]函數時偶有陷入局部最優(yōu)，但多數情況下能尋得全局最優(yōu)點，且尋優(yōu)精度達到[10-4]。

表3為4種算法在問題為50維下的測試結果，可以看出，隨著問題維度的提高，3種已有算法在8個測試函數上的性能不同程度降低，PSO-w算法精度上降低了一個數量級，TFPSO算法在函數[f1]和[f2]上精度降低了兩個數量級，50維實驗時RHPSO算法性能與30維實驗保持一致，說明問題維度增大時，本文算法仍能表現出十分良好的性能，具有較強的魯棒性。

3.3 最優(yōu)粒子進化曲線分析

為更直觀地比較4種算法收斂性能，本文繪制了全局最優(yōu)粒子收斂曲線圖。圖1（a）-圖1（f）是兩個單模態(tài)與4個多模態(tài)函數在30維時的進化曲線，橫軸為迭代次數，縱軸為適應值對數。

由圖1（a）和（b）進化曲線看出，RHPSO算法處理單模態(tài)問題和多模態(tài)問題時收斂速度明顯優(yōu)于其它3個改進算法。由圖1（c）、（e）和（f）可看出，RHPSO算法在搜索前期能較快地向最優(yōu)值靠近，當最優(yōu)粒子陷入局部最優(yōu)時，RHPSO算法能快速跳出局部最優(yōu)，并有較高的搜索精度。

顯然，與3種已有的改進方法相比，RHPSO算法收斂速度明顯提高，跳出局部最優(yōu)的能力明顯增強。

4 結語

本文針對PSO算法在解決高維多峰問題上易陷入局部最優(yōu)、收斂速度慢以及收斂精度低等不足，提出了一種融合Rosenbrock搜索的混合粒子群算法（RHPSO）。該算法以簡化粒子群的更新公式為基礎，引進3種優(yōu)化策略，分別是Tent混沌初始化種群、對個體極值加入擾動以及利用Rosenbrock搜索提高解的質量。表2、表3實驗中的8個測試函數尋優(yōu)結果表明，本文算法在高維單峰和多峰問題上均有良好的性能，求解精度高于已有改進算法，且在大部分函數上均能尋得最優(yōu)解，在解決一些容易陷入局部最優(yōu)的問題時也表現出良好性能。由圖1可看出，相比于其它改進算法，本文算法收斂速度明顯提高。

但本文算法對函數[f8]測試結果仍不太理想，尚有部分實驗結果陷入局部最優(yōu)，穩(wěn)定性有待提高。此外，面對不同問題時，Rosenbrock搜索參數的設定會影響算法搜索性能，找出一套自適應選擇參數的方案，可增強算法對問題的普適性，這些問題是下一步研究內容。

參考文獻：

[1] KENNEDY J，EBERHART R. Particle swarm optimization[C]. IEEE International Conference on Neural Networks，1995：1942-1948.

[2] 田峰，林榮文，吳雅琳. 基于CMPSO算法的永磁同步電機轉動慣量識別研究[J]. 電機與控制應用，2019，46（10）：14-18，65.

[3] 李輝，王軍. 基于粒子群算法與循環(huán)神經網絡的短期電力負荷預測[J]. 軟件導刊，2017，16（11）：125-128.

[4] 裴佳佳，劉媛華. 基于多因素灰色模型的上海市基層醫(yī)療機構診療量預測[J]. 軟件導刊，2019，18（6）：130-134.

[5] SHI Y H， EBERHART R C. Fuzzy adaptive particle swarm optimization[C]. 2001 Congress on Evolutionary Computation[C]. 2001： 101-106.

[6] ZHANG L，TANG Y，HUA C， et al. A new particle swarm optimization algorithm with adaptive inertia weight based on Bayesian techniques[J].? Applied Soft Computing， 2015（28）：138-149.

[7] 楊智，陳穎. 改進粒子群算法及其在PID整定中的應用[J]. 控制工程，2016，23（2）：161-166.

[8] 楊曉，王國柱. 基于PID控制理論的改進粒子群優(yōu)化算法[J]. 控制工程，2019，26（8）：1497-1502.

[9] 胡旺，李志蜀. 一種更簡化而高效的粒子群優(yōu)化算法[J]. 軟件學報，2007（4）：861-868.

[10] 趙志剛，張振文，張福剛. 自適應擴展的簡化粒子群優(yōu)化算法[J]. 計算機工程與應用，2011，47（18）：45-47.

[11] 邵鵬，吳志健. 一種帶正弦函數因子的粒子群優(yōu)化算法[J]. 小型微型計算機系統(tǒng)，2015，36（1）：156-161.

[12] SHIEH H L，KUO C C，CHIANG C M.? Modified particle swarm optimization algorithm with simulated annealing behavior and its numerical verification[J]. Applied Mathematics & Computation， 2011， 218（8）：4365-4383.

[13] 袁光輝，樊重俊，張惠珍，等. 一種新的粒子群算法與人工魚群算法的混合算法[J]. 上海理工大學學報，2014，36（3）：223-226，238.

[14] CHANG Y P. Integration of SQP and PSO for optimal planning of harmonic filters[J].? Expert Systems with Applications， 2010， 37（3）：2522-2530.

[15] 張娜，趙澤丹，包曉安，等. 基于改進的Tent混沌萬有引力搜索算法[J/OL]. 控制與決策：1-8.https：//doi.org/10.13195/j.kzyjc.2018. 0795.

[16] ROSENBROCK H H. An automatic method for finding the greatest or least value of a function[J]. Computer Journal，1960，3（3）： 175-184.

[17] 陳寶林.? 最優(yōu)化理論與算法[M]. 北京：清華大學出版社，2005.

[18] 艾兵，董明剛. 基于高斯擾動和自然選擇的改進粒子群優(yōu)化算法[J]. 計算機應用，2016，36（3）：687-691.

[19] 韓敏，何泳. 基于高斯混沌變異和精英學習的自適應多目標粒子群算法[J]. 控制與決策，2016，31（8）：1372-1378.

[20] 吳定海，張培林，李勝，等. 基于混沌變異的自適應雙粒子群優(yōu)化[J]. 控制與決策，2011，26（7）：1083-1086，1095.

（責任編輯：江 艷）