基于q-学习的合同网适应性协商机制研究

基于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.