李 驍，曹子建，賈浩文，郭瑞麒

(西安工業(yè)大學 計算機科學與工程學院,西安 710021)

路徑搜索是人工智能領(lǐng)域中的一個重要問題,涉及到諸如自動規(guī)劃、運動控制、資源分配、游戲策略等諸多應用場景。在路徑搜索問題中,通常需要在狀態(tài)空間中找到一條最優(yōu)路徑,以滿足某些約束條件或優(yōu)化目標。針對不同的問題,可以采用多種搜索算法進行求解,

目前已有的路徑搜索算法有很多,例如人工勢場方法[1]、蟻群算法[2]等,但這些傳統(tǒng)搜索算法在實際應用中面臨著挑戰(zhàn)和限制。而強化學習類型的方法能夠自主探索未知環(huán)境模型,以提高路徑搜索問題的求解效率和精度,故該方向成為了近年來的研究熱點。

強化學習(Reinforcement Learning,RL)作為人工智能領(lǐng)域的一個重要分支,已經(jīng)得到廣大學者的高度認可,在解決序貫決策問題上,強化學習采用馬爾可夫決策過程的方式,智能體通過與環(huán)境交互得到經(jīng)驗集于當前狀態(tài)進行決策[3]。而Q-Learning作為一種經(jīng)典的無模型強化學習方法[4]非常適合求解有限空間的路徑搜索問題,其收斂能力主要取決于智能體對環(huán)境信息的探索與利用。而在優(yōu)化Q-Learning探索能力方面,不同研究人員提出了多種改進方法。文獻[5]引入了探索因子和深度學習因子來提高算法的探索效率,但忽略了算法的可拓展性和穩(wěn)定性;文獻[6]通過勢場優(yōu)化Q表初值,并采用多步長策略和動態(tài)調(diào)節(jié)貪婪因子來平衡探索與利用,但未考慮動態(tài)障礙物的避障策略;文獻[7]提出了使用平均獎賞和相對值函數(shù)的值迭代方式來加速收斂,但計算復雜度較高且對獎勵信號不敏感;文獻[8]將資格跡概念融入Q-Learning中,提出了Q(λ)-Learning算法,減少了Q值的計算量,但缺乏實驗驗證;文獻[9]提出了Double Q-Learning算法,通過使用兩個估計器分離最優(yōu)動作和最大Q值的選取,改善了收斂速度;同樣,Speedy Q-Learning(SQL)和Double Speedy Q-Learning也對Q值的更新方式進行了改進,提高了收斂能力[10-11],但這些方法通常需要更長的訓練時間;除此之外,許多學者考慮Q-Learning與演化算法結(jié)合優(yōu)化的模式,將演化算法的思想融入Q-Learning中,并從多個角度對算法存在的問題進行了優(yōu)化。文獻[12]提出了一種結(jié)合退火算法(Simulated Annealing)中的Metropolis準則的Q-Learning改進算法(SA-Q-Learning),利用模擬退火的思想對ε的取值進行線性控制,從而保證算法更加快速找到最優(yōu)策略,但并未發(fā)揮出演化算法的優(yōu)勢。文獻[13]為了解決不確定性的POMDP近似最優(yōu)解問題,在基于SA-Q-Learning算法的基礎(chǔ)上提出了一種有限步歷史信息與狀態(tài)信度概率分布相結(jié)合,提出了一種直接進化策略的新算法(MA-Q-Learning),該算法提高了算法的收斂速度,但存在Q值過估計的問題。在實際工程應用中,文獻[14]針對虛擬作業(yè)中存在的不確定性問題,提出了一種遺傳算法(Genetic Algorithm,GA)結(jié)合Q-Learning算法進行最優(yōu)策略選擇的策略規(guī)劃模型(GA-Q-Learning),該模型有效地避免了早期較大的Q值動作,但該模型魯棒性較差,無法有效地解決行為空間較少的問題。

上述改進算法能夠提高Q-Learning算法的性能,但均未考慮Q-Learning算法在初始化時的盲目性,這會導致Q-Learning算法在前期路徑搜索中長時間地無效探索,影響算法的收斂速度和平均回報。基于此,文中提出了一種利用差分演化(Differential Evolution,DE)算法對Q表進行優(yōu)化來改進Q-Learning收斂能力的方法DE-Q-Learning。該方法利用演化算法優(yōu)化Q表的初始化,解決了Q-Learning算法在初始環(huán)境中的盲目性問題。通過使用差分演化算法推動Q表的進化,DE-Q-Learning在時間和空間上提高了算法的探索效率。最后在復雜迷宮環(huán)境、實驗環(huán)境Pacmman游戲和OpenAI的gym工具包中MountainCar上進行了仿真實驗,實驗結(jié)果顯示DE-Q-Learning算法相比于Q-Learning及其改進算法具有優(yōu)異的性能,并且能夠在更短的時間內(nèi)快速收斂。

