具有組合變異策略的回溯搜索優化算法

魏鋒濤，史云鵬，石 坤

西安理工大學 機械與精密儀器工程學院，西安710048

1 引言

回溯搜索優化算法（Backtracking Search Optimiza‐tion Algorithm，BSA）是Civicioglu 在2013 年提出的一種求解優化問題的進化算法[1]。該算法結構簡單，僅有一個控制參數，使其受初始控制參數影響很小，且在變異策略中充分考慮歷史種群的影響，并采用了新型的交叉方式，使算法具有較強的搜索能力，能夠很好地解決不同類型的優化問題，已被廣泛用于許多工程領域[2～6]。

針對回溯搜索優化算法存在開發能力較弱、搜索時間較長，且容易陷入局部最優的缺點，許多學者對該算法進行了改進研究。Zhao 等[7]結合歷史經驗和最佳個體經驗設計了數值優化問題的最佳引導回溯算法（Best Guided Backtracking Search Optimization Algo‐rithm，BGBSA），在迭代后期得到的最優個體有助于加快收斂速度；Nama等[8]提出了一種改進的回溯搜索算法（Improved Backtracking Search Optimization Algorithm，IBSA）并進行工程應用，利用改進交叉率和變異尺度系數的方法，豐富了種群的多樣性并提高了算法收斂精度；Su 等人[9]在算法中利用了最優適應度值和最差適應度值以及經驗參數，設計了隨個體變化的自適應變異尺度系數，有利于種群的進化；Wang 等[10]針對該算法收斂速度慢的缺點，提出了基于差分變異算子的改進思路，利用差分變異算子引導較差個體向較好方向進化，提高了算法收斂速度。

以上文獻雖然在不同方面提高了算法的收斂速度，但僅通過改變變異尺度系數或全局最優個體等方法在一定程度上增強了算法的搜索效率，提高了算法的局部搜索能力，但仍需要進一步提高算法的搜索效率和收斂精度。故本文研究一種基于組合變異策略的改進回溯搜索優化算法（Improved Backtracking Search Optimi‐zation Algorithm Based On Combined Mutation Strategy，CMBSA）。首先，該算法通過柯西分布尺度系數生成更優秀的歷史種群，以增加歷史種群的多樣性；其次，通過種群適應度值的方差來判斷算法是否陷入局部最優，并利用組合變異策略產生更優秀的種群，以擴大種群的搜索范圍；最后，對新種群中越界個體進行越界處理，保證算法在預定的搜索范圍內進行搜索，以提高算法的搜索效率和收斂精度。用標準測試函數進行仿真分析，并與文獻[1]BSA、文獻[7]BGBSA 和文獻[8]IBSA 算法在低維和高維下進行比較，以驗證本文所提出CMBSA 算法的優越性。

2 回溯搜索優化算法

回溯搜索優化算法與差分進化算法在框架上有一定的相似性，不同之處在于該算法有兩個選擇過程分別是選擇Ⅰ和選擇Ⅱ。BSA 算法通常包含種群初始化、選擇Ⅰ、變異、交叉和選擇Ⅱ五個步驟。

2.1 種群初始化

BSA通過上界和下界隨機產生pop和historical_pop，如式（1）和式（2）所示：

式中，popi,j為初始種群，historical_popi,j為歷史種群，i=1,2, … ,N ，j=1,2,… ,D，N 為種群數，D 為問題維數；lowj和upj分別是變量的下界和上界。

2.2 選擇Ⅰ

BSA在每次迭代之前通過式（3）產生新的歷史種群historical_pop。

其中，a,b是（0,1）均勻分布的隨機數，當生成historical_pop后，需對historical_pop中的個體利用式（4）進行隨機排序。

其中，permuting 是隨機排序函數。

2.3 變異

為了獲取新的個體，采用式（5）進行變異操作：

其中，F 為變異尺度系數，F=3×randn，randn是標準正態分布隨機數。

2.4 交叉

BSA 的交叉策略是一種基于兩種交叉方式等概率調用的聯合交叉策略。首先，生成一個初始值為1、大小為N×D 的矩陣；然后，通過式（6）更新矩陣Map；最后，通過矩陣Map來確定種群交叉的位置，具體如式（7）所示：

其中，a,b是( )0,1 均勻分布的隨機數；mixrate是交叉率；rand 是( 0,1) 均勻分布的隨機數；D 是問題維數；randi( D )是( 0,D )內的一個隨機整數；u=randperm( D)是對D 重新排序；ceil 是向上取整。BSA 通過這種新交叉方式產生種群T。然后對生成的新種群T 進行邊界越界處理，對超出邊界的個體按式（1）重新生成。

2.5 選擇Ⅱ

比較新種群和初始種群的適應度值，保留適應度值小的個體并且記錄當前最優解和最優個體，同時更新當代種群，具體如式（8）所示：

重復上述步驟，直至滿足終止條件即可。

3 改進回溯搜索優化算法

