受啟發(fā)的回溯搜索算法在優(yōu)化問題中的應(yīng)用

李媛媛，賈志成,*，陳 雷，郭艷菊

(1.河北工業(yè)大學(xué) 電子信息工程學(xué)院，天津300401；2.天津商業(yè)大學(xué) 信息工程學(xué)院，天津300134；3.天津大學(xué) 精密儀器與光電子工程學(xué)院，天津300072)

0 引言

回溯搜索(Backtracking Search,BS)算法是Pinar Ciricioglu[1]于2013年提出的一種群體智能優(yōu)化算法。BS算法與粒子群(PSO)算法[2]，差分(DE)算法[3]，生物地理優(yōu)化(BBO)算法[4]和人工蜂群(ABC)算法[5]等元啟發(fā)式優(yōu)化算法一樣，具有相似的特點(diǎn)：算法結(jié)構(gòu)比較簡單、尋優(yōu)過程易于實(shí)現(xiàn)、方程涉及參數(shù)較少、無需梯度信息等。一經(jīng)提出便吸引到了大量學(xué)者前來研究，并且在風(fēng)力渦輪機(jī)功率曲線模型[6]、經(jīng)濟(jì)排放調(diào)度問題[7]及表面波分析[8]等眾多領(lǐng)域得到了廣泛的應(yīng)用。

然而，與其他智能算法類似，較慢的收斂速度和較低的搜索精度也是BS算法急需解決的問題，限制了BS算法在實(shí)際中的應(yīng)用。對此，學(xué)者們提出了多種改進(jìn)策略來優(yōu)化BS算法的性能。文獻(xiàn)[9]通過改進(jìn)算法的搜索方程，提高了BS算法的優(yōu)化性能。文獻(xiàn)[10]從擾動方式角度出發(fā)，得到了一個高效變異尺度系數(shù)并將其應(yīng)用于BS算法中，另外，將貪婪性添加于交叉策略，從而優(yōu)化了BS算法的性能。文獻(xiàn)[11]為避免出現(xiàn)早熟收斂，在變異策略中添加了一種選擇機(jī)制以增加全局搜索能力。但是，在處理過于復(fù)雜的問題時，改進(jìn)的算法依然在收斂速度和早熟收斂兩方面難以取得平衡。

為了提高BS算法的收斂速度及避免早熟現(xiàn)象，本文對影響這一現(xiàn)象的主要因素即算法的搜索方程進(jìn)行了分析與改進(jìn)。在貪婪機(jī)制的啟發(fā)下，提出了一個具有較強(qiáng)開發(fā)能力的新搜索方程，它是在最優(yōu)解的引導(dǎo)下產(chǎn)生一個新的候選解以便算法更快地收斂于全局最優(yōu)位置。為了避免BS算法陷于局部極值點(diǎn)，采取了在BS算法的搜索方程中添加擾動算子的策略。仿真實(shí)驗(yàn)表明結(jié)合兩種搜索方程的BS算法能夠有效地提高優(yōu)化性能和優(yōu)化效率。

1 回溯搜索算法

BS算法是最近提出的一種新型的群體智能優(yōu)化算法，通過模擬生物進(jìn)化的行為而搭建的一種隨機(jī)模型。該算法的基本理論簡單易懂，現(xiàn)將BS算法的基本原理簡述如下：

BS算法的描述概括為5個部分：初始化、選擇-1、變異、交叉和選擇-2。BS算法的簡單流程圖如圖1所示。

圖1 BS算法的簡單流程圖
Fig.1 Simple flow chart of BS algorithm

1)初始化

BS算法和其他群體智能優(yōu)化算法一樣，在設(shè)置好問題參數(shù)后需對種群進(jìn)行初始化操作，即根據(jù)所求的優(yōu)化問題形成一個可行的解空間，并在生成的解空間里對種群進(jìn)行初始化操作，唯一不同之處在于BS算法需完成雙種群P和oldP的初始化操作，初始化操作如下式：

(1)

式中，Pi={Pi,1,Pi,2,…,Pi,D}代表原始種群P的每一個粒子，oldPi={oldPi,1,oldPi,2，…,oldPi,D}代表歷史種群oldP的每個粒子，i=1,2,…,NP為種群中每個粒子的編號，NP為種群中所有粒子的總數(shù)，j=1,2,…,D為所求優(yōu)化問題的解維數(shù)，D為所求優(yōu)化問題的最大解維數(shù)，U為隨機(jī)均勻分布函數(shù)。

2)選擇-1

BS算法在選擇-1階段主要是針對歷史種群oldP進(jìn)行選擇，如下式：

ifa

(2)

式中，a，b為[0,1]均勻分布隨機(jī)數(shù)。在每次迭代過程中，由a和b的大小決定歷史種群oldP是否更新。若滿足a