1 基礎(chǔ)理論

1.1 Q-Learning

Q-Learning是一種基于時序差分的無模型學習方法,其Q-Learning的核心是Q表,Q表的行和列分別表示State和Action的值,用Q表的值Q(s,a)來衡量當前狀態(tài)采取動作a的價值,所以Q-Learning只考慮當前狀態(tài)st以及當前狀態(tài)選擇的行為at,使Q(st,at)值最大即可,智能體采用Q-Learning算法與環(huán)境交互如圖1所示。

圖1 Q-Learning算法與環(huán)境交互過程

通過這種局部映射的方式,無需充分地計算全局信息,只需通過局部選擇的方式便可獲得全局最優(yōu)動作序列,進而使智能體獲取最大目標收益。Q-Learning的算法偽代碼如算法1所示。

算法1 Q-Learning偽代碼

初始化環(huán)境E,狀態(tài)空間S,動作空間A,折扣因子γ,Q表Q-table

Fork=0,1,…,mdo #agent的每條完整路徑

初始化 狀態(tài)s

Fort=0,1,2,3,…,do #agent的每一個訓練步

通過貪心策略εof π在環(huán)境E中采取動作A

r,s′=Step(A) #執(zhí)行下一個動作A產(chǎn)生獎勵r和下一個狀態(tài)s′

s←s′

end forsis terminated

end for

π*(s)=argmaxQ(s,a) #根據(jù)Q表更新策略

Q-Learning的狀態(tài)行為值函數(shù)更新為

(1)

式中:s為當前狀態(tài);a為當前狀態(tài)s所采取的動作;α為學習率;r為在當前狀態(tài)s下執(zhí)行動作所得到的立即回報。γ為折扣因子,用來控制將來累積回報對當前狀態(tài)所產(chǎn)生的影響。s′表示當前狀態(tài)s采取動作到達的后續(xù)狀態(tài),a′為在狀態(tài)s′下選擇的動作,然后用新的Q值去更新Q表。

Q-Learning分別采取兩種不同的策略來進行策略評估和更新。在策略更新上Q-Learning采用ε貪心算法來選擇動作,在更新Q表時則采用貪心算法,通過下一個狀態(tài)的最大Q值來更新當前狀態(tài)的值。而在動作選擇中,Q-Learning采用ε貪心算法,其主要思想是在探索的同時也能同時進行一定的利用。在行為選擇時采用的ε-貪心算法,其中ε值越大則探索的效果越好。反之,若ε值越小則更加注重利用。但正因為其ε取值的固定,往往不能更好地平衡其探索和利用的效率,ε取值的不合理同時也會使得算法的搜索效率大幅度下降,在實際案例中ε一般在[0,0.1]區(qū)間內(nèi)取值。

1.2 差分演化算法

差分演化(DE)算法自1996年由文獻[15]提出后,在解決優(yōu)化問題上有著廣泛的適用性。DE算法在遺傳算法的啟發(fā)下提出,其思想與傳統(tǒng)演化算法保持一致,主要由變異、交叉、選擇這三個步驟所組成,在解決NP(Nondeterministic Polynominal)難問題上有著良好的適用性。對于求解以下形式的最小化問題。

minf(x)

s.t.x∈Ω∈RD,

(2)

式中:D為目標解空間的維數(shù);Ω∈RD則為可行解集。DE算法關(guān)鍵步驟為

Step1:變異

(3)

Step2:交叉

(4)

Step3:選擇

(5)

通過選擇操作將適應度值較好的個體進行保留,并作為下一代種群的初始值。

2 演化優(yōu)化Q表的改進Q-Learning方法

