基于布朗運動與梯度信息的交替優(yōu)化算法

沙林秀，聶凡，高倩，孟號

基于布朗運動與梯度信息的交替優(yōu)化算法

沙林秀，聶凡*，高倩，孟號

（西安石油大學 電子工程學院，西安 710065）（ ? 通信作者電子郵箱1823032532@qq.com）

針對群智能優(yōu)化算法在優(yōu)化過程中容易陷入局部最優(yōu)、種群多樣性低以及高維函數(shù)優(yōu)化困難的問題，提出一種基于布朗運動與梯度信息的交替優(yōu)化算法（AOABG）。首先，采用全局、局部搜索交替的尋優(yōu)策略，即在有變優(yōu)趨勢的范圍內(nèi)切換為局部搜索，有變劣趨勢的范圍內(nèi)切換為全局搜索；然后，局部搜索引入基于梯度信息的均勻分布概率的隨機游走，全局搜索引入基于最優(yōu)解位置的布朗運動的隨機游走。將所提出的AOABG與近三年的哈里斯鷹優(yōu)化算法（HHO）、麻雀搜索算法（SSA）、特種部隊算法（SFA）在10個測試函數(shù)上對比。當測試函數(shù)維數(shù)為2、10時，AOABG在10個測試函數(shù)上的100次最終優(yōu)化結果的均值與均方差均優(yōu)于HHO、SSA與SFA。當測試函數(shù)為30維時，除了HHO在Levy函數(shù)上的表現(xiàn)優(yōu)于AOABG（兩者優(yōu)化結果均值處于同一數(shù)量級）外，AOABG在其他9個測試函數(shù)上表現(xiàn)最好，與上述算法相比，優(yōu)化結果均值提升了4.64%～94.89%。實驗結果表明，AOABG在高維函數(shù)優(yōu)化中收斂速度更快、穩(wěn)定性更好、精度更高。

交替尋優(yōu)策略；高維函數(shù)優(yōu)化；收斂速度；布朗運動；梯度信息

0 引言

目前，群智能優(yōu)化算法已經(jīng)成為研究解決非凸全局優(yōu)化問題的熱點。此類算法基于生物習性或人類經(jīng)驗而構造，以仿自然算法為主，具有操作簡單、易于并行處理、魯棒性強等特點。國內(nèi)外眾多學者受到自然界中許多自適應優(yōu)化現(xiàn)象的啟發(fā)，模擬生物群體機制設計出了遺傳算法（Genetic Algorithm， GA）、蟻群優(yōu)化（Ant Colony Optimization， ACO）算法、粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法等多種仿生智能算法［1］。除上述幾種經(jīng)典群智能優(yōu)化算法外，Zong等［2］在2001年提出了和聲搜索（Harmony Search， HS）；劍橋?qū)W者Yang［3-5］2008年提出了螢火蟲算法（Firefly Algorithm，F(xiàn)A），2009年與拉曼工程大學Deb教授提出布谷鳥搜索（Cuckoo Search， CS），2010年提出了蝙蝠算法（Bat Algorithm， BA）。以上這些算法雖然都各有特色，但在迭代后期都有不同程度的種群多樣性趨同、全局尋優(yōu)能力依靠隨機變異、難以進一步優(yōu)化的問題。最近幾年有Heidari等［6］在2019年提出了哈里斯鷹優(yōu)化（Harris Hawk Optimization， HHO）算法；2020年Xue等［7］提出了麻雀搜索算法（Sparrow Search Algorithm， SSA）；2021年潘科等［8］提出了特種部隊算法（Special Forces Algorithm， SFA），這三種算法較前面的優(yōu)化算法采用了分類尋優(yōu)策略，如HHO的探索階段、開發(fā)階段；SSA的發(fā)現(xiàn)者、跟隨者；SFA的探索階段、過渡階段、開發(fā)階段。并且，個體之間除了合作，還有一定的獨立探索、競爭等，因此在尋優(yōu)性能上有進一步提升。然而與其他群智能算法類似，隨著目標函數(shù)維度的增加，搜索過程同樣容易出現(xiàn)陷入局部最優(yōu)、種群多樣性低、收斂精度低的問題。

