基于q-學習的合同網適應性協商機制研究

0研究設計與文獻綜述長期以來，生產計劃優化一直是組合優化和生產操作領域的重點和難點。傳統集中式調度方法往往難以適應動態、復雜的柔性作業車間環境。近年來,基于Agent(Holon)等概念實體和人工智能技術的分布式調度方法得到了廣泛研究。這類方法是在物理或功能實體Agent(Holon)化的基礎上,以自治與協商機制為核心,具有優于集中式調度方法的一系列潛在特點,如響應性、局部化和適應性等。但這些潛在優點的實現離不開有效協商機制的運用。協商機制是一組用來組織和約束Agent之間對話序列和決策的規則集,是實現局部行為和整體系統全局目標之間一致性的關鍵。現有的面向生產調度控制領域的協商機制,包括基于蟻群系統的“stigmergic”協商機制、合同網協商機制(ContractNetProtocal,CNP)、基于拍賣的協商機制等。根據Caridi和Cavalieri以及Shen等對基于Agent調度的綜述研究,現有的協商機制中,合同網機制最為常用。傳統的合同網機制通常包括任務招標、投標、標書評估和任務簽訂四個基本過程。一般認為,CPN具有對較大規模任務的“分而治之”能力、較好的開放性以及動態分配和自然平衡能力。但是,傳統的合同網機制仍存在兩方面的缺陷:①僅僅規定單一的工作過程,本身沒有優化能力和動態學習能力;②當系統中Agent數量較大時,合同網協議過程中的招投標通信將大幅增加系統的網絡通信負荷。因此,圍繞這兩點的研究成為分布式人工智能和分布式生產調度的研究熱點。相應地,現有的研究主要集中于:①利用機器學習算法減少協議通信負荷,如Deshpande等提出了集成k-近鄰算法與合同網協議的協商機制,并用于虛擬分布式醫院系統的資源共享調度;②利用各種機器學習算法(尤其是強化學習算法)提高協商機制的目標優化和動態學習能力,如Csaji等提出了基于時間差分學習算法TD(λ)以提高Agent的學習能力,從而在協商過程中得到更好的投標者。Wang和Usher運用強化學習中的Q-學習結合CNP機制解決動態單機調度問題的調度規則動態優化選擇問題,基于類似的思路,他們同時探討了作業車間(JobShop)環境下的動態作業路徑優化問題。目前而言,利用強化學習和合同網協商機制解決柔性作業車間環境下的調度和控制問題還未見報道。因此,本文在文獻和文獻的啟發和先前工作的基礎上,深入探討了集成Q-學習和CNP機制的分布式柔性作業車間環境下(每個單元內是柔性JobShop調度問題(flexibleJobShopschedulingproblem))作業動態分配優化問題。相比文獻和文獻,本文的研究擴展了集成機制的應用場景,給出了具有針對性的集成機制的策略決策過程和學習過程,并在目標函數值、狀態確定準則、獎懲函數設計和搜索策略等方面進行了有針對性的設計和改進。1反應時間柔性作業單元動態作業分配問題描述如下:假設作業根據一定的隨機分布進入柔性作業車間。柔性作業車間包括多個制造單元。由于存在操作柔性、序列柔性和加工柔性,每個新進入的作業可由一個或多個可選制造單元加工。假設每個單元內有一緩沖區可用于存放已分配的作業。一旦被分配到某一單元,作業將根據特定的加工序列在該單元內加工,直到完成為止。由于具有加工柔性,作業在每個單元內都形成柔性JobShop調度問題,可以運用特定的調度規則或啟發式算法來確定作業在選定單元內的加工路徑和序列。假設整個系統的主要制造成本是與加工時間關聯的成本。整體系統目標是確定如何分配新進入的作業,以優化一個或多個系統目標。為解決該問題,需要解決兩階段決策問題(如圖1):決定作業在可選單元上的分配和確定作業在選定單元內的加工路徑。本文集中在第一階段決策。由于單元內的路徑選擇不是本文的決策重點,先來先服務(First-in-First-out,FIFO)和最短加工時間(ShortestProcessingTime,SPT)規則用作第二階段決策規則,即單元將首先從其緩沖區內選擇最早分配進入該單元的作業,并將作業的每道工序分配給可加工該工序且加工時間最小的機床。作為第一階段決策的目標函數,本文考慮完成作業的平均延誤時間,即min(F=Ν∑j=1EΤijΝ)?i=1,2,?,nCell。(1)式中:ETij=max[0,ECij-EDj]表示作業j在單元i的延誤時間;ECij為作業j選擇待加工單元i后,利用FIFO和SPT組合規則調度得到的完成時間;EDj=rj+f×ETPT,其中rj為作業的到達時間,f為松弛因子,決定作業交貨期的松緊程度,ETPT=avg(nCell∑i=1EPij),EPij為作業j在單元i上的平均加工時間總和。為說明ETPT的計算過程,假設1個車間內有3個單元CELL1,CELL2和CELL3,一作業j可由CELL1和CELL2加工。CELL1和CELL2分別由4臺和3臺機床組成,如作業在CELL1上加工,完成該作業的所有加工工序數為3,在CELL2上加工的所有工序數為4。對應的加工時間分別為表1和表2。CELL1上的總體平均時間為EP1=7+13+9=29,CELL2上的總體平均時間為EP2=3+7+15+9=34,ETPT=(EP1+EP2)/2=31.5。2保持動作akQ-學習算法是一種典型的與模型無關的強化學習方法,最早由Watkins在1989年提出,是一種基于有限狀態離散馬爾可夫決策過程(MarkovDecisionProcess,MDP)的遞增式動態規劃算法,是一種認為在不確定環境中能夠達到較好效果的控制方法。Q-學習算法迭代時采用狀態—動作對的獎懲和Qπ(sk,ak)作為估計函數,在每一次學習迭代時都需要考察每一動作,以確保學習過程收斂。Q-學習算法的基本方程為:Qπ(sk,ak)=rk(π(sk))+γ∑sk+1∈SΡsksk+1(ak)Vπ(sk+1),(2)Vπ(sk+1)=maxbQπ(sk+1,b)。(3)式中:rk(π(sk))為策略π下,在當前狀態sk(sk∈S),Agent采取動作ak(ak∈A)獲得的即時報酬;sk+1(sk+1∈S)為在當前狀態sk和當前動作ak下系統轉入的下一狀態;Psksk+1(ak)為在當前狀態sk和當前動作ak下系統轉入下一狀態sk+1的概率;γ是折扣率,0≤γ≤1,影響未來獎懲的當前值;b為下一狀態sk+1下可采取的動作;Qπ(sk,ak)為Agent在當前狀態sk和當前動作ak下得到的總計期望獎懲,也稱狀態—動作對值。Q-學習算法的思想是不去估計環境模型,而是直接優化學習狀態-動作對值Qπ(sk,ak)。應用Q-學習算法所求得的Q值已經被證實收斂于最優的狀態-動作對值Q*,Q*值代表Agent試圖學習的最優策略。Q-學習算法的標準過程如下:步驟1任意初始化Q(sk,ak)值函數。步驟2觀察獲得當前狀態sk。步驟3根據特定的搜索策略(如ε貪婪算法),選擇對應當前狀態sk的合適動作ak。步驟4執行動作ak,獲得獎懲值rk,并觀察得到下一個狀態sk+1。步驟5根據Q-學習規則,更新狀態-動作對值:Q(sk,ak)=Q(sk,ak)+α[rk+γmaxbQ(sk+1,b)-Q(sk,ak)]。步驟6更新狀態,即令sk=sk+1。步驟7轉步驟3,直到狀態sk表示一最終狀態(或穩定狀態)。步驟8將步驟2～步驟7重復執行既定的次數(稱為學習周期)。學習率α可為常數,也可隨著迭代步數的增加而逐漸減小。采用常數的學習率,盡管不能確保Q值完全收斂,但能根據最常接收到的獎懲值而有規律地變化,這種情況更適合動態調度環境。折扣率γ越接近0,Agent越不考慮未來獎懲,更趨于接收即時獎懲;反之,越接近1,Agent越具有遠見,能減少即時獎懲對學習策略的影響。在沒有先驗知識的前提下,Q(sk,ak)值函數一般初始化為相同值。算法步驟3的搜索策略用來平衡“探索(Exploration)”和“利用(Exploitation)”。“探索”使系統嘗試未做過的動作,使其有得到更多回報的機會;而在“利用”過程中,系統更傾向于采取先前受到獎勵的動作。“利用”可以在一次動作過程中保證得到好的期望獎勵,“探索”則從長遠角度為系統提供更多機會找到總的最大獎勵值。盡管Q-學習算法中必須解決“探索”和“利用”之間的平衡,但是具體的“探索”策略不會影響算法的收斂性。因此,Q-學習算法是最常用和最有效的與模型無關的算法。3合同網絡與q-學習單元任務的動態協調分配機制cnp-ql3.1q-學習算法的生成為了描述提出的合同網Q-學習協商機制(表示為CNP-QL),用統一建模語言(UnifiedModelingLanguage,UML)序列圖描述其協商過程,如圖2所示,基本交互過程發生在產品(任務)Agent和單元Agent之間。交互過程以基本合同網協議為藍本,內嵌Q-學習算法,以充分利用歷史協商記錄。CNP-QL的基本流程描述如下:(1)作業一進入柔性作業車間,生成關聯的作業Agent,并通過初始化獲取調度需要的相關信息,包括工藝計劃、可加工的替換單元(或在不同單元上的柔性路徑)、加工時間等。(2)根據加工特征,作業Agentj分為多個具有序列約束的任務{Task1,Task2,…,Taskj},每一任務可在一個或多個單元內{Cj1,Cj2,…,Cjk}加工完成。任務在其緊前任務結束時即刻向所有可加工該任務的可選單元Agent發出任務公告CFP(callforproposal),并傳送相關加工信息。(3)單元Agent接收到CFP后,估計任務的預定性能指標(如延誤性能)。為了估計預定性能指標,單元需要利用規則從緩沖區內選擇下一加工任務,根據一定規則從任務在單元上的柔性路徑中確定一加工路徑,并以性能指標或其他信息(如單元的加工負載)等決定是否做出投標。這一步與Q-學習算法的狀態確定準則密切相關。(4)收集到投標后,根據系統Q-學習算法定義的策略表,任務對各投標進行策略評估,并根據搜索策略從可選單元中選擇加工單元,把作業發送到選中單元的緩沖區內。(5)分配單元根據預定規則計算該任務在單元內加工的完成時間,以此完成時間為信息,根據Q-學習算法的獎懲函數,對作業Agent的選擇做出獎勵或懲罰。(6)更新系統Q-學習算法的策略表、更新產品的分配情況等信息。3.2任務的確定及q-學習搜索策略CNP-QL機制的策略決策過程如圖3所示。一般情況下,作業Agent將按加工特征分解為具有次序約束的加工任務集{Task1,Task2,…,Taskj}。一加工任務可由一個或多個單元組成的可替換單元集{Cj1,Cj2,…,Cjk}完成。策略決策過程主要在任務接收到各個可選單元的投標后進行評估,確定在當前狀態下最終選擇的加工單元,即解決如何確定π(s,a)的過程。狀態s的確定可考慮任務發出CFP的時刻,各可選單元內部的加工特性或任務在各單元上的加工特性,或由兩者共同決定。然后,在特定狀態下,動作a選擇單元,確定任務加工路徑。如圖3所示,任務Taskj可由三個單元Cj1,Cj2和Cj3加工,則任務在當前狀態s1下,有動作集A(s1)={a1(s1),a2(s1),a3(s1)},利用Q-學習搜索策略(本文采用變化ε的ε-貪婪法),決定加工任務的單元為Cj1。在任務Taskj加工完成時刻,利用同樣的策略決策過程決定加工后續任務Taskj+1的單元為C(j+1)2。為實現策略決策過程,需要結合Q-學習算法的協商學習迭代過程。作業(或任務)在當前狀態st選擇特定動作at(即選擇一可加工單元)后,得到獎懲值rt,同時進入下一狀態st+1,Q(st,at)值得到更新,并進行下一迭代。Q(st,at)值的動態迭代變化是搜索策略決策過程的基礎。最終目的是在確定Q-學習算法因素(包括狀態變量和劃分狀態空間、獎懲函數、搜索策略、初始Q(st,at)值函數,以及學習率α和折扣率γ等)的情況下,確定可加工單元的動態選擇以最優化既定的系統性能指標。3.3完善q-學習算法CNP-QL機制在運用學習迭代過程中需要考慮下列Q-學習算法的因素,包括:①狀態確定準則;②確定獎懲范圍的數目;③設定分割獎懲范圍的界限值;④設定獎懲量級;⑤Q初始值;⑥步長α;⑦折扣系數γ;⑧“探索”和“利用”的應用等。下面就CNP-QL機制中Q-學習算法的關鍵因素具體展開。這里假設作業的所有工序在選擇的單元內全部加工完成。(1)狀態劃分策略表該關鍵因素主要確定問題的狀態空間S,并完成狀態空間S的離散化和定量化。由于假設單元Agent具有估計每個作業在其內部加工時間的能力,類似文獻的思想,本文考慮以所有待加工工序的平均加工時間總和WIQij為狀態變量,i為單元標志(i=1,2,…,nCell,nCell為可加工單元數),j為作業標志(j=1,2,…,N,N為進入作業總數)。與文獻的不同之處在于,由于作業可在可選單元內的任何一臺機床上加工(路徑完全柔性設置),待加工工序在該單元內的預計加工時間WIQij以在各個可選機床上的加工時間的平均值計算。表3給出了一種狀態劃分策略表實例,反映在具有三個單元的柔性作業車間內,動態進入的每個作業都能在任意兩個單元內加工的動作決策中選擇。表中共有11種狀態,其中兩種狀態為虛狀態,分別表示作業進入車間之前的初始狀態和所有作業動態分配完成后的狀態。其中DIFFij表示單元CELLi與單元CELLj上的所有待加工工序平均加工時間總和之間的絕對離差與上述兩者總和均值之間的比率,可以通過下列公式決定:AWΙQij=(WΙQi+WΙQj)/2,(4)DWΙQij=|WΙQi-WΙQj|,(5)DΙFFij=DWΙQij/AWΙQij。(6)以狀態1為例說明策略表的詳細定義。假設一作業動態進入車間時,單元CELL1和CELL2都可加工該作業。如果作業進入時的WIQ1>WIQ2(即作業進入時刻,單元CELL1上所有待加工工序的平均加工時間總和大于CELL2上所有待加工工序的平均加工時間總和),DIFF12>0.1(閾值設為0.1),則對應系統狀態s=1,作業有兩種動作(a1=CELL1和a2=CELL2)。每種控制動作分別對應表中“Q值”列所描述的狀態—動作對值Q(1,1)和Q(1,2)。如果在動態分配過程中,作業根據搜索策略選擇了a1=CELL1,則對應的狀態—動作對值Q(1,1)將更新,以反映當前動作對下一階段的影響。(2)獎懲函數的選擇獎懲函數的建立通常以學習目標為指引。本文考慮估計交貨延遲時間平均值最小為學習目標,假設作業j最終選擇單元i,表4給出了范圍數目為10的獎懲函數示例。其中,作業在可選單元上的平均加工時間總和EPij作為獎懲函數范圍設置的界限值;乘子n可以根據系統的負載狀態進行調整,如當系統負載較大時,可適當提高n以區分延誤較大時的獎懲設置;range用來調整延誤時間為零時的獎勵值。(3)學習結束后至20采用ε-貪婪算法來平衡“探索”和“利用”,并在學習過程中,隨著進入作業數量的增加動態調整ε值;當學習過程結束時,ε減小到0。即設ε=(1-JinΝ)×ε0,其中ε0為初始值,Jin為進入作業數,N為用于學習的作業總數。這樣,在一定程度上可使Agent在學習早期“探索”,然后逐步轉換到“利用”型策略。編程實現時,任意產生一個0～1之間的隨機數,判斷其與ε的大小后再決定應選擇的動作。(4)q-學習開始停止準則有兩種:①當系統在所有狀態下,只有一個或幾個動作演化為主要動作時,Q-學習搜索趨于穩定,學習結束;②當學習迭代次數達到某個界限值學習結束。本文采用后一種停止方法,仿真過程中假設進入車間的作業數達到一定界限值時就結束仿真。4標準4仿真實驗仿真實驗在Matlab7.1編程環境下進行,假設條件和參數定義如下:①假設一柔性作業車間由nCell個柔性制造單元組成(本文實例設nCell=3);②每一柔性制造單元所具有的機床數nMi(i=1,2,…,nCell)服從2～4之間的離散均勻分布,即nMi～U;③進入柔性作業車間的作業之間間隔時間服從Exp(5.5)分布;④每一作業Ji(i=1,2,…,N)可在任意兩個單元內加工,作業的所有工序在可加工單元內完成;⑤每一作業在每個可加工單元內的工序數n(ji)服從離散均勻分布n(ji)～U(j=1,2,…,N,i=1,2,…,nCell);⑥作業在可選加工單元內,每道工序O(ji)k可由單元內任一機床加工,即具有完全柔性,加工時間p(ji)km(k=1,2,…,n(ji),m=1,2,…,nMi)服從下列分布:對于一道工序,首先,任選一臺機床,其在該機床上的加工時間服從離散均勻分布P～U(5,15),然后,對于該工序在其他機床上的加工時間服從U[p,min(2×p,15)],這樣從一定程度上避免了加工時間在可選機床上變動過大,從而有利于強化Q-學習要素中有關平均時間的設置。實驗測試時,設松弛因子f～U[1.2,1.8]。對同一測試問題,將CNP-QL算法與基本CNP算法進行了比較。CNP根據min(EPij)在可選單元之間分配作業,不具有學習能力。由于沒有相關的先驗知識,在每種測試組合下,所有初始的狀態—動作對值設置為0。仿真實驗一直進行到5500個作業進入車間時停止。每種參數配置下進行5次實驗,然后記錄平均值。算法參數根據文獻建議設為n=0.