強化學習A3C算法在電梯調度中的建模及應用

劉 宇，張 聰，李 濤

(1.武漢大學 計算機學院，湖北 武漢 430000；2. 武漢輕工大學 數學與計算機學院， 湖北 武漢 430000；3.國網湖北省電力有限公司荊州供電公司 發展策劃部，湖北 荊州 434000)

0 引 言

樓宇電梯調度[1]是一個復雜的過程，調度算法的設計復雜性一般取決于調度環境的復雜性，當調度電梯數量越多樓宇樓層越高時，從眾多調度策略中選擇最優調度策略這本質上類似一個NP完全問題。當前隨著認知智能技術的發展，探索更加智能的調度算法，讓調度算法更具多環境適應性、調度高效性和低能耗性成為新的研究熱點。

目前電梯調度算法往往基于特定需求方面進行建模，例如基于最短等待時間的算法(先來先服務算法、掃描算法和LOOK算法等)，這類算法往往以滿足各樓層用戶需求為目的，但在多梯復雜環境下建模往往困難且缺乏適應性，特別是在人流高峰階段的復雜環境之下，整個電梯群控效率較低[1]。同時基于算法進行最優解搜索也是研究點之一，如劉桂雄等通過引入統計方法提出了以節能優先的電梯調度算法[2]，仲惠琳根據客流量變化同時引入啟發式算法提出了基于神經網絡的電梯調度重規劃算法[3]，郎曼等基于現有算法控制參數多和計算較復雜特性提出了采用人工蜂群算法的電梯群控系統[4]。劉清等針對傳統的電梯群控系統的問題，提出一種模糊控制結合神經網絡算法的電梯群控系統來進行優化調度[5]。劉劍等提出了基于Fast R-CNN的多轎廂電梯調度算法[6]。

電梯調度算法設計需要考慮用戶體驗、電梯能耗和空載情況等多個目標，上述文獻的調度算法往往基于特定環境建模，存在很難平衡多個調度目標的問題。因此，本文提出了基于A3C的電梯調度算法，利用強化學習自主智能學習的優點，讓調度算法在電梯和環境地不斷交互中學習得到使調度目標收益最大化的調度策略[7]。同時對調度環境、電梯行為和調度目標3個方面進行統一建模，這極大方便模型在新調度環境和新目標下的低成本部署。本文基于開源LiftSim電梯調度仿真環境[8]進行了相關實驗，實驗結果表明A3C算法運用于群組電梯環境下進行電梯調度具有建模便捷、多環境移植適應性強、調度效率高和有效平衡多個調度目標的優勢。

1 電梯調度環境

基于強化學習的電梯調度算法建模需要將不同的電梯調度環境歸納為統一的表達形式。近年來相關研究者針對電梯調度環境進行研究，開發了眾多的電梯運行環境實例[8,9]，電梯調度環境可用圖1進行表示。本文將電梯調度環境分為樓宇環境和電梯環境，樓宇環境主要反映樓宇基本信息和樓宇各樓層用戶乘梯需求信息，其中樓宇信息包括樓層和電梯橋箱數等信息，電梯調度同一時間內乘梯需求主要包含上下行需求和用戶所在樓層。樓宇環境作為電梯調度算法需要考慮的主要環境，是當前調度算法的主要考慮因素。電梯環境主要指具體電梯橋箱內環境，這往往包括電梯橋箱內用戶的意圖樓層、載重量、橋箱所在樓層和橋箱開關門情況等信息。

圖1 電梯調度環境

高層樓宇的發展讓電梯調度算法面對的調度環境越來越復雜多樣[10]，越來越多的樓宇具備更高樓層的同時也具備了更多的電梯數量，同時不同樓層不同時段的人流往往呈現較大波動。將電梯調度環境以樓宇環境和電梯環境進行表示，一方面能較完整反映瞬時電梯調度環境，另一方面為強化學習中環境狀態建模提供依據。