作為大多數(shù)群智能優(yōu)化算法產(chǎn)生的來源，自然界中生物的自適應現(xiàn)象因個體有不同程度地向最優(yōu)個體學習的行為，這保證了算法局部尋優(yōu)能力，但此行為的內(nèi)在趨同特征是導致許多優(yōu)化算法會陷入局部最優(yōu)的原因。而生物卻仍在不斷進化，這是因為復雜的外部環(huán)境變化，如其他種群的侵略競爭、自然環(huán)境的優(yōu)劣交替等，這些干擾因素的引入讓種群產(chǎn)生分離，各自與新的外部環(huán)境調(diào)整至一個新的平衡從而進一步進化。這一部分處理的好壞直接影響算法全局尋優(yōu)能力，而許多優(yōu)化算法在這一塊處理多采用隨機生成新解，且在貪心策略的作用下，對解空間的探索不夠充分。如文獻［9］中采用柯西分布函數(shù)以一定概率對當前最優(yōu)解施加擾動，此策略雖能提高全局搜索能力，但僅對當前最優(yōu)解使用，全局搜索能力提升有限；文獻［10］中對所有個體以一定概率進行以當前最優(yōu)解為基礎的反向?qū)W習，雖然此策略是對所有個體使用，但受貪心策略的影響，對解空間探索依舊有限；文獻［11］中則采用精英等級制度，即用當前多個優(yōu)勢個體信息引導其他個體搜索，此策略雖能改善逃脫局部最優(yōu)的能力，但逃脫范圍受限于優(yōu)勢個體所圍的空間。綜上所述，如何讓群智能優(yōu)化算法同時有強的全局尋優(yōu)與局部尋優(yōu)能力是提升算法尋優(yōu)性能的關鍵。

本文在群智能優(yōu)化算法的多個解并行優(yōu)化思想這一基礎上，設計了全局、局部交替搜索的搜索策略并提出了基于布朗運動與梯度信息的交替優(yōu)化算法（Alternately Optimizing Algorithm based on Brownian-movement and Gradient-information， AOABG），以提高解空間的搜索效率與搜索精度。實驗結果表明，在高維函數(shù)優(yōu)化中能更快、更穩(wěn)定地搜索到全局最優(yōu)解。

1 基于布朗運動與梯度信息的交替優(yōu)化算法

1.1　交替尋優(yōu)策略

全局搜索和局部搜索的目的不一樣，完成這兩種搜索的算子自然也不同。因此將全局、局部搜索分開單獨執(zhí)行，個體在優(yōu)化過程中不斷切換這兩種狀態(tài)，既能同時找到局部最優(yōu)而又不陷入局部最優(yōu)，能更好地兼顧目標函數(shù)解空間的搜索效率與搜索精度。交替尋優(yōu)策略流程如圖1所示。

AOABG是以交替尋優(yōu)策略為基礎，利用梯度信息和布朗運動分別輔助局部搜索與全局搜索，下面將從以上各個方面逐個介紹。

圖1　交替尋優(yōu)策略流程

1.2　搜索縮減因子

1.3　局部搜索策略

局部搜索，即在個體所在鄰域內(nèi)盡可能探索更優(yōu)個體，只需能快速搜索到局部最優(yōu)即可。梯度下降法因其實現(xiàn)簡單，局部搜索效果明顯，可作為個體優(yōu)化的局部搜索策略。因此，個體在局部搜索時策略如式（2）所示：

1.4　全局搜索策略

在全局最優(yōu)解的搜索中，應以盡可能多地、均勻地搜索整個解空間為目的。考慮到自然界中的擴散現(xiàn)象，如一滴墨水滴在水中，由中心向四周擴散最終至整片水中。此擴散在微觀下粒子做的布朗運動，宏觀下做的是從中心點向四周發(fā)散的運動。

因此，以當前群體最優(yōu)個體為中心，做擴散運動，即從中心向四周發(fā)散為搜索方向，并附加布朗運動引入全局最優(yōu)解的搜索策略中實現(xiàn)全局搜索。

1.4.1布朗運動

布朗運動是指懸浮在液體或氣體中的微粒所做的永不停息的無規(guī)則運動，維納過程是布朗運動的數(shù)學模型。維納過程定義如下。

3）（）關于是連續(xù)函數(shù)。

因此，維布朗運動的遞增的增量如式（4）所示：

1.4.2全局搜索

個體在全局搜索時的搜索方向為以最優(yōu)個體向四周發(fā)散的方向，如式（5）所示：

（5）

其中：，作為參數(shù)自行設置。二維中的全局搜索策略如圖2所示。

圖3　全局搜索策略下二維空間搜索軌跡與點分布

1.5　局部與全局搜索切換

局部搜索著重搜索個體所在鄰域內(nèi)的極值，并在極值處震蕩或無限逼近；全局搜索可著重均勻搜索解空間。因而，局部搜索與全局搜索的切換實現(xiàn)非常重要。

1.5.1局部搜索向全局搜索切換

