基于約束邊長FART-Q的智能決策算法

周亞楠，龔光紅

(北京航空航天大學 自動化科學與電氣工程學院，北京100191)

隨著人工智能與機器學習技術的快速發展，智能體的應用越來越廣泛.為獲得做出適當決策所必需的知識，智能體可使用專家系統［1－2］獲得領域專家的決策知識，或通過強化學習［3］等方法學習決策知識.專家系統可將領域內權威專家的知識以特定形式保存到決策系統中形成知識庫，常見的專家系統有基于規則的專家系統和基于案例的專家系統等［4］.專家系統在處理復雜的決策問題時，往往面臨獲取和表示專家知識較困難、推理決策時間較長等問題.強化學習可通過在線學習的方式，不斷更新和完善知識庫，具有較好的適應性和智能性.智能決策可表示為從狀態(state)到動作(action)的映射［5］.由于可選的動作通常可用離散值表示，而智能體所處的狀態往往要用一組連續的變量表示，這就需要對連續量進行離散化或分類.自適應共振理論(ART)是一種無監督學習型人工神經網絡，網絡通過訓練可自動對輸入模式進行分類［6］.模糊ART將模糊理論與ART相結合，是一種可在線學習的對連續輸入進行分類的方法［5，7］.模糊 ART可在訓練獲得的知識基礎上，增量式地繼續獲取新的知識，同時不會破壞原有知識.模糊ART被用于各種分類應用中，如文檔聚類［8］、多變量化學數據分類［9］、無線傳感器網絡遺漏數據的估計［10］等.

傳統的模糊ART只將模糊相似度作為分類的依據，沒有考慮狀態變量的物理含義，在智能決策應用中存在分類不合理的問題.本文提出在模糊ART的共振條件中加入分類的邊長約束的改進，以使得分類所覆蓋的各狀態變量的范圍得到限制，分類更為合理.

將模糊 ART 與強化學習算法結合［5，11－12］可完成智能決策所需的狀態分類和學習決策規則的任務.強化學習通過與環境交互得到的反饋進行調整，以獲得更好的行為.Q學習是強化學習的一種，通過與“狀態－動作對”相關聯的Q值來調整行為.本文將改進的模糊ART與Q學習算法結合，給出了約束邊長FART－Q智能決策網絡結構.

本文對約束邊長FART－Q智能決策網絡進行了仿真實驗，驗證了改進算法的效果.

1 模糊自適應共振理論

1.1 模糊ART神經網絡

1.1.1 模糊運算與模糊子集

在模糊理論［7］中，對n維向量a和b，模糊與運算(∧)定義為

若a和b滿足

1.1.2 模糊ART分類算法

模糊ART是一種對連續數值向量進行自適應聚類的分類算法.圖1所示為模糊ART的神經網絡結構.

圖1 模糊ART網絡Fig.1 Fuzzy ART network

網絡由輸入層F1和輸出層F2組成.輸入層有L=2M個神經元，接收輸入向量:

其中，am∈［0，1］;ac是 a的補.對輸入向量采用互補編碼，可有效防止分類數激增［7］.輸出層有N個神經元，輸出分類結果.每個輸出層神經元連接有一個權值向量:

模糊ART分類算法步驟如下:

1)初始化神經網絡，N=0.向輸出層添加第1個神經元，N=1，且對所有 l=1，2，…，L，令=1.

2)輸入待分類向量I，對輸出層的每個神經元，計算選擇函數:

其中α是值很小的正常數.

3)對選擇函數最大的神經元J，驗證共振條件:

其中ρ∈［0，1］為警戒值.若滿足共振條件，進入下一步;否則將TJ置為0，重復步驟3)，直至滿足共振條件.

4)對神經元進行學習:

其中 β∈［0，1］為學習率，若 β=1則稱為快速學習.

5)輸出分類結果:

6)若J=N，則向輸出層新增加一個神經元(N:=N+1)，且對所有 l=1，2，…，L，令 wNl=1.

最后一個輸出層神經元的所有權值都為1，確保了共振條件一定能夠滿足.

可見，模糊ART網絡是依據輸入向量與權值向量間的“模糊相似度”來進行分類的.這里，模糊相似度由WJ是I的模糊子集的程度以及I是WJ的模糊子集的程度共同決定.

