張 韻，鐘慧超，張春江，李新宇+，叢建臣

(1.華中科技大學(xué) 數(shù)字制造裝備與技術(shù)國家重點實驗室，湖北 武漢 430074;2.山東理工大學(xué) 機械工程學(xué)院，山東 淄博 255000)

0 引言

在自然界生物遺傳和進化中，適應(yīng)自然環(huán)境的基因和形狀大概率得以存留，使得生物朝著適應(yīng)生存環(huán)境的方向不斷進化。20世紀70年代，Holland教授受遺傳學(xué)原理的啟發(fā)，提出了遺傳算法(Genetic Algorithm, GA)[1]。遺傳算法是借鑒生物遺傳機制和自然選擇的隨機經(jīng)典啟發(fā)式算法。算法中，使用染色體代表所需求解問題的一個解，通過對種群、染色體的操作(選擇、交叉、變異)，模擬遺傳和自然選擇的整個過程[2]。

遺傳算法具有較強的全局搜索能力和可拓展性，相關(guān)的研究和應(yīng)用較多。但遺傳算法也存在一些缺陷，如局部搜索能力不強、隨機性較大等。針對這些不足，近年來有很多相關(guān)研究，以提升遺傳算法的性能和應(yīng)用價值[3-4]。WANG等[5]針對交叉操作和變異操作對遺失解影響較大的問題，設(shè)計了一種參數(shù)自適應(yīng)方法，由此提出一種基于激素調(diào)節(jié)的自適應(yīng)遺傳算法;WANG等[6]針對遺傳算法早熟、精度差等問題，將正交設(shè)計方法用于優(yōu)化遺傳算法參數(shù)，并將所改進的算法用于作業(yè)車間調(diào)度問題;OSABA等[7]提出一種自適應(yīng)多策略交叉方法，交叉概率由前面幾代的搜索經(jīng)驗和迭代次數(shù)確定;ISMKHAN等[8]提出一種變異概率控制方法，該方法是在遺傳算法處于特定狀態(tài)時調(diào)整變異概率，在多峰連續(xù)函數(shù)優(yōu)化問題中表現(xiàn)較好;ZHANG等[9]提出一種基于聚類的自適應(yīng)交叉概率和變異概率方法，使用K均值聚類算法分析解空間的分散狀況，由此自適應(yīng)改變交叉概率和變異概率，并用于多維函數(shù)優(yōu)化問題;JEBARI等[10]提出一種動態(tài)優(yōu)化算法，使用模糊聚類方法來尋找未被探索的解空間，引導(dǎo)部分個體向未被探索的空間進行探索，增強算法搜索能力;SUN等[11]針對算法早熟導(dǎo)致種群多樣性減小的問題，對相鄰代的種群多樣性進行限定，根據(jù)種群多樣性評估結(jié)果和個體適應(yīng)度評估結(jié)果調(diào)整交叉概率和變異概率，該算法可以保持種群多樣性，保證全局搜索能力的穩(wěn)定性。

為提高遺傳算法的魯棒性，以上研究使用多種方法對其進行了改進。然而，上述方法雖然利用種群特征對參數(shù)進行了調(diào)整或?qū)崿F(xiàn)自適應(yīng)優(yōu)化，但考慮不夠全面，如并沒有充分利用之前迭代過程中的信息，大多只考慮本代的特征，使得參數(shù)自適應(yīng)過程與實際規(guī)律并不具有很強的相關(guān)性。而強化學(xué)習能對以往數(shù)據(jù)進行學(xué)習，利用過去的經(jīng)驗指導(dǎo)算法進行決策。此外，考慮并行計算可以減少算法運行時間，但一般的并行策略易忽略種群特征，受以上研究中使用K均值聚類算法獲得種群分布的啟發(fā)，可使用K均值聚類算法對種群進行聚類，使相似個體被分配到不同子種群，提高子種群多樣性。