當局部搜索靠近某一極值時，若在極值點處斜率較小，搜索遞增的模（二范數(shù)）會很?。蝗粼跇O值點處斜率較大，搜索時的目標函數(shù)會不斷震蕩，喪失單調(diào)性。當出現(xiàn)這兩個特征時，即可放棄局部搜索，轉(zhuǎn)向全局搜索。局部搜索向全局搜索切換的偽代碼為：

procedureLocalSearchToGlobalSearch

foreach local searching individualin iteration

end for

end procedure

1.5.2全局搜索向局部搜索切換

全局搜索過程中，如果目標函數(shù)出現(xiàn)變差的趨勢，說明正在脫離之前局部搜索到的極值范圍；如果目標函數(shù)有變優(yōu)的趨勢，說明周圍有新的極值存在，此時，可放棄全局搜索，轉(zhuǎn)向局部搜索。偽代碼為：

procedure GlobalSearchToLocalSearch

for each local searching individualin iteration

end for

end procedure

1.6　最優(yōu)個體處理與邊界處理

1.6.1最優(yōu)個體處理

最優(yōu)個體表示當前種群中的最優(yōu)解，為了不讓最優(yōu)個體在全局搜索中被破壞，最優(yōu)個體應始終處于局部搜索狀態(tài)，在此，采用施加柯西概率分布的擾動作用于最優(yōu)個體，其計算如式（7）所示：

在采用施加柯西概率分布的擾動后，再采用貪心策略保證最優(yōu)個體不被破壞。其計算如式（8）所示：

1.6.2邊界處理

在算法更新時，會出現(xiàn)個體搜索到定義域之外的情況。局部搜索時，只需將越出定義域邊界的個體限制在邊界上即可。但是，全局搜索時，個體出離邊界意味著此方向的搜索已結束，需重新從已搜索到的最優(yōu)個體附近出發(fā)，隨機選擇方向繼續(xù)搜索。

1.7　AOABG執(zhí)行流程

AOABG的算法流程如圖4所示。

1.8　算法時間復雜度分析

從AOABG時間復雜度中可以看到，相較于常規(guī)的群智能優(yōu)化算法，因AOABG在局部尋優(yōu)時采取了梯度下降法，時間復雜度與目標函數(shù)的維度成正相關。

圖4　AOABG的流程

2 實驗與結果分析

2.1　算法及參數(shù)設置

表1算法參數(shù)設置

Tab.1　Parameter settings of algorithms

2.2　測試函數(shù)

2.3　對比實驗結果

實驗環(huán)境為：Inter i5 CPU 2.90 GHz、RAM 16.0 GB、Windows 10操作系統(tǒng)，Matlab R2015a。

表2測試函數(shù)

Tab.2　Test functions

實驗結果統(tǒng)計了采用HHO、SSA、SFA與AOABG分別求解10個測試函數(shù)獲得最優(yōu)值均值、均方差，見表3～5，加粗數(shù)值表示在該測試函數(shù)下與其他算法相比結果最優(yōu)。

同時，為分析不同優(yōu)化算法的收斂速度，給出測試函數(shù)1～8在2維、30維時的優(yōu)化收斂曲線，如圖5、6所示。

表3各算法優(yōu)化結果（=2，=10）

Tab.3　Optimization results of different algorithms （s=2，n=10）

表4各算法優(yōu)化結果（=10，=20）

Tab.4　Optimization results of different algorithms （s=10，n=20）

2.4　實驗結果分析

綜合分析表3～5和圖5、6的實驗數(shù)據(jù)，可以得出以下結果：

1） 從表3～5中可以看出，在測試函數(shù)維數(shù)為2、10時，AOABG在10個測試函數(shù)下的優(yōu)化結果均值均優(yōu)于HHO、SSA與SFA，同時優(yōu)化結果的均方差也最?。划敎y試函數(shù)為30維時，除了HHO在4上表現(xiàn)優(yōu)于AOABG（兩者優(yōu)化結果均值處于同一數(shù)量級）外，AOABG在其他9個測試函數(shù)中同樣表現(xiàn)最好。

表5各算法優(yōu)化結果（=30，=30）

Tab.5　Optimization results of different algorithms （s=30，n=30）

圖5　二維測試函數(shù)F1～F8下的優(yōu)化曲線

圖6　30維測試函數(shù)F1～F8下的優(yōu)化曲線

