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

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

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