劉 曉 毛 寧

(中航工業(yè)西安航空計(jì)算技術(shù)研究所，西安，710065)

?

一種新的連續(xù)動(dòng)作集學(xué)習(xí)自動(dòng)機(jī)*

劉 曉 毛 寧

(中航工業(yè)西安航空計(jì)算技術(shù)研究所，西安，710065)

學(xué)習(xí)自動(dòng)機(jī)(Learning automation，LA)是一種自適應(yīng)決策器。其通過(guò)與一個(gè)隨機(jī)環(huán)境不斷交互學(xué)習(xí)從一個(gè)允許的動(dòng)作集里選擇最優(yōu)的動(dòng)作。在大多數(shù)傳統(tǒng)的LA模型中，動(dòng)作集總是被取作有限的。因此，對(duì)于連續(xù)參數(shù)學(xué)習(xí)問(wèn)題，需要將動(dòng)作空間離散化，并且學(xué)習(xí)的精度取決于離散化的粒度。本文提出一種新的連續(xù)動(dòng)作集學(xué)習(xí)自動(dòng)機(jī)(Continuous action-set learning automaton，CALA)，其動(dòng)作集為一個(gè)可變區(qū)間，同時(shí)按照均勻分布方式選擇輸出動(dòng)作。學(xué)習(xí)算法利用來(lái)自環(huán)境的二值反饋信號(hào)對(duì)動(dòng)作區(qū)間的端點(diǎn)進(jìn)行自適應(yīng)更新。通過(guò)一個(gè)多模態(tài)學(xué)習(xí)問(wèn)題的仿真實(shí)驗(yàn)，演示了新算法相對(duì)于3種現(xiàn)有CALA算法的優(yōu)越性。

機(jī)器學(xué)習(xí)；強(qiáng)化學(xué)習(xí)；在線學(xué)習(xí)；學(xué)習(xí)自動(dòng)機(jī)；連續(xù)動(dòng)作集學(xué)習(xí)自動(dòng)機(jī)

引 言

學(xué)習(xí)自動(dòng)機(jī)(Learning automation, LA)是一種可應(yīng)用于未知的、隨機(jī)環(huán)境的自適應(yīng)決策單元[1-2]。在任一時(shí)刻，LA根據(jù)某種概率分布從其動(dòng)作集里選擇一個(gè)動(dòng)作，并輸出給環(huán)境；環(huán)境則反饋回一個(gè)強(qiáng)化信號(hào)，作為對(duì)所選動(dòng)作的評(píng)價(jià)。根據(jù)環(huán)境的評(píng)價(jià)，LA對(duì)其概率分布進(jìn)行調(diào)整，以使表現(xiàn)好的動(dòng)作的被選概率逐漸增大。與有教師指導(dǎo)的監(jiān)督學(xué)習(xí)不同，LA采用的是一種強(qiáng)化學(xué)習(xí)。其中環(huán)境并不直接告訴自動(dòng)機(jī)應(yīng)該選擇哪個(gè)動(dòng)作，而只是對(duì)自動(dòng)機(jī)選出的每個(gè)動(dòng)作給出一個(gè)好或不好的評(píng)價(jià)，并且這種評(píng)價(jià)通常都帶有一定的不確定性或隨機(jī)噪聲。作為一種有效的機(jī)器學(xué)習(xí)方法，LA已經(jīng)在許多領(lǐng)域得到了應(yīng)用，如汽車懸掛控制[3]、數(shù)字濾波器設(shè)計(jì)[4]、噪聲容忍模式分類[5]、自適應(yīng)網(wǎng)頁(yè)爬取[6]、智能電網(wǎng)中的電源管理[7]、無(wú)線傳感器網(wǎng)絡(luò)中的覆蓋算法[8-9]以及糖尿病病人最佳胰島素劑量的確定[10]等。

根據(jù)動(dòng)作集的性質(zhì)，LA可分為兩大類[2]：有限動(dòng)作集學(xué)習(xí)自動(dòng)機(jī)(Finite action-set learning automata，F(xiàn)ALA)和連續(xù)動(dòng)作集學(xué)習(xí)自動(dòng)機(jī)(Continuous action-set learning automata，CALA)。 FALA的動(dòng)作數(shù)是有限的，CALA則可以從一個(gè)連續(xù)區(qū)間甚至整個(gè)實(shí)數(shù)軸上選取動(dòng)作。對(duì)于實(shí)值參數(shù)學(xué)習(xí)問(wèn)題，若采用FALA，首先要對(duì)動(dòng)作空間進(jìn)行離散化。離散化的顆粒度太粗，不能保證結(jié)果的精度；太細(xì)又會(huì)導(dǎo)致動(dòng)作數(shù)過(guò)多，學(xué)習(xí)速度減慢。LA也可以根據(jù)環(huán)境反饋的強(qiáng)化信號(hào)來(lái)分類[1]：若強(qiáng)化信號(hào)只有兩種取值(如用0表示成功，1表示失敗)，就稱為P型的；若強(qiáng)化信號(hào)取值多于兩種但又是有限的，則稱為Q型的；如果強(qiáng)化信號(hào)可取連續(xù)的實(shí)數(shù)值，則稱作S型的。上述LA從環(huán)境接收的信息只有強(qiáng)化信號(hào)。還有一類LA，除強(qiáng)化信號(hào)外還可以接收來(lái)自環(huán)境的狀態(tài)信息(稱為情境輸入)。這時(shí)，LA的任務(wù)是為每一種情境輸入選擇最適合的輸出動(dòng)作。這種LA被稱作聯(lián)想型LA或者廣義學(xué)習(xí)自動(dòng)機(jī)(Generalized learning automata，GLA)[2]。本文將要研究的是一種P型的、非聯(lián)想型CALA。