1.2 約束邊長的模糊ART

某些情況下，兩個模糊相似度較高的輸入向量所代表的物理含義并非相似，甚至相差很大.

在智能決策應用中，待分類的狀態向量往往是由多個物理含義不同的變量，經歸一化處理后組合而成的.例如，智能小車的目標方向需要用角度等變量描述［13］.以目標方向角φ為例，其取值范圍通常為(－π，π］.對φ進行歸一化，有

設網絡參數α =0.1，β=1，ρ=0.5，當I1輸入到全新的網絡中時，分類結果為第1類，且有

當I2輸入到網絡中時，T1≈0.619，T2≈0.488，T1＞ T2，故 J=1.又=0.65＞0.5滿足共振條件，故分類結果仍為第1類，且有

I1中，=0.1，即 φ = － 0.8π;I2中，=0.7，即 φ =0.4π.

兩種情況下，目標分別處在左后方和右前方，態勢相差甚遠.如果將這兩種態勢分為一類，會對后續的決策造成非常不利的影響.

文獻［7］指出，模糊ART網絡中的任一輸出層神經元j均滿足如下條件:

其中，Rj為神經元j所代表的分類區域為該區域所有邊長的和.

當M=2時，設輸入I=(a，ac)，相應地可將權值向量寫為 Wj=(uj，vcj)，uj，vj均為二維向量.令uj，vj分別代表二維平面中的一個點.前例中 W1=(0.1，0.5，0.3，0.4)，則 u1=(0.1，0.5)，v1=(0.7，0.6)，R1即為圖2中的長方形區域.

式(12)中W1所表示的分類1的第1個邊長，該分類覆蓋∈［0.1，0.7］的范圍.

圖2 W1所代表的分類區域Fig.2 Category area covered by W1

為解決模糊ART網絡分類邊長可能過大的問題，對原分類算法步驟3)中的共振條件進行加強，得到新的步驟3):

對選擇函數最大的神經元J，若滿足式(16)，且J＜N，則對Wj′=I∧Wj求邊長向量，定義邊長約束向量:

若對所有 m=1，2，…，M，都有

則滿足共振條件.否則將TJ置為0，重復步驟3)，直至滿足共振條件.

當∑=(1，1，…，1)時，式(16)恒成立，算法退化為傳統的模糊ART.

1.3 邊長約束的優點

邊長約束引入了如下兩方面優點:

1)如1.2節所述，能夠避免分類的某個邊長過大導致的分類不合理的問題.

2)對大量輸入進行分類時，能夠減少分類數量.由式(14)可知，模糊ART限制了分類區域的邊長總和.可定義分類區域的體積:

由平均值不等式，結合式(14)可得

2 約束邊長FART-Q智能決策網絡

智能決策問題中，通過模糊ART網絡可對智能體當前所處的態勢進行分類，獲得智能體面對環境的狀態 si，i=1，2，…，N.該狀態下相應可選擇的動作為 aj∈A={a1，a2，…，aP}，P 為可選的動作個數.對應預期的回報為 Q(si，aj)∈［0，1］.Q 值可用如下迭代方法［14－15］求得:

其中，η∈［0，1］是學習參數;ETD是時域差分值;r是執行動作 a帶來的回報;γ∈［0，1］是折扣參數;是下一狀態 s′下的最大估計回報.初始時，所有的Q值均設為0.5.

將Q學習與模糊ART結合，可用于智能決策.約束邊長FART－Q智能決策網絡如圖3所示，模糊ART網絡輸出狀態分類si，選取使得Q值最大的動作aK，即

圖3 約束邊長FART－Q智能決策網絡結構Fig.3 Structure of intelligent decision－making network with bounded FART－Q

執行選取的動作aK后，獲得新的態勢輸入I′，經模糊ART網絡分類后得到下一狀態s′.將s′和動作aK獲取的回報r反饋，則Q值按式(19)迭代更新.

約束邊長FART－Q智能決策網絡的決策步驟如下:

1)將從傳感器等渠道獲取的態勢信息進行歸一化預處理，生成分類輸入向量I.

2)將I輸入到模糊ART網絡中進行分類，得到分類結果 si，并通過學習調整模糊 ART網絡.

