劉 星，張文娟，廖帥元

（1.國網(wǎng)湖南省電力有限公司 信息通信分公司，長沙 410007；2.長沙凱鈿軟件有限公司，長沙 410000）

0 引言

任務(wù)分配的主要研究方法可分為兩種：固定分配方法和綜合評估方法。固定分配方法：按要求設(shè)置好每個(gè)任務(wù)的執(zhí)行用戶。該方法存在一定缺陷，即不能隨著系統(tǒng)和實(shí)際任務(wù)的變化而靈活設(shè)置任務(wù)的執(zhí)行用戶。綜合評估方法：通過考慮各方面因素，綜合評估每個(gè)時(shí)刻可能發(fā)生的不同情況和影響因子（如負(fù)載、工作能力水平等），以此進(jìn)行任務(wù)分配。財(cái)務(wù)機(jī)器人采用綜合評估的思想，以工作任務(wù)進(jìn)度自動(dòng)計(jì)算規(guī)則作為深度策略梯度方法的重要依據(jù)，得到最大的總獎(jiǎng)賞。

近年來，深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)研究熱點(diǎn)，應(yīng)用廣泛。深度學(xué)習(xí)側(cè)重對事物的感知，強(qiáng)化學(xué)習(xí)更側(cè)重解決問題，因此采用深度學(xué)習(xí)算法以及自定義策略梯度優(yōu)化任務(wù)執(zhí)行路徑，為任務(wù)分配提供新的思路，從而找到全局最優(yōu)解。

1 任務(wù)分配數(shù)學(xué)模型

1.1 問題描述

目前輸配電成本監(jiān)審日常工作仍舊采用人工方式進(jìn)行工作安排、電話溝通、紙質(zhì)傳遞和報(bào)送等工作，缺少對整體工作計(jì)劃的有效管理手段，工作范圍上存在遺漏缺少情況，工作進(jìn)度上無法及時(shí)準(zhǔn)確地把控和監(jiān)管，工作過程中信息傳遞和溝通不暢通，部門工作配合方面步伐不一致，工作的組織和開展零散、效率不高，工作成果的質(zhì)量低，亟待建設(shè)相應(yīng)的信息化項(xiàng)目來滿足實(shí)際成本監(jiān)審和監(jiān)管的工作需要，做到工作事前有計(jì)劃、事中有監(jiān)管（進(jìn)度和質(zhì)量）、事后有評價(jià)，提升精益管理水平。

在財(cái)務(wù)機(jī)器人工作分配中通常包括人工分配任務(wù)以及自動(dòng)分配任務(wù)。在任務(wù)分配過程中，由于系統(tǒng)缺少對用戶工作經(jīng)驗(yàn)、用戶任務(wù)完成度的評估，而引起任務(wù)分配不均衡。這種情況通常會(huì)降低工作效率。因此任務(wù)均衡分配極其重要。

1.2 任務(wù)分配的主要因素

在財(cái)務(wù)機(jī)器人中，任務(wù)和用戶及其任務(wù)完成情況是任務(wù)分配的核心影響因素。由于每個(gè)任務(wù)和用戶都存在不同的屬性值，因此在財(cái)務(wù)機(jī)器人工作任務(wù)分配問題中，依據(jù)主要的工作任務(wù)進(jìn)度自動(dòng)計(jì)算規(guī)則判定該用戶是否是最合理的任務(wù)執(zhí)行者。

工作任務(wù)進(jìn)度自動(dòng)計(jì)算規(guī)則是由開發(fā)者根據(jù)以往的工作經(jīng)驗(yàn)，合理得到的一組判定任務(wù)完成進(jìn)度的算法。進(jìn)度自動(dòng)計(jì)算結(jié)果=A*B*C,其中B 和C 支持自定義。其中A 表示任務(wù)提交次數(shù)，如表1；B 表示任務(wù)收集狀態(tài)，如表2；C 表示任務(wù)審核狀態(tài)，如表3。

表1 提交次數(shù)

表2 收集狀態(tài)

表3 審核狀態(tài)

為了提高財(cái)務(wù)機(jī)器人的工作效率，達(dá)到最高點(diǎn)，需構(gòu)造工作任務(wù)進(jìn)度自動(dòng)計(jì)算規(guī)則，讓任務(wù)分配均衡達(dá)到最好，因此構(gòu)造任務(wù)分配總體達(dá)到最優(yōu)目標(biāo)函數(shù)是必要的。

2 算法分析