在FALA中，動(dòng)作概率的表示只需一個(gè)維數(shù)與動(dòng)作數(shù)相同的矢量即可。但對(duì)于CALA，由于有無(wú)窮多個(gè)動(dòng)作，動(dòng)作概率如何表示就成為一個(gè)很棘手的問(wèn)題。故相對(duì)于FALA，CALA的研究要困難得多。Gullapalli[11]和Vasilakos等[12]分別提出了可產(chǎn)生實(shí)值動(dòng)作的聯(lián)想型CALA。這類帶有情境輸入的GLA，主要用于隨機(jī)神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)。目前已知的非聯(lián)想型的CALA只有以下幾種：由Santharam，Sastry和Thathachar提出的模型[13](為區(qū)分起見，以下簡(jiǎn)記為CALA-SST，其中的后綴代表3位提出者名字的首字母)，Beigy和Meybodi提出的模型[14](以下簡(jiǎn)記為CALA-BM)，Vlachogiannis提出的模型[15](原文作者稱其為R-CALA)，以及由Frost，Howell，Gordon和吳青華提出的連續(xù)動(dòng)作強(qiáng)化學(xué)習(xí)自動(dòng)機(jī)(Continuous action-set reinforcement learning automata，CARLA)[3]。這些CALA都是S型的，其中的環(huán)境反饋都可以取連續(xù)的實(shí)數(shù)值。

CALA-SST，CALA-BM和R-CALA都采用高斯分布作為動(dòng)作選擇的概率模型。R-CALA實(shí)際上是一種截?cái)喔咚狗植?，因?yàn)槠鋭?dòng)作被限制在一個(gè)有限區(qū)間上。CALA-SST每次要輸出兩個(gè)動(dòng)作，一個(gè)根據(jù)高斯分布隨機(jī)產(chǎn)生，另一個(gè)則直接取高斯分布的均值。算法根據(jù)這兩個(gè)動(dòng)作以及環(huán)境對(duì)它們的評(píng)價(jià)信號(hào)，對(duì)高斯分布的均值μ和標(biāo)準(zhǔn)差σ進(jìn)行更新。為防止σ減小到0甚至出現(xiàn)負(fù)值，算法引入一個(gè)參數(shù)σL，使σ不能小于σL。與CALA-SST不同，CALA-BM和R-CALA每次只輸出一個(gè)動(dòng)作(按照高斯分布隨機(jī)產(chǎn)生)。CALA-BM在對(duì)高斯分布的均值進(jìn)行更新時(shí)，要求強(qiáng)化信號(hào)必須處于0到1之間(如果不在此區(qū)間，需先做歸一化處理)；R-CALA采用簡(jiǎn)單的貪婪策略對(duì)分布均值進(jìn)行更新：當(dāng)所選動(dòng)作好于迄今最好的動(dòng)作時(shí)，將該動(dòng)作作為新的均值，否則原均值保持不變。在CALA-BM和R-CALA中，高斯分布的標(biāo)準(zhǔn)差直接根據(jù)學(xué)習(xí)步數(shù)來(lái)計(jì)算，其σ單調(diào)減小并最終趨于0。與前面幾種CALA不同，CARLA采用非參數(shù)化的概率模型，其初始概率分布為一個(gè)有限區(qū)間上的均勻分布。在學(xué)習(xí)過(guò)程中，算法通過(guò)一個(gè)對(duì)稱的高斯型鄰近函數(shù)，將表現(xiàn)好的動(dòng)作的獎(jiǎng)賞“傳播”給其相鄰的動(dòng)作。該算法的實(shí)現(xiàn)非常復(fù)雜，需要大量的數(shù)值積分計(jì)算。另外，該算法也需要?dú)w一化的強(qiáng)化信號(hào)，為此需開辟一個(gè)參考存儲(chǔ)器以保存環(huán)境反饋的歷史值。