3)通過狀態si的動作－Q值對選取Q值最大的動作aK并執行.

4)獲得執行完aK后的態勢輸入I′，經模糊ART網絡分類后得到下一狀態s′，獲得執行aK的回報r，并將 s′和 r反饋給動作－Q值對，通過式(19)學習Q值.

3 智能決策仿真實驗

3.1 雷區導航實驗簡介

雷區導航(minefield navigation)［13］仿真實驗如圖4所示，在尺寸為16×16的正方形網格區域中，隨機放置有10個地雷，自動小車放置在一個隨機的起點上，小車的任務是一定的步數內，在不碰到障礙(地雷或雷區的邊界)的情況下，穿越雷區到達隨機選定的終點.每個回合開始前，隨機產生上述地雷、起點和終點;回合過程中，地雷和終點的位置不變;當小車到達終點(成功)或碰到障礙(失敗)，或者超過30步(超時)時，一個回合結束.

圖4 雷區導航實驗Fig.4 Minefield navigation experiment

自動小車每一步都執行“探測、移動、學習”的過程.

1)探測:車的左、左前、前、右前、右5個方向上各有一個傳感器，可以探測相應方向上障礙的距離di(i=1，2，…，5);另有一個傳感器可以感知終點的相對方向b(1×5)，b的每一維代表一個方向，如圖5所示，若終點在相應方向范圍內，則這一方向上的值為1，其他方向上值為0.

圖5 探測目標相對方向的范圍Fig.5 Destination’s direction scopes relative to the vehicle

2)移動:小車每次可以向車的左、左前、前、右前、右5個方向移動1格.

3)學習:每移動1步后，小車可獲得相應的回報r(見表1)，Q學習算法根據回報對執行的動作效果進行學習.若移動后，小車離終點更近，則r=0.8，否則r=0.2;若移動后小車到達終點，r=1.0，若碰到障礙，則r=0.

表1 每步移動后的回報Table1 Reward of each step

令 a=(d1，d2，d3，d4，d5，b1，b2，b3，b4，b5)，則可將I=(a，ac)作為模糊ART網絡的輸入，利用第2節所述的約束邊長FART－Q決策網絡進行動作決策.

3.2 實驗結果與分析

實驗運行的環境為:Intel Core2 P8400，2.26 GHz CPU;2.0 GB內存;32位Windows 7操作系統.

實驗分3組進行:第1組和第2組使用傳統的模糊 ART，即分類邊長∑=(1，1，…，1)，警戒值ρ分別為0.5和0.8;第3組使用約束邊長的模糊 ART，分類邊長∑=(0.5，0.5，…，0.5)，警戒值ρ與第2組相同.表2所示為每組實驗使用的約束邊長FART－Q決策網絡參數.

表2 實驗中使用的參數Table2 Parameters used in each test group

由于每回合都隨機生成起點、終點以及10個地雷，實驗結果有一定隨機性，故每組實驗重復進行10次，每次實驗中，小車先清空并初始化約束邊長FART－Q網絡，然后完成3000回合的雷區導航任務.

對各組10次實驗的統計數據求平均值，3組實驗的平均成功率曲線如圖6所示.

可見，初始時，由于決策網絡中均沒有知識，成功率都很低.隨著回合數增加，網絡通過不斷學習，知識越來越多，成功率也越來越高.實驗數據顯示，使用約束邊長的模糊ART的第3組實驗成功率最高，500回合時成功率就上升到85.6%，1000回合后成功率一直保持在90%以上.

各組實驗3000回合后的統計數據平均值如表3所示.

圖6 3組實驗的平均成功率比較Fig.6 Comparison of average success rate among three test groups

表3 各組實驗的統計數據平均值Table3 Mean values of statistical results from each test group

由前兩組實驗統計數據可見，在未加入模糊ART分類中的邊長約束時，ρ值大的情況下獲得的分類數明顯更多，分類更細，成功率也明顯更高;同時，更多的分類數也導致每次決策的計算時間更長.

由后兩組實驗統計數據可知，ρ值相同的情況下，加入模糊ART分類的邊長約束后，分類數減少33.5%，每次決策的計算時間減小27.7%;而同時，成功率上升了近6%.

加入分類邊長的約束使得分類更合理，決策的成功率更高，且使分類數減少，提高了決策速度.