馬爾可夫模型作為強化學習與演化算法共同的理論基礎(chǔ),其定義如下:通過創(chuàng)建一個五元組并結(jié)合Bellamn方程構(gòu)成一個基本的馬爾可夫決策過程(MDP)問題模型,其中五元組中的元素分別表示為:S(有限的狀態(tài)空間),A(有限的動作空間),P(狀態(tài)-動作轉(zhuǎn)移概率矩陣),R(獎勵函數(shù)),γ(折扣因子)。MDP動態(tài)過程如圖2所示,智能體初始狀態(tài)為S0,從合法狀態(tài)集A中挑選一個動作執(zhí)行,得到回報r0,然后按照一定概率隨機轉(zhuǎn)移到下一個S1狀態(tài),如此往復直到到達終止狀態(tài)。在這個過程中不同的狀態(tài)動作影響著最優(yōu)策略的搜索進度,因此,可以使用演化算法來優(yōu)化存儲狀態(tài)動作對的Q表,以加速Q(mào)-Learning尋找最優(yōu)策略的效率。演化算法由于其固有的并行性,能夠不受問題性質(zhì)的限制,有效地解決傳統(tǒng)優(yōu)化問題難以處理的復雜問題,加快了策略搜索速度。從而能夠有效緩解Q-Learning在環(huán)境信息匱乏的情況下的盲目搜索性問題。

圖2 MDP結(jié)構(gòu)

2.1 時間復雜度分析

Q-Learning作為一種無模型算法,樣本復雜性T決定了其時間復雜度O(T),空間復雜度O(SAH)更多取決于狀態(tài)和動作的空間大小。其中S代表狀態(tài)空間大小,A代表動作空間大小,H則表示為每一次執(zhí)行所走的步長[16]。而在解決無模型問題上,Q-Learning在已知狀態(tài)空間和動作空間的前提下,如何有效地利用環(huán)境信息是提升算法收斂能力的關(guān)鍵。隨著模型環(huán)境復雜度的提升,不僅狀態(tài)、動作對的數(shù)量增加,而且智能體在每次探索時所需的步長H也會隨之增加。由此可以看出,環(huán)境信息對算法的運行效率起著至關(guān)重要的作用。

演化算法作為一種解決復雜問題的有效手段,可以用于解決強化學習在算法初期的盲目探索性問題。DE具有較低的時間復雜度O(NP-D-Gmax)[17-20],其中NP代表種群大小,D表示維度,Gmax為算法最大運行代數(shù)。對于復雜無模型問題,若將狀態(tài)行為值函數(shù)Q作為NP的輸入,S作為D的輸入,步長H則在搜索空間進行了提升。每當演化算法生成一代Q表種群作為NP輸入時,步長H在空間上則擴展為NP*H,由此便提高了算法的執(zhí)行效率。由于DE算法具有控制參數(shù)少、收斂速度快、尋優(yōu)精度高及魯棒性強的優(yōu)點,因此文中選用DE作為演化算法實例。當然任何其它演化算法都可以作為實例算法來對Q-Learning進行優(yōu)化,文中主要側(cè)重于DE-Q-Learning算法的原理。

2.2 算法的局限性

在Q-Learning算法運行初期,Q表參數(shù)的初始化會導致采集到的數(shù)據(jù)往往是未經(jīng)訓練的樣本集。如何更加有效地提升算法的執(zhí)行效率,更多程度取決于算法前期的探索能力。另外,在算法前期的探索階段,所獲取到的立即回報值不一定對算法訓練有效,能夠正確引導智能體進行決策的立即匯報過少,無法有效地幫助算法在前期快速收斂。同時,對于大多數(shù)問題模型而言,若屬于密集回報型問題,則對算法的訓練相對較好。但遇到稀疏回報問題時,大多數(shù)的狀態(tài)轉(zhuǎn)移對可能始終無法獲得有效的回報值。這樣便導致算法重復了很多盲目的訓練,既浪費了時間也得不到令人滿意的效果。

2.3 演化Q表的初始化方式

在Q-Learning算法中,Q表的初始化通常為一個全0矩陣,所以在模型探索初期存在較大的盲目性而導致算法無法快速的收斂。如何有效的初始化Q表信息對算法收斂起到了強有力的推動作用,但在無模型問題上,往往只能以隨機的方式來初始化Q表信息,這未必會對算法的收斂能力起到促進作用。Q表由狀態(tài)和動作的映射所組成,若初始化得到一個合適的Q表,這無疑在很大程度上加快了算法的收斂速度?？梢詫⒃搯栴}轉(zhuǎn)換為一種組合優(yōu)化問題,采用演化算法的方式來尋求一種最優(yōu)解,最優(yōu)解的輸出代表最合適的Q表。將一個Q表視作種群中的個體,通過隨機初始化若干Q表來構(gòu)成演化種群NP,并采用特定的評價標準保留優(yōu)良個體,較好的Q表個體中的狀態(tài)-動作值滿足較好的組合方式。 隨著演化的進行,狀態(tài)-動作值的最好組合方式將被找到并作為Q表的初始化信息。圖3給出了個體與種群的設(shè)定形式。

