基于強(qiáng)化學(xué)習(xí)的差分進(jìn)化算法改進(jìn)方法研究

白 蕓

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

引言

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

1 基于強(qiáng)化學(xué)習(xí)的差分進(jìn)化算法改進(jìn)方法

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

1.1.1 融合變異算子

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

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

1.1.2 加入模擬退火操作

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

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

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

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

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

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

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

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

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

更新算式為：

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

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

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

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

式中：Bo(h) 代表著函數(shù)生成變異的第h代的個(gè)體。因?yàn)橐黾铀阉鞯姆秶允剑?）就是計(jì)算個(gè)體Yo(h)參與函數(shù)變異算法操作的概率：

新的坐標(biāo)系建設(shè)成功后，因?yàn)橐尳徊娌僮髦械南蛄靠梢愿拥剡m應(yīng)此坐標(biāo)系，就需要C D(h)對(duì)種群中個(gè)體Yo(h) 、函數(shù)變異后的個(gè)體Bo(h)進(jìn)行相對(duì)應(yīng)的調(diào)整，得到對(duì)和，在新構(gòu)建的坐標(biāo)系中執(zhí)行的是交叉操作，并且從中會(huì)得到對(duì)應(yīng)實(shí)驗(yàn)的向量，然后再通過C(h)把對(duì)應(yīng)實(shí)驗(yàn)的向量轉(zhuǎn)換成傳統(tǒng)的坐標(biāo)系中所需要研究的向量，然后進(jìn)行選擇的操作。由此可知，轉(zhuǎn)換方式如式（8）所示:

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

1.3 強(qiáng)化學(xué)習(xí)改進(jìn)差分進(jìn)化算法

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

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

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

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

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

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

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

1.3.3 融入動(dòng)態(tài)強(qiáng)化學(xué)習(xí)機(jī)制

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

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

2 應(yīng)用的實(shí)驗(yàn)測(cè)試

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

表1 實(shí)驗(yàn)測(cè)試具體數(shù)據(jù)結(jié)果（%）

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

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

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

3 結(jié)論

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