基于q-學習的合同網(wǎng)適應性協(xié)商機制研究

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