基于以上分析，本文提出一種基于機器學(xué)習的改進遺傳算法，實現(xiàn)并行和多策略進化。一方面，使用強化學(xué)習對參數(shù)進行學(xué)習和調(diào)整，使參數(shù)隨種群進化合理變化；另一方面，設(shè)計多種群并行搜索策略，使用K均值聚類算法提高子種群的種群多樣性和均勻性，并設(shè)計了種群通信機制，充分挖掘多種群的優(yōu)勢。

1 基于機器學(xué)習的多策略并行遺傳算法

1.1 基于強化學(xué)習的參數(shù)調(diào)整策略

在機器學(xué)習中，強化學(xué)習較為特殊，它通過與環(huán)境的反復(fù)交互和試錯，根據(jù)獲得的反饋不斷對決策進行優(yōu)化[12]。近年來，在圍棋、工業(yè)自動化、數(shù)據(jù)科學(xué)等領(lǐng)域，強化學(xué)習得到了較多應(yīng)用，取得了較好的效果，是實現(xiàn)智能系統(tǒng)的重要技術(shù)之一[13-15]。其原理是：智能體記錄不同環(huán)境下做出不同決策的趨勢，在作出某一決策后，如果得到環(huán)境獎勵，則智能體會增加該狀態(tài)下做出這一決策的趨勢；相反地，如果得到環(huán)境的懲罰，則智能體會降低該狀態(tài)下作出這一決策的趨勢。經(jīng)過反復(fù)學(xué)習，智能體能達到可以做出累積獎勵最大決策的狀態(tài)[16]。

Q-Learning算法是一種經(jīng)典的強化學(xué)習算法，屬于異步策略學(xué)習(off-policy learning)，其數(shù)據(jù)生成策略和評估策略不相同，數(shù)據(jù)生成策略是ε-greedy策略，評估策略是貪婪策略。Q-Learning算法值的更新使用Q函數(shù)實現(xiàn)，Q-Table用來存儲Q值，式(1)為算法更新原理，式(2)用于計算決策的動作趨勢值[17]。

Q(st+1,at)-Q(st,at)];

(1)

Qπ(s,a)=Eπ{Rt|st=s,at=a}

(2)

基本遺傳算法應(yīng)用于具體問題時，參數(shù)往往需要多次試探或根據(jù)經(jīng)驗給定，因此參數(shù)設(shè)置與遺傳算法的泛化能力關(guān)系密切。為了使參數(shù)變化符合種群進化需求，利用強化學(xué)習與種群環(huán)境進行交互，針對遺傳算法中的交叉概率，設(shè)計了一種基于Q-learning算法參數(shù)調(diào)整策略。

Q-learning算法設(shè)置：

(1)狀態(tài)空間

狀態(tài)空間定義為兩位小數(shù)表示的交叉概率數(shù)值，取值范圍為[0.70,1.00)。

(2)動作空間

動作空間設(shè)置為交叉概率的減小、不變、增大3種，分別由{-1,0,1}表示，動作幅值設(shè)置為0.01。因此，Q-Table的規(guī)模為300×3。下一狀態(tài)的交叉概率為：

st+1=st+0.01×action。

(3)

(3)獎勵機制

獎勵機制的主要依據(jù)是種群的平均適應(yīng)度和最佳適應(yīng)度兩個指標，分為4種情況：①平均適應(yīng)度增大;②最佳適應(yīng)度增大;③兩者都增大;④其他。每種情況的獎懲力度不同。

(4)貪婪策略

利用ε-greedy策略使算法具有探索現(xiàn)有經(jīng)驗之外的規(guī)律的能力，能在一定程度上避免算法陷入早熟。ε為接受現(xiàn)有經(jīng)驗最優(yōu)解的概率。

(5)參數(shù)調(diào)整策略的流程

