基于狼群搜索算法的函數(shù)優(yōu)化問題求解*

孫 潔， 王姍姍

(1.西北大學(xué) 現(xiàn)代學(xué)院，陜西 西安 710130 ; 2.西安工程大學(xué) 理學(xué)院, 陜西 西安 710048)

在生產(chǎn)和實(shí)際中，一些科研和工程領(lǐng)域問題能夠轉(zhuǎn)換為函數(shù)優(yōu)化問題，并可以通過建模方法對(duì)函數(shù)優(yōu)化問題進(jìn)行分析和求解.函數(shù)優(yōu)化問題有多種類型，變化曲線十分復(fù)雜，大多數(shù)具有高維、非線性、不可微等特點(diǎn)，導(dǎo)致傳統(tǒng)統(tǒng)計(jì)學(xué)方法無法對(duì)其進(jìn)行有效求解，有的雖然能求解，但是求解精度低、通用性差，因此函數(shù)優(yōu)化問題求解一直是現(xiàn)代數(shù)學(xué)研究領(lǐng)域中的難點(diǎn)[1-2].

隨著仿生學(xué)研究的不斷深入，出現(xiàn)許多模擬生物習(xí)性的智能算法，如遺傳算法、布谷鳥搜索算法、蟑螂算法、人工蜂群算法等，學(xué)者們將這些仿生智能算法以及一些改進(jìn)算法引入函數(shù)優(yōu)化問題的求解過程中，函數(shù)優(yōu)化問題的求解結(jié)果要明顯優(yōu)于傳統(tǒng)統(tǒng)計(jì)學(xué)方法[3-5].在實(shí)際應(yīng)用中，這些仿生智能算法也存在一定的不足，如遺傳算法的遺傳算子難以確定，布谷鳥搜索算法和人工蜂群算法的種群初始化沒有統(tǒng)一理論指導(dǎo)，經(jīng)常獲得函數(shù)優(yōu)化問題的局部最優(yōu)點(diǎn)，尤其對(duì)于復(fù)雜、高維的函數(shù)優(yōu)化問題，收斂速度慢、精度低，獲得全局最優(yōu)解的概率小[6].狼群搜索算法是一種模擬狼群捕食行為的新型仿生智能算法，最初被用于機(jī)器人路徑規(guī)劃問題的求解，隨后有學(xué)者將其與人工蜂群算法進(jìn)行融合，應(yīng)用于求解TSP問題，取得了不錯(cuò)的效果[7].

為了獲得更加理想的函數(shù)優(yōu)化問題的解，本文提出了基于狼群搜索算法的函數(shù)優(yōu)化問題求解方法，并通過具體函數(shù)優(yōu)化問題求解的仿真實(shí)驗(yàn)測(cè)試其性能.結(jié)果表明，狼群搜索算法的函數(shù)優(yōu)化問題求解整體性能要優(yōu)于其他方法.

1 函數(shù)優(yōu)化問題的描述

函數(shù)優(yōu)化問題通?？梢圆捎靡粋€(gè)3元組描述，具體為：G=(S，Ω，f)，其中S表示函數(shù)優(yōu)化問題的變量Xi(i=1,2,…,m)，Ω表示函數(shù)優(yōu)化問題的相關(guān)約束，f為優(yōu)化函數(shù).x∈X，x={x1，x2，…，xD}表示函數(shù)優(yōu)化問題的解，則可以建立如下形式的模型.

min(f(x)) ,x=(x1,x2,…,xd) ,s.t.l≤x≤u.

式中，l=(l1，l2，…，lD)和u=(u1，u2，…，uD)表示解的取值范圍.

2 狼群搜索算法

