基于強化學(xué)習(xí)的差分進化算法改進方法研究

白 蕓

（西安外事學(xué)院，陜西 西安 710077）

引言

差分進化算法是一種智能優(yōu)化的算法，它有著很強的搜索能力，并將其進行啟發(fā)式的優(yōu)化。其基本的算法過程是在種族群體中隨機的選擇兩個個體，并將兩個個體之間的差分向量當成基礎(chǔ)的擾動向量，從而可以計算出變異后的向量，然后再利用適應(yīng)程度的函數(shù)來對其進行交叉的測試，通過交叉測試之后選擇最優(yōu)質(zhì)的個體進入到下一代。這樣算法在使用的過程中，尋優(yōu)的速度較慢，而且比較容易陷入到局部中的最優(yōu)值里，這樣表示著其檢測的精準度比較低。因此，就需要在當前所擁有的差分進化算法基礎(chǔ)上，簡化算法步驟，提升整體的尋優(yōu)速度。為此，研究基于強化學(xué)習(xí)的差分進化算法改進方法。

1 基于強化學(xué)習(xí)的差分進化算法改進方法

1.1 增加SAMDE 算法尋優(yōu)能力

1.1.1 融合變異算子

差分進化算法（簡稱SAMDE 算法）在變化的過程中會產(chǎn)生一定數(shù)量的變異算子，這種變異算子會在一定的層面上決定整體算法尋找優(yōu)質(zhì)個體的好壞程度，這就需要我們必須選擇出最合適的變異因子，才可以讓差分進化算法的性能更加優(yōu)質(zhì)。但在算法的尋優(yōu)過程中，沒有辦法更好的平衡全局和局部的搜索能力，所以就需要一種融合因子是結(jié)合了rand 和best 兩種算子的，那么算變異的過程見式（1）：

式中：c1≠c2 ≠c3 ≠m,G∈[ 0,1]代表縮放因子；表示個體產(chǎn)生變異后第a 代第m 個個體中包含著第n 個小的分量；q 表示最初種族群體的個體；則表示第a 代最優(yōu)質(zhì)的個體。h 為當前更迭的次數(shù)；為更迭變化中最大的次數(shù)，? =h/hmax就是隨著變化而變化的系數(shù)[1]。

1.1.2 加入模擬退火操作

隨著算法逐漸進化，就可能導(dǎo)致差分進化算法會因為種族群體多重性減少，從而容易進入局部模式的最優(yōu)值中。因為互補的原因，就需要在DE 算法的前提下融合模擬退火操作，從而找到當前所擁有的最優(yōu)質(zhì)個體，然后采取SA 準則進行第二次的搜索，具體步驟如下：

（1） 對于第a 代最優(yōu)質(zhì)的個體w0=，模擬退火的產(chǎn)生步驟，見式（2）：

式中：i 表示模擬退火的次數(shù)；zn表示經(jīng)過n 次更迭后產(chǎn)生的新個體；znmax和znmin則分別代表第n 維向量的最大值與最小值。

（2） 根據(jù)模擬退火的算法準則來進行調(diào)整為最優(yōu)質(zhì)的個體，見式（3）：

在操作模擬退火更迭的過程中，需要計算出任何一次更迭適應(yīng)程度的變化 Δ=f(wi+1) -f()，其中如果 Δ?0，就代表著新的個體被接受，并且可以把最優(yōu)質(zhì)的個體替換成wi+1；如果無法滿足以上所說的條件，但仍然滿足e(-Δ/A)?random(0,1)，代表著新的個體也被接受，并且會把種族群體中一個并不是最優(yōu)質(zhì)的個體替換掉，以此來保證種族群體個體多樣性的同時最優(yōu)質(zhì)的個體不會被破壞。如果上述的兩個條件都無法被滿足的話，就需要拒絕接受新的個體，對于每個溫度階段的模擬退火化算法（簡稱SA）都需要被搜索更迭x 次。滿足這個條件后，按照Ai+1=bAi（其中b 為常數(shù)）來進行降溫，反之則不進行降溫[2]。