首先，初始化強化學(xué)習參數(shù)，包括學(xué)習率α、折扣率γ、探索率ε。然后，強化學(xué)習根據(jù)當前狀態(tài)，選擇動作空間中Q值最大的動作，或根據(jù)貪婪策略進行探索，對當前交叉概率進行調(diào)整。最后，完成本次種群迭代后，根據(jù)反饋信號和獎勵機制更新Q-Table，即完成一次決策和自學(xué)習。通過不同環(huán)境下的反復(fù)訓(xùn)練，使模型不斷學(xué)習經(jīng)驗，提高參數(shù)調(diào)整的準確程度?；趶娀瘜W(xué)習的參數(shù)調(diào)整策略的流程如圖1所示。

1.2 基于K均值聚類的并行策略

引入并行優(yōu)化能顯著加快算法運行速度，減少運行時間，特別是在多核處理器上，并行計算能充分利用計算資源。然而，如果設(shè)計不合理，即使是在多核處理器上，并行算法也可能因為資源爭奪等原因?qū)е滦Ч蝗缙胀ㄋ惴?。遺傳算法的并行策略中，子種群的劃分至關(guān)重要，子種群中各個個體的分散程度影響算法的疏散性和全局搜索能力，會對收斂速度、解的質(zhì)量均產(chǎn)生影響。以往研究中，子種群劃分往往是隨機的，難以保證算法整體的疏散性。

聚類是無監(jiān)督學(xué)習的一種，K均值聚類算法是典型的分割聚類算法。K均值聚類算法基于數(shù)據(jù)之間的相似度，將數(shù)據(jù)劃分到不同的簇[18]。K均值聚類算法的原理[19]是：首先將數(shù)據(jù)樣本分為K組，并隨機指定K個聚類中心，根據(jù)相似度計算方法，逐個計算每個點到各聚類中心的距離，將其分配到最近的聚類中心所在簇，簇中聚類中心會被重新指定。通過反復(fù)迭代更新聚類中心，直到其不再變化，距離誤差平方和局部最小，即完成聚類。

為設(shè)計有效的并行策略、充分發(fā)揮并行算法同步優(yōu)化的優(yōu)勢，本文使用K均值聚類算法來劃分子種群。在初始化種群形成后，用K均值算法對所有個體進行聚類，再將同類個體均勻劃分，形成多個內(nèi)部個體具有較大差異性的子種群，以提高子種群在解空間內(nèi)的分散程度，提升算法疏散性和全局搜索能力。

基于K均值聚類的并行策略流程如圖2所示，具體過程如下：

(1)定義數(shù)據(jù) 種群初始化后的每條染色體都作為一條數(shù)據(jù)，數(shù)據(jù)集大小等于種群規(guī)模。

(2)聚類 起始隨機確定K個聚類中心，計算數(shù)據(jù)與所有聚類中心的歐式距離，將該數(shù)據(jù)劃分給最近的聚類中心所在簇。每次分配一條數(shù)據(jù)后重新計算聚類中心，直到滿足終止條件，即可完成聚類。

(3)調(diào)整 按順序排列所有簇，得到{C(1),C(2),…,C(k)}，記調(diào)整后的數(shù)據(jù)集為Pc。

(4)劃分子種群 將Pc中的個體分為多個子種群，其中，第n個子種群由{Pc[1][n],Pc[2][n],Pc[3][n],…,Pc[k][n]}組成。

1.3 基于機器學(xué)習的多策略并行遺傳算法

使用上述兩種策略對遺傳算法進行改進，提出一種基于機器學(xué)習的多策略并行遺傳算法。首先，利用并行優(yōu)化加速算法進化過程，引入K均值聚類對種群進行劃分，保證子種群的種群多樣性和均勻性；同時，在進化過程中，使子種群間相互通信，加快算法收斂。最后，使用基于強化學(xué)習的參數(shù)調(diào)整策略，實現(xiàn)遺傳算法交叉概率的自學(xué)習，使交叉概率根據(jù)經(jīng)驗適應(yīng)進化過程。算法流程如圖3所示。