1 本文提出的CALA

在本文提出的CALA模型中，自動(dòng)機(jī)的動(dòng)作集對(duì)應(yīng)一個(gè)連續(xù)區(qū)間[xL,xR]，該區(qū)間的位置和長(zhǎng)度可以動(dòng)態(tài)變化。在任一時(shí)刻n，自動(dòng)機(jī)以均勻分布方式從當(dāng)前區(qū)間上隨機(jī)選擇一個(gè)動(dòng)作xn并輸出給環(huán)境，環(huán)境則給出一個(gè)二值的評(píng)價(jià)信號(hào)βn∈{0,1}，0表示成功，1表示失敗。根據(jù)該評(píng)價(jià)信號(hào)，自動(dòng)機(jī)對(duì)其動(dòng)作區(qū)間的兩個(gè)端點(diǎn)進(jìn)行調(diào)整更新。

算法參數(shù)：λ1為大于0小于1的常數(shù)，控制區(qū)間外擴(kuò)的幅度；λ2為大于0小于1的常數(shù)(應(yīng)小于λ1)，控制區(qū)間內(nèi)縮的幅度；θ為大于0小于1的常數(shù)，控制在強(qiáng)化信號(hào)為失敗的情況下區(qū)間端點(diǎn)調(diào)整的幅度；ε為足夠小且大于0的常數(shù)，控制解的精度，并防止區(qū)間長(zhǎng)度無(wú)限縮小。

初始化：給動(dòng)作區(qū)間的左右端點(diǎn)xL和xR分別賦初值，并置n=0。

學(xué)習(xí)過(guò)程：

(1) 按照下式產(chǎn)生一個(gè)動(dòng)作xn，并輸出給環(huán)境：xn=xL+rn(xR-xL)，其中rn為0到1之間均勻分布的隨機(jī)數(shù)(每次都重新產(chǎn)生)。

(2) 接收環(huán)境反饋的強(qiáng)化信號(hào)βn。

(3) 更新動(dòng)作區(qū)間(等價(jià)于更新概率分布)： 令cL=xL+Δ，cR=xR-Δ，其中Δ= (xR-xL)/3； 當(dāng)βn=0時(shí)：

若xn

否則令xL=xL+λ2(1 -ε/Δ)(xn-cL)；

若xn>cR則令xR=xR+λ1(xn-cR)，

否則令xR=xR-λ2(1 -ε/Δ)(cR-xn)； 當(dāng)βn=1時(shí)：

若xn

否則，若xn>cR則令xL=xL-θλ1(xn-cL)；

若xn>cR則令xR=xR-θλ2(1 -ε/Δ)(xn-cR)，

否則，若xn

(4) 令n=n+1，轉(zhuǎn)(1)。

上述動(dòng)作區(qū)間更新的基本原理是：先確定區(qū)間的左右1/3分界點(diǎn)cL和cR。然后，根據(jù)βn的取值情況和xn落于3等分區(qū)間的哪一段，對(duì)區(qū)間的端點(diǎn)進(jìn)行調(diào)整。當(dāng)βn為成功時(shí)，將兩個(gè)端點(diǎn)均朝xn所在位置的方向移動(dòng)(獎(jiǎng)勵(lì)xn)；當(dāng)βn為失敗時(shí)，若xn落于中間的1/3段，兩個(gè)端點(diǎn)均保持不變，否則均朝xn所在位置相反一側(cè)的方向移動(dòng)(懲罰xn)。區(qū)間端點(diǎn)移動(dòng)的幅度與xn跟相應(yīng)分界點(diǎn)之間的距離成正比，具體的比例系數(shù)由參數(shù)λ1，λ2，θ和ε控制。其中λ2通?？扇ˇ?/3，以使左端點(diǎn)向右、右端點(diǎn)向左的移動(dòng)(收縮)比左端點(diǎn)向左、右端點(diǎn)向右的移動(dòng)(擴(kuò)張)更謹(jǐn)慎一些。θ的作用是讓對(duì)失敗動(dòng)作的懲罰比對(duì)成功動(dòng)作的獎(jiǎng)勵(lì)輕一些。

在區(qū)間左右移動(dòng)時(shí)，由于兩個(gè)端點(diǎn)移動(dòng)的幅度不同，整個(gè)區(qū)間實(shí)際上是擴(kuò)張的；而當(dāng)兩個(gè)端點(diǎn)均向內(nèi)移動(dòng)時(shí)，區(qū)間會(huì)收縮。自動(dòng)機(jī)正是通過(guò)對(duì)其動(dòng)作區(qū)間的自適應(yīng)調(diào)整(可形象地稱之為調(diào)焦和變焦)，以發(fā)現(xiàn)和跟蹤最好的動(dòng)作，將其包圍在一個(gè)長(zhǎng)度逐漸縮小的區(qū)間的中心。故將該模型稱作“聚焦區(qū)間學(xué)習(xí)自動(dòng)機(jī)(Focused interval learning automaton，F(xiàn)ILA)。為體現(xiàn)其對(duì)成功的動(dòng)作進(jìn)行獎(jiǎng)勵(lì)、對(duì)失敗的動(dòng)作進(jìn)行懲罰的“獎(jiǎng)罰”式學(xué)習(xí)的特點(diǎn)，再在FILA的后面綴以RP，記作FILA/RP。