圖3 個體的創(chuàng)建過程

這樣便產(chǎn)生了多個并行的解空間?；谝陨戏绞嚼醚莼惴ㄉ膳c目標函數(shù)相關(guān)的高適應度初始種群,從而可以充分探索問題的解空間,極大地提高算法前期的探索效率。

2.4 DE-Q-Learning理論思想

在求解無模型問題時,Q-Learning采用時序差分(Temporal Difference,TD)思想來進行策略更新,通過行為值函數(shù)計算公式對當前Q表進行更新,如此反復地進行“收集-利用-更新”這一過程來找尋最優(yōu)策略。對于每一步狀態(tài)轉(zhuǎn)移所產(chǎn)生Q表的更新,都將直接或間接影響后續(xù)策略的選擇。由于算法在更新迭代時,對先前信息存在較大的依賴性,而在探索初期,若收集到的環(huán)境反饋信息較少,則會使算法陷入盲目勘探中,無法有效獲得更加具有指導性的環(huán)境信息。

圖4描繪了以DE算法為例所提出的一種新型優(yōu)化算法(DE-Q-Learning)。這里從宏觀層面表述了DE-Q-Learning的通用性,并重點闡明了算法的獨特性。在算法框架的設(shè)計上,文中提出了一種通用的方法,使其可以自由更換演化算法類型以滿足在不同問題下Q-Learning的適用性。

圖4 DE-Q-Learning算法流程

對比Q-Learning與DE-Q-Learning可觀察到,在初始化Q表時,兩者最大的區(qū)別在于同一時間所更新Q表的數(shù)量。DE-Q-Learning在空間層面出現(xiàn)了更加豐富的并行解集,極大程度優(yōu)化了算法的執(zhí)行效率。與此同時,由于在優(yōu)化過程中Q表種群信息是隨機初始化的,在使用演化算法對其進行優(yōu)化后,輸出較優(yōu)的Q表時總會伴隨著有效Q值的存在。

對于如何使用DE算法來優(yōu)化Q-Learning,需要重點解決表示方法、個體的定義及評價函數(shù)設(shè)定問題。由于不同的演化算法對應的演化過程不盡相同,這里重點突出優(yōu)化的思路和方式,而不針對演化算法的具體搜索過程展開對比描述。

山地車(MountainCar)問題是強化學習中的經(jīng)典問題,如圖5所示,小車在一條一維的軌道上,位于兩座“山”之間,目標是開車上山,但是一開始小車的發(fā)動機不足以直接行駛上山,所以需要來回行駛增強動力以達到目的。接下來在MountainCar中進行實驗來驗證DE-Q-Learning算法的理論假設(shè)。

圖5 MountainCar 游戲環(huán)境

1) 表示方法的設(shè)定

在問題的設(shè)定上,將Q表作為演化種群NP,最終將得到一個最優(yōu)個體作為Q表的輸出。在MountainCar游戲環(huán)境和大部分強化學習環(huán)境中,回報值的定義均為實數(shù)形式,最終計算得到的Q值也為實數(shù)形式,所以這里采用實數(shù)編碼形式作為演化算法的個體編碼以及函數(shù)值表示方法。小車的參數(shù)見表1。

表1 MountainCar-v0參數(shù)

2) 演化個體的設(shè)定

在個體的定義問題上,Q-Learning算法中的Q表思想上均可以視作為一個狀態(tài)動作對應值的二維列表。隨機初始化若干Q表作為演化算法中的初始種群,并通過不斷地演化來更新種群中的個體信息。在山地車問題中,Q表的內(nèi)容由狀態(tài)-動作對應的Q值組成構(gòu)成,根據(jù)游戲的回報將Q值初始化在[-2,0]之間。根據(jù)表1,小車的觀測值Observation是20×20的二維表格,表示小車的速度與位置,將其作為狀態(tài),而動作集是由3個離散動作組成的一維表格,故整個Q表是狀態(tài)×動作的三維表格。

3) 適應度函數(shù)的設(shè)定

在演化算法中,適應度函數(shù)的設(shè)定取決于優(yōu)化問題的目標。而在解決強化學習問題時,針對不同的問題模型制定不同的評價函數(shù)是解決問題的最佳手段。在MountainCar游戲環(huán)境中,回報設(shè)置很簡單:如果小車到達山頂終點的旗幟(Position=0.5),則獎勵0;如果小車的位置低于0.5(Position<0.5),則獎勵-1。

