基于改進(jìn)型遺傳算法的強(qiáng)化學(xué)習(xí)特征選擇方法

張坤 姚媛 蔡宇

（1.海軍大連艦艇學(xué)院 遼寧省大連市 116000 2.63751 部隊(duì) 陜西省西安市 710038）

（3.31455 部隊(duì) 遼寧省沈陽(yáng)市 110000）

1 引言

近年來(lái)，強(qiáng)化學(xué)習(xí)算法正廣泛應(yīng)用在電力分配、網(wǎng)絡(luò)通信、機(jī)器人控制領(lǐng)域，其基本原理是通過(guò)智能體與環(huán)境不斷的交互產(chǎn)生評(píng)價(jià)性的反饋信號(hào)，并利用反饋信號(hào)不斷改善智能體的策略，最終使智能體能夠自主學(xué)習(xí)到適應(yīng)環(huán)境的最優(yōu)策略[1-4]，在與環(huán)境的互動(dòng)過(guò)程中，選擇何種特征作為模型輸入是一個(gè)關(guān)鍵問(wèn)題，特征選擇不當(dāng)不僅會(huì)導(dǎo)致算法性能下降，在實(shí)際問(wèn)題中，也會(huì)導(dǎo)致更多的成本。無(wú)用的特征反而會(huì)干擾算法判斷，因此必須非常慎重地選擇狀態(tài)特征。

目前，對(duì)于特征選擇方面的研究主要包括三類(lèi)：基于特征子集評(píng)價(jià)策略的特征選擇算法[5-6]、基于搜索策略的特征選擇算法[7-9]、基于不同監(jiān)督信息的特征選擇方法[10-12]。其中基于搜索策略的特征選擇算法分為全局最優(yōu)搜索策略、隨機(jī)搜索策略以及序列搜索策略的特征選擇算法。由于強(qiáng)化學(xué)習(xí)算法特征之間具有非線性關(guān)系，而且適應(yīng)度函數(shù)計(jì)算耗時(shí)長(zhǎng)，因此本文使用能兼顧效果和效率的基于隨機(jī)搜索策略的特征選擇方法。

2 基本思路

本文提出一種基于改進(jìn)型遺傳算法，使用PPO 算法作為適應(yīng)度函數(shù)的特征選擇方法，其中染色體為各特征的序列串，使用改進(jìn)型遺傳算法在特征空間進(jìn)行搜索，將當(dāng)前個(gè)體的特征作為PPO 算法的輸入特征與環(huán)境進(jìn)行互動(dòng)，進(jìn)而得出當(dāng)前個(gè)體綜合得分作為適應(yīng)度值。由于強(qiáng)化學(xué)習(xí)算法訓(xùn)練時(shí)間較長(zhǎng)，因此為了加速特征的選擇，需要提前截?cái)嘤?xùn)練過(guò)程，同時(shí)保證對(duì)特征有效性進(jìn)行一定程度的選擇，綜合以上因此，設(shè)計(jì)了本文算法，偽代碼如下：

算法1 本文算法偽代碼輸入：17 種特征f1,f2,…f17超參數(shù)：種群數(shù)量 N最大迭代次數(shù) T交叉概率 Pc 突變概率 Pm

輸出：最優(yōu)染色體序列 C 1 Q1 初始化，數(shù)量為N 2 使用適應(yīng)度函數(shù)F 對(duì)Q1 進(jìn)行評(píng)價(jià)，得到F(Q1,1)2 循環(huán) t=2，3，…T 3 根據(jù)適應(yīng)度選擇父代染色體4 根據(jù)Pc 交叉染色體5 根據(jù)Pm 突變?nèi)旧w6 更新種群7 使用F 對(duì)Qt 進(jìn)行評(píng)價(jià)，得到F(Qt,t)8 對(duì)每個(gè)染色體的適應(yīng)度進(jìn)行標(biāo)記9 結(jié)束10 返回 最優(yōu)染色體序列 C