2 本文算法的分析

(1) FILA/RP選擇動(dòng)作的方法非常簡(jiǎn)單，只需產(chǎn)生一個(gè)均勻分布隨機(jī)數(shù)，并將其映射到當(dāng)前的動(dòng)作區(qū)間上即可。CALA-SST，CALA-BM和R-CALA則需要產(chǎn)生高斯分布隨機(jī)數(shù)。對(duì)于沒有現(xiàn)成的高斯隨機(jī)數(shù)函數(shù)的場(chǎng)合，則需要通過(guò)均勻分布隨機(jī)數(shù)來(lái)生成高斯分布隨機(jī)數(shù)，計(jì)算量將明顯增加。至于CARLA，其動(dòng)作選擇需要計(jì)算數(shù)值積分，時(shí)間開銷更大。

(2) FILA/RP對(duì)動(dòng)作區(qū)間(對(duì)應(yīng)概率分布)的更新也相當(dāng)簡(jiǎn)單，像CALA-SST那樣只涉及四則運(yùn)算，再加一些條件判斷。而CALA-BM和R-CALA在計(jì)算高斯分布的標(biāo)準(zhǔn)差時(shí)，則需要進(jìn)行開3次方根的運(yùn)算。CARLA就更加復(fù)雜，其對(duì)概率密度函數(shù)的更新、對(duì)概率密度和環(huán)境反饋的歸一化處理，都需要大量的數(shù)值計(jì)算。

(3) CARLA需要以離散化的方式存儲(chǔ)其概率密度函數(shù)，為計(jì)算歸一化的強(qiáng)化信號(hào)還要保存一個(gè)滑動(dòng)窗口內(nèi)的歷史環(huán)境反饋值(典型設(shè)置為500個(gè))。而FILA/RP則只需保存動(dòng)作區(qū)間的兩個(gè)端點(diǎn)，存儲(chǔ)空間花費(fèi)非常少。

(4) 在FILA/RP中，當(dāng)區(qū)間左端點(diǎn)向右、或右端點(diǎn)向左移動(dòng)時(shí)，通過(guò)因子(1 -ε/Δ)來(lái)調(diào)節(jié)移動(dòng)的幅度。在學(xué)習(xí)開始階段，區(qū)間范圍寬，ε/Δ很小，(1 -ε/Δ)基本等于1，移動(dòng)量幾乎不受影響；而當(dāng)區(qū)間變得足夠窄時(shí)，ε/Δ接近于1，(1 -ε/Δ)幾乎為0，相應(yīng)端點(diǎn)的移動(dòng)量將非常小。這樣可防止區(qū)間收縮為一個(gè)長(zhǎng)度為0的“點(diǎn)”，以保持對(duì)環(huán)境變化進(jìn)行跟蹤的能力(CALA-SST通過(guò)引入σL來(lái)達(dá)到這一點(diǎn))。而在CALA-BM和R-CALA中，由于高斯分布的標(biāo)準(zhǔn)差單調(diào)減小并最終趨于0，自動(dòng)機(jī)將無(wú)法發(fā)現(xiàn)和跟蹤環(huán)境的動(dòng)態(tài)變化。

(5) FILA的核心思想是：以一個(gè)可變區(qū)間作為動(dòng)作集，按照均勻分布方式產(chǎn)生動(dòng)作，再根據(jù)環(huán)境反饋對(duì)動(dòng)作區(qū)間的兩個(gè)端點(diǎn)進(jìn)行更新。在該框架下，根據(jù)環(huán)境反饋的性質(zhì)、是否使用歷史信息以及如何使用，可以形成不同的學(xué)習(xí)算法。本文的FILA/RP是一種P型LA，直接利用環(huán)境的二值反饋信號(hào)對(duì)區(qū)間端點(diǎn)進(jìn)行獎(jiǎng)罰式更新。對(duì)于環(huán)境反饋(即待優(yōu)化的目標(biāo)函數(shù))取連續(xù)值的情況，則可以記憶歷史目標(biāo)函數(shù)值，利用其中“最新”且“最好”的動(dòng)作對(duì)區(qū)間進(jìn)行“獎(jiǎng)勵(lì)”式更新，這樣可以得到S型的學(xué)習(xí)算法。

3 仿真實(shí)驗(yàn)和結(jié)果分析