(4)

該段染色體的長度滿足：

(5)

染色體過長會對計算速度造成影響，因此對該段染色體長度向上取整，如式(6)所示，ceil(x)表示大于x的最小整數(shù)。

(6)

一條染色體的總長度len=Σleni。

(2)解碼。解碼是由染色體得到所表示的各自變量的值的過程。染色體中對應(yīng)vi取值的一段二進制序列為Bvi，將二進制數(shù)轉(zhuǎn)換為十進制數(shù)Dvi，則vi取值的計算如下：

(7)

例如，對于函數(shù)f(v1,v2)，其中v1∈[0,2]，v2∈[2,6]，設(shè)精度ε=0.01。編碼時，先作對稱調(diào)整，mean_v1=1，mean_v2=4，range_vi=1，range_v2=2，對稱調(diào)整后的區(qū)間分別為v1∈[-1,1],v2∈[-2,2]。由式(6)可得，len1=8，len2=9。對于v1=1.26，v2=3.48，Dv1=33，Dv2=-66.3按照二進制編碼，v1的二進制編碼表示為Bv1=00 011 010，v2的二進制編碼表示為Bv2=100 110 100。解碼時，按式(7)即可反解得v1和v2的真實取值。

(3)種群初始化。采用隨機初始化，種群規(guī)模為N。

(4)子種群劃分。采用前述的基于K均值聚類的并行策略進行子種群劃分。其中，距離計算采用歐氏距離，如式(8)所示。

d(x,y)=

(8)

(5)適應(yīng)度評估與選擇。由所有自變量和函數(shù)方程可以計算出函數(shù)值，適應(yīng)度設(shè)置為函數(shù)值的倒數(shù)。個體i表示為pi，染色體解碼出的函數(shù)值為obj(·)，則適應(yīng)度函數(shù)為：

(9)

選擇操作采用“輪盤賭法”與精英保留策略結(jié)合。個體i被選擇的概率如式(10)所示。

(10)

適應(yīng)能力越強的個體，存留的機會越大。為加速種群進化，并保證較優(yōu)個體不在其他過程中喪失，使用精英保留策略，用本代適應(yīng)度最高的個體替換子代中適應(yīng)度最差的個體。

(6)交叉。交叉父代的選擇規(guī)則為：對1～N的有序序列進行隨機排序，表示N個個體的隨機排列，記為序列A；然后生成長度為N、大小在區(qū)間[0,1]內(nèi)的隨機數(shù)序列，記為序列B。序列A與序列B位置一一對應(yīng)，若序列B某一位置的值比當前交叉率小，則序列A中該位置的個體與相鄰的下一個位置的個體交叉。

采用高效的PMX(partial-mapped crossover)作為交叉算子，如圖4所示。二進制編碼的染色體的交叉過程為：首先隨機確定兩個基因作為交叉起止位置；然后將兩個父代染色體所選片段互換，完成交叉。

(7)基于強化學(xué)習的交叉概率自學(xué)習。使用前述基于強化學(xué)習的參數(shù)調(diào)整策略對交叉概率進行學(xué)習和決策。

(8)變異。采用隨機單點變異，按照變異概率，選擇隨機點位，對基因值進行反轉(zhuǎn)，即01或10。

(9)子種群通信機制。為了充分發(fā)揮并行優(yōu)勢，加快收斂速度，設(shè)計了子種群通信機制。按一定步數(shù)，將全局最優(yōu)個體替換其他子種群中的最差個體。

2 數(shù)值實驗結(jié)果與分析

2.1 測試函數(shù)

本文選擇了9個常用的測試函數(shù)，如式(11)～式(19)所示。前3個函數(shù)的目標是求解函數(shù)的最大值，后6個以最小值為目標。

xi∈[-5.12,5.12],i=1,2;

(11)

f(X)=1+x1sin(4πx1)-x2sin(4πx2+π),

