具有廣泛學習策略的回溯搜索優化算法

李牧東，趙 輝，翁興偉

（空軍工程大學航空航天工程學院，陜西西安710038）

具有廣泛學習策略的回溯搜索優化算法

李牧東，趙 輝，翁興偉

（空軍工程大學航空航天工程學院，陜西西安710038）

回溯搜索優化算法（backtracking search optimization algorithm，BSA）是一種新型的進化算法。同其他進化算法類似，該算法仍存在收斂速度較慢的缺點。針對這一問題，在詳細分析該算法原理的基礎上，提出了具有廣泛學習策略的改進算法。為了充分利用種群搜索到的較優位置，該策略首先利用提出的最優學習進化方程，通過與引入的隨機進化方程之間隨機選擇來提高算法的收斂速度和搜索精度；另一方面，該策略利用提出的最優學習搜索方程，通過控制種群的搜索方向，促使種群盡快收斂至全局最優解。最后對20個復雜測試函數進行了仿真實驗，并與其他3種目前流行的算法進行了比較，統計結果和Wilcoxon符號秩檢驗結果均表明，所提出的改進算法在收斂速度以及搜索精度方面具有明顯優勢。

回溯搜索優化算法；廣泛學習策略；Wilcoxon符號秩檢驗；函數優化

0 引 言

在過去的二十年中，元啟發式優化算法以其結構簡單、求解效率高等特點得到了前所未有的發展，例如眾所周知的遺傳算法（genetic algorithm，GA）［1］，蟻群算法（ant colony optimization，ACO）［2］和粒子群算法（particle swarm optimization，PSO）［3］等，并在網絡優化、智能識別、圖像處理以及多目標優化處理等眾多領域都得到了廣泛的應用。然而，隨著多模態、高維、非線性優化問題的出現，對全局優化算法提出了更大的挑戰。對此，學者們在對現有元啟發式優化技術研究的基礎上，提出了大量的改進算法以及新的優化算法，以期提高算法的優化性能。文獻［4］通過利用PSO算法搜索過程中粒子的較優解，對搜索方程加以改進，提高了算法的收斂速度；文獻［5］通過模擬生物的進化模型提出了差分進化（differential evolution，DE）算法；文獻［6］在DE算法的基礎上通過引入自適應進化策略提高了算法的性能；文獻［7- 9］通過模擬生物的覓食行為分別提出了人工蜂群（artificial bee colony，ABC）算法、布谷鳥搜索（cuckoo search，CK）算法以及森林狼（grey wolf optimize，GWO）算法等新型元啟發式優化算法。

回溯搜索優化算法（backtracking search optimization algorithm，BSA）是Cicicioglu于2013年提出的一種新的進化算法［10］。不同于其他進化算法，該算法通過產生實驗種群并控制搜索方向和搜索邊界大大提高了算法的優化效率，同時，由于該算法僅有一個控制參數，因此操作更加簡單。文獻［10］通過對不同類型測試函數的仿真實驗，證明了該算法具有較好的優化性能。

但是，由于BSA在優化過程中需要對函數進行足夠多次數的評價，算法才會逐漸收斂，因此算法消耗較大，同時存在收斂速度慢的缺點。針對這一問題，本文提出了一種新的改進BSA。受文獻［11- 12］的啟發，首先利用種群當前最優解和較優解信息，提出了廣泛學習策略，并在此基礎上對算法中的差分進化策略加以改進；其次，為了進一步提高算法的收斂速度，對BSA產生的新種群進行最優學習操作，從而使種群中的個體盡快跳出局部最優點。仿真實驗表明該算法能夠有效地提高優化性能和效率，是一種可行的優化算法。

1 BSA

BSA是一種基于種群的進化算法，該算法同其他進化算法類似，共分為5個步驟，分別為種群初始化、歷史種群設置、種群進化、種群交叉和選擇。

（1）種群初始化