現(xiàn)在考慮這樣一個(gè)隨機(jī)學(xué)習(xí)問(wèn)題，其中動(dòng)作參數(shù)x可在(-∞,∞)上連續(xù)取值。對(duì)于每個(gè)x,環(huán)境都會(huì)給出一個(gè)二值的強(qiáng)化信號(hào)β(x)，其中β(x)以d(x)的概率取0(表示成功)，以1-d(x)的概率取1(表示失敗)。不同動(dòng)作參數(shù)的成功概率由下式確定

(1)

這是一個(gè)多模態(tài)的非線性函數(shù)，在點(diǎn)-4和4處各有一個(gè)高度約為0.8的峰值，在x等于0處則有一個(gè)高度約為0.47的“波谷”。在±4之外、隨著x絕對(duì)值的增大，d(x)逐漸減小并趨近其下限0.4。分別利用FILA/RP和3種基于參數(shù)化概率模型的CALA，即CALA-SST，CALA-BM和R-CALA對(duì)上述問(wèn)題進(jìn)行仿真實(shí)驗(yàn)。CALA-SST的內(nèi)部參數(shù)[5]經(jīng)反復(fù)嘗試選取如下的效果相對(duì)好的數(shù)值：λ=0.008，K=0.7，σL=0.02；高斯分布的初始參數(shù)取μ0=0，σ0=5。關(guān)于CALA-BM，文獻(xiàn)[14]指出可根據(jù)σn=1/[floor(n/10)]1/3來(lái)計(jì)算n時(shí)刻高斯分布的標(biāo)準(zhǔn)差，其中floor為下取整函數(shù)。顯然，當(dāng)n<10時(shí)該式會(huì)出現(xiàn)除法溢出。為此，floor替換為向上取整函數(shù)ceil。但即使這樣，算法仍不能較好地工作，原因是σn衰減過(guò)快。因此對(duì)該算法再次進(jìn)行了“改造”，即像CALA-SST那樣，引入一個(gè)新的參數(shù)σ0，并按照σn=σ0/[ceil(n/10)]1/3計(jì)算n時(shí)刻高斯分布的標(biāo)準(zhǔn)差，使得σn的衰減速度可以被控制。CALA-BM的內(nèi)部參數(shù)，學(xué)習(xí)步長(zhǎng)a取0.015，新引入的σ0取5；高斯分布的初始均值μ0取0。原始的R-CALA算法[15]，保存β的全程最小值βmin，當(dāng)βn<βmin時(shí)將對(duì)應(yīng)的xn賦給μn同時(shí)更新βmin。由于本文的β只有0和1兩種取值，若采用該規(guī)則，μn和βmin最多只能被更新一次，無(wú)法實(shí)現(xiàn)學(xué)習(xí)。故在本研究中，以″≤″取代″<″。R-CALA只有兩個(gè)內(nèi)部參數(shù)：動(dòng)作參數(shù)的上、下限xmax和xmin，仿真中分別取7和-7。對(duì)于FILA/RP，相關(guān)參數(shù)設(shè)置如下：θ=0.1，ε=0.02，λ1=3λ2且λ2=0.01；初始動(dòng)作區(qū)間取為[-5,5]。每次仿真均運(yùn)行20 000步。圖1給出的是4種算法各7次仿真過(guò)程中，動(dòng)作空間的中心(對(duì)FILA/RP來(lái)說(shuō)就是動(dòng)作區(qū)間的中點(diǎn)，對(duì)另外3種算法來(lái)說(shuō)則是高斯分布的均值)隨仿真時(shí)間n的演化軌跡。

圖1 動(dòng)作空間的中心隨仿真時(shí)間的變化軌跡(每種算法各仿真7次)Fig.1 Center of action space vs.time step(7 simulations per algorithm)

由圖1可以看出，CALA-SST和R-CALA的高斯分布均值的演化軌跡非常雜亂，到仿真時(shí)間結(jié)束時(shí)(n=20 000)，仍有部分μn未能穩(wěn)定于最優(yōu)解-4或4。相比之下，CALA-BM則好很多，7次仿真全都能收斂到兩個(gè)最優(yōu)解之一。不過(guò)，CALA-BM有一條μn曲線向目標(biāo)靠近的速度相當(dāng)緩慢。這是由于其高斯分布的標(biāo)準(zhǔn)差σn衰減相對(duì)較快，限制了μn的移動(dòng)速度。增大新引入的參數(shù)σ0，可以加快μn移動(dòng)的速度，但算法選擇動(dòng)作時(shí)的目標(biāo)將不再集中，自動(dòng)機(jī)選出的xn的波動(dòng)將會(huì)增大。4種算法中，表現(xiàn)最好的還是FILA/RP，其動(dòng)作區(qū)間的中心全都能很快移動(dòng)到兩個(gè)最優(yōu)解之一。