基于以上設(shè)定,文中在MountainCar游戲環(huán)境中對DE-Q-Learning進行驗證,并且使用傳統(tǒng)Q-Learning以及它的改進SA-Q-Learning與Double-Q-Learning進行對比,其中Double Q-Learning主要思想是采用雙估計器的方式來解決Q-Learning的過估計問題,SA-Q-Learning則優(yōu)化了算法探索和利用之間的權(quán)衡關(guān)系。算法使用的參數(shù)見表2,超參數(shù)無具體單位,可以根據(jù)具體情況進行調(diào)整和優(yōu)化,“-”代表該算法不使用此參數(shù)。

表2 MountainCar環(huán)境各算法實驗參數(shù)

每種強化學習算法在該游戲環(huán)境迭代2 000次,將每代回報取平均、最大、最小的實驗結(jié)果如圖6～7所示。根據(jù)實驗結(jié)果可以看出DE-Q-Learning算法的累積回報在訓練的各個階段都要大于原始Q-Learning算法以及它的改進算法,并且收斂速度明顯快于其他算法,這是由于DE-Q-Learning算法在訓練開始前就已經(jīng)獲得了DE算法優(yōu)化出的最佳Q表,使得智能體在與環(huán)境的交互過程中能夠根據(jù)狀態(tài)選擇出Q值最大的動作,說明DE-Q-Learning應用于此類二維狀態(tài)空間有限的環(huán)境中是很有效的。為了達到在輸出最優(yōu)個體時不影響實例模型中Q表變化這一目的,文中提出的DE-Q-Learning算法在演化Q表時取極小運算值來初始化種群,這樣既達到優(yōu)化的目的,又將無關(guān)干擾因素降至最小。

圖6 MountainCar環(huán)境下算法的平均回報

圖7 MountainCar環(huán)境下算法的最大回報

2.5 DE-Q-Learning算法流程

根據(jù)2.4對DE-Q-Learning算法的理論闡述做出驗證證明其是有效的,該算法的核心在于使用DE算法演化得到最優(yōu)Q表,智能體能夠根據(jù)Q表中的最優(yōu)Q值來選取能夠獲得最大的收益的動作,DE-Q-Learning算法描述如下:

Step1:初始化。針對不同問題模型構(gòu)建相對應的環(huán)境信息,使用隨機初始化的方式構(gòu)建若干Q表作為種群中不同個體:

Qi=rand(D,U)i=1,2,…,NP,

(6)

式中:Q為數(shù)量對應種群個數(shù)NP,(NP=1,2,…,n),其編碼形式采用實數(shù)編碼方式;D,U為特定環(huán)境Q值的最小最大值。rand(D,U)隨機生成指定范圍內(nèi)的Q值來構(gòu)成Q表種群。

Step2:計算種群中每個個體的適應度fitness,并找尋最優(yōu)個體Qi及最大適應度值bestfitness。

Step3:(變異)DE/rand-to-best/1/bin為文中所采用的變異算法。

vij(t+1)=Qr1,j+F·(Qbest-Qr1,j)+

F·(Qr2,j-Qr3,j),

(7)

式中:i,r1,r2,r3∈{1,2,…,NP};j∈{1,2,....,D},且r1≠r2≠r3;Qr1,j,Qr2,j,Qr3,j表示從Q表種群中隨機選取的Q表個體;Qbest代表當代最優(yōu)個體。通過以上步驟得到一個變異后的種群vij。

Step4:(交叉)采用二項式交叉的方式得到新的種群uij,令A為條件“rand(j)≤CR”,B為條件“j=random(i)”,則交叉?zhèn)€體為

(8)

Step5:(選擇)計算交叉后種群u的適應度值ufitness,并與初始種群的適應度值fitness進行比較從而挑選出優(yōu)良個體作為下一代的初始種群。

Step6:判斷是否達到所需精度或最大迭代次數(shù),若滿足,則終止循環(huán)并輸出最優(yōu)個體。否則,返回步驟2。

Step7:將最優(yōu)個體作為Q-Learning的初始模型輸入,通過訓練找到最優(yōu)策略。

DE-Q-Learning的偽代碼如算法2所示。

算法2 DE-Q-Learning偽代碼

Q表種群的隨機初始化

Qbest=DE(q_table_population) #最優(yōu)Q表由DE算法演化

輸入:環(huán)境E,狀態(tài)空間S,動作空間A,折扣因子γ

Fork=0,1,…,mdo #agent的每條完整路徑

初始化狀態(tài)s

