第2期 连传强，等：面向资源分配问题的Q-CF多智能体强化学习算法 ·97 规则为 时候，定义为low,反之定义为high,那么一个计算节 Q(s,a)+Q(s,a)+a[r+yQ-Q(s,a)]. 点的资源状态可用(low,low)、(low,hi冲)、(high, (2) low)、(high,high)中的一种来表示.因此，定义s= 式中：0=∑p(s'1s,a)∑aπ(s',a)Q(s',a'),T (n1,2,n3,n4),其中n1表示一个簇中节点状态为 (s',a)为在s'状态下执行a'动作的概率.a∈(0,1) (low,low)的数量，n2表示(low,high)的数量，n3表示 为学习率，y∈(0,1)为折算因子，r为在s状态下执 (high,low)的数量，n4表示(high,high)的数量. 行a动作的立即回报 动作空间a:a=(actionl,action2),其中actionl 在状态s上的最优动作a为 表示选取的任务类型，action2表示为选取的任务分 π*(s)=arg max Q(s,a) 配到哪一种类型的节点.例如a=(3,4),表示将第 Hu和Wellman将单智能体的Q-学习算法推广 3种任务类型的任务分配到状态为(hig,high)的节 到了多智能体系统[.在他们的算法中，假设一个 点.如果任务中有多个相同的任务类型，将优先选取 智能体可以感知其他智能体的行动和从环境中得到 效用率高的任务。 的回报，所有智能体的Q值表都被保存.在假设有2 状态转移矩阵p:通过实验可以实现对状态转 个智能体的系统中，当智能体在状态s选择动作 移矩阵p的估计. (a1,a2)到达状态s'时，智能体得到回报(r1,r2),Q 回报函数：如果相应的任务完成了，r=u,其中 值表通过下式进行更新： 4为任务的效用率；反之，r=0. Q(s,a1,a2)←-(1-x)Q.(s,a1,a2)+ 定义好(S,A,P,)之后，就可以利用Q值更新 air;+yvi(s'). 规则(1)以及搜索策略(e-greedy)进行Q-学习： 式中：V(s)是智能体i在双矩阵决策〈A1,A2, e(s,a;).T T(s,a:）= Q1(S),Q2(S)〉的平衡点 ∑，e(s,4)/4 式中：e、r均为大于0的常量. 2Q-C多智能体强化学习算法 本地策略的分布式Q-学习算法流程为 QCF学习算法是一个异步的强化学习算法，即 对簇i每个s,a初始化表项Q:(s,a)为0，t时刻 通过Q学习算法和C℉学习算法相结合实现异步学 簇i的状态为s,等待本地分配的任务数为n; 习，其中利用Q学习算法来学习任务的本地分配策 循环（循环次数为n): 略，而通过CF学习算法来学习任务的传递对象选 1)利用&greedy方法选择1个动作a并执行它； 择策略。 2)接收到立即回报r； 2.1本地策略的分布式Q-学习算法 3)观察新状态s'; 每个簇均独立地使用Q学习算法学习任务在 4)对Q:(s,a)按照式(3)进行更新； 本地的分配策略.当一个簇接收到一定数量的任务 5)s←-s; 时，如何根据簇的资源状态合理地分配这些任务使 6)若r=0,则将该任务放入等待传递队列，否 得平均效用率最大，这是学习的目的.首先定义集合 则移除该任务； (S,A,p,r). 结束 状态空间S:为了便于对比，采用了文献[1]中的 2.2智能体之间任务传递策略的CF学习算法 问题模型，原问题模型有2种资源，即cpu资源和net- CF学习算法学习的是本地未分配的任务该如 work资源，将每种资源按照数量的多少分成n个层 何选择传递对象，以便让其他簇完成该任务.它的学 次，再将每个节点各资源的层次联合起来，便成为描 习算法思想来源于K臂赌博机问题，对(S,A,P, 述这个节点的资源状态，n越大，对节点状态的描述 )中的各项定义如下： 能力就越强，但同时状态空间也急剧变大，严重影响 状态空间s:状态只有1个，那就是k个簇。 了Q学习的效果.因此在这里每种资源只分为2个 动作空间a:a=(G,),表示将任务类型为的 层次，设定一个阈值，比如60，当资源低于这个阈值的 任务传递给编号为i的簇