1.2 改變交叉與變異操作模式

1.2.1 更新協(xié)方差矩陣

為了保證算法的搜索能力，就需要對差分進化算法中改變交叉與變異操作模式。所以，更新協(xié)方差矩陣的策略可以簡單稱為子代個體的生成，其中算法則是通過基向量和差分向量來分別進行變異以及交叉的操作之后會生成新的個體，因此步長的參數(shù)β(h)不需要更新，并且只需要研究協(xié)方差矩陣V(h)更新的過程[3]。當 β (h) =1，如式（4）所示：

式中：C(h)代表著正交矩陣，其中列所對應(yīng)在向量V(h) 中的特征向量；E(h)則為對角矩陣，其中對角的元素所對應(yīng)的是V(h)特征值。

更新算式為：

式中：ε 代表著第h代種族群體中最優(yōu)質(zhì)個體的數(shù)量；Yo:η(h)代表著第h代中有 η個種族群體的個體中第o個最優(yōu)秀的個體；代表著權(quán)重系數(shù)；Z(h)則代表著第h代中最優(yōu)質(zhì)個體平均值的向量。

1.2.2 添加函數(shù)排序算法

差分進化算法的變異操作模式大多數(shù)情況下是因為種族群體是隨機選擇的父代個體。對變異的操作模式進行優(yōu)化處理，在完成最初的操作之后，利用函數(shù)來計算種族群體里個體的適應(yīng)值，并且進行排序，適應(yīng)程度比較好的種群中的個體所相對應(yīng)的序列值o比較小一點[4]，把適應(yīng)程度較好的種群中個體對應(yīng)著較高的編號To。

在第h代的種群中選擇部分個體Ya(h) 、Yb(h)、Yc(h)來參與函數(shù)變異排序的操作，個體的選擇對實際的性能是非常重要的，Ya(h)是可以引起進化的基向量，而且差分的向量是可以確定搜索的范圍，如式（6）所示:

式中：Bo(h) 代表著函數(shù)生成變異的第h代的個體。因為要增加搜索的范圍，所以式（7）就是計算個體Yo(h)參與函數(shù)變異算法操作的概率：

新的坐標系建設(shè)成功后，因為要讓交叉操作中的向量可以更加地適應(yīng)此坐標系，就需要C D(h)對種群中個體Yo(h) 、函數(shù)變異后的個體Bo(h)進行相對應(yīng)的調(diào)整，得到對和，在新構(gòu)建的坐標系中執(zhí)行的是交叉操作，并且從中會得到對應(yīng)實驗的向量，然后再通過C(h)把對應(yīng)實驗的向量轉(zhuǎn)換成傳統(tǒng)的坐標系中所需要研究的向量，然后進行選擇的操作。由此可知，轉(zhuǎn)換方式如式（8）所示:

通過在構(gòu)建的坐標系里添加函數(shù)排序算法，就可以通過交叉操作來形成某個更接近于最優(yōu)解的個體，從而提高了種族群體的搜索能力，讓策略可以更加地合理。

1.3 強化學(xué)習(xí)改進差分進化算法

1.3.1 構(gòu)建動作選擇策略

強化學(xué)習(xí)可以幫助決策者在任何時間內(nèi)準確的做出不同的決策，因此就可以通過強化學(xué)習(xí)，再結(jié)合現(xiàn)有的差分進化算法來獲得更加有效的算法。

在智能狀態(tài)下的策略是相當于一直選擇出最高W值的動作，這種智能狀態(tài)下的策略可以被稱為貪心策略，如式（9）所示:

式中：1 -χ的概率是可以得到當前最優(yōu)質(zhì)的動作，χ的概率是為了選擇整體中的任何一項動作，這樣才可以維持空間內(nèi)的平衡。并且，其中代表著可以選擇的動作數(shù)量，s*代表著所知道的W值中最大的動作，而且 χ的取值范圍必須始*-/終保持在[ 0,1]內(nèi)。