回溯搜索優化算法在迭代過程中容易陷入局部最優，通常所獲得的解與最優解相差甚遠，且由于BSA 算法的搜索方向是由歷史種群控制，便導致其收斂速度較慢。針對以上不足，本文對回溯搜索優化算法進行改進研究，首先，在算法迭代過程中利用柯西種群生成策略在一定概率下生成新的歷史種群；其次，通過歷史種群適應度值的方差來判斷是否陷入局部最優，借助伽瑪分布和混沌映射的組合變異策略生成新的種群；最后，通過越界控制策略對新種群進行檢測，保證所生成的新種群都在搜索區域內，以保證算法所獲取的最優解在搜索空間內。

3.1 柯西種群生成策略

由于BSA 算法生成歷史種群方式較簡單，所生成歷史種群的多樣性較差，易使算法陷入局部最優，故采用柯西種群生成策略，以增加歷史種群的多樣性，使算法不易陷入局部最優從而得到比較精確地最優解。

柯西種群生成策略是利用柯西分布尺度系數對種群變異生成歷史種群，所利用的柯西分布函數[11～12]如式（9）所示：

由式（9）可獲得式（10）：

其中，y=rand( 0,1)。

故在算法迭代過程中，新的歷史種群生成方式如式（11）所示：

利用式（11）代替BSA 算法中式（3）生成的歷史種群，可提高歷史種群多樣性，幫助算法在組合變異策略過程中生成更加優良的新種群，從而使算法快速跳出局部最優。

3.2 組合變異策略

BSA算法獨特的變異方式使得算法變異過程簡單，通過歷史種群的信息來控制搜索方向，但收斂速度較慢且易陷入局部最優。為了改善該缺陷，利用一種基于混沌映射和伽瑪分布的組合變異策略，使種群向著有利于尋找最優解的方向進行變異，加速了算法的收斂速度。

（1）混沌映射

混沌模型有Logistic、Tent、Henon、Kent和Sinusoidal映射等，每種映射均有自身的參數設置、映射區間和對初值敏感性差異等，本文選取優化效果較好的Sinusoi‐dal 混沌映射[13]作為組合變異算子之一，具體定義如式（12）所示：

其中，a=2.3，xk=rand( 0,1)。

（2）伽瑪分布

伽瑪分布是一種連續概率函數，由α、β 兩個參數同時控制，其中，α 為形狀參數，β 為尺度參數。本文選用伽瑪分布作為另外一個組合變異算子，其概率密度為式（13）所示：

由于BSA 算法在迭代過程中前期需對整個種群進行大規模搜索，后期需進行局部搜索，為了獲取不同的α、β 參數值對伽瑪分布概率密度函數的影響，分析了在不同參數值下對概率密度函數的影響，具體分析如圖1 所示。

伽瑪分布作為組合變異算子之一，前期需要有較大的變異率，并隨著迭代次數增加而逐漸減少，通過分析對比，圖1（b）中α=1和β=2曲線可滿足算法變異率要求，故算法概率密度函數如式（14）所示：

（3）組合變異策略

本文采用組合突變思想[14]對種群進行變異，將混沌映射和伽瑪分布兩個變異算子融合形成一個新的組合變異策略，如式（15）所示：

圖1 伽瑪分布概率密度曲線分析圖

上述組合突變雖將兩種變異算子融入到同一個變異中，彌補了單個變異的不足，但僅利用當前種群和組合變異算子引導種群變異，所獲取新種群多樣性不大，故將全局最優個體pg 和歷史種群historical_pop融入到組合突變過程中來引導種群變異，以提高新種群的多樣性，具體如式（18）所示：

其中，pop為初始種historical_pop為歷史種群，r3和r4為權重且r3=rand( 0,1) r4=rand( 0,1)，F=3×randn，Map為交叉矩陣。

在CMBSA 算法中方差反映了種群的密集程度，利用歷史種群適應度值方差來判斷是否進行變異，若方差小于某個閾值a（通常取a=3）則說明算法在迭代過程中陷入局部最優。對于歷史種群適應度值方差具體求解過程如下：

先通過式（19）求出歷史種群的適應度值總和：

其中，fitness(historical_pop)為歷史種群historical_pop的適應度值，N 為種群規模。

再通過式（20）求出historical_pop的方差s2：

其中，favg 是平均值。

故在CMBSA 算法中，通過方差判斷種群是否陷入局部最優，若陷入局部最優，則利用組合變異策略對種群變異；若種群沒有陷入局部最優，則按照式（5）引導種群變異，具體變異如式（22）所示：

3.3 越界控制策略

由于BSA 算法中個體越界按式（1）重新生成，導致新個體隨機性變大，難以保證生成優秀個體，故本文利用自適應正弦控制因子和全局最優個體引導越界個體重新生成。在算法迭代前期需進行全局搜索，控制因子取值通常較大，而在迭代后期只需局部搜索，控制因子取值相應變小，結合正弦曲線的特點，本文設計了一種正弦控制因子w，具體如式（23）所示：

其中，t 為當前迭代代數，T 為總迭代數。

同時，考慮全局最優個體引導越界個體重新生成，故新越界控制策略如式（24）所示：

其中，pg 是全局最優個體，rand 是( )0,1 的隨機數，w 是正弦控制因子。