深度強(qiáng)化學(xué)習(xí)（Deep Reinforcement Learning，DRL）是人工智能領(lǐng)域新的研究熱點(diǎn)，DRL 是由具有感知能力的深度學(xué)習(xí)（Deep Learning，DL）和具有決策能力的強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）相結(jié)合產(chǎn)生的。DL 的基本思想是通過多層的網(wǎng)絡(luò)結(jié)構(gòu)和非線性變換，組合底層特征，形成抽象的、易于區(qū)分的高層表示，已發(fā)現(xiàn)數(shù)據(jù)的分布式特征表示。RL 的基本思想是通過最大化智能體（Agent）從環(huán)境中獲得的累計(jì)獎(jiǎng)賞值，以學(xué)習(xí)到完成目標(biāo)的最優(yōu)策略。其中DQN 作為經(jīng)典算法之一，它用一個(gè)深度網(wǎng)絡(luò)代表價(jià)值函數(shù)，依據(jù)強(qiáng)化學(xué)習(xí)中的Q－Learning，為深度網(wǎng)絡(luò)提供目標(biāo)值，對網(wǎng)絡(luò)不斷更新直至收斂。由于DQN 是基于Q－Learning，如果輸出DQN 的Q 值，可能會(huì)發(fā)現(xiàn)，Q 值非常大，這時(shí)QLearning 預(yù)測目標(biāo)值的時(shí)候可能出現(xiàn)overestimate，對于這一類問題，我們可采用DDQN 解決。

本文采用DQN 算法、DDQN 和輪詢調(diào)度三種算法，其中DQN 和DDQN 融合了強(qiáng)化學(xué)習(xí)的Q－Learning和深度神經(jīng)網(wǎng)絡(luò)，本文將探索哪一種算法能更快地求取合理的任務(wù)分配。

2.1 DQN 算法

DQN 包含狀態(tài)（state）、行動(dòng)（action）和獎(jiǎng)勵(lì)（reward）三個(gè)要素。reward 值靜態(tài)描述了各個(gè)狀態(tài)之間轉(zhuǎn)移的立即獎(jiǎng)勵(lì)值，行動(dòng)則決定狀態(tài)之間的轉(zhuǎn)移規(guī)則。QLearning 迭代時(shí)采用立即獎(jiǎng)勵(lì)值、Q 值函數(shù)和折扣率共同組成評價(jià)函數(shù)，Q 值表中保存各狀態(tài)行動(dòng)對（s，a）的估計(jì)值。Q－Learning 算法在給定策略h（x）下，在狀態(tài)S采取行動(dòng)A的評價(jià)函數(shù)為：

式中：α∈（0，1）為學(xué)習(xí)步長；γ∈（0，1］為折扣率，決定agent 以多大權(quán)重考慮未來獎(jiǎng)勵(lì)；t 為時(shí)間步；R為在采取當(dāng)前（S，A）的立即獎(jiǎng)勵(lì)；max 函數(shù)表示算法會(huì)根據(jù)下一個(gè)（S，A）中預(yù)測值的最大值來評價(jià)（S，A）；式中R＋γ max Q（S，a）－Q（S，A）定義為時(shí)間差分誤差（TD error），算法通過TD error 對估計(jì)值遞增更新直到收斂，行動(dòng)選擇常采用ε－greedy 策略。將agent從開始狀態(tài)轉(zhuǎn)移到目標(biāo)狀態(tài)整個(gè)過程稱為一次情景（epsiode），在episode 中每次狀態(tài)轉(zhuǎn)移的時(shí)刻稱為一個(gè)時(shí)間步（time step）。

Deep Q－Learning 算法流程如下：

（1）首先初始化“樣本集”（Memory D），簡稱D，它的容量為N，初始化Q 網(wǎng)絡(luò)，隨機(jī)生成權(quán)重ω，初始化target Q 網(wǎng)絡(luò)，權(quán)重為ω-=ω，循環(huán)遍歷episode=1，2，…，M：初始化initial state S1；

（2）循環(huán)遍歷step=1，2，…，T：用∈-greedy 策略生成action at（以∈概率選擇一個(gè)隨機(jī)的action，或選擇at=maxaQ（S，a；ω））；

（3）執(zhí)行action at，接收reward rt 及新的state S＋1；

（4）將transition 樣本（S，a，r，S）存入D 中；

（5）從D 中隨機(jī)抽取一個(gè)minibatch 的transitions（S，a，r，S）；