圖2給出的是每種算法一次典型的仿真中，自動(dòng)機(jī)選出的動(dòng)作序列xn的演化軌跡。在圖2所示的仿真中，4種算法基本上都發(fā)現(xiàn)了最優(yōu)動(dòng)作-4，但不同算法的運(yùn)行軌跡卻有很大的差異。FILA/RP和CALA-BM均能較快地定位目標(biāo)，然后堅(jiān)守，它們找到目標(biāo)后的動(dòng)作軌跡都很筆直。不過(guò)，CALA-BM的軌跡要臃腫和粗糙得多，這表明其目標(biāo)不夠集中，選擇的動(dòng)作有較大的波動(dòng)。減小新引入的參數(shù)σ0，可以使軌跡變細(xì)，但這又會(huì)導(dǎo)致μn的移動(dòng)變緩(正如圖1(b)中的那條移動(dòng)緩慢的曲線)。再看CALA-SST和R-CALA，二者的動(dòng)作軌跡都相當(dāng)曲折，很難穩(wěn)定在最優(yōu)解上。另外，CALA-SST的動(dòng)作軌跡上有一些明顯的、幾乎垂直分布的突跳點(diǎn)，這是由于其高斯分布的標(biāo)準(zhǔn)差變化劇烈，突然間增大，隨即又快速變小。相比之下，F(xiàn)ILA/RP的表現(xiàn)最好，其先通過(guò)調(diào)整動(dòng)作區(qū)間的端點(diǎn)，將最優(yōu)解包圍在區(qū)間的中心，然后再使區(qū)間迅速收縮，此后則基本上只在該最優(yōu)解的一個(gè)很小的鄰域內(nèi)選取動(dòng)作。

圖2 一次典型仿真中自動(dòng)機(jī)選出的動(dòng)作隨時(shí)間的變化軌跡Fig.2 Action selected by LA vs. time step in typical simulation

為評(píng)估每種算法的在線學(xué)習(xí)性能，在仿真過(guò)程中的每一步，都計(jì)算截止當(dāng)前自動(dòng)機(jī)實(shí)際獲得的成功率Rn=sn/n，其中sn為到n時(shí)刻的累計(jì)成功次數(shù)。這樣，每做一次仿真，就會(huì)得到一條Rn曲線。由d(x)的定義不難知道，Rn的理想的變化軌跡是逐漸逼近0.8(理論最大成功概率)。由于LA本質(zhì)上是一種由隨機(jī)數(shù)序列驅(qū)動(dòng)的隨機(jī)搜索算法，每次運(yùn)行不一定能得到相同的結(jié)果，故為全面、客觀地評(píng)估各算法的性能，對(duì)每一種算法各做了200次仿真。圖3給出的是每種算法200次仿真中Rn曲線疊加在一起的效果。

由圖3可以看出，3種現(xiàn)有算法的學(xué)習(xí)軌跡都很散亂(尤其是CALA-SST和R-CALA)，這表明它們對(duì)隨機(jī)數(shù)序列很敏感，算法每次運(yùn)行結(jié)果的一致性很差。仔細(xì)觀察不難發(fā)現(xiàn)，各算法的行為表現(xiàn)還存在一些細(xì)節(jié)上的差異。在學(xué)習(xí)初期，CALA-SST反應(yīng)較為遲鈍，Rn上升緩慢。R-CALA的某些Rn，從一開始就處于相當(dāng)高的水平(不過(guò)后面并沒有進(jìn)一步上升)；但又有一些Rn卻幾乎一直呆在很低的水平上(CALA-SST也一樣)。到仿真時(shí)間結(jié)束時(shí)，CALA-SST和R-CALA的Rn都非常分散，分布范圍很寬。至于改造后的CALA-BM，有一些仿真相當(dāng)不錯(cuò)，最好的結(jié)果顯著好于前兩種算法；但另一些則不好，Rn上升緩慢，其中最差的一個(gè)在仿真結(jié)束時(shí)只到0.56。相比之下，F(xiàn)ILA/RP的學(xué)習(xí)軌跡則顯得相當(dāng)緊湊，上升趨勢(shì)也很清晰，到仿真結(jié)束時(shí)其成功率全都集中于一個(gè)很窄的范圍之內(nèi)。表1給出了4種算法各200次仿真(每次仿真20 000步)的相關(guān)統(tǒng)計(jì)結(jié)果。