Fort=0,1,2,3,…,do #agent的每個訓練步

通過貪心策略εof π在環(huán)境E中采取動作A

r,s′=Step(A) #執(zhí)行下一個動作A產(chǎn)生獎勵r和下一個狀態(tài)s′

s←s′

end forsis terminated

end for

π*(s)=argmaxQ(s,a) #根據(jù)Q表更新策略

3 實驗與分析

為了進一步驗證文中提出DE-Q-Learning的性能,文中采用兩種不同的二維迷宮環(huán)境進行實驗,這類游戲有兩個特點:① 動作維數(shù)小,狀態(tài)維數(shù)大。② 具有明顯勝利和失敗的條件,且獎懲區(qū)別明顯,適合驗證Q-Learning改進算法的通用性和泛化能力。

3.1 復雜迷宮環(huán)境

3.1.1 實驗環(huán)境

在如圖8所示的復雜迷宮環(huán)境中,分別對三個算法的收斂性能進行對比實驗。具體實驗仿真環(huán)境為:16 GB RAM,512 G硬盤,2.60 GHz 64位處理器,Windows 10操作系統(tǒng),使用Matlab2018b仿真軟件。

圖8 實驗迷宮環(huán)境

3.1.2 環(huán)境狀態(tài)設(shè)定

為了凸顯出算法在稀疏回報狀況下的高效性,該實驗環(huán)境設(shè)定如下。設(shè)定黑色區(qū)域為墻體,代表不可達狀態(tài),模型左下角綠色區(qū)域為迷宮起點,即智能體的初始位置。模型右上角對應的藍色區(qū)域則為迷宮出口,代表終止狀態(tài)。模型中共有376個可抵達的狀態(tài),智能體在除終止狀態(tài)的其余位置上回報值R均為0,在抵達終止狀態(tài)時,回報R設(shè)定為100。之所以將模型的反饋情況設(shè)置為稀疏回報,其目的是為了突顯出DE-Q-Learning算法的高效性。當積極回報僅存在于終止狀態(tài)時,只有通過智能體反復地探索直至抵達目標狀態(tài)從而不斷地更新Q表,才能促使算法收斂。這一過程起初可能是盲目的,智能體在毫無先驗信息的基礎(chǔ)上進行探索無疑增加了算法的運行時間。

3.1.3 適應度函數(shù)以及評價指標

由于需要更加直觀的評價標準即找到迷宮出口的次數(shù),若在規(guī)定的步長下,智能體到達終止狀態(tài)的次數(shù)較多,則說明此時的Q表具備較好的環(huán)境信息。所以針對文中實驗所涉及的問題,將適應度函數(shù)設(shè)定為在指定步長下目標狀態(tài)命中次數(shù),即

f(x)=

(9)

f(num)=

(10)

(11)

式中:t為算法運行代數(shù);num為智能體在t代時累計目標狀態(tài)命中次數(shù)。通過計算函數(shù)表達G(x)求得算法的平均命中率。

DE-Q-Learning算法與對比算法的具體參數(shù)見表3。對于其它在實驗中所涉及到的參數(shù)設(shè)定,這里給出統(tǒng)一規(guī)定。設(shè)定參數(shù)“Step”代表各算法在每次探索中所需最大步長,用來限制智能體的移動次數(shù);設(shè)定參數(shù)“Gen”作為各算法的循環(huán)次數(shù),代表最大訓練程度。在智能體探索環(huán)境時,Q表的每一代變化都為下一代智能體在探索環(huán)境時提供了更新信息。

表3 DE-Q-Learning與對比算法參數(shù)

3.1.4 實驗結(jié)果及分析

圖9對比了DE-Q-Learning與Q-Learning、Double Q-Learning及SA-Q-Learning算法在目標狀態(tài)命中率上的比較情況。橫坐標表示算法的運行代數(shù)Gen,縱坐標為命中率,這里將Gen的取值設(shè)為500。圖9(a)中,DE-Q-Learning算法在DE處理上的參數(shù)設(shè)置為:種群數(shù)量NP設(shè)置為20,演化代數(shù)G設(shè)置為20。圖9(b)中,種群數(shù)量NP設(shè)置為20,演化代數(shù)G設(shè)置為50。由實驗結(jié)果發(fā)現(xiàn),隨著演化代數(shù)的提升,DE-Q-Learning在命中率上有明顯的提升,相較于SA-Q-Learning和Q-Learning,其效果有著明顯的提升。而Double Q-Learning在動作選擇上采用雙估計器的方式來解決過擬合問題,在前期的收斂能力上可能不及Q-Learning和SA-Q-Learning。