3)變異

BS的變異過程是在原始種群P和歷史種群oldP之間進(jìn)行變異操作。以原始種群P為中心，歷史種群oldP為搜索方向，產(chǎn)生變異種群Mutant，即

Mutant=P+R·(oldP-P)，

(3)

式中，R用來控制產(chǎn)生的新搜索方向的前進(jìn)幅度，其產(chǎn)生方法為R=3·rand,rand為[0,1]均勻分布隨機(jī)數(shù)。

4)交叉

BS的交叉策略由兩種交叉策略組成，在交叉過程中等概率調(diào)用兩種交叉策略。在交叉策略一中，交叉長度始n終被賦值為1；在交叉策略二中，交叉長度n是一個面向每一個粒子所產(chǎn)生的隨機(jī)數(shù)，如下式：

n(i)=[mixrate·rang·D]，

(4)

式中，mixrate是交叉概率。交叉后產(chǎn)生的新種群粒子Ci有可能超出搜索的解空間，需進(jìn)行邊界處理，即在優(yōu)化問題的解空間內(nèi)由式(1)產(chǎn)生一個隨機(jī)粒子Pi，用Pi取代超出優(yōu)化問題的解空間范圍內(nèi)的新種群粒子Ci。經(jīng)過交叉和邊界處理后，最終產(chǎn)生一個新種群C。

5)選擇-2

在BS的選擇-2操作中，采用貪婪機(jī)制選取更優(yōu)種群保留下來，該貪婪機(jī)制通過比較原始種群粒子Pi和新種群粒子Ci的適應(yīng)度值來實(shí)現(xiàn)。若新種群粒子Ci的適應(yīng)度值優(yōu)于原始種群粒子Pi的適應(yīng)度值，則將新種群粒子Ci取代原始種群粒子Pi；否則，繼續(xù)保留原始種群粒子Pi。如下式：

(5)

式中，fit是適應(yīng)度函數(shù)，選擇-2操作的完成標(biāo)志著進(jìn)化過程的一次優(yōu)化搜索，重復(fù)進(jìn)行上述優(yōu)化搜索過程實(shí)現(xiàn)多次優(yōu)化搜索，最終得到全局最優(yōu)種群粒子Pbest。

2 受啟發(fā)的回溯搜索算法

2.1 全新的搜索方程

由1節(jié)可知，BS算法是以種群為對象進(jìn)行變異和交叉操作，此做法不可避免地忽視了種群中的個體所具有的優(yōu)化能力。受貪婪機(jī)制的啟發(fā)，本文提出一個全新的搜索方程以保證更具優(yōu)化能力的粒子來進(jìn)行變異和交叉操作，而不是種群間盲目地進(jìn)行此操作。此策略通過衡量種群中每一個粒子在所有粒子當(dāng)中優(yōu)化能力水平，將處于平均優(yōu)化能力水平以下的粒子淘汰，用當(dāng)前種群中最具優(yōu)化能力的粒子取代。粒子優(yōu)化能力水平的衡量標(biāo)準(zhǔn)參照種群中所有粒子的平均適應(yīng)度值afit的大小，如下所示：

(6)

本文所提出的用以生成具有較高的優(yōu)化能力的粒子的全新搜索方程如下所示：

Pi=bestPi+R·(oldP-bestPi)afit

(7)

式中，bsetPi為當(dāng)前種群中最優(yōu)粒子，引導(dǎo)種群向更優(yōu)的方向搜索以保證種群粒子的搜索能力水平。

采用了全新的搜索方程的IBS算法不僅將處于劣勢地位的粒子淘汰，還在當(dāng)前種群最優(yōu)粒子的引導(dǎo)下生成了更具優(yōu)化能力的粒子來取代劣勢粒子。與BS算法相比，IBS算法具有更精準(zhǔn)的尋優(yōu)方向和更強(qiáng)大的開發(fā)優(yōu)秀粒子的能力，這不僅保證了解的質(zhì)量還加快了算法的收斂速度。

2.2 改進(jìn)的搜索方程

標(biāo)準(zhǔn)BS算法由于只有一個控制參數(shù)即歷史種群，來控制種群搜索方向，在處理較復(fù)雜優(yōu)化問題時，往往會陷入局部最優(yōu)。雖然在算法執(zhí)行的初期具有較好的探索能力，然而在后期算法效果并不理想，出現(xiàn)收斂速度減慢，對于較復(fù)雜的高峰函數(shù)，甚至搜索不到最優(yōu)解。受簡化而高效的粒子群優(yōu)化算法[12]，為擺脫局部極值而添加擾動算子的啟發(fā)，本文提出了一種改進(jìn)的回溯搜索算法，即在搜索方程中添加擾動算子。

