基于強化學習的差分進化算法改進方法研究

白 蕓

（西安外事學院，陜西 西安 710077）

引言

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

1 基于強化學習的差分進化算法改進方法

1.1 增加SAMDE 算法尋優能力

1.1.1 融合變異算子

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

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

1.1.2 加入模擬退火操作

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

（1） 對于第a 代最優質的個體w0=，模擬退火的產生步驟，見式（2）：

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

（2） 根據模擬退火的算法準則來進行調整為最優質的個體，見式（3）：

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

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

1.2.1 更新協方差矩陣

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

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

更新算式為：

式中：ε 代表著第h代種族群體中最優質個體的數量；Yo:η(h)代表著第h代中有 η個種族群體的個體中第o個最優秀的個體；代表著權重系數；Z(h)則代表著第h代中最優質個體平均值的向量。

1.2.2 添加函數排序算法

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

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

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

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

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

1.3 強化學習改進差分進化算法

1.3.1 構建動作選擇策略

強化學習可以幫助決策者在任何時間內準確的做出不同的決策，因此就可以通過強化學習，再結合現有的差分進化算法來獲得更加有效的算法。

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

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

1.3.2 引入多步Q(λ )學習

引入有預見能力的多步Q(λ )學習，滿足動態優化中及時地優化滾動。具體操作步驟如下：

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

1.3.3 融入動態強化學習機制

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

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

2 應用的實驗測試

實驗測試目標為同一基地站點的同一系統設備，在相同的時間內進行。兩種算法分別進行5 次運行測試，實驗測試數據見表1。

表1 實驗測試具體數據結果（%）

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

由圖1 可知，改進前的算法更迭次數在100 次的時候，尋優的速度已經達到300 s 以上，當到達600次的時候，尋優的速度已經超過600 s 以上。但改進后的算法，當更迭次數到達600 次的時候，所需時間需要200 s 左右。

圖1 算法尋優速度曲線變化

3 結論

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