2 強化學習

強化學習(reinforcement learning，RL)學習方式類似人類的學習模式，通過在實踐環境中執行相應動作以期望獲得環境給予的最大獎勵值，從而依據獎勵不斷地進行試錯學習來不斷地修正自己在具體環境中的動作策略。強化學習典型學習模式如圖2所示，圖示中智能體在和環境交互過程中會根據環境狀態St選擇執行相應的動作策略At，執行動作At后環境的狀態值St會變為新的狀態St+1，同時會得到在環境St下執行動作At的獎勵Rt，然后智能體對于新的狀態St+1又會選擇執行相應的動作策略At+1，以此往復不斷地在和環境交互過程中進行學習以期獲得更多獎勵[11,12]。

圖2 強化學習框架

強化學習模式和電梯調度模式二者建模之間存在一定的相似性，基于強化學習的電梯調度算法建模中可將電梯調度環境和電梯分別視為強化學習中環境狀態(State)和智能體(Agent)，同時電梯調度目標和電梯上下行動作可視為強化學習中的獎勵函數(Reward)和動作策略(Action)。電梯調度算法中引入強化學習方法，讓電梯智能體在不斷地和環境交互中自主學會最優調度策略，這對目前設計電梯調度算法具有一定的實用價值。近年隨著強化學習的發展也逐漸涌現出眾多的強化學習算法[13,14]，例如DQN和MADDPG算法，探索強化學習算法在電梯調度領域的運用潛力具有一定研究意義。

3 基于強化學習A3C的電梯調度算法建模

基于強化學習的電梯調度模型通過強化學習實現電梯的自主調度策略學習，這大大減少了不同調度環境目標下的建模成本，實現了電梯的智能高效調度。本文基于強化學習A3C的電梯調度算法建模如圖3所示，圖示中首先需要對調度環境、獎勵函數和電梯動作行為3個方面進行定義并進行編碼，然后基于Actor和Critic角色構建融合網絡實現A3C算法的自主策略輸出以及模型參數更新，最后通過多線程異步訓練的方式對模型進行訓練直至收斂。

圖3 基于強化學習A3C的電梯調度算法模型框架

3.1 強化學習四元組建模

基于強化學習算法的電梯調度算法建模依賴馬爾科夫決策過程，需要對其四元組 進行定義，其分別是狀態S、動作A和獎勵值R，而狀態轉移函數f則由強化學習中深度神經網絡進行表現。實際中電梯調度環境可以視作樓宇環境和電梯自身環境兩者的組合，本文所提強化學習算法中電梯自身環境建模狀態S所需定義參數項見表1，其中針對多電梯情況，只需要將多部單電梯自身環境進行順序排列組合。強化學習運用于電梯調度算法中的智能體可視整體電梯為一個智能體，也可針對每個電梯橋箱進行多智能體建模，即每個調度電梯作為一個智能體進行強化學習建模，如強化學習中MADDPG算法就是多個智能體在同一環境下進行策略學習[15]。

復雜環境下電梯調度算法的調度目標是在提升用戶體驗的情況下，使電梯的能耗盡可能低，因此建模過程中獎勵函數的設計需要充分考慮用戶體驗和電梯能耗兩方面。本文強化學習的獎勵函數R設計如式(1)所示，式子中time表示所有乘客在一個時間周期內的等待時長總和，energy表示一個時間周期內電梯消耗的電力，person表示一個時間內放棄的人數，實驗仿真環境中默認排隊等待一定時間后自動放棄等待。式子中調節參數α、β和γ分別調節各自比例，本文α、β和γ調節因子取值分別為0、0.01和100

R=α×time+β×energy+γ×person

(1)

表1 電梯調度環境建模參數項

電梯調度算法中電梯作為智能體，需要在強化學習中定義其動作空間A，電梯實際調度過程調度動作由目標樓層和方向構成，則其動作空間A可由二元組 組成，其中DispatchTarget表示是相應電梯調度分配的目標樓層，DispatchTargetDirection表電梯抵達目標樓層后的后繼方向，1表向上運行，-1表向下運行，0則為無方向[8]。

