受啟發的回溯搜索算法在優化問題中的應用

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

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

0 引言

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

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

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

1 回溯搜索算法

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

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

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

1)初始化

BS算法和其他群體智能優化算法一樣，在設置好問題參數后需對種群進行初始化操作，即根據所求的優化問題形成一個可行的解空間，并在生成的解空間里對種群進行初始化操作，唯一不同之處在于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為種群中所有粒子的總數，j=1,2,…,D為所求優化問題的解維數，D為所求優化問題的最大解維數，U為隨機均勻分布函數。

2)選擇-1

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

ifa

(2)

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

3)變異

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

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

(3)

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

4)交叉

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

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

(4)

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

5)選擇-2

在BS的選擇-2操作中，采用貪婪機制選取更優種群保留下來，該貪婪機制通過比較原始種群粒子Pi和新種群粒子Ci的適應度值來實現。若新種群粒子Ci的適應度值優于原始種群粒子Pi的適應度值，則將新種群粒子Ci取代原始種群粒子Pi；否則，繼續保留原始種群粒子Pi。如下式：

(5)

式中，fit是適應度函數，選擇-2操作的完成標志著進化過程的一次優化搜索，重復進行上述優化搜索過程實現多次優化搜索，最終得到全局最優種群粒子Pbest。

2 受啟發的回溯搜索算法

2.1 全新的搜索方程

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

(6)

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

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

(7)

式中，bsetPi為當前種群中最優粒子，引導種群向更優的方向搜索以保證種群粒子的搜索能力水平。

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

2.2 改進的搜索方程

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

文獻[12]添加的擾動算子為

pg=rtg>Tgpg，

(8)

本文在文獻[12]的基礎上提出了帶擾動算子的方程，如下所示：

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

(9)

式中，r為擾動算子。當出現早熟收斂現象時，改進的搜索方程通過擾動算子操作來更新種群，使算法快速跳出局部最優區域。

2.3 算法的實現步驟

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

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

Step2：計算初始化原始種群P中每一個粒子的適應度值，得到初始化原始種群P中的最優粒子。

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

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

Step5：計算搜索種群P中每一個粒子的適應度值，得到搜索種群P中的最優粒子，與原始種群P中的最優粒子做比較，更新當前全局最優種群粒子Pbest及對應的適應度值。

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

3 仿真實驗

3.1 實驗設計

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

表1 測試函數
Tab.1 Benchmark functions

函數名公式搜索范圍最小值收斂精度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 實驗結果及分析

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

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

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

3.2.2 測試算法的迭代次數

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

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

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

3.2.3 與其他算法的性能比較

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

4 結論

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

此外，將本文所改進的算法應用到通信、科技和工業等領域，是下一步需要研究的方向。

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