1.3.2 引入多步Q(λ )學(xué)習(xí)

引入有預(yù)見能力的多步Q(λ )學(xué)習(xí)，滿足動態(tài)優(yōu)化中及時地優(yōu)化滾動。具體操作步驟如下：

其中：d 代表著當前狀態(tài)；s 代表著將要進行的動作；t代表著所獲得的獎勵；d'代表著即將進入下一個階段的狀態(tài)。β 則表示著學(xué)習(xí)效率；μ 表示為折扣率；η 則代表著資格跡消減的系數(shù)。并且此時η 的數(shù)值在很大程度上接近于0。β 則代表著已經(jīng)完成更新部分的所信任的程度，一般情況下，學(xué)習(xí)算法所收斂的速度加快就是因為β 的數(shù)值正在逐漸的增大。

1.3.3 融入動態(tài)強化學(xué)習(xí)機制

將差分進化算法融入動態(tài)的強化學(xué)習(xí)機制，得到一種新型算法，這種算法可以將種族群體中的任何一個個體都視為一個強化后的智能個體，并且把多重性和可以適應(yīng)的程度作為整個系統(tǒng)的動態(tài)信息，此狀態(tài)基本上會因為時間的變化而發(fā)生改變，只需要用其中一項變化量Dy就可以代表著y 時間段的狀態(tài)信息。智能個體中也包括三種非常典型的差分進化算法的變異操作可以使用，將可以變異的算子視為動作因子，只需要用其中一種變量sy就可以代表著y 時間段所有的工作信息。

差分進化算法是可以對參數(shù)問題進行調(diào)節(jié)的，其參數(shù)的空間就是決策問題中的所處動作空間，其目標是可以表示為從開始的時間段到y(tǒng) 時間內(nèi)所期望的適應(yīng)程度，并讓其最大化顯示，如式（10）所示，g 表示適應(yīng)程度的函數(shù)，即當所處的狀態(tài)Dy在執(zhí)行sy的動作時，可以立刻就得到的獎勵。

2 應(yīng)用的實驗測試

實驗測試目標為同一基地站點的同一系統(tǒng)設(shè)備，在相同的時間內(nèi)進行。兩種算法分別進行5 次運行測試，實驗測試數(shù)據(jù)見表1。

表1 實驗測試具體數(shù)據(jù)結(jié)果（%）

由上述表1 可看出，改進前算法雖然隨著次數(shù)增多精準度也隨之增多，但明顯可以看出最初始測試次數(shù)為100 次的時候，其精準度只有40%，運行500 次的平均精準度只有35.6%。但改進后的算法初始次數(shù)為100 次時，其精準度就已經(jīng)達到67.5%，運行500 次的平均精準度為82.2%。改進后的算法更迭時的精準度比改進前的要更加準確。還需要對兩種算法的尋優(yōu)速度進行比較，見圖1。

由圖1 可知，改進前的算法更迭次數(shù)在100 次的時候，尋優(yōu)的速度已經(jīng)達到300 s 以上，當?shù)竭_600次的時候，尋優(yōu)的速度已經(jīng)超過600 s 以上。但改進后的算法，當更迭次數(shù)到達600 次的時候，所需時間需要200 s 左右。

圖1 算法尋優(yōu)速度曲線變化

3 結(jié)論

此次改進的差分進化算法是在當前所擁有的算法基礎(chǔ)上增加了強化學(xué)習(xí)，這樣可以使整體算法變得更加簡單，而且尋優(yōu)更加快速。但只利用強化學(xué)習(xí)是無法使整體運行的速度更快，今后可以通過改變系統(tǒng)中空間運行的速度問題，從而使整體的算法可以通過改變內(nèi)部和外部的情況，都對其速度進行提升。