xi∈[-1,1],i=1,2;

(12)

xi∈[-2.048,2.048],i=1,2;

(13)

x1∈[-15,5],x2∈[-3,3]

f*=0?X*=[-10,1]T;

(14)

(15)

f(X)=(x1+2x2-7)2+(2x1+x2-5)2,

xi∈[-10,10],i=1,2

f*=0?X*=[1,3]T;

(16)

f(X)=sin(x1+x2)+(x1-x2)2-1.5x1+

2.5x2+1,x1∈[-1.5,4],x2∈[-3,4]

f*=-1.913 3?X*

=[-0.547 19,-1.547 19]T;

(17)

f(X)=(x1-1)2+(x2-1)2-x1x2,

xi∈[-4,4]f*=-2?X*=[2,2]T;

(18)

f(X)=-cos(x1)cos(x2)exp(-(x1-π)2-

(x2-π)2),xi∈[-5,5],i=1,2

f*=-1?X*=[π,π]T。

(19)

2.2 參數(shù)設(shè)置

遺傳算法的基本參數(shù)設(shè)置為：種群規(guī)模為100，最大進化代數(shù)為200，起始交叉概率為0.85，變異概率為0.05?；趶娀瘜W(xué)習的參數(shù)調(diào)整策略的參數(shù)設(shè)置為：學(xué)習率α=0.05，折扣率γ=0.9，ε-greedy中的選中概率ε=0.85，Q-Table更新周期為20步。基于K均值聚類的并行策略為：聚類中心數(shù)K=5，種群通訊機制更新周期為20步。解的精度設(shè)置為0.000 001。

2.3 實驗結(jié)果與分析

實驗結(jié)果如表1所示，其中GA是基本遺傳算法，RLGA(reinforcement learning based genetic algorithm)是基于強化學(xué)習的參數(shù)調(diào)整策略的改進遺傳算法，KPGA(K-mearns based parallel genetic algorithm)是基于K均值聚類的并行策略的改進遺傳算法，MLGA(machine learning based genetic algorithm)是本文所提算法。4種算法中遺傳算法的基本參數(shù)設(shè)置都相同，RLGA與MLGA中基于強化學(xué)習的參數(shù)調(diào)整策略的參數(shù)設(shè)置相同，KPGA與MLGA中基于K均值聚類的并行策略的參數(shù)設(shè)置相同。4種算法分別對每個測試函數(shù)運行10次。

表1 實驗結(jié)果

表1中AVG表示10次結(jié)果的平均值，σ表示10次結(jié)果的總體標準差。由表1可見，對于9個測試函數(shù)，MLGA能獲得全部的最好平均值，對大多數(shù)問題MLGA的標準差也是最小的，說明改進算法運行的穩(wěn)定性較好。同時，RLGA與KPGA求解效果均遠超GA，驗證了兩種改進策略是有效的。

為進一步展示算法的優(yōu)越性，選取函數(shù)f1和函數(shù)f7的10次實驗結(jié)果如圖5所示。由圖5可知，對于最大化問題f1，MLGA、RLGA、KPGA在大多數(shù)實驗中能獲得優(yōu)于基本GA的解，且求解穩(wěn)定性均在GA基礎(chǔ)上有很大提升；對于最小化問題f7，MLGA每次運行都能獲得接近最優(yōu)值的解，RLGA、KPGA所求得的解略差于MLGA，但兩者相對于基本GA都具有很大優(yōu)勢。由此驗證了所提出的基于強化學(xué)習的參數(shù)調(diào)整策略、基于K均值聚類的并行策略的合理性，使用這些策略的MLGA具有更強的尋優(yōu)能力和穩(wěn)定性。