3.2 貝葉斯優化下A3C算法建模

強化學習A3C算法來源于Actor-Critic算法，經典A3C算法基于Actor-Critic算法在網絡結構、Critic評估點和異步訓練框架3個方面進行了優化，這一定程度上克服了Actor-Critic算法收斂性問題[16]。但在實際建模訓練過程中很多時候依然存在收斂慢和調參困難的問題，基于A3C算法依然存在性能提升的可能性，本文基于經典A3C算法引入貝葉斯優化算法對超參數進行學習，同時借鑒著名算法Alpha Zero中使用的融合網絡結構設計Actor和Critic網絡結構對整個A3C算法進行建模。

A3C是Actor-Critic算法的改進升級，Actor-Critic算法[16]是一種策略(Policy Based)和價值(Value Based)相結合的強化學習方法。如圖3所示A3C算法建模主體亦包括演員(Actor)和評論家(Critic)兩部分，A3C算法中Actor負責生成動作和環境進行交互，Critic則對Actor的行動進行評估，指導Actor的動作。Actor網絡輸入環境狀態S，輸出為當前環境下的動作策略π(S)， Critic網絡輸入環境的狀態S，輸出為對狀態S的評估值v(S)， v(S) 表示狀態下S的平均期望價值[17]。A3C算法中采用優勢函數(動作價值函數和狀態價值函數的差值)作為Critic評估標準，同時結合N步采樣加速收斂，A3C中優勢函數表達式如式(2)所示，式中A(S,t) 是優勢函數，其表當前狀態S的價值，γ是衰減因子

A(S,t)=Rt+γRt+1+…γn-1Rt+n-1+γnv(S′)-v(S)

(2)

Critic網絡的評估值直接作用于Actor網絡的參數更新，由于策略函數損失函數中加入了策略的熵項，Actor網絡參數θ更新公式如式(3)所示

(3)

A3C算法中Critic網絡則通過計算TD誤差值δ，使用均方差作為損失函數對自身網絡參數w進行參數更新，相關計算式如式(4)所示

δ=R+γv(S′)-v(S)loss=∑(R+γv(S′)-v(S,w))2

(4)

強化學習中超參數的設置對于結果收斂性起到一定程度的作用，A3C算法建模過程中需要設置部分的參數項，例如需要設置全局共享迭代輪數T、相應網絡參數更新步長、熵系數值和衰減因子等，本文為了A3C算法性能有效提升引入經典貝葉斯優化方法對部分超參數進行搜尋，貝葉斯優化作為最受歡迎的方法，其充分利用相關歷史信息來指導進行最優解的搜索。貝葉斯優化中假設待優化參數為X=(x1,x2,…,xn)， 同時存在一個與X相關的損失函數f(x)，貝葉斯優化目標函數即是尋找X得到最小損失函數f(x)。本文基于A3C算法的電梯調度算法建模中采用Hyperopt工具來實現貝葉斯優化算法。

A3C算法中Actor網絡和Critic網絡一般針對實際任務可采取融合網絡和分離網絡兩種網絡形式，本文基于強化學習A3C算法的電梯調度算法建模中Actor網絡和Critic網絡采用融合網絡，融合網絡即是讓Actor網絡和Critic網絡為同一個神經網絡，融合網絡的輸入狀態為S，輸出為狀態的價值V和對應的策略，強化學習著名算法Alpha Zero中也使用融合網絡結構[18]。

3.3 多線程異步訓練