該越界控制策略不再是單純的通過上下界引導產生新的種群，而是引入了自適應正弦控制因子和全局最優個體共同引導種群的進化，使算法收斂速度加快，增加了局部探索能力。

3.4 CMBSA算法流程

將柯西種群生成策略、組合變異策略和越界處理策略引入回溯搜索優化算法，保證了算法種群的多樣性，同時也提高了算法的收斂精度和收斂速度。通過式（1）和式（2）生成初始種群和歷史種群；利用2 個隨機數rand1和rand2進行比較，若rand1小于rand2，則按式（11）生成新的歷史種群，否則，不改變原來的歷史種群；接著按式（4）對歷史種群重新排序；利用式（20）求出歷史種群適應度值方差，再利用式（22）對種群交叉、變異；利用式（24）重新生成新種群中的越界個體，然后進行選擇Ⅱ操作；最后判斷當前迭代次數是否大于最大迭代次數，若大于最大迭代次數，則輸出最優解，否則，重復上述步驟，直至滿足終止條件。具體如圖2所示。

4 數值實驗與仿真分析

4.1 測試函數

為了測試CMBSA 算法的性能，本文選取了11個性能不同的測試函數，其中包含6 個單峰函數和5 個多峰函數，并與文獻[1]BSA、文獻[7]BGBSA 和文獻[8]IBSA比較，測試函數具體如表1所示。

4.2 實驗平臺及參數設定

實驗在操作系統是Win7，處理器為Pentiun?DualCore CPU，運行內存為2 GB 的臺式計算機上進行，使用Matlab2014a獲取優化結果。

具體實驗參數設置如下：種群規模N=30，交叉概率mixrate=1，實驗分別對函數在30 維下仿真，最大迭代次數5 000 次。對每個測試函數分別獨立運行30 次，取其最優值（Best）、平均值（Mean）和方差（Std）進行比較，函數30維下測試結果比較如表2所示。

圖2 CMBSA算法流程圖

表1 基本測試函數

由表2 可知，CMBSA 算法的收斂精度均高于BSA、BGBSA 和IBSA 算法，且比其他三種算法穩定。特別是函數f1和函數f2，CMBSA 算法非常穩定且最優值達到了函數的理論最優值；對于函數f3、f4、f7和f10，CMBSA算法的穩定性和收斂精度明顯優于其他三種算法，所獲得的函數最優解非常接近函數的理論最優值，且獲取的平均值效果更顯著；對于f9函數和f11函數，CMBSA 算法的平均值和最優值均優于BSA、BGBSA 和IBSA 算法，且穩定性較強；對于f5、f6和f8函數，CMBSA 算法均優于其他三種算法的平均值和最優值。故，CMBSA 算法的優化性能高于其他三種算法。

為了更好地體現CMBSA 算法在收斂速度上也具有很大優勢，本文選取其中6個測試函數，包含3個單峰函數和3 個多峰函數，并與BSA、BGBSA 和IBSA 算法比較，具體結果如圖3 所示。由圖3 可以看出，CMBSA算法的收斂速度遠遠高于其他三種算法，在迭代前期就基本收斂，且收斂精度明顯高于其他三種算法。特別是f1函數，CMBSA算法在迭代前期達到了理論最優值；對f3、f9和f10函數，CMBSA 算法非常接近函數理論最優值，收斂精度很高；對于函數f5和函數f8，CMBSA 算法的收斂精度和收斂速度也優于其他三種算法。

表2 CMBSA算法測試結果比較

4.3 高維函數下的性能仿真分析

為了進一步地說明CMBSA 算法在高維下的性能，在D=100 和D=400 下對CMBSA 算法仿真分析，但由于篇幅有限，僅對函數f6和函數f7仿真，具體的仿真結果如表3 和圖4 所示。由表3 可以看出，CMBSA 算法對于f6和f7兩個函數在不同的高維情況下收斂精度和穩定性都要明顯優于BSA，BGBSA 和IBSA 算法，且CMBSA 算法的平均值也優于其他三種算法。同時由圖4 可以看出，CMBSA 算法的收斂速度和收斂精度均優于其他三種算法。由此可見，CMBSA 算法在高維函數下收斂精度和收斂速度仍比另外三種算法具有優勢。

圖3 CMBSA算法測試函數曲線對比圖

5 結束語

本文研究了一種基于組合變異策略的改進回溯搜索優化算法，在迭代初期引入柯西分布尺度系數以提高歷史種群的多樣性；緊接著，利用組合突變的思想，通過伽瑪分布和混沌映射組成的變異策略產生新種群，提高了種群的多樣性；最后，利用越界控制策略重新生成越界的個體，在一定程度上解決了變異種群越界問題并且增加了變異種群的多樣性，使算法得到的最優解更加精確。通過對11個測試函數仿真分析，驗證了CMBSA 算法不管在低維還是高維情況下的收斂精度和收斂速度均優于其他算法并且具有一定的穩定性。

表3 高維函數下的算法性能仿真（D=100和D=400）

圖4 高維下的CMBSA算法曲線對比圖