圖9 DE-Q-Learning在NP為20時與不同算法命中率比較

圖10對比了Q-Learning、Double Q-Learning、SA-Q-Learning與DE-Q-Learning在種群個體為50的情況下,分別演化20代與50代的命中率情況。由實驗結(jié)果可以看出,隨著NP數(shù)量的增加,算法在空間上提升了搜索效率,在對模型進一步擬合后,得到誤差相對較小的最優(yōu)樣本輸出,有效地避免了算法進行盲目搜索,更進一步地提高了算法的命中率。

圖10 DE-Q-Learning在NP為50時與不同算法命中率比較

圖11對比了DE-Q-Learning在NP和Gen都為100代的情況下所得到的命中率曲線?？梢杂^察到,伴隨著演化程度的提升,算法在收斂性能上幾乎可以做到“零失誤”,DE-Q-Learning在效果上遠超Q-Learning、Double Q-Learning及SA-Q-Learning。

圖11 DE-Q-Learning在NP為100時與不同算法命中率比較

圖12對比了DE-Q-Learning在NP和G不同取值下的命中率情況。

圖12 DE-Q-Learning在NP和G不同取值下的命中率比較

圖12(a)繪出了演化種群NP取值為20,演化代數(shù)分別為20,50,100時算法的命中率曲線,圖12(b)繪制了將演化種群NP提升至50的的命中率曲線。通過實驗數(shù)據(jù)可以看出,在NP不變的情況下,隨著演化代數(shù)的增加,對算法性能有著明顯的提升。而隨著種群數(shù)量NP的提升,對算法性能也有著一定的改善,但是同時也會帶來一定的代價即算法運行時間增加。

從收斂速度上,由于DE-Q-Learning具有獨特的隱并行特點,無論從累計回報還是平均回報來看,其算法都具有優(yōu)異的效果。只有采用時間作為評價標準時,才能滿足對比的公平性。在“目標狀態(tài)命中率”評價標準的基礎(chǔ)上,表4分別記錄了各算法訓練500代所需運行時間。圖13為最終的訓練效果圖,展示了改進算法在路徑搜索中所訓練出的最佳路徑。

表4 各算法運行500代所消耗時長

圖13 訓練效果圖

3.2 Pacman游戲環(huán)境

3.2.1 實驗環(huán)境參數(shù)

Pacman吃豆人游戲是上世紀80年代日本南夢宮游戲公司推出的一款街機游戲,后來被加州大學伯克利分校引入到強化學習的實驗環(huán)境中作為實操項目,該環(huán)境在驗證算法的路徑搜索能力的基礎(chǔ)上添加了動態(tài)避障的訓練。文中使用該項目中的小型實驗環(huán)境smallGrid和中型實驗環(huán)境MediumClassic,如圖16～17所示。文中在16GB RAM,512 G硬盤,2.60 GHz 64位處理器,Windows 10操作系統(tǒng),Python3.7的環(huán)境下進行實驗。

3.2.2 環(huán)境狀態(tài)設(shè)定

在Pacman游戲環(huán)境中,強化學習訓練的智能體是如圖14～15所示的黃色扇形移動體,白色小圓點代表小獎勵,白色圓點代表大獎勵,具有兩只眼睛的橢圓形代表ghost,藍色邊框代表不可穿越的墻體。智能體具有上下左右四個動作維度,狀態(tài)使用Pacman項目中的layout地圖樣式表示,可以凸顯游戲中各元素的具體位置,pacman碰撞白色小圓點、大圓點分別獲取獎勵10分和20分,若與ghost碰撞,則會對pacman扣除50分并且游戲結(jié)束,并且在游戲中為了避免pacman長時間躲避ghost而不去探索獎勵,定義TIME_PENALTY=1作為時間懲罰,即每秒鐘pacman會受到-1分的懲罰。訓練的目標是智能體pacman通過墻體的保護上下左右移動躲避ghost并且盡可能吃掉所有白色圓點,以期望獲得最大的收益。

圖14 Pacman-SmallGrid環(huán)境

圖15 Pacman-mediumClassic環(huán)境

3.2.3 適應度函數(shù)以及評價指標

Pacman游戲環(huán)境利用每回合智能體所得到的回報來判斷訓練算法的優(yōu)劣,且智能體的回報根據(jù)環(huán)境返回觀測數(shù)據(jù)observation得到,全局獎勵R隨著時間變化如式(12)所示,其中r代表當前狀態(tài)獲得的即時獎勵:tp代表時間懲罰值,取值為當前所耗費時間(s)。在DE-Q-Learning算法中Q表個體的適應度值由智能體使用該Q表與環(huán)境交互n回合的R取平均得到,其適應度函數(shù)為