由于BSA的性能受種群初始值影響很小，故在該算法中采用隨機產生種群的方法進行初始化，即

式中，Pop為種群，i∈［1，2，3，…，N］且j∈［1，2，3，…，D］，N是種群個數，D是種群維數；low和up分別為搜索區間的下界和上界；U是隨機均勻分布函數。

（2）歷史種群設置

在BSA中，通過設置歷史種群OPop來計算搜索方向，按照式（1）對其進行初始化。在算法循環開始時，當隨機數a小于隨機數b時，OPop＝Pop并將OPop中種群的位置進行隨機排列。通過對歷史種群的這一操作實現了該算法對種群位置的記憶功能。

（3）種群進化

通過式（2）產生新的種群：

式中，F為控制搜索方向矩陣（OPop－Pop）幅度的參數，且Fi＝3·rand，i∈［1，2，…，N］，rand是［0，1］的隨機數。

（4）種群交叉

BSA提出了一種新的種群交叉策略，通過設置混合比例參數來控制種群間交叉的粒子個數，具體公式如下：

式中，map為N×D的二元整數矩陣，初始賦值為1，具體計算公式如下：

式中，randi（D）為從［0，D］中隨機取一個整數，mr為混合比例參數，且mr＝1；rand，a，b為［0，1］的隨機數；u為隨機排序后且u∈［1，2，3，…，D］的整數向量。不同于DE算法的交叉策略，BSA通過利用mr·rand·D和randi（D）有效控制了新種群T中元素的個數，當a＜b時，mapi為多個具有隨機位置的二元向量；反之，mapi為僅有一個元素為0的二元向量。

在新種群產生后，對種群中的元素進行邊界控制，若種群中的元素超出搜索邊界，則按式（1）產生新的種群。

（5）選擇

通過貪婪選擇機制在新種群T與初始種群Pop中選擇適應度值較好的種群個體，并記錄當前最優解和對應的解向量，同時更新初始種群，完成一次迭代。重復上述過程，直到滿足循環終止條件，最后輸出最優解。

2 具有廣泛學習策略的BSA改進算法

通過對BSA的原理分析可知，該算法在循環初期具有較好的探索能力，然而隨著迭代次數的增多，BSA容易陷入局部最優，導致算法收斂速度減慢，對于較復雜的多峰函數，存在無法搜索到最優值的缺點。另一方面，BSA中僅僅通過設置歷史種群對種群的搜索方向加以控制，這也是導致其收斂速度減慢的原因。對此，本文提出了廣泛學習策略，通過學習種群當前搜索到的最優信息來控制算法的搜索方向，具體包括最優學習進化方程和最優學習搜索方程；另一方面，考慮到保持BSA的探索能力，改進算法設置了兩種不同的進化方程，具體改進如下。

2.1 最優學習進化方程

文獻［11］在研究現有DE算法進化策略的基礎上，提出了一種新的進化策略，即“DE／current-to-gr_best／1”進化搜索策略，如式（5）所示。該策略通過從當前種群選取的p%個種群個體中選出較優的個體作為控制算法搜索方向的控制向量，有效地提高了算法的收斂速度。

式中，Pgr_best為選取的較優個體，i，r，g∈［1，2，3，…，N］且它們之間互不相等。同時文獻［4］提出了利用種群當前最優解信息的方法改善了PSO算法的優化性能。本文在文獻［11］的基礎上，通過充分學習種群個體當前搜索到的最優信息，對式（5）加以改進，提出了最優學習進化方程：

式中，Pbest為當前種群搜索到的最優位置；OPop是歷史記錄種群。同時為了避免算法陷入局部最優，本文引入“DE／rand／2”進化策略：

式中，i，m，n，r，g∈［1，2，3，…，N］且它們之間互不相等；OPop是歷史記錄種群。通過隨機選擇式（6）和式（7）平衡算法的探索與開發能力。

2.2 最優學習搜索方程