文獻(xiàn)[12]添加的擾動算子為

pg=rtg>Tgpg，

(8)

本文在文獻(xiàn)[12]的基礎(chǔ)上提出了帶擾動算子的方程，如下所示：

M=P+R·(r·oldP-P)，

(9)

式中，r為擾動算子。當(dāng)出現(xiàn)早熟收斂現(xiàn)象時，改進(jìn)的搜索方程通過擾動算子操作來更新種群，使算法快速跳出局部最優(yōu)區(qū)域。

2.3 算法的實(shí)現(xiàn)步驟

BS作為一種新生的群體智能優(yōu)化算法，已比其他的經(jīng)典群體智能優(yōu)化算法取得了較佳的收斂速度和收斂精度，但是在處理復(fù)雜的實(shí)際優(yōu)化問題時，BS算法的優(yōu)化過程還需進(jìn)一步提高。因此，本文提出了一種改進(jìn)的回溯搜索(Improved Backtracking Search,IBS)算法，即在其尋優(yōu)過程中將全新的搜索方程和改進(jìn)的搜索方程配合使用。現(xiàn)將IBS算法的具體步驟介紹如下：

Step1：設(shè)置種群中所有粒子的總數(shù)為NP，通過式(1)初始化原始種群P和歷史種群oldP。

Step2：計(jì)算初始化原始種群P中每一個粒子的適應(yīng)度值，得到初始化原始種群P中的最優(yōu)粒子。

Step3：通過式(9)和式(4)對種群中的粒子進(jìn)行變異和交叉操作，產(chǎn)生新的種群M，計(jì)算新種群M中每一個粒子的適應(yīng)度值，和初始化原始種群中P每一個粒子的適應(yīng)度值比較，選擇更優(yōu)的粒子更新搜索種群P，并得到當(dāng)前最優(yōu)粒子。

Step4：對搜索種群P進(jìn)行淘汰選擇，通過式(6)計(jì)算搜索種群P中所有粒子的平均適應(yīng)度值和每個粒子的適應(yīng)度值，并把它們進(jìn)行比較。依據(jù)式(7)產(chǎn)生一個新的粒子取代淘汰的粒子，再一次更新搜索種群P。

Step5：計(jì)算搜索種群P中每一個粒子的適應(yīng)度值，得到搜索種群P中的最優(yōu)粒子，與原始種群P中的最優(yōu)粒子做比較，更新當(dāng)前全局最優(yōu)種群粒子Pbest及對應(yīng)的適應(yīng)度值。

Step6：檢查是否滿足停止條件。若滿足條件，則停止迭代，并輸出全局最優(yōu)種群粒子Pbest及對應(yīng)的適應(yīng)度值。否則，返回Step3。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了測試本文提出的IBS算法的性能，進(jìn)行仿真實(shí)驗(yàn)的測試函數(shù)從文獻(xiàn)[13]中選取。表1中列出了6個常用于優(yōu)化算法比較的標(biāo)準(zhǔn)測試函數(shù)。其中，f1～f3為單峰函數(shù)，優(yōu)化算法在對單峰函數(shù)測試時比較容易找到全局最優(yōu)點(diǎn)，故單峰函數(shù)主要用來檢測算法的收斂速度。f4～f6為多峰函數(shù)，多峰函數(shù)存在許多局部極值點(diǎn)導(dǎo)致算法在搜索過程中很容易陷入局部最優(yōu)，故多峰函數(shù)主要用來檢測算法跳出局部極值點(diǎn)的能力。優(yōu)化這些測試函數(shù)的難度會隨著它們的維數(shù)、自變量范圍的增加而增加。本文選取較為苛刻的實(shí)驗(yàn)參數(shù)，具體參數(shù)設(shè)置為：種群粒子總數(shù)為30，優(yōu)化問題維數(shù)為30，進(jìn)化迭代次數(shù)為500或1 000。為使實(shí)驗(yàn)結(jié)果更具有說服力，所有的實(shí)驗(yàn)結(jié)果均采用獨(dú)立運(yùn)行30次后的平均值。本實(shí)驗(yàn)分成3個部分進(jìn)行：1)在迭代次數(shù)一定的條件下，測試算法的收斂速度和收斂精度；2)在收斂精度一定的條件下，測試算法的迭代次數(shù)；3)一般條件下，與其他算法的性能比較。

表1 測試函數(shù)
Tab.1 Benchmark functions