（6）如果j＋1 步是terminal 的話，令y=r；否則，令y=r＋γ maxa′Q（S，a′；ω-）；

（7）對（y-Q（S，a；ω））2 關(guān)于ω 使用梯度下降法進(jìn)行更新；

（8）每隔C steps 更新target Q 網(wǎng)絡(luò)，ω-=ω。

（9）輸出原始問題的最優(yōu)策略h*（x）為在各狀態(tài)下貪婪地選擇Q 值最大的行動(dòng)。

2.2 DDQN 算法

DDQN 網(wǎng)絡(luò)結(jié)構(gòu)和DQN 一樣，也有一樣的兩個(gè)Q網(wǎng)絡(luò)結(jié)構(gòu)。在DQN 的基礎(chǔ)上，通過解耦目標(biāo)Q 值動(dòng)作的選擇和目標(biāo)Q 值的計(jì)算這兩步，來消除過度估計(jì)的問題。在DDQN 這里，不是直接在目標(biāo)Q 網(wǎng)絡(luò)里面找各個(gè)動(dòng)作中最大Q 值，而是先在當(dāng)前Q 網(wǎng)絡(luò)中先找出最大Q 值對應(yīng)的動(dòng)作，即

然后利用這個(gè)選擇出來的動(dòng)作amax（S，w）在目標(biāo)網(wǎng)絡(luò)里面去計(jì)算目標(biāo)Q 值。即：

綜合起來寫就是：

DDQN 算法流程如下：

（1）隨機(jī)初始化所有的狀態(tài)和動(dòng)作對應(yīng)的價(jià)值Q，且隨機(jī)初始化當(dāng)前Q 網(wǎng)絡(luò)的所有參數(shù)w，初始化目標(biāo)Q 網(wǎng)絡(luò)Q′的參數(shù)w′=w。清空經(jīng)驗(yàn)回放集合D。

（2）進(jìn)行迭代。

1）初始化S 為當(dāng)前狀態(tài)序列的第一個(gè)狀態(tài)，拿到其特征向量φ（S）；

2）在Q 網(wǎng)絡(luò)中使用φ（S）作為輸入，得到Q 網(wǎng)絡(luò)的所有動(dòng)作對應(yīng)的Q 值輸出。用∈-貪婪法在當(dāng)前Q 值輸出中選擇對應(yīng)的動(dòng)作A；

4）將｛φ（S），A，R，φ（S′），is_end｝這個(gè)五元組存入經(jīng)驗(yàn)回放集合D；

5）S=S′；

6）從經(jīng)驗(yàn)回放集合D 中采樣m 個(gè)樣本｛？（S），A，R，φ（S′），is_endj｝，j=1，2，…，m，計(jì)算當(dāng)前目標(biāo)Q 值y：

7）使用均方差損失函數(shù)1／m∑j=1／m（y-Q（φ（S），A，w））2，通過神經(jīng)網(wǎng)絡(luò)的梯度反向傳播來更新Q 網(wǎng)絡(luò)的所有參數(shù)w；

8）如果T%C=1，則更新目標(biāo)Q 網(wǎng)絡(luò)參數(shù)w′=w；

9）如果S′是終止?fàn)顟B(tài)，當(dāng)前輪迭代完畢，否則轉(zhuǎn)到步驟2）。

2.3 輪詢調(diào)度算法

輪詢調(diào)度算法是簡潔的，無須記錄所有用戶任務(wù)分配情況，只需要把任務(wù)依次按順序輪流分配給用戶，當(dāng)用戶都分配了任務(wù)后，還需要繼續(xù)分配，則重新開始循環(huán)。

3 任務(wù)分配流程

（1）學(xué)習(xí)環(huán)境設(shè)計(jì)：通過和環(huán)境進(jìn)行交互，利用不確定的環(huán)境獎(jiǎng)賞來發(fā)現(xiàn)最優(yōu)行為序列。本文提出的學(xué)習(xí)環(huán)境主要根據(jù)調(diào)度方案包含工作任務(wù)進(jìn)度完成度建模，獲取當(dāng)前調(diào)度方案下完成任務(wù)所需的時(shí)間，從而對當(dāng)前調(diào)度方案針對調(diào)度目標(biāo)的優(yōu)劣進(jìn)行評估。

（2）動(dòng)作集：動(dòng)作集是為Q 學(xué)習(xí)算法的可以選擇執(zhí)行動(dòng)作的集合。本文通過工作任務(wù)自動(dòng)計(jì)算規(guī)則，充當(dāng)Q 學(xué)習(xí)算法的動(dòng)作集合。

