魏鋒濤，史云鵬，石 坤

西安理工大學(xué) 機(jī)械與精密儀器工程學(xué)院，西安710048

1 引言

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

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

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

2 回溯搜索優(yōu)化算法

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

2.1 種群初始化

BSA通過上界和下界隨機(jī)產(chǎn)生pop和historical_pop，如式（1）和式（2）所示：

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

2.2 選擇Ⅰ

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

其中，a,b是（0,1）均勻分布的隨機(jī)數(shù)，當(dāng)生成historical_pop后，需對(duì)historical_pop中的個(gè)體利用式（4）進(jìn)行隨機(jī)排序。

其中，permuting 是隨機(jī)排序函數(shù)。

2.3 變異

為了獲取新的個(gè)體，采用式（5）進(jìn)行變異操作：

其中，F(xiàn) 為變異尺度系數(shù)，F(xiàn)=3×randn，randn是標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)。

2.4 交叉

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

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

2.5 選擇Ⅱ

比較新種群和初始種群的適應(yīng)度值，保留適應(yīng)度值小的個(gè)體并且記錄當(dāng)前最優(yōu)解和最優(yōu)個(gè)體，同時(shí)更新當(dāng)代種群，具體如式（8）所示：

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

3 改進(jìn)回溯搜索優(yōu)化算法

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

3.1 柯西種群生成策略

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

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

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

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

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

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

3.2 組合變異策略

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

（1）混沌映射

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

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

（2）伽瑪分布

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

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

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

（3）組合變異策略

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

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

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

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

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

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

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

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

其中，favg 是平均值。

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

3.3 越界控制策略

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

其中，t 為當(dāng)前迭代代數(shù)，T 為總迭代數(shù)。

同時(shí)，考慮全局最優(yōu)個(gè)體引導(dǎo)越界個(gè)體重新生成，故新越界控制策略如式（24）所示：

其中，pg 是全局最優(yōu)個(gè)體，rand 是( )0,1 的隨機(jī)數(shù)，w 是正弦控制因子。

該越界控制策略不再是單純的通過上下界引導(dǎo)產(chǎn)生新的種群，而是引入了自適應(yīng)正弦控制因子和全局最優(yōu)個(gè)體共同引導(dǎo)種群的進(jìn)化，使算法收斂速度加快，增加了局部探索能力。

3.4 CMBSA算法流程

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

4 數(shù)值實(shí)驗(yàn)與仿真分析

4.1 測試函數(shù)

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

4.2 實(shí)驗(yàn)平臺(tái)及參數(shù)設(shè)定

實(shí)驗(yàn)在操作系統(tǒng)是Win7，處理器為Pentiun?DualCore CPU，運(yùn)行內(nèi)存為2 GB 的臺(tái)式計(jì)算機(jī)上進(jìn)行，使用Matlab2014a獲取優(yōu)化結(jié)果。

具體實(shí)驗(yàn)參數(shù)設(shè)置如下：種群規(guī)模N=30，交叉概率mixrate=1，實(shí)驗(yàn)分別對(duì)函數(shù)在30 維下仿真，最大迭代次數(shù)5 000 次。對(duì)每個(gè)測試函數(shù)分別獨(dú)立運(yùn)行30 次，取其最優(yōu)值（Best）、平均值（Mean）和方差（Std）進(jìn)行比較，函數(shù)30維下測試結(jié)果比較如表2所示。

圖2 CMBSA算法流程圖

表1 基本測試函數(shù)

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

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

表2 CMBSA算法測試結(jié)果比較

4.3 高維函數(shù)下的性能仿真分析

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

圖3 CMBSA算法測試函數(shù)曲線對(duì)比圖

5 結(jié)束語

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

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

圖4 高維下的CMBSA算法曲線對(duì)比圖