文獻［12］針對ABC算法收斂速度慢、搜索精度不高的問題，受到文獻［4］的啟發，提出了最優引導搜索方程，改善了ABC算法的優化性能：

式中，φi，j和μi，j分別為［－1，1］和［0，1.5］的隨機數；Popbest，j為當前最優解向量的第j維。

考慮到種群在完成最優學習隨機差分進化操作之后，種群需要對搜索空間進一步搜索，以期快速搜索到全局最優解，因此在式（8）的基礎上提出了最優學習搜索方程：

式中，Popgr_best是從更新后的Pop種群中隨機選取p%后，選出較優的種群個體作為進一步搜索的方向引導向量；OPop是歷史記錄種群。該方程在式（8）的基礎上，進一步提高了方程的開發能力，對快速收斂至全局最優解具有明顯作用。

2.3 改進算法流程

由于BSA存在收斂速度慢，容易陷入局部最優的缺點，結合本文提出的最優學習策略，提出了一種新的BSA改進算法。該算法首先通過隨機選擇兩種不同的隨機進化方程，分別為“DE／rand／2”和本文提出的最優學習進化方程，對種群進行初始搜索；隨后對優化后的種群采用最優學習搜索方程進行進一步的優化操作，使其快速跳出局部最優，提高其收斂速度。下面給出了BSA改進算法的流程：

（1）種群初始化

（2）while不滿足算法終止條件do

（3） for i＝1 to N do

（4） if rand＜rand do

（5） mapi，u（1∶｜mr·rand·D｜）＝0

（6）Mi＝Pbest＋（mapi·Fi）·（Pgr_best－Popi＋OPopr－Popg）

（7） else do

（8） mapi，randi（D）＝0

（9）Mi＝Popi＋（mapi·Fi）·（Popm－Popn＋OPopr－Popg）

（10） end if

（11） end for

（12）貪婪選擇機制選出較優的解并更新Pop

（13） for i from 1 to N

（14） 利用式（9）產生新的優化種群V

（15） end for

（16）貪婪選擇機制選出較優的解并更新Pop

（17）end while

（18）輸出最優值和最優解向量

3 仿真實驗

為了驗證本文提出的BSA改進算法（后簡稱CLBSA）的有效性，對CEC 2005［12］中的20個復雜實數優化問題進行了測試仿真，同時與標準BSA、文獻［4］提出的CLPSO算法以及文獻［6］提出的DE改進算法SADE進行了比較。其中F1～F5為單模函數，F6～F12為標準多模函數，F13～F14為擴展的多模函數，F15～F20是具有混合結構的復雜函數。相比于一般的測試函數，CEC 2005中所用到的測試函數能較好地測試算法的優化性能，表1給出了20個函數的基本信息，包括函數名稱、搜索區間、函數維數以及最優值，其他關于函數的詳細描述可以參見文獻［12］。在仿真中，設置種群個數為30，最大評價次數為150 000，算法精度GolErr＝1e－14（即優化得到的全局最優值與理論最優值差的絕對值小于GolErr或者達到最大評價次數時，算法終止）在BSA和CLBSA中，控制參數mr＝1，p%＝20%；其他兩種比較算法按照文獻［4］和文獻［6］的參數設置方法進行設置。

表1 20個測試函數的基本描述

本文采用Matlab R2013a進行仿真，運行環境為Intel（R）Core（TM）i5- 3470處理器，3．46G內存。仿真針對同一測試函數，每個算法獨立運行30次，比較了4種算法對20個測試函數的統計平均值和方差。另外，為了更好地對實驗結果進行分析，本文引入了文獻［13］采用的優化算法比較分析方法，即Wilcoxon符號秩檢驗。該檢驗方法是一種成對比較方法，能夠有效檢驗出不同算法存在的明顯差異。在本文中通過將CLBSA分別與其他算法分別比較得出統計數據，其中，將30次獨立運行的最優值作為算法間比較的樣本數據，信息顯著水平設置為0．05。