F(Q,t)為采用PPO 算法的適應(yīng)度評(píng)價(jià)函數(shù)，本文使用種群迭代次數(shù)t 作為PPO 算法訓(xùn)練的次數(shù)，具體流程如下：

算法2 評(píng)價(jià)函數(shù)偽代碼輸入：染色體序列 Q種群迭代次數(shù)t超參數(shù)：minibatch size M actor number N hori：染色zon H輸出體序列適應(yīng)度F(Q,t)1 初始化模型參數(shù) θ;3 循環(huán) iteration=1，2，…t 4 循環(huán) actor=1，2，…N 5 使用參數(shù)θ 與環(huán)境交互H 次6 計(jì)算Advantage 的估計(jì) ，…，7 結(jié)束8 從NH 個(gè)樣本中，選擇M 次樣本，其中M ≤NH，對(duì)θ進(jìn)行更新9 θold ←θ 10 結(jié)束11 使用訓(xùn)練好的θ 和Q 進(jìn)行測(cè)試，并返回適應(yīng)度值F(Q,t)

本文主要完成以下工作：

（1）針對(duì)自回避行走問(wèn)題中的尋路任務(wù)設(shè)計(jì)了17 種特征，包含感知特征、方位特征、狀態(tài)特征、時(shí)間序列特征等。

（2）針對(duì)強(qiáng)化學(xué)習(xí)模型收斂速度慢的缺點(diǎn)，改進(jìn)了遺傳算法適應(yīng)度函數(shù)，添加了準(zhǔn)確和效率的平衡參數(shù)，加快了訓(xùn)練速度。

（3）通過(guò)將遺傳算法應(yīng)用在強(qiáng)化學(xué)習(xí)特征選擇任務(wù)中，在不降低算法效果的基礎(chǔ)上，將17 種特征縮減為5 種特征，減少了70.59%的特征數(shù)量，適應(yīng)度提高了23.98%。

3 具體方法

3.1 場(chǎng)景構(gòu)建

自回避行走（self-avoiding walk，簡(jiǎn)稱(chēng)SAW）指在一些格點(diǎn)內(nèi)行走的路徑，它們不重復(fù)經(jīng)過(guò)任何一個(gè)點(diǎn)。本文使用貪吃蛇游戲作為算法運(yùn)行場(chǎng)景，該游戲是自回避行走的一個(gè)特例，游戲過(guò)程中由agent 控制一條蛇的移動(dòng)方向，并試圖通過(guò)到達(dá)隨機(jī)出現(xiàn)的目標(biāo)點(diǎn)來(lái)增加自己的長(zhǎng)度，同時(shí)使游戲變得越來(lái)越困難。游戲結(jié)束方式有3 種分別為蛇撞到自己或屏幕邊界、距離上一次到達(dá)目標(biāo)點(diǎn)超過(guò)25 步或者蛇身填充滿屏幕。

3.2 特征工程

本文使用5*5 格子的貪吃蛇游戲環(huán)境，初始條件下蛇的長(zhǎng)度為1，每次到達(dá)目標(biāo)位置后蛇的長(zhǎng)度增加1，并隨機(jī)生成下一個(gè)目標(biāo)點(diǎn)的位置。在一輪游戲當(dāng)中，有效元素包括蛇頭、蛇身、蛇尾、目標(biāo)點(diǎn)、空白點(diǎn)、邊界6 種。在不考慮元素相關(guān)性條件下，特征空間為65*5，因此如何有效的表示這6 種元素是本文討論的重點(diǎn)。本文共設(shè)計(jì)了17 種狀態(tài)特征，下面分別進(jìn)行描述。

3.2.1 感知特征

感知特征表征環(huán)境的態(tài)勢(shì)，有2 個(gè)分別為3 方向元素特征和8 方向元素特征。3 方向元素特征指以蛇頭為中心探測(cè)前、左、右一格距離內(nèi)是否為自身或者邊界，如果有為1，沒(méi)有為0，長(zhǎng)度為3，如圖1(a)所示。