由表1不難看出，F(xiàn)ILA/RP的最高、最低和平均成功率在4種算法中都是最好的，其最差結(jié)果不僅遠(yuǎn)遠(yuǎn)好于3種現(xiàn)有算法的最差結(jié)果，甚至比CALA-SST和R-CALA的最好結(jié)果還要好，快趕上經(jīng)改造的CALA-BM的平均結(jié)果了。FILA/RP性能優(yōu)異的根本原因，在于其獨(dú)特的概率模型和模型參數(shù)的更新機(jī)制。在現(xiàn)有的采用參數(shù)化概率模型的CALA-SST，CALA-BM和R-CALA中，高斯分布的均值和標(biāo)準(zhǔn)差分別進(jìn)行更新或計(jì)算，容易造成分布位置和寬度的脫節(jié)，使得均值尚未移動(dòng)到理想位置、方差就已經(jīng)很小，或者方差衰減過(guò)慢、算法遲遲不能收斂。FILA/RP對(duì)區(qū)間端點(diǎn)的更新，則同時(shí)實(shí)現(xiàn)了區(qū)間位置和寬度的調(diào)整，其目標(biāo)的準(zhǔn)確度和集中度得到很好的統(tǒng)一。CALA-SST和R-CALA表現(xiàn)不好還有一個(gè)原因，二者都基于對(duì)環(huán)境反饋(β)的比較來(lái)更新高斯分布的均值。對(duì)于環(huán)境反饋只有0和1兩種取值的P型環(huán)境，這種比較不能給算法提供足夠的信息。

在算法的運(yùn)行時(shí)間方面，CALA-SST耗時(shí)最少，其次是FILA/RP。CALA-BM和R-CALA在確定高斯分布的標(biāo)準(zhǔn)差時(shí)都要計(jì)算三次方根，時(shí)間花費(fèi)較長(zhǎng)。在本文的仿真中，高斯隨機(jī)數(shù)均通過(guò)調(diào)用Matlab的randn函數(shù)產(chǎn)生。如果通過(guò)自編程序產(chǎn)生，則3種現(xiàn)有算法的耗時(shí)都將顯著加長(zhǎng)。

圖3 在線學(xué)習(xí)性能(每種算法各仿真200次)Fig.3 Online learning performance(200 simulations per algorithm)

學(xué)習(xí)算法最高成功率最低成功率平均成功率花費(fèi)時(shí)間/sCALA?SST0．7560．5210．66324．67CALA?BM0．7850．5600．76628．64R?CALA0．7420．5610．66828．76FILA/RP0．7880．7630．77827．42

4 結(jié)束語(yǔ)

為解決備選動(dòng)作取實(shí)數(shù)值的強(qiáng)化學(xué)習(xí)問(wèn)題，本文提出一種新的連續(xù)動(dòng)作集學(xué)習(xí)自動(dòng)機(jī)，即基于獎(jiǎng)罰式學(xué)習(xí)的聚焦區(qū)間學(xué)習(xí)自動(dòng)機(jī)(FILA/RP)。該自動(dòng)機(jī)的動(dòng)作集為一個(gè)實(shí)數(shù)區(qū)間，通過(guò)均勻分布方式選擇輸出動(dòng)作，并根據(jù)環(huán)境反饋對(duì)區(qū)間的端點(diǎn)進(jìn)行自適應(yīng)調(diào)整。跟現(xiàn)有的CALA相比，本文的FILA/RP有一些顯著的特點(diǎn)和優(yōu)勢(shì)?，F(xiàn)有的CALA都是S型的，即環(huán)境反饋可以連續(xù)取值，F(xiàn)ILA/RP則是P型的，因而更適合具有二值反饋的隨機(jī)環(huán)境。FILA/RP采用一種特殊的參數(shù)化概率模型，學(xué)習(xí)過(guò)程中需要存儲(chǔ)和更新的參數(shù)只有兩個(gè)(即區(qū)間的兩個(gè)端點(diǎn))，這使得與采用非參數(shù)化概率模型的CARLA相比，該算法的實(shí)現(xiàn)非常簡(jiǎn)單，時(shí)間和空間開銷都很小?，F(xiàn)有的參數(shù)化CALA在選擇動(dòng)作時(shí)，都需要高斯分布隨機(jī)數(shù)，新算法則只需要均勻分布隨機(jī)數(shù)，其產(chǎn)生更為容易。由于動(dòng)作區(qū)間不會(huì)無(wú)限收縮，F(xiàn)ILA/RP可以跟蹤環(huán)境的動(dòng)態(tài)變化；CALA-BM和R-CALA則不能，因?yàn)樗鼈兊母咚狗植嫉臉?biāo)準(zhǔn)差只能單調(diào)減小并最終變?yōu)?。通過(guò)一個(gè)多模態(tài)的實(shí)值參數(shù)強(qiáng)化學(xué)習(xí)問(wèn)題的仿真實(shí)驗(yàn)，演示了新算法的優(yōu)異性能。與3種現(xiàn)有的參數(shù)化CALA相比，本文提出的FILA/RP具有學(xué)習(xí)速度快、精度高和運(yùn)行結(jié)果的一致性好等優(yōu)點(diǎn)。目前，已將該算法應(yīng)用于聯(lián)想強(qiáng)化學(xué)習(xí)問(wèn)題，其效果仍然好于現(xiàn)有的CALA(相關(guān)內(nèi)容將另文發(fā)表)。進(jìn)一步研究的方向，包括用更多、更復(fù)雜的問(wèn)題對(duì)該算法的學(xué)習(xí)性能進(jìn)行測(cè)試和評(píng)估，以及嘗試將其應(yīng)用于模式識(shí)別、智能控制等實(shí)際工程領(lǐng)域。