A3C算法相比較Actor-Critic算法更容易收斂，同時A3C強化學習算法借用DQN經驗回放的技巧，利用多線程訓練的方法。本文A3C算法多線程異步訓練部署框架如圖4所示，訓練過程中多個線程分別和環境進行交互學習，同時將結果匯總保存到一個全局線程中進行智能體學習和參數更新，而各個線程智能體則定期從全局線程獲取參數指導后面和環境的交互。通過多線程交互A3C算法避免了經驗回放相關性強的問題，同時多線程訓練能夠確保電梯智能體能在最短時間學習得到最優調度策略。

圖4 A3C算法多線程訓練部署框架

4 實驗仿真及結果分析

為了充分驗證強化學習A3C算法運用于樓宇電梯調度的可行性，本文進行了相關的仿真實驗，實驗環境基于百度飛槳和百度 AI Studio平臺進行，實驗GPU采用英偉達Tesla V100。電梯仿真環境采用LiftSim進行，LiftSim是一款類似gym的仿真環境[8]，同時基于LiftSim開源代碼能夠方便進行環境的自定義。本文通過在單電梯環境和多電梯復雜環境下對強化學習A3C調度算法和部分常用的傳統電梯調度算法進行了對比實驗，同時在多電梯且具有分時人流的復雜環境下引入多種強化學習算法和A3C算法進行對比實驗。

4.1 單梯環境下電梯調度

單電梯調度環境下假設整棟樓宇只存在一部電梯，為了驗證在單電梯調度環境下強化學習A3C算法和傳統調度算法的有效性，本文基于LiftSim進行了仿真實驗，傳統調度算法中選用FCFS、SCAN、SCAN-EDF和LOOK算法作為對比算法。其中FCFS算法是一種先來先服務算法，它根據用戶樓層的請求電梯先后次序進行依次調度。SCAN算法即掃描算法，是一種按照樓層順序依次服務請求，它讓電梯在最底層至最高層之間往返運行。SCAN-EDF算法是一種實時調度算法，結合了調度算法SCAN和EDF的優勢，SCAN-EDF首先按照EDF算法選擇請求隊列中下一個服務對象，而對于相同時限的請求，則按照SCAN算法選擇下一個服務對象。LOOK算法調度電梯在最底層和最頂層之間運行，當電梯前進方向未有用戶請求時則立即改變運行方向運行。

本實驗設計強化學習A3C算法和傳統算法得分評價標準為對10層大樓的4小時人流進行調度，綜合得分計算公式如式(3)所示，所得得分值為負，分值越大代表電梯能耗和用戶等待時長越短，電梯調度效率越高。調度環境大樓人流產生是一個均勻隨機過程，與時間無關。強化學習A3C算法超參數學習率設置為0.001，訓練線程數設置25線程，A3C訓練過程每一萬次迭代進行評測一次。整個A3C算法訓練過程情況如圖5所示，圖示為A3C算法60萬次迭代訓練過程圖。

圖5 單梯環境A3C算法訓練過程

由圖5強化學習A3C算法在不斷地和環境進行交互過程中，可以明顯看出A3C算法獲得的獎勵值逐漸增加，調度綜合得分逐漸增大這說明電梯的能耗和人員等待時間逐漸降低，智能體逐步學到了最優調度策略。圖5中大約在50萬次迭代后得分達到-22分左右，大約60萬次迭代后得分達到-21分左右。利用收斂后的算法和傳統相關算法進行對比實驗，對比實驗調度得分如圖6所示，圖示中A3C_50算法采用約50萬次迭代訓練后的模型，A3C_60算法采用約60萬次迭代后的模型。

圖6 單梯環境下各調度算法性能對比

由圖6可知A3C強化學習算法60萬次迭代后調度效果最好達到-21.06分，調度效果超過其它傳統電梯調度算法，傳統調度算法中SCAN-EDF算法具有較好調度效率，最終得分為-21.88分。A3C算法50萬次迭代后調度得分-22.36分，相比較SCAN-EDF算法存在不足。在單電梯環境中A3C調度算法隨著迭代數上升相比較傳統算法存在一定優勢，但迭代數的增加一定程度上也將消耗一定的GPU資源。綜合來說單電梯環境中傳統調度算法具備一定的運用價值，但強化學習A3C算法在一定的迭代訓練之后相比較傳統調度算法也存在一定優勢。