8 方向元素特征指以蛇頭為中心，分別探測(cè)前、左前，左、左后，后，右后，右，右前8 個(gè)方向直線上是否有邊界、蛇身或蛇尾、目標(biāo)點(diǎn)，其值為1/N，其中N 為距離元素的距離，沒(méi)有元素值為0，長(zhǎng)度為24，如圖1(b)所示。

3.2.2 方位特征

方位特征表征目標(biāo)或者蛇尾的方位，共5 個(gè)分別為目標(biāo)方位、蛇尾方位、目標(biāo)角度、目標(biāo)相對(duì)方位、目標(biāo)絕對(duì)方位。目標(biāo)方位特征檢測(cè)目標(biāo)點(diǎn)相對(duì)于頭部的位置，以頭部為中心，分為4 個(gè)象限和2 條坐標(biāo)軸共6 個(gè)位置，使用onehot 編碼，長(zhǎng)度為6。蛇尾方位與目標(biāo)方位類(lèi)似，只不過(guò)檢測(cè)蛇尾相對(duì)于蛇頭的位置，其余一致。目標(biāo)角度檢測(cè)目標(biāo)相對(duì)蛇頭的角度，公式為：R/360，其中R 為目標(biāo)角度，特征長(zhǎng)度為1，如圖1(c)。

圖1：特征示意圖1

3.2.3 狀態(tài)特征

狀態(tài)特征表征agent 自身的狀態(tài)，共3 個(gè)分別為自身方向、填充度、上步動(dòng)作。自身方向特征使用1 維向量表示，檢測(cè)頭部方向，分為上下左右四個(gè)方向，使用onehot 編碼，長(zhǎng)度為4，如圖1(d)。

3.2.4 標(biāo)量時(shí)間序列特征

該特征將當(dāng)前態(tài)勢(shì)特征S0和上一步態(tài)勢(shì)特征S-1疊加后生成新的特征，一同輸入給下一步計(jì)算，對(duì)于向量特征，將S-1直接添加在S0的尾部，特征尺寸為原特征的2 倍。

3.2.5 S0矩陣特征

該類(lèi)特征用矩陣的方式以蛇頭作為中心描述S0時(shí)刻的態(tài)勢(shì)，分為灰度特征、RGB 特征，6 層分解特征。灰度特征將蛇頭、蛇身、蛇尾、目標(biāo)點(diǎn)、空白點(diǎn)和邊界表示在一個(gè)值為0 至1 的一維實(shí)數(shù)矩陣上，其中蛇頭、蛇身、蛇尾值為0.7，目標(biāo)點(diǎn)值為1，邊界值為0.4，其余值為0，可以配合動(dòng)態(tài)中心使用，特征尺寸為(sizex*sizey*1)，如圖2(a)(b)所示。

圖2：特征示意圖2

RGB 特征將6 種元素表示在一個(gè)值為0 至1 的三維實(shí)數(shù)矩陣上，其中不同部位使用不同的矩陣值，特征尺寸為(sizex*sizey*3)，如圖2(c)(d)所示。

6 層分解特征將蛇頭、蛇身、蛇尾、目標(biāo)點(diǎn)和邊界表示在一個(gè)值為0 至1 的六維實(shí)數(shù)矩陣上，其中不同部位使用不同的矩陣值，保證在不同部位保持描繪在不同層上，如圖3所示。

圖3：特征示意圖3

3.2.6 S-1矩陣特征

該類(lèi)特征用矩陣的方式以蛇頭作為中心描述S-1時(shí)刻的態(tài)勢(shì)，同樣分為灰度特征、RGB 特征，6 層分解特征3 類(lèi)，其余與S0矩陣特征一致。

3.3 遺傳算法的改進(jìn)