當目標函數(shù)為30維時，與其他算法相比，AOABG除4（Levy函數(shù)）外的優(yōu)化最優(yōu)值均值分別提升了49.76%、94.89%、87.35%、83.75%、37.21%、10.44%、4.64%，53.05%、31.89%，其中，提升幅度最小的是在單峰函數(shù)8的最優(yōu)值，為4.64%，可以看到各算法的局部尋優(yōu)能相差不大；提升幅度最大的是在多峰函數(shù)2的最優(yōu)值，為94.89%，AOABG普遍在多峰測試函數(shù)中最優(yōu)值提升明顯，可以看出AOABG采用的全局尋優(yōu)策略能明顯提高算法的全局搜索能力。

仿真結果表明：在高維函數(shù)優(yōu)化時，AOABG的全局搜索性能較其他函數(shù)有明顯提高。

3 結語

采用全局、局部交替搜索的交替尋優(yōu)策略結構，引入梯度信息引導局部搜索、布朗運動引導全局搜索提出的AOABG在高維函數(shù)優(yōu)化中的全局尋優(yōu)能力、收斂速度和尋找到的全局最優(yōu)解絕大多數(shù)優(yōu)于近三年提出的HHO、SSA和SFA算法。

同樣，AOABG缺點也較為明顯，即局部尋優(yōu)采用了梯度信息策略，梯度信息的計算很大程度上影響了算法的時間復雜度。若能在局部尋優(yōu)策略中引入更有效的策略，算法性能將會有進一步提升。

在當前待優(yōu)化函數(shù)逐漸向高維度發(fā)展的趨勢下，如石油領域內(nèi)的石油鉆井控制參數(shù)優(yōu)選、三維復雜井眼軌跡優(yōu)化［15］等，此優(yōu)化思路可為解決多維復雜問題優(yōu)化提供參考，具有一定應用推廣價值。

[1] 段海濱，葉飛. 鴿群優(yōu)化算法研究進展［J］. 北京工業(yè)大學學報， 2017， 43（1）：1-7.（DUAN H B， YE F. Progresses in pigeon-inspired optimization algorithms［J］. Journal of Beijing University of Technology， 2017， 43（1）：1-7.）

[2] ZONG W G， KIM J H， LOGANATHAN G V. A new heuristic optimization algorithm： harmony search［J］. Simulation， 2001， 2（2）：60-68.

[3] YANG X S. Firefly algorithms for multimodal optimization［C］// Proceedings of the 5th International Conference on Stochastic Algorithms： Foundations and Applications. Cham： Springer， 2009：169-178.

[4] YANG X S， DEB S. Cuckoo search via Lévy flights［C］// Proceedings of the 2009 World Congress on Nature and Biologically Inspired Computing. Piscataway： IEEE， 2009：210-214.

[5] YANG X S. A new metaheuristic bat-inspired algorithm［J］. Computer Knowledge and Technology， 2010， 284：65-74.

[6] HEIDARI A A， MIRJALILI S， FARIS H， et al. Harris hawks optimization： algorithm and applications［J］. Future Generation Computer Systems， 2019， 97：849-872.

[7] XUE J K， SHEN B. A novel swarm intelligence optimization approach： sparrow search algorithm［J］. Systems Science and Control Engineering， 2020，8（1）：22-34.

[8] 潘科，張偉，王亞剛. 特種部隊算法：一種新的元啟發(fā)式算法［J/OL］. 控制與決策. （2021-08-02） ［2021-08-21］. http：//kns.cnki.net/kcms/detail/21.1124.TP.20210802.1113.044.html.（PAN K， ZHANG W， WANG Y G. Special forces algorithm： a new meta-heuristic algorithm［J/OL］. Control and Decision. （2021-08-02） ［2021-08-21］.http：//kns.cnki.net/kcms/detail/21.1124.TP.20210802.1113.044.html.）

[9] 郭雨鑫，劉升，高文欣，等. 多策略改進哈里斯鷹優(yōu)化算法［J］. 微電子學與計算機， 2021， 38（7）：18-24.（GUO Y X， LIU S， GAO W X， et al. Improved Harris hawks optimization algorithm with multiple strategies［J］. Microelectronics and Computer， 2021， 38（7）：18-24.）

[10] 毛清華，張強. 融合柯西變異和反向?qū)W習的改進麻雀算法［J］. 計算機科學與探索， 2021， 15（6）：1155-1164.（MAO Q H， ZHANG Q. Improved sparrow algorithm combining Cauchy mutation and opposition-based learning［J］. Journal of Frontiers of Computer Science and Technology， 2021， 15（6）：1155-1164.）

[11] 湯安迪，韓統(tǒng)，徐登武，等. 混沌精英哈里斯鷹優(yōu)化算法［J］. 計算機應用， 2021， 41（8）：2265-2272.（TANG A D， HAN T， XU D W， et al. Chaotic elite Harris hawks optimization algorithm［J］. Journal of Computer Applications， 2021， 41（8）：2265-2272.）