函數(shù)名公式搜索范圍最小值收斂精度Spheref1(X)=∑ni=1x2i[-100,100]010-21Schwefel 2.21f2(X)=max|xi|,1?i?n{}[-10,10]010-1Schwefel 2.22f3(X)=∑ni=1|xi|+Πni=1|xi|[-10,10]010-13Ackleyf4(X)=-20exp-0.21n∑ni=1x2i()-exp1n∑ni=1cos(2πx1)()+20+e[-32,32]010-12Griewankf5(X)=14 000∑ni=1x2i-Πni=1cosxii()+1[-600,600]010-6Rastriginf6(X)=∑ni=1[x2i-10cos(2πxi)+10][-5.12,5.12]010-2

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1 測試算法的收斂速度和收斂精度

圖2給出了BS和IBS算法在迭代次數(shù)一定時，它們各自達(dá)到的收斂速度和收斂精度的實(shí)驗(yàn)結(jié)果。其中，圖2給出了測試函數(shù)f1～f6的適應(yīng)度收斂曲線，橫坐標(biāo)表示進(jìn)化迭代次數(shù)，縱坐標(biāo)表示測試函數(shù)的適應(yīng)度。為了方便收斂曲線的觀察，本文采用以10為底的對數(shù)作為函數(shù)的適應(yīng)度值。由圖2可以看出，在D=30，迭代次數(shù)均為1 000次的條件下，IBS比BS算法的收斂速度明顯快出很多。特別地，圖2(e)和(f)在保證收斂速度的情況下很快地找到了全局最優(yōu)值。這說明強(qiáng)強(qiáng)聯(lián)合的兩個搜索方程在收斂速度和收斂精度上獲得了平衡，同時也說明了本文改進(jìn)的IBS算法在實(shí)用性方面性能良好。

圖2 BS和IBS算法的收斂曲線圖
Fig.2 Convergence curves of BS and IBS algorithms

3.2.2 測試算法的迭代次數(shù)

參照表1中給定的收斂精度，BS和IBS算法的測試結(jié)果如表2所示，其中,平均迭代次數(shù)、最小迭代次數(shù)、最大迭代次數(shù)、成功率[12]和期望迭代次數(shù)[12]分別是經(jīng)過30次獨(dú)立運(yùn)行后的得到的結(jié)果。成功率=達(dá)到固定精度的運(yùn)行次數(shù)/總實(shí)驗(yàn)次數(shù)，期望迭代次數(shù)=種群粒子總數(shù)×平均迭代次數(shù)/成功率，“∞”表示Expected iterations為無窮大。由表2可以看出，除了f2以外，本文改進(jìn)的IBS算法的成功率均達(dá)到了100%，并且在收斂精度一定的條件下，平均迭代次數(shù)均小于500。這說明本文提出的IBS算法具有非常高的優(yōu)化性能。

表2 指定收斂精度下的迭代次數(shù)
Tab.2 The number of iterations under convergence accuracy

函數(shù)算法迭代次數(shù)平均值最小值最大值成功率期望迭代次數(shù)f1BS5005005000∞IBS418361480112 526f2BS5005005000∞IBS128335000.966 73 978f3BS5005005000∞IBS417363485112 504f4BS5005005000∞IBS430361484112 899f5BS5005005000∞IBS26517937917 943f6BS5005005000∞IBS27214145718 159

3.2.3 與其他算法的性能比較

為進(jìn)一步展示IBS的先進(jìn)性，將ABC、差分搜索(DS)算法、改進(jìn)的人工蜂群(MABC)算法和IBS算法的結(jié)果進(jìn)行比較，如圖3所示。將以上4種算法的參數(shù)都設(shè)置成：種群中所有粒子的總數(shù)為30，所求優(yōu)化問題的最大解維數(shù)為30，進(jìn)化迭代次數(shù)為1 000。由圖3可以很明顯地看出，在相同實(shí)驗(yàn)條件下，本文提出的IBS算法比其他算法具有更快的收斂速度和更高的收斂精度。

4 結(jié)論

受貪婪機(jī)制和粒子群算法的啟發(fā)，本文分別提出了一個全新的搜索方程和改進(jìn)了一個原有的搜索方程。在算法的實(shí)際優(yōu)化過程中，兩個搜索方程的配合使用平衡了算法的開發(fā)能力和探索能力，同時有效的解決了BS算法在收斂速度和收斂精度兩方面效果不佳的問題。對測試函數(shù)尋優(yōu)的實(shí)驗(yàn)結(jié)果表明，本文IBS算法能夠在較低迭代次數(shù)下很快趨近全局最佳值，甚至找到了最小值。

此外，將本文所改進(jìn)的算法應(yīng)用到通信、科技和工業(yè)等領(lǐng)域，是下一步需要研究的方向。

圖3 ABC、DSA、MABC和IBS算法的收斂曲線圖
Fig.3 Convergence curves of ABC,DSA,MABC and IBS algorithms