表2給出了4種算法在20種測試函數下基于30次獨立運行的統計平均值（Mean）和方差（Std）。從表2中可以看出，CLBSA無論從收斂精度還是算法穩定性方面，相比于BSA，除了在函數F1，F3，F13和F16外，均有明顯提高，其中在函數F1的優化方面，CLBSA和BSA性能相當。相比于CLPSO算法，可以看出，除了函數F1，F7外，CLBSA在收斂精度和算法穩定性方面均優于CLPSO算法，其中，對F1函數的優化表現出相當的性能，在函數F7的優化方面，CLBSA在收斂精度方面與CLPSO算法相當，但算法穩定性優于CLPSO算法。相比于SADE算法，CLBSA除了函數F1，F4，F5和F7，均表現出了明顯較優的優化性能，其中在函數F1，F4和F7優化中，CLBSA表現出了較優的穩定性。

表2 4種算法對20種測試函數的測試結果

圖1 4種不同算法關于8個測試函數隨函數評價次數變化的收斂曲線

為了進一步說明CLBSA算法的有效性，圖1給出了4種算法的收斂曲線。由于篇幅限制，本文列出了典型的8種測試函數的收斂曲線。從圖1中可以看出，相比于BSA、 CLPSO算法，本文的改進算法具有明顯較快的收斂速度；相比于SADE算法，本文算法除對函數F1和F9的收斂過程略差外，對于其他函數的收斂過程均優于SADE算法。

為了更加清楚地比較4種算法的優化性能，表3給出了Wilcoxon符號秩檢驗的檢驗結果。其中“R＋”表示CLBSA樣本數據中優于其他算法的符號數；“R－”表示不如其相比較算法的符號數；“＋”表示假設不成立（兩種算法存在明顯差異），CLBSA表現出更好的性能；“－”表示假設不成立（兩種算法存在明顯差異），CLBSA表現出較差的性能；“＝”表示假設成立，即兩種算法沒有較大差異。各統計值的具體計算原理可參見文獻［13］。從表3中可以看出，相比于CLPSO算法，本文算法僅對F1函數優化中與其性能并無明顯差異，而在其他函數的優化方面明顯優于CLPSO算法；相比于SADE算法，在函數F1、F2和F7的優化過程中，本文算法與其并無明顯差異，在函數F16的優化中，SADE算法優于本文算法，而在其他函數的優化方面，本文算法表現出了明顯優于SADE算法的優化性能；相比于BSA算法，在F3、F15、F16和F18的優化過程中，性能優于本文算法，在函數F1和F2的優化中，本文算法與其優化性能相當，而對于其他函數的優化方面，本文算法表現出明顯優于BSA的性能。因此，相比于其他3種算法，CLBSA在對CEC 2005中的20個測試函數的試驗結果可以說明其改進的有效性。

表3 基于30次獨立運行的20個測試函數最優值雙邊Wilcoxon符號秩檢驗結果

4 結 論

為了解決標準BSA收斂速度慢和搜索精度不高的問題，本文提出了基于廣泛學習策略的改進算法，該策略主要由最優學習進化方程和最優學習搜索方程組成，實現了對BSA兩部分的改進。通過對CEC 2005中20個復雜測試函數的統計結果和Wilcoxon符號秩檢驗結果可以看出，相比于其他3種優化算法，本文提出的BSA改進算法有效提高了算法的搜索性能，是一種提高BSA收斂速度的可行解決方案。

另一方面，如何利用改進的優化算法解決多目標優化問題以及動態優化問題是下一步需要研究的方向。

［1］Holland J．Adaptation in natural and artificial systems［M］．Cambridge，MA：MIT Press，1992．

［2］Dorigo M，Stutzle T．Ant colony optimization［M］．Cambridge，MA：MIT Press，2004．