4.2 多梯復雜環境下電梯調度

多梯復雜環境下電梯調度算法建模更加復雜，需要考慮調度電梯的運行情況和其它電梯的調度情況，而強化學習中，通過在多電梯環境下增加環境狀態S維度就容易達到算法建模的要求。為了驗證本文所提調度算法的有效性，本文針對A3C算法和傳統SCAN-EDF算法進行了對比實驗，基于SCAN-EDF算法在多部電梯情況之下采用最近派遣法則，即電梯距離需求樓層最近則派遣此電梯。同時本文為了驗證不同強化學習算法的性能，引入了調度算法DDQN和MADDPG進行了相關對比實驗，DDQN是經典的強化學習算法[19]，而MADDPG則是DDPG算法運用于多智能體的升級版算法。對比實驗是在固定4小時時長情況下對大樓4部電梯進行聯合調度，同時設定4小時人流分布呈現一定非隨機性，在初期1小時左右引入早高峰上行，在后期3小時左右引入晚高峰下行，通過引入早晚高峰上下行人流可以模擬當前高層樓宇寫字樓的調度環境。

由圖7可知在模型訓練初期MADDPG算法能夠比較好的到達分值區間(-50,-60)，但是隨后在訓練過程中MADDPG卻沒有表現出更高的分值區間，相反針對DDQN算法和A3C算法在訓練初期階段其得分情況波動較大，大約在60萬次訓練之后A3C算法表現出了綜合得分逐步上升的趨勢，最終抵達得分區間大約為(-30,-35)，而DDQN算法則達到了得分區間(-45,-55)，這說明A3C算法運用多梯電梯調度環境具有一定的優勢。同時本實驗待強化學習模型訓練較收斂后和傳統調度算法SCAN-EDF算法進行了對比實驗，最終實驗調度得分情況如圖8所示。

圖7 多梯復雜環境下強化學習算法訓練過程

圖8 多梯復雜環境下各調度算法性能對比

由圖8各調度算法調度綜合得分可知，在復雜多電梯環境下由于傳統電梯調度算法建模困難，很難做到用戶體驗和電梯能耗的平衡，而強化學習算法中建模相對簡單，由于長時間的模型訓練讓模型逐漸從和環境的交互過程中學習得到了最佳的調度策略，這說明強化學習運用于復雜環境下電梯調度算法具有可行性，同時對比相關強化學習算法調度分值發現其中A3C算法運用于電梯電梯調度具有一定的優勢，更容易收斂。

5 結束語

本文基于強化學習A3C算法構建電梯調度算法，通過對調度環境、電梯行為和調度目標3個方面進行統一建模，讓電梯在不斷地和調度環境進行交互過程中學習最優調度策略，一方面克服了傳統調度算法的建模復雜性，讓調度算法在新環境下的也能方便移植，另一方面利用強化學習設計滿足用戶需求和能耗的獎勵函數能有效平衡用戶體驗和電梯能耗等多方面調度目標。通過進行單電梯和多電梯復雜環境下電梯調度對比實驗，實驗結果表明強化學習A3C算法經過一定迭代次數的訓練之后相比較傳統調度算法具有一定的優勢，能有效平衡用戶用梯和電梯節能需求。同時本文通過對比A3C、DDQN和MADDPG強化學習算法運用于復雜環境電梯調度中的效果，實驗結果表明A3C算法具有更好的調度性能，更易收斂。本文所提基于強化學習的調度方法同時也在國網湖北省電力公司科技項目的湖北電網運營監控實用化關鍵技術研究項目中有進行相關研究，強化學習在諸多調度領域存在運用可能。在以后的進一步研究中，可以結合強化學習和相關深度學習方法進行電梯調度的建模和算法優化，讓電梯調度模型更快收斂。