[1] Narendra K S,Thathachar M A L.Learning automata：An introduction[M].Englewood Cliffs,NJ：Prentice Hall,1989：35-58.

[2] Thathachar M A L，Sastry P S.Varieties of learning automata：An overview[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B：Cybernetics,2002,32(6)：711-722.

[3] Howell M N,Frost G P,Gordon T J,et al.Continuous action reinforcement learning applied to vehicle suspension control[J].Mechatronics,1997,7(3)：263-276.

[4] Howell M N,Gordon T J.Continuous action reinforcement learning automata and their application to adaptive digital filter design[J].Engineering Applications of Artificial Intelligence,2001,14(5)：549-561.

[5] Sastry P S,Nagendra G D,Mamwani N.A team of continuous-action learning automata for noise-tolerant learning of half-spaces[J].IEEE Transactions on Systems,Man,and Cybernetics，Part B：Cybernetics, 2010,40(1)：19-28.

[6] Torkestani J A.An adaptive focused web crawling algorithm based on learning automata[J].Applied Intelligence,2012,37(4)：586-601.

[7] Misra S,Krishna P V,Saritha V,et al.Learning automata as a utility for power management in smart grids[J].IEEE Communications Magazine,2013,51(1)：98-104.

[8] Mohamadi H,Ismail A S,Salleh S.Solving target coverage problem using cover sets in wireless sensor networks based on learning automata[J].Wireless Personal Communications,2014,75(1)：447-463.

[9] 王建平,陳改霞，孔德川，等.一種基于學(xué)習(xí)自動(dòng)機(jī)的WSN區(qū)域覆蓋算法[J].數(shù)據(jù)采集與處理，2014,29(6)：1016-1022.

Wang Jianping,Chen Gaixia,Kong Dechuan,et al.Learning automata-based area coverage algorithm for wireless sensor networks[J].Journal of Data Acquisition and Processing,2014,29(6)：1016-1022.

[10]Torkestani J A,Pisheh E G.A learning automata-based blood glucose regulation mechanism in type 2 diabetes[J].Control Engineering Practice,2014,26：151-159.

[11]Gullapalli V.A stochastic reinforcement learning algorithm for learning real-valued functions[J].Neural Networks,1990,3：671-692.

[12]Vasilakos A,Loukas N H.ANASA—A stochastic reinforcement algorithm for real-valued neural computation[J].IEEE Transactions on Neural Networks,1996,7：830-842.

[13]Santharam G,Sastry P S,Thathachar M A L.Continuous action set learning automata for stochastic optimization[J].Journal of the Franklin Institute,1994,331B(5)：607-628.

[14]Beigy H,Meybodi M R. A new continuous action-set learning automaton for function optimization[J]. Journal of the Franklin Institute,2006,343(1)：27-47.

[15]Vlachogiannis J G.Probabilistic constrained load flow considering integration of wind power generation and electric vehicles[J].IEEE Transactions on Power Systems,2009,24(4)：1808-1817.

New Continuous Action-set Learning Automation

Liu Xiao, Mao Ning

(Xi'an Aeronautics Computing Technique Research Institute，AVIC，Xi'an，710065，China)

Learning automaton (LA) is an adaptive decision maker that learns to choose the optimal action from a set of allowable actions through repeated interactions with a random environment. In most of the traditional LA, the action set is always taken to be finite. Hence, for continuous parameter learning problems, the action space needs to be discretized, and the accuracy of the solutions depends on the level of the discretization. A new continuous action-set learning automaton (CALA)is proposed. The action set of the automaton is a variable interval, and actions are selected according to a uniform distribution over this interval. The end-points of the interval are updated using the binary feedback signal from the environment. Simulation results with a multi-modal learning problem experiment demonstrate the superiority of the new algorithm over three existing CALA algorithms.

machine learning; reinforcement learning; online learning;learning automata; continuous action-set learning automata

2014-06-05；

2014-06-30

TP181；TP202.7；O234

A

劉曉(1965-)，男，高級(jí)工程師，研究方向：進(jìn)化計(jì)算、學(xué)習(xí)自動(dòng)機(jī)，E-mail：xiao.liu@163.com。

毛寧(1983-)，男，高級(jí)工程師，研究方向：計(jì)算機(jī)應(yīng)用，E-mail:vikermao@163.com。