一群狼中，經(jīng)常有一個(gè)狼頭稱為領(lǐng)導(dǎo)者，而領(lǐng)導(dǎo)者不是固定不變的，通常會(huì)通過競(jìng)爭，獲勝的狼才能成為領(lǐng)導(dǎo)者.狼群分工十分明確,領(lǐng)導(dǎo)者帶領(lǐng)狼群進(jìn)行捕食，在捕食過程中，均以領(lǐng)導(dǎo)者所在位置為導(dǎo)向，通過嚎叫進(jìn)行信息傳遞和共享，捕捉到獵物后，狼群根據(jù)優(yōu)勝劣汰、適者生者的原則對(duì)獵物進(jìn)行分配，而狼群搜索算法就是根據(jù)該理論提出的一種仿生智能算法.對(duì)一個(gè)待優(yōu)化求解的問題，狼群搜索算法通過狼群中個(gè)體的相互協(xié)作、競(jìng)爭找到最優(yōu)解，其工作步驟如下：

(1) 產(chǎn)生狼群.每頭狼與待優(yōu)化求解問題的解一一對(duì)應(yīng)，在解的空間中隨機(jī)產(chǎn)生N頭狼，解的空間維數(shù)為D，那么第i頭狼的位置可以描述為：

Xi=(xi1,xi2,…,xid,…,xiD,)，xid=xmin+rand×(xmax-xmin).

式中，rand表示隨機(jī)數(shù)，xmax和xmin分別為解空間的搜索范圍.

(2) 競(jìng)爭領(lǐng)導(dǎo)者.為了更好得到頭狼，首先從狼群中選擇出q頭最優(yōu)狼，它們均在附件h個(gè)方向進(jìn)行搜索，若較優(yōu)狼的當(dāng)前位置為Pi=(pi1,…,pid,…,piD)，其周圍最好位置為P1，若P1優(yōu)于當(dāng)前位置，那么P1作為當(dāng)前位置繼續(xù)進(jìn)行搜索，如果搜索次數(shù)大于競(jìng)爭領(lǐng)導(dǎo)者的最大搜索次數(shù)，那么就認(rèn)為此時(shí)已經(jīng)找到了狼群的領(lǐng)導(dǎo)者.設(shè)xxid表示第i只競(jìng)選狼的當(dāng)前位置，那么其周圍的第j個(gè)點(diǎn)位置為yjd=xxid+rand×stepa，式中stepa表示狼群搜索的步長.

(3) 狼群的移動(dòng).為了更好發(fā)現(xiàn)和搜索獵物，其他狼均向狼群領(lǐng)導(dǎo)者所在的位置不斷移動(dòng)，但是有時(shí)候獵物不一定處于狼群領(lǐng)導(dǎo)者搜索的方向，那么此時(shí)有的狼就會(huì)遠(yuǎn)離領(lǐng)導(dǎo)者，狼群移動(dòng)后，第i只狼的位置為：zid=xid+rand×stepb×(xld-xid)，式中，stepb表示狼群的移動(dòng)步長；xld表示狼群領(lǐng)導(dǎo)者的當(dāng)前位置.如果狼的新位置zi=(zi1,…,zid,…,ziD)優(yōu)于當(dāng)前位置，那么新位置取代當(dāng)前位置，完成獵物搜索移動(dòng).

(1)

式中，rm表示隨機(jī)數(shù)，θ表示一個(gè)閾值，ra為狼群包圍的步長.從式(1)可知，當(dāng)rm>θ時(shí)，第i頭狼對(duì)獵物進(jìn)行包圍，不然該狼不進(jìn)行移動(dòng)，位置保持不變.實(shí)現(xiàn)獵物包圍后，狼群中有的狼位置可能出現(xiàn)越界現(xiàn)象，即不在問題解的搜索范圍內(nèi)，那么應(yīng)該做如下處理

在實(shí)際應(yīng)用中，隨著迭代次數(shù)的增加，狼群越來越接近最優(yōu)解，那么狼群包圍的步長要做相應(yīng)的改變，即步長值應(yīng)該不斷縮小，在第t次迭代時(shí)，ra的變化方式具體為

式中，maxt表示最大迭代次數(shù)，ramax和ramin表示包圍步長的取值范圍.