在本文使用的硬件環(huán)境下，使用PPO 算法進(jìn)行10000輪訓(xùn)練需要約30 分鐘，則按照每次種群數(shù)量為20 計(jì)算，每代計(jì)算需要10 小時(shí)，如果進(jìn)行20 輪計(jì)算，需要200 小時(shí)，這顯然是無(wú)法接受的，因此針對(duì)強(qiáng)化學(xué)習(xí)算法收斂速度慢和縮減特征的目標(biāo)，設(shè)計(jì)了如下適應(yīng)度函數(shù)：

其中Nc(αt)表示當(dāng)前參數(shù)C 進(jìn)行αt 次訓(xùn)練獲得的平均抵達(dá)次數(shù)，Mc表示當(dāng)前參數(shù)C 的特征數(shù)量，這樣可以保證訓(xùn)練前期更快的獲得評(píng)價(jià)結(jié)果，后期獲得更準(zhǔn)確的評(píng)價(jià)結(jié)果。根據(jù)任務(wù)本身的難度，調(diào)節(jié)β 參數(shù)，從而對(duì)特征數(shù)量和算法表現(xiàn)進(jìn)行平衡，獲得適應(yīng)當(dāng)前任務(wù)的算法參數(shù)。本文α 設(shè)置為12.5，β 設(shè)置為0.5。

本文染色體編碼長(zhǎng)度為17，對(duì)應(yīng)于是否使用17 個(gè)特征，形如[0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1]，如果對(duì)應(yīng)位為1，則使用特征，如果對(duì)應(yīng)位為0，則相應(yīng)特征位置輸入全0，這樣可以保證PPO 算法使用的網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定，排除因網(wǎng)絡(luò)結(jié)構(gòu)引起的性能變化。

4 結(jié)果分析

本文共進(jìn)行了20 輪改進(jìn)型遺傳算法的訓(xùn)練，初始染色體為[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]，最優(yōu)染色體為[1,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0]，具體的特征為（8 方向元素特征，3方向元素特征，目標(biāo)角度，S0時(shí)刻RGB 特征，S0時(shí)刻6 層分解特征），每輪的最優(yōu)適應(yīng)度曲線如圖4所示，每輪的特征數(shù)量如圖5所示。

圖4：最優(yōu)適應(yīng)度曲線

圖5：特征數(shù)量曲線

經(jīng)過(guò)20 輪訓(xùn)練后，得到可能的最優(yōu)個(gè)體后，進(jìn)行20000輪訓(xùn)練，并與使用全部特征的個(gè)體進(jìn)行對(duì)比，訓(xùn)練結(jié)果如圖6所示。

圖6：最優(yōu)染色體對(duì)比曲線

觀察可知，最優(yōu)染色體每輪平均抵達(dá)次數(shù)為23.25425，使用全部特征的染色體每輪平均抵達(dá)次數(shù)為23.5964，優(yōu)化過(guò)的染色比原版染色體有1.47%的性能差距，這可以理解為算法的性能誤差，但使用的特征數(shù)量減少了70.59%，最優(yōu)染色體適應(yīng)度為29.25425，比初始染色體適應(yīng)度提高了23.98%。

5 結(jié)語(yǔ)

本文提出了一種基于改進(jìn)型遺傳算法的強(qiáng)化算法特征選擇方法，將自回避行走中的尋路任務(wù)作為測(cè)試環(huán)境，設(shè)計(jì)了17 種特征，經(jīng)過(guò)試驗(yàn)后發(fā)現(xiàn)，本文方法能夠有效縮減特征數(shù)量，同時(shí)不降低算法性能，是一種行之有效的方法。但觀察最優(yōu)值可以發(fā)現(xiàn)，5 個(gè)最優(yōu)特征有一定相關(guān)性，可能是一個(gè)局部最優(yōu)值，下一步將繼續(xù)研究如何利用特征相關(guān)性進(jìn)一步提升算法表現(xiàn)。