[12] 國強，朱國會，李萬臣. 基于混沌麻雀搜索算法的TDOA/FDOA定位［J/OL］. 吉林大學學報（工學版）. （2021-09-02） ［2021-09-11］.http：//kns.cnki.net/kcms/detail/22.1341.t.20210901.1814.023.html.（GUO Q， ZHU G H， LI W C. TDOA/FDOA localization based on chaotic sparrow search algorithm［J/OL］. Journal of Jilin University （Engineering and Technology Edition）. （2021-09-02） ［2021-09-11］.http：//kns.cnki.net/kcms/detail/22.1341.t.20210901.1814.023.html.）

[13] 夏學文，劉經(jīng)南，高柯夫，等. 具備反向?qū)W習和局部學習能力的粒子群算法［J］. 計算機學報， 2015， 38（7）：1397-1407.（XIA X W， LIU J N， GAO K F， et al. Particle swarm optimization algorithm with reverse-learning and local-learning behavior［J］. Chinese Journal of Computers， 2015， 38（7）：1397-1407.）

[14] 張永韡，汪鐳，吳啟迪. 動態(tài)適應布谷鳥搜索算法［J］. 控制與決策， 2014， 29（4）：617-622.（ZHANG Y W， WANG L， WU Q D. Dynamic adaptation cuckoo search algorithm［J］. Control and Decision， 2014， 29（4）：617-622.）

[15] SHA L X， PAN Z Q. FSQGA based 3D complexity wellbore trajectory optimization［J］. Oil and Gas Science and Technology， 2018， 73： No.79.

SHA Linxiu， born in 1978， Ph. D.， associate professor. Her research interests include intelligent drilling control.

NIE Fan， born in 1997， M. S. candidate. His research interests include drilling optimization.

GAO Qian， born in 1995， M. S. candidate. Her research interests include virtual reality.

MENG Hao， born in 1993， M. S. candidate. His research interests include detection system， graphic processing.

Alternately optimizing algorithm based on Brownian movement and gradient information

SHA Linxiu， NIE Fan*， GAO Qian， MENG Hao

（，’，’710065，）

Aiming at the problems that swarm intelligence optimization algorithms are easy to fall into local optimum as well as have low population diversity in the optimization process and are difficult to optimize high-dimensional functions， an Alternately Optimizing Algorithm based on Brownian-movement and Gradient-information （AOABG） was proposed. First， a global and local alternately optimizing strategy was used in the proposed algorithm， which means the local search was switched in the range of getting better and the global search was switched in the range of getting worse. Then， the random walk of uniform distribution probability based on gradient information was introduced into local search， and the random walk of Brownian motion based on optimal solution position was introduced into global search. The proposed AOABG algorithm was compared with Harris Hawk Optimization （HHO）， Sparrow Search Algorithm （SSA） and Special Forces Algorithm （SFA） on 10 test functions. When the dimension of test function is 2 and 10， the mean value and standard deviation of AOABG’s 100 final optimization results on 10 test functions are better than those of HHO， SSA and SFA. When the test function is 30-dimensional， except for Levy function where HHO performs better than AOABG but the mean value of the two is in the same order of magnitude， AOABG performs best on the other nine test functions with an increase of 4.64%-94.89% in the average optimization results compared with the above algorithms. Experimental results show that AOABG algorithm has faster convergence speed， better stability and higher accuracy in high-dimensional function optimization.

alternately optimizing strategy; high-dimensional function optimization; convergence rate; Brownian movement; gradient information

This work is partially supported by Key Science and Technology Project of Shaanxi Province （2020GY-046）， Postgraduate Innovation and Practical Ability Training Program of Xi’an Shiyou University（YCS21212115）.

TP301.6

A

1001-9081（2022）07-2139-07

10.11772/j.issn.1001-9081.2021050839

2021?05?21；

2021?09?29；

2021?09?30。

陜西省科技攻關重點項目（2020GY?046）；西安石油大學研究生創(chuàng)新與實踐能力培養(yǎng)計劃項目（YCS21212115）。

沙林秀（1978—），女，陜西安康人，副教授，博士，主要研究方向：智能鉆井控制； 聶凡（1997—），男，四川廣安人，碩士研究生，主要研究方向：鉆井優(yōu)化； 高倩（1995—），女，陜西渭南人，碩士研究生，主要研究方向：虛擬現(xiàn)實； 孟號（1993—），男，安徽淮北人，碩士研究生，主要研究方向：檢測系統(tǒng)、圖形處理。