(5) 獵物分配.根據(jù)獵物分配原則對(duì)獲取的獵物進(jìn)行分配，最優(yōu)分配獵物的為狼頭，其次為較粗壯的一些狼，最后為一些弱小的狼，從而使最弱小的狼可能會(huì)分不到獵物而餓死，強(qiáng)壯狼可以繼續(xù)生存下去，這樣符合生物種群進(jìn)化的優(yōu)勝劣汰、適者生存原則.對(duì)于餓死的m匹狼，采用隨機(jī)方式生成，從而保持種群的多樣性，并且可以加快算法的收斂速度，提高問題解的精度.

3 狼群搜索算法的性能測(cè)試與分析

3.1 測(cè)試函數(shù)

為了評(píng)價(jià)狼群搜索算法對(duì)函數(shù)優(yōu)化問題的求解性能，采用MATLAB 2014作為仿真平臺(tái)，從當(dāng)前經(jīng)典函數(shù)集中選擇4個(gè)具有代表性的函數(shù)作為測(cè)試對(duì)象，具體如下：

上述函數(shù)中：f1是最簡單的函數(shù)，只有一個(gè)峰值；f2、f3具有高維、非線性變化特性，而且有多個(gè)峰值；f4是一個(gè)非凸病態(tài)函數(shù)，很難收斂到全局最優(yōu)點(diǎn).其中f3和f4的解空間圖如圖1所示.

3.2 結(jié)果與分析

對(duì)狼群搜索算法的相應(yīng)參數(shù)進(jìn)行設(shè)置，然后每一個(gè)函數(shù)求解50次，統(tǒng)計(jì)它們的平均求解結(jié)果，采用解的值、找到最優(yōu)解的迭代次數(shù)、求解時(shí)間作為評(píng)價(jià)指標(biāo)，結(jié)果如表1所示.對(duì)表1的實(shí)驗(yàn)結(jié)果進(jìn)行分析可以得出：在大多數(shù)情況下，狼群搜索算法能夠找到函數(shù)優(yōu)化問題的最優(yōu)解，而且解的精度相當(dāng)高，找到解的時(shí)間短，可以較快的收斂速度找到問題最優(yōu)解，實(shí)驗(yàn)結(jié)果驗(yàn)證了狼群搜索算法應(yīng)用于函數(shù)優(yōu)化問題求解的有效性和合理性.

表1 狼群搜索算法的性能測(cè)試

為了使狼群搜索算法的函數(shù)優(yōu)化問題求解結(jié)果具有可比性，選擇粒子群算法進(jìn)行對(duì)比測(cè)試，采用平均值作為性能對(duì)比指標(biāo)，結(jié)果如表2所示.分析表2可以發(fā)現(xiàn)，在相同實(shí)驗(yàn)條件下，狼群搜索算法的求解精度要優(yōu)于粒子群優(yōu)化算法，找到最優(yōu)解的迭代次數(shù)明顯減少，平均求解時(shí)間也大幅度降低，加快了函數(shù)優(yōu)化問題的收斂速度.實(shí)驗(yàn)結(jié)果驗(yàn)證了狼群搜索算法對(duì)于函數(shù)優(yōu)化問題求解的優(yōu)越性.

表2 與粒子群優(yōu)化算法的性能對(duì)比

4 基于狼群搜索算法的無線電異常信號(hào)特征選擇

異常信號(hào)識(shí)別是無線電信號(hào)監(jiān)測(cè)的一項(xiàng)關(guān)鍵技術(shù)，有利于保障無線電信號(hào)的正常傳輸.而異常信號(hào)識(shí)別是一種模式識(shí)別問題，所以要進(jìn)行特征提取和選擇.由于原始特征中存在一些無用特征，通過特征選擇保留一些對(duì)異常信號(hào)識(shí)別有用的特征可減少特征的維數(shù)，以提高異常信號(hào)識(shí)別正確率.為此,異常信號(hào)識(shí)別的特征問題可以轉(zhuǎn)化為函數(shù)優(yōu)化問題，然后采用狼群搜索算法對(duì)該問題進(jìn)行求解.設(shè)異常信號(hào)識(shí)別的原始特征集合為：F={f1,f2,…,fn}，n表示特征數(shù)的量，通過狼群搜索算法得到的最優(yōu)特征為：S={s1,s2,…,sn}，si∈{0,1}，“1”表示特征被選中，“0”表示特征沒有被選中.采用異常信號(hào)識(shí)別正確率(G)作為狼群搜索算法的目標(biāo)函數(shù)，那么異常信號(hào)識(shí)別的特征問題可以表示為：