4 結論

1)本文提出了約束邊長的模糊ART算法，并將其與Q學習結合構建了約束邊長FART－Q智能決策網絡.

2)經3組雷區導航仿真實驗驗證，該網絡可快速進行智能決策.實驗中，輸入向量維數為20(M=10)，在分類數達到120以上的情況下，每步決策平均用時為1～2 ms;

3)與傳統的模糊ART相比，約束邊長的模糊ART能夠使分類更為合理，既能提高決策的成功率，又可以減小決策的運算時間.

References)

［1］ 祝世虎，董朝陽，張金鵬，等.基于神經網絡與專家系統的智能決策支持系統［J］.電光與控制，2006，13(1):8－11.Zhu S H，Dong C Y，Zhang J P，et al.An intelligent decision－making system based on neural networks and expert system［J］.Electronics Optics and Control，2006，13(1):8－11(in Chinese).

［2］ 魏強，周德云.基于專家系統的無人戰斗機智能決策系統［J］.火力與指揮控制，2007，32(2):5－7.Wei Q，Zhou D Y.Research on UCAV’s intelligent decisionmaking system based on expert system［J］.Fire Control and Command Control，2007，32(2):5－7(in Chinese).

［3］ 馬耀飛，龔光紅，彭曉源.基于強化學習的航空兵認知行為模型［J］.北京航空航天大學學報，2010，36(4):379－383.Ma Y F，Gong G H，Peng X Y.Cognition behavior model for air combat based on reinforcement learning［J］.Journal of Beijing University of Aeronautics and Astronautics，2010，36(4):379－383(in Chinese).

［4］ 楊興，朱大奇，桑慶兵.專家系統研究現狀與展望［J］.計算機應用研究，2007，24(5):4－9.Yang X，Zhu D Q，Sang Q B.Research and prospect of expert system［J］.Application Research of Computers，2007，24(5):4－9(in Chinese).

［5］ Ueda H，Naraki T，Hanada N，et al.Fuzzy Q－learning with the modified fuzzy ART neural network［J］.Web Intelligence and A－gent Systems，2007，5(3):331－341.

［6］ 彭小萍.自適應共振理論原理與應用研究［D］.北京:北京化工大學，2012.Peng X P.The study on adaptive resonance theory principles and applications［D］.Beijing:Beijing University of Chemical Technology，2012(in Chinese).

［7］ Carpenter G A，Grossberg S，Rosen D B.Fuzzy ART:fast stable learning and categorization of analog patterns by an adaptive resonance system［J］.Neural Networks，1991，4(6):759－771.

［8］ Hsieh S，Su C L，Liaw J.Fuzzy ART for the document clustering by using evolutionary computation［J］.WSEAS Transactions on Computers，2010，9(9):1032－1041.

［9］ Song X H，Hopke P K，Bruns M A，et al.A fuzzy adaptive resonance theory－supervised predictive mapping neural network applied to the classification of multivariate chemical data［J］.Chemometrics and Intelligent Laboratory Systems，1998，41(2):161－170.

［10］ Li Y Y，Parker L E.Classification with missing data in a wireless sensor network［C］//Southeastcon，2008.Piscataway，NJ:IEEE，2008:533－538.

［11］ Ediriweera D D，Marshall I W.Advances in computational algorithms and data analysis［M］.Netherlands:Springer，2009:293－304.

［12］ Araujo R.Prune－able fuzzy ART neural architecture for robot map learning and navigation in dynamic environments［J］.Neural Networks，IEEE Transactions on Neural Networks，2006，17(5):1235－1249.

［13］ Tan A H.FALCON:a fusion architecture for learning，cognition and navigation［C］//2004 IEEE International Joint Conference on Neural Networks.Piscataway，NJ:IEEE，2004，4:3297－3302.

［14］ Teng T H，Tan A H.Knowledge－based exploration for reinforcement learning in self－organizing neural networks［C］//Proceedings of the 2012 IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technology，Volume 02.Washington，D C:IEEE Computer Society，2012:332－339.

［15］ Teng T H，Tan A H，Teow L N.Adaptive computer－generated forces for simulator－based training［J］.Expert Systems with Applications，2013，40(18):7341－7353.