R=R+r-tp,

(12)

(13)

為了使對比實驗結(jié)果更加直觀,采用每一回合訓練得到的R作為評價算法優(yōu)劣的指標,DE-Q-Learning,算法與對比算法的具體參數(shù)見表3。

3.2.4 實驗結(jié)果及分析

圖16展示了DE-Q-Learning算法與對比算法在smallGrid環(huán)境中訓練2 000代的回報情況,可以觀察到文中提出DE-Q-Learning算法在整個訓練過程中所得到的回報是高于其他算法的,為了更加直觀展現(xiàn)DE-Q-Learning算法的優(yōu)越性。

圖16 SmallGrid環(huán)境各算法訓練2 000代回報

圖17展示了圖16中縱軸的累計回報sum_reward,可以看出與其他算法不同,DE-Q-Learning在訓練前期回報遠遠大于其他算法,并且后期能夠快速收斂。在收斂的速度上,表5展示了各算法訓練2 000代所消耗的時間,其中Double-Q-Learning算法收斂速度最慢,SA-Q-Learning算法收斂速度最快,其效果也好于原始Q-Learning,DE-Q-Learning收斂速度僅次于SA-Q-Learning。

表5 各算法訓練2 000代所消耗時長Tab.5 Time consumed to train each algorithm for 2 000 generations

圖17 SmallGrid環(huán)境各算法訓練2 000代縱軸回報和

式(14)為收斂速度的計算方式,其中Ir(Improvement rate)表示改進算法相對于原始算法速度的提升率,to、ti分別表示原始算法與改進算法訓練所耗時長。由表5中各算法訓練2 000代的時間數(shù)據(jù)可知DE-Q-Learning相對于Q-Learning速度提升26.18%,相對于Double-Q-Learning速度提升42.80%,但相對于SA-Q-Learning其速度并無優(yōu)勢;而由表6中各算法訓練10 000代的數(shù)據(jù)可知DE-Q-Learning相對于Q-Learning,Double-Q-Learning,SA-Q-Learning其速度分別提升了28.58%,42.16%,15.88%。

表6 各算法訓練10 000代消耗時長Tab.6 Time consumed to train each algorithm for 10 000 generations

(14)

由于mediumClassic環(huán)境的復雜程度遠遠高于smallGrid環(huán)境,故訓練次數(shù)需要大大增加,圖18展示了各算法在mediumClassic環(huán)境中訓練10 000代的回報情況,圖19展示了各代累計回報sum_reward,DE-Q-Learning算法在前期、中期、后期的回報仍然遠遠高于其他Q-Learning改進算法,表6展示了各算法訓練10 000代所消耗的時間,DE-Q-Learning算法的收斂速度快于其他改進算法,這說明DE-Q-Learning在復雜的環(huán)境中較其他算法更有優(yōu)勢。

圖18 MediumGrid環(huán)境各算法訓練10 000代回報

圖19 MediumGrid環(huán)境各算法訓練10 000代縱軸回報

4 結(jié) 論

為解決Q表規(guī)模增大時Q-Learning前期的盲目搜索問題,文中提出了一種使用演化算法優(yōu)化Q表的新型算法(DE-Q-Learning)。使用DE算法作為演化算法實例,經(jīng)過Gym的山地車環(huán)境驗證后,在復雜迷宮測試環(huán)境和Pacman游戲環(huán)境中與Q-Learning、Double Q-Learning、SA-Q-Learning三個算法進行比較。實驗結(jié)果表明,DE-Q-Learning無論在目標狀態(tài)命中率、累計回報及收斂速度上,都具有優(yōu)異的表現(xiàn),算法的性能得到了明顯的提升,證明該算法的有效性。從理論上來講,文中所提出的DE-Q-Learning可以應用于任何Q表有限的無模型問題,具有較好的魯棒性,并且在演化算法的設(shè)定上,不僅局限于DE演化算法,其它的智能算法均可適用于該模型中。但在高維復雜環(huán)境中,由于無法創(chuàng)建合適的Q表來存儲狀態(tài)-動作值,且對于一些及時性策略問題Q-Learning算法也無法有效解決,故未來的工作將進一步研究如何利用深度強化學習優(yōu)化算法解決此類高緯度、及時性的復雜問題。