無線電信異常信號(hào)主要包括：干擾機(jī)、雷達(dá)、單載波和單頻點(diǎn)，分別采集這4種無線電信異常信號(hào)，從信號(hào)提取原始特征，得到16個(gè)特征，然后對(duì)這些特征進(jìn)行歸一化處理，具體如下：

采用經(jīng)驗(yàn)法、遺傳算法和狼群搜索算法對(duì)無線電異常信號(hào)特征進(jìn)行選擇，選擇最優(yōu)特征子集，如表3所示.然后，采用支持向量機(jī)作為無線電異常信號(hào)的分類算法，統(tǒng)計(jì)無線電異常信號(hào)識(shí)別的正確率，具體如表4所示.從表4可以看出，狼群搜索算法的無線電異常信號(hào)整體識(shí)別正確率要高于經(jīng)驗(yàn)法、遺傳算法.這是由于狼群搜索算法可以選出更優(yōu)的特征子集，從而獲得更理想的無線電異常信號(hào)識(shí)別效果.

表3 無線電異常信號(hào)特征選擇結(jié)果

表4 無線電異常信號(hào)的識(shí)別正確率

5 結(jié)束語

為了改善函數(shù)優(yōu)化問題的求解效果，提出了基于狼群搜索算法的函數(shù)優(yōu)化問題求解方法.通過模擬狼群的團(tuán)隊(duì)協(xié)作機(jī)制找到函數(shù)優(yōu)化問題的最優(yōu)解，并與粒子群算法進(jìn)行了對(duì)比實(shí)驗(yàn).對(duì)比實(shí)驗(yàn)證明了狼群搜索算法用于函數(shù)優(yōu)化問題求解的有效性和優(yōu)越性.將狼群搜索算法應(yīng)用于無線電異常信號(hào)特征選擇中，選出了更優(yōu)的特征子集，從而獲得了更理想的無線電異常信號(hào)識(shí)別效果，具有一定的實(shí)際應(yīng)用價(jià)值.

參考文獻(xiàn)

[1] 李莉,李洪奇. 基于混合粒子群算法的高維復(fù)雜函數(shù)求解[J]. 計(jì)算機(jī)應(yīng)用,2007，27(7):1754-1756.

[2] 程樂,楊曄. 引入Logistic 混沌映射的連續(xù)蟑螂算法應(yīng)用于函數(shù)優(yōu)化問題[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2011, 32(6):1222-1227.

[3] 胡欣欣,尹義龍. 求解連續(xù)函數(shù)優(yōu)化問題的作協(xié)同進(jìn)化布谷鳥搜索算法[J]. 模式識(shí)別與人工智能, 2013, 26(11): 1042-1050.

[4] 趙輝,李牧東,翁興偉. 分布式人工蜂群免疫算法求解函數(shù)優(yōu)化問題[J]. 控制與決策, 2015, 30(7): 1181-1188.

[5] 馬胡雙,石永革. 函數(shù)優(yōu)化問題的動(dòng)態(tài)并行量子遺傳算法[J]. 青島科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2017, 38(1):109-116.

[6] 王志剛,王明剛. 優(yōu)化高維復(fù)雜函數(shù)的改進(jìn)人工蜂群算法[J]. 東北師大學(xué)報(bào)(自然科學(xué)版), 2016, 48(2): 56-64.

[7] 張正文,譚文龍,潘甲,等. 狼群搜索算法在光伏陣列MPPT中的應(yīng)用[J]. 河南科技大學(xué)學(xué)報(bào):自然科學(xué)版, 2015, 36(5): 57-61.