（3）狀態(tài)變量確定和狀態(tài)空間劃分：該因素是Q 學(xué)習(xí)算法合理選擇動(dòng)作的基礎(chǔ)，為了使得算法更好地選擇工作任務(wù)自動(dòng)計(jì)算規(guī)則，實(shí)現(xiàn)優(yōu)化調(diào)度目標(biāo)，必須完成算法狀態(tài)空間的離散化和定量化。

（4）懲罰函數(shù)：懲罰函數(shù)的設(shè)計(jì)目的在于對算法每次動(dòng)作執(zhí)行后的優(yōu)化效果進(jìn)行獎(jiǎng)懲。對于優(yōu)化的動(dòng)作，進(jìn)行獎(jiǎng)勵(lì)，使得該動(dòng)作具有較大的選取概率；對于不優(yōu)的動(dòng)作，進(jìn)行懲罰，減小該動(dòng)作的選取概率。

（5）算法流程：根據(jù)上述Q 學(xué)習(xí)算法相關(guān)定義，最后確定算法的流程。

算法實(shí)現(xiàn)步驟如圖1 所示。

圖1 優(yōu)化算法實(shí)現(xiàn)步驟

4 仿真校驗(yàn)

為了驗(yàn)證上述方法的均衡性以及工作效率，選擇本文提出的DQN 算法、DDQN 算法和輪詢調(diào)度方法進(jìn)行實(shí)驗(yàn)對比分析。

4.1 用戶所獲得各類任務(wù)比例

三種方法的用戶所獲得的類別任務(wù)比例分別如圖2、圖3、圖4 所示。從圖2 可以看出，對于不同的任務(wù)，4個(gè)實(shí)驗(yàn)用戶分配到的任務(wù)數(shù)量基本一致，并沒有按照用戶完成任務(wù)的效率合理分配任務(wù)；從圖3 可以看出，根據(jù)不同的任務(wù)類型，4 個(gè)實(shí)驗(yàn)用戶分配到的任務(wù)數(shù)量完全不一樣，可以推斷出DQN 算法可以給用戶合理地分配任務(wù)；從圖4 可以看出，DDQN 與DQN 任務(wù)分配占比相似，可推斷DDQN 算法可用于任務(wù)分配問題。用戶對于該任務(wù)完成度越高，被分配的任務(wù)量也就越多，并且隨著其他一些任務(wù)或用戶屬性的影響，任務(wù)量與工作進(jìn)度之間的關(guān)系還可以產(chǎn)生動(dòng)態(tài)變化，說明深度強(qiáng)化學(xué)習(xí)算法可以有效的按照工作進(jìn)度合理分配任務(wù)。

圖2 輪詢調(diào)度法

圖3 DQN 算法

圖4 DDQN 算法

4.2 深度強(qiáng)化學(xué)習(xí)訓(xùn)練結(jié)果分析

因?yàn)镈QN 和DDQN 算法區(qū)別在于Q－target 的計(jì)算，所以兩者神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)一樣，結(jié)構(gòu)圖如圖5 所示。其中target_net 與eval_net 采用相同的網(wǎng)絡(luò)架構(gòu)和不同的參數(shù)。

圖5 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖

采用DQN 算法得到的損失結(jié)果展示如圖6 所示。采用DDQN 算法得到的損失結(jié)果展示如圖7 所示。由圖可知隨著訓(xùn)練步長的增加，損失值在不斷減小，表明該函數(shù)更加趨近于最優(yōu)解。

圖6 DQN 函數(shù)損失圖

圖7 DDQN 函數(shù)損失圖

5 結(jié)論

本文通過系統(tǒng)地分析任務(wù)分配問題的特點(diǎn)，提出了財(cái)務(wù)機(jī)器人任務(wù)分配問題的數(shù)學(xué)描述，采用深度強(qiáng)化學(xué)習(xí)算法（DQN、DDQN）解決任務(wù)均衡分配問題。這兩種方法收斂速度快，可以有效地處理連續(xù)動(dòng)作集的問題，彌補(bǔ)了后者初期解決速度慢的缺點(diǎn)。實(shí)驗(yàn)結(jié)果表明，該方法適用于財(cái)務(wù)機(jī)器人，在性能上優(yōu)于傳統(tǒng)的任務(wù)分配方法（輪詢調(diào)度法）。