［3］Kennedy J，Eberhart R．Particle swarm optimization［C］∥Proc. of the IEEE International Conference on Neural Networks，1995：1942- 1948.

［4］Liang J J，Qin A K，Suganthan P N，et al．Comprehensive learning particle swarm optimizer for global optimization of multimodal functions［J］.IEEE Trans.on Evolutionary Computation，2006，10（3）：281- 295.

［5］Price K V，Storn R，Lampinen J．Differential evolution：a practical approach to global optimization［M］．Berlin：Springer Press，2005．

［6］Zhang J Q，Sanderson A C．SADE：adaptive differential evolution with optional external archive［J］.IEEE Trans.on Evolutionary Computation，2009，13（5）：945- 958.

［7］Karaboga D，Akay B．A comparative study of artificial bee colony algorithm［J］.Applied Mathematics and Computation，2009，214（12）：108- 132.

［8］Yang X S，Deb S．Cuckoo search via levy flights［C］∥Proc.of the World Congress on Nature and Biologically Inspired Computing，2009：210- 214.

［9］Seyedali M，Seyed M M，Andrew L．Grey wolf optimizer［J］. Advances in Engineering Software，2014，69：46- 61.

［10］Pinar C．Backtracking search optimization algorithm for numerical optimization problems［J］.Applied Mathematics and Computation，2013，219（15）：8121- 8144.

［11］Minhazul I S，Das S，Ghosh S，et al．An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization［J］.IEEE Trans.on Systems，Man，and Cybernetics—Part B：Cybernetics，2012，42（2）：482- 500.

［12］Suganthan P N，Hansen N，Liang J J，et al．Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization［R］．Singapore：Nanyang Technological University，2005．

［13］Derrac J，Garcia S，Molina D，et al．A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms［J］. Swarm Evolution Computation，2011，1（1）：3- 18.

Backtracking search optimization algorithm with comprehensive learning strategy

LI Mu-dong，ZHAO Hui，WENG Xing-wei
（School of Aeronautics and Astronautics，Air Force Engineering University，Xi’an 710038，China）

The backtracking search optimization algorithm（BSA）is a novel evolution algorithm．However，the BSA has the problem of low convergence speed as the same as the other evolution algorithms．Aiming at this problem，an improved BSA with the comprehensive learning strategy is proposed based on detailed analysis of BSA．The strategy is used for making full use of the better solutions that the population obtains．Firstly，the global best learning equation is proposed and the random evolution equation is introduced in the strategy．They are chosen randomly so as to improve the convergence speed and precision of the improved algorithm．Secondly，in order to control the search direction，the global best search equation is proposed in the strategy so as to reach the global best solution as fast as possible．Finally，20 complex benchmarks and other three popular algorithms are compared to illustrate the superiority of BSA with comprehensive learning strategy．The experimental results and the Wilcoxon signed ranks test results show that the BSA with comprehensive learning strategy outperformed the other three algorithms in terms of convergence speed and precision．

backtracking search optimization algorithm（BSA）；comprehensive learning strategy；Wilcoxon signed ranks test；function optimization

TP 13

A

10．3969／j．issn．1001-506X．2015．04．36

李牧東（1987-），男，博士研究生，主要研究方向為最優化理論與方法、無人飛行器武器系統總體技術。E-mail：lmd422＠163．com

1001-506X（2015）04-0958-06

2014- 05- 13；

2014- 09- 25；網絡優先出版日期：2014- 11- 05。

網絡優先出版地址：http：／／w ww．cnki．net／kcms／detail／11．2422．TN．20141105．1633．011．html

航空科學基金（20105169016）；中國博士后基金（2012M5211807）資助課題

趙 輝（1974-），男，教授，博士，主要研究方向為武器系統與運用工程、最優化方法。E-mail：zhao_kgy＠163．com

翁興偉（1980-），男，副教授，博士，主要研究方向為武器系統與運用工程、最優化方法。E-mail：liuziyang_kgy＠163．com