通過表1和圖5的實驗結(jié)果進一步對比分析兩種策略，在9個測試函數(shù)中，KPGA在其中8個的表現(xiàn)優(yōu)于RLGA，在函數(shù)f1和函數(shù)f7的10次測試中可看出，無論在解的優(yōu)劣方面還是穩(wěn)定性方面，KPGA都表現(xiàn)得比RLGA更好。因此，在這些問題上，基于K均值聚類的并行策略比基于強化學(xué)習的參數(shù)調(diào)整策略對遺傳算法的改進效果更好。但是，基于強化學(xué)習的參數(shù)調(diào)整策略的強化學(xué)習模型會隨著種群規(guī)模與迭代次數(shù)的增加而不斷穩(wěn)健，效果會進一步提升，因此該策略有較大的潛力應(yīng)對更復(fù)雜的問題。MLGA結(jié)合兩種策略的優(yōu)勢，求解效果和穩(wěn)定性都比RLGA和KPGA好，具有較大的潛力。

在計算復(fù)雜度方面，基于強化學(xué)習的參數(shù)調(diào)整策略中使用的Q-Learning算法計算過程和Q-Table更新過程都比較簡單，且每一步均只需要重新計算一次交叉率，每20步才更新一次Q-Table，并不會顯著增大遺傳算法的計算復(fù)雜度，且由上述實驗結(jié)果中的RLGA相對于GA的求解效果可知該策略的有效性，該策略使用了較小的計算代價獲得了較大的性能提升。而基于K均值聚類的并行策略每一步都需要多次對n個個體計算其與K個聚類中心的距離，因此具有一定的計算復(fù)雜度，但由于該策略是建立在并行計算的基礎(chǔ)上的，有效減小了K均值聚類帶來的計算負擔。從以上實驗結(jié)果中KPGA的表現(xiàn)可得出，該策略的應(yīng)用較大地提升了遺傳算法的性能，由此增加了一定的計算復(fù)雜度是值得的。

在算法參數(shù)方面，本文中遺傳算法其他參數(shù)是根據(jù)實驗效果和經(jīng)驗選定的，強化學(xué)習用來自適應(yīng)調(diào)整交叉率，并證明了該思路的可行性，強化學(xué)習也可以用來調(diào)整算法中的其他參數(shù)，實現(xiàn)自適應(yīng)，可進一步提升算法性能。強化學(xué)習的學(xué)習率α、折扣率γ、探索率ε以及K均值聚類的參數(shù)K是通過多次實驗選定的，對算法的收斂有較大影響，但參數(shù)適應(yīng)性較高，通過少量試驗即可獲得較好的參數(shù)。

3 結(jié)束語

本文提出一種基于機器學(xué)習的多策略并行遺傳算法。一方面，利用并行計算思想提高算法效率，使用K均值聚類算法按照相似程度將種群劃分為多個簇，然后將每個簇中的個體均勻分配到不同的子種群中，以保證子種群多樣性和均勻性；同時，設(shè)計子種群通信機制，使用優(yōu)秀個體替換其他種群中的較差個體，加快進化速度。另一方面，使用強化學(xué)習實現(xiàn)遺傳算法交叉概率的調(diào)整，通過對歷史數(shù)據(jù)規(guī)律的學(xué)習作出合理的決策，使參數(shù)更適應(yīng)進化過程，提高遺傳算法的魯棒性。使用提出的算法對9個函數(shù)進行測試求解，并對比了基本GA、RLGA、KPGA，證明了本文所提算法具有較強的尋優(yōu)能力和穩(wěn)定性。

對機器學(xué)習結(jié)合啟發(fā)式算法的研究有待更加深入，未來可從以下兩方面展開工作：①引入深度學(xué)習結(jié)合啟發(fā)式算法,如使用神經(jīng)網(wǎng)絡(luò)擬合Q-learning中離散且數(shù)量有限的Q-Table，實現(xiàn)狀態(tài)的連續(xù)和數(shù)量無限;②擴展應(yīng)用領(lǐng)域,如將所提算法用于車間調(diào)度問題、車輛路徑調(diào)度問題等。