合作博弈调度

合作博弈调度（精选4篇）

合作博弈调度 篇1

随着B2B商业网络的日渐成熟,全球供应链网络日渐复杂,供应链中各利益方之间竞争与合作的机会并存。举例而言,在电子设备行业中,常常可以看到多个生产商将某些特定的生产工序,外包给同一个第三方代工商的情况,如苹果、三星等电子品牌同代工商富士康之间的关系。基于该行业中信息的高效传递性及高度共享性,这些生产商与第三方代工商之间可以通过设定合作机制,从而使实现生产调度的全局优化成为可能。

在过去四十年中,产生了一些很有趣的关于生产调度计划中的合作博弈问题的思考和研究。这类研究被称作调度博弈问题,是生产调度问题和合作博弈理论的交叉研究,主要涉及两个方面:1)解决生产调度排序的优化问题,通过优化排序,实现成本节约;2)使用合作博弈理论,寻找成本节约的均衡分配,研究所有参与者之间的合作机制设计。

调度博弈问题最早由I. Curiel等人[1]在1989 年提出,他们给出了标准调度博弈模型,即单一机器环境下,待加工工序不存在约束条件,使用加权完成时间作为目标函数的调度模型,他们证明了此类调度博弈为凸博弈,因而存在均衡解。之后的研究,主要通过增加对工序的约束条件,改变工序及生产商之间的对应关系,增加机器的数量等方式,对调度博弈模型进行了复杂。如P.Borm等人[2]研究了在工序具有工期(due dates)的约束条件下,针对三种不同的目标函数:加权罚金约束(weighted penalty criteri-on),加权滞后和(weighted tardiness criterion)以及完工时间(completion time criterion),证明了该模型下均衡解的存在性。从1989 年以来所有关于调度博弈,核仁分配以及合作博弈凸性问题的研究可以在I.Curiel,H.Hamer,F.Klijn等人[3]撰写的文献综述中找到。然而,涉及每个生产商拥有多个待加工工序的研究相对有限,P.Calleja等人[4]研究了单一机器环境下,每个参与者有多个待加工工序,每个工序有多个受益方的调度博弈问题,并证明了在一定条件下均衡解的存在。近年来,X.Cai和G.Vairaktarakis[5]及T.Aydinliyim和G.Vairaktarakis[6]研究了考虑外包的调度博弈问题,研究模型中每个生产商可以拥有多个代加工工序。

本文的模型在以下两个方面区别于T.Aydinliyim等人的研究:1) 是给出了一个更接近生产实际的合作调度博弈的生产计划模型,其中第三方代工商的可用生产能力被表示为一些不连续的具有有限生产能力的生产窗口;2)使用了复合目标函数,我们在目标成本函数中,除加权流水时间外,还考虑了生产窗口的预订成本,并且本文中的预订成本函数不具有随时间单调递减的线性约束,而是使用分段函数,模拟普通工时和加班工时的预订成本。

一、研究问题描述

本文研究的生产调度模型主要关注供应链中,生产商与第三方代工商之间的外包流程。一组生产商,将某些同质性的待加工工序外包给同一个第三方代工商。每一个生产商根据先到先服务(FCFS)的原则,使自身的目标成本函数最小化,独立地预定第三方代工商的生产能力。第三方代工商在接到所有生产商的待加工订单和预订安排后,将所有待加工工序打乱,以整体目标成本函数最小化为目标,重新优化,给出最优化排序和生产窗口预订方案,实现成本结余。在这一重新优化的过程中,一些生产商的个体利益得到了优化,而另一些生产商的个体利益受到了损害。因此,需要设定相应的促进合作实现的收益分配机制,将整体优化获得的成本结余,按照一定的规则,分配给所有对整体优化有贡献的生产商,以促使整体优化的实现。

本文的研究模型将给出一个基于博弈的合作机制。因为所有的生产商依照先到先服务的原则独立地预订第三方代工商的生产能力,从而会产生以下两种效率损失的情况:1) 每个生产商预订的最后一个生产窗口可能存在空闲时间(idle time),在这种情况下,所有生产商产生的空闲时间的总和很有可能会超过一个完整的生产窗口的长度;2)由于依照先到先服务的原则,某些后到的生产商因为较早的生产窗口都已经被预订,则不得不将一些优先级较高的工序排在较晚的时间生产,这将会带来在制品库存成本的增加。以上两点潜在的效率损失,可以通过设计合作机制,从而实现整体最优排序,以带来整条供应链的效率优化。

除此之外,第三方代工商自身也可以从这一合作机制中受益。例如,一些之前被预订的生产窗口因为整体优化排序而空闲下来。第三方代工商则可以保留一部分的重新空闲窗口的预订成本,将剩下的部分以预订退款(booking refunds)的形式退还给生产商。此外,第三方代工商还可以通过将这些重新空闲的窗口再次预订出去而获得额外的收益。我们将会在本文模型中考虑预订退款的情况,而将可能存在的重新预订成本作为第三方代工商的潜在收益,不列入计算。

二、模型设计

参数表示如下:

生厂商m对应的待加工工序集合为Nm,其中|Nm|≥1,即每个生厂商有多个待加工工序。每道工序Jj的作业时间为pj,相应的单位在制品库存成本为Wj。模型假设整个生产计划期的长度为T个工作日,每个工作日中有两个可预订的生产窗口:W2k-1为普通工时窗口,W2k为加班工时生产窗口。工作日之间存在相同长度的停工时段G。每个窗口的预订成本hk因时段的性质不同而对应两个不同的值,第三方代工商会在T0时刻将报价信息告知所有的生产商M:

下图表示了本文的生产窗口模型:

生产商按照先到先服务的原则预订窗口,令 σ0m表示生产商m的所有待加工工序的初始最优化排序,Wσ0m表示生产商m依据该排序 σ0m和自身的目标函数最优化而预订的生产窗口集合。生产商m的最优化目标即最小化总成本TC(σ0m),是加权流水时间 和总预订成本 的加和。本文模型基于立即装运协议(immediate shipments),即每道工序一旦完工就会被立即装配发货,所以工序Jj的在制品库存成本可以被表示为 因而,生产商m所面临的目标成本函数可以表示为:

在m个生产商都决定了加工窗口预订决策Wσ0m后,第三方代工商将对所有n个工序进行重新排序 σ*,并得到一个最优的排序以及相应的最优加工窗口组合Wσ*。排序 σ*是针对所有生产商待加工工序N的全局最优解,所以其结果不会劣于仅仅把各生产商的排序 σ01,σ02,σ03,...,σ0|M|相连接而获得的初始排序 σ0。

由于这一过程中,一些生产商的个体利益受到了损害,对于这些生产商而言,存在着通过与其他个别生产商形成小联盟而获益的可能。因而如果要想使每个生产商m都能同意按照 σ*的顺序加工工件,则必须保证每个生产商参与大联盟而获得的收益不低于它以任何形式同其他个别生产商结盟而获得的收益。因此,第三方代工商需要设计一种成本结余的分配机制,使得所有生产商只有通过大联盟合作才能获得最优收益。通常情况下,由于联合决策使得整体对独立预订时所产生的空闲时间的充分利用,我们预期在 σ*的排序下所使用的生产窗口将少于排序 σ0所使用的生产窗口。第三方代工商可以将一部分的预订成本结余 ρ 作为预订退款返还给生产商,自己保留剩下的部分,从而促使联合决策的实现。

以下是本文模型中的一些假设:模型基于信息完全透明共享的假设(即信息在所有生产商和第三方代工商之间是完全对称的)。所有的待加工工序是同质的,即工序间的转换时间不计,这一类型的工作有很多,例如测试工作,维修保养工作,装配工作等。第三方代工商在T0公布所有的可用生产窗口,所有的生产商的预订决策都是在生产计划期开始即T0时刻前完成的。生产商进行预订的先到先服务原则(FCFS)意味着后续生产商只能从未被先前生产商预订的窗口中,选择窗口进行预订。即:

上式说明,生产商m只能在未被先前m-1 个生产商预订走的窗口中进行选择。因此,在初始排序 σ0中,每个被预定的窗口中都只含有来自同一生产商的待加工工序。我们假设对每个生产商m而言,所有需要被加工的工序Nm的处理时间不会超过当前可预订窗口) 的生产能力。否则,生产商m的生产需求则不能被该第三方代工商满足,需要再寻找其他的代工商。此外,如果一道工序在生产窗口结束时还未完工,该工序可以在下一预订窗口开始后继续加工直至完成。最后,对k=1,…,2T,我们假设所有的生产窗口WK∈Γ 的可用时长均为L小时。我们将完成所有待加工工序集合N所需要的最少窗口数量记为 ω, 其中

如前所述,每个生产商,以及第三方代工商都面临着相同性质的优化问题,只是各方拥有的工序数量及可选择的生产窗口集合有所不同。因而本文将针对第三方代工商面对的集中优化问题设计优化算法,并假设各个生产商,以及个别生产商之间结成的小联盟将使用相同的算法来处理优化问题。具体而言,第三方代工商通过调度排序,将N中的所有待加工工序排列,并从 Γ 中选择一些生产窗口以使得总成本最小化。在此,我们引入批次(Batch)的概念,每个被预定的窗口,都将会被用来处理某个批次的工序。同一批次指的是在同一个生产窗口内完工的那些工序。因此,集中优化问题就被转变为两个步骤:1)将集合N中所有的待加工工序按照一定的规则分成不同批次;2) 为各个批次从集合 Γ 中寻找到最优的生产窗口。

假设 π 是单一机器环境中,所有待加工工序N的一

个排序,Fπj表示排序π中第j个工序的完工时间。我们需要把排序π划分成ω个批次,并计算出每个批次所有完工工序的总的单位在制品库存成本。具体方法如下:令ti=i·L,并定义

Bi表示第i个批次,即在排序 π 下,所有完工时间Fjπ:ti-1

此外,我们引入变量qj:qj=Fjπ-ti-1,表示工序Jj最后被加工部分时长,即工序Jj在批次Bi中所占用的加工时间。举例而言,有些工序的加工时间超过了生产窗口的长度L,因此必须被分割在多个批次中进行生产。对于这样的工序,在考虑其流程时间时,我们借助于该工序最后完工时的所在批次,参考其在完工批次中所占用的加工时间,即qj,来计算其总的完工时间。为了表示批次Bi是否使用窗口WK,我们引入另一个决策变量zik,即:

最后,我们用DK表示窗口WK的结束时间。基于这些参数设定,一个调度 σ 可以用所有待加工工序的排序 π和各加工批次选择使用的窗口集合W来表示,即 σ=σ(π,W)。从而,对所有待加工工序N和生产窗口集合 Γ寻找最优化调度方案的集中优化问题的目标函数可以用下式表达:

三、模型分析及求解:合作博弈均衡解

在预订生产窗口的过程中,某些生产商可以通过形成小联盟S(S哿M),实现优于独立决策时的排序与预订,从而减少小联盟中个体的总成本。但是这一小联盟的决策,相对于全局最优而言,可能并非效率最优的。因而在这一过程中,第三方代工商担当着制定机制以促进各方通过合作形成大联盟的职责,从而实现整条供应链上的效率最优。

(一)合作博弈的定义

我们用Cj(σ0(S)) 及Cj(σ*(S)) 分别表示在 σ0(S)和 σ*(S) 两种调度下工序Jj∈NS产生的在制品库存成本。相应的总成本表示为TC(σ0(S))及TC(σ*(S)) 。联盟S试图通过对NS中的所有工序进行重排,并在所有可选择的生产窗口集合 ΓWσ0(MS)中,挑选最优的窗口组合,以期获得最大的成本结余V(S):

其中V:2|M|→R,表示了合作博弈(M,v)的特征方程。

只有当所有的生产商都服从第三方代工商给出的最优调度的情况下,才能实现全局最优解,即 σ*或 σ*(M)。为了实现这一最优化排序,我们需要设计分配机制,将通过全局优化而实现成本结余v(M)分配出去以使得所有的生产商遵循 σ*的调度排序。即使得其在 σ*的排序下,总收益不劣于其独自决策或与其他生产商结成小联盟S奂M的情况。我们将分配给每个生产商的成本结余记为Xm:m∈M,则分配向量,X={X1,...,X|M|}需要满足以下条件,才能保证均衡解的存在[7]:

第一组约束条件确保了每个小联盟中的成员通过服从全局优化而获得的收益至少不劣于其可以在小联盟中获得的收益。第二组约束条件确保了所有因合作而带来的成本收益,都被完全分配给了参与合作的各个生产商。

此时,我们引入可以被接受的重新排序(admissiblerearrangements) 的定义,类似的定义可以在I. Curiel et al(1994)的研究中找到:

定义1:令 σ(S)表示关于工序集合NS的一个调度排序。当所有Jj∈NNS在排序 σ(S)和排序 σ0(S)下具有完全相同的前项工序时,我们则称 σ(S)是对于 σ0(S)而言可以接受的重新排序。

基于这一定义,我们对生产商之间的合作博弈行为做如下假设:

假设1:任意联盟的最优化调度排序 σ*(S),必须是对于 σ0(S)而言可以接受的重新排序。

基于假设1,我们定义相应的成本结余合作博弈(Cooperative saving games)(M,v),其中 是关于 σ0(S)而言可以接受的重新排序,则成本结余:

可以进一步被改写为:

式中第一项二重加和表示了在制品库存成本结余,式中第二项表示的是对重新空闲窗口的预订退款,式中第三项表示由于新预订了在初始排序中未预订的窗口而带来的新增预订成本。

显然,V(S):S哿M表示了在满足假设1 的条件下,联盟S中的所有成员通过合作调度所有工序NS所能得到的最大总成本结余。为了求得最优调度排序 σ*(S),其中 σ*(S)关于 σ0(S)是可以被接受的重新排序,只需求得使目标函数V(S)最大的 σ。注意到该目标函数存在以下的沉没成本

因此,优化问题可以简化为求下列函数的最小值:

(二)合作博弈的均衡解

Shapley[8]的研究证明了具有凸性的博弈问题存在非空的核仁。

定义2:满足下列条件的合作博弈问题是凸博弈:

但是,合作博弈(M,v)并不必然具有凸性。尽管如此,对于具有超加性的合作博弈,我们仍然可以寻找到均衡内核。

定义3:满足下列条件的合作博弈(M,v)具有超加性(Superadditive)

该定义表明两个不相连的联盟合作形成的更大的联盟带来的收益不会比不合作更差。在此定义的基础上,我们仍需要一个严谨的分配方案以保证合作得以实现。在下文中,我们将具体研究因结成大联盟而可能带来的三种成本结余,并在每种情况下证明超加性,从而给出一个核仁分配的原则。

(三)收益分配机制

我们将生产调度问题的目标成本函数改写为:

式中Jj表示排序 π 中第j道工序,因此我们不再需要指标函数yji,ek是对窗口k之前的停工间隙G的计数,即

Si如前文给出,是批次Bi中所有工序的单位在制品库存成本之和:

我们注意到在按照初始调度 σ0进行生产的总成本中其实包含一部分的空闲时间成本It,表示每个生产商预订的最后一个窗口Wt中的空闲时间,则按照初始调度σ0进行生产的总成本函数可以表示如下:

为了举例说明,考虑如下的例子:

例1:假设生产商1有一道待加工工序,单位在制品库存成本为W1,需要的加工处理时间p1

或,等价的:

其中两个方括号分别表示生产商1 和生产商2 各自的成本。

例1 中的两个生产商可以通过合作调度,而获得来自两方面的成本结余:1)充分利用空闲时间而带来的成本结余,2)整合所有待加工工序后更好的调度安排和窗口预订带来的结余。因此我们将所要研究的合作博弈问题分为1)和2)两类博弈进行进一步的研究,对M中的任意联盟S,我们定义:

1.vi(S)表示由空闲时间的充分利用而带来的成本结余博弈

2.vn(S)表示因对所有工序进行重新排序和生产窗口的重新分配带来的成本结余博弈

我们给出以下结论:

命题1:博弈(M,vi(S)),(M,vn(S))以及博弈(M,v)都具有超加性(Superadditive)。

基于初始预定窗口和生产商之间的对应关系,为了便于表示,我们使用窗口集合来表示相应的生产窗口联盟Wσ0(S)。令[a,b]表示窗口集合{Wa,Wa+1,Wa+2,...,Wb},则联盟Wσ0(S)可以表示为:

其中1≤a1

由[a,b]生产窗口集合中的窗口创造的成本结余由通过对空闲时间的充分利用而带来的成本结余 ωi([a,b])和由重新安排工序的加工顺序和加工窗口而来带的成本结余 ωn([a,b])共同组成。因此:

下面,我们将给出一种均衡分配规则,对0≤λ≤1,我们定义

关于该分配原则的直观解释如下:对于因空闲时间的充分利用而带来的成本结余Xim,窗口Wk对所有在其后续窗口加工的工序贡献了Ik单位的空闲时间,空闲Ik对在制品库存成本带来的贡献为 我们将这一部分结余的一半分配给拥有窗口Wk的生厂商,把剩下的一半分配给所有预订Wk窗口之后生产窗口的生产商。根据对称性,窗口Wk的拥有者也从先前生产窗口的空闲时间成本结余中分配到了一部分收益,即提早 时间开工的收益。这里需要注意,由于对空闲时间的充分利用,可能会使一些工序在更早的窗口完工,在这种情况下,其完工时间可能会减少Ik+G(或Ik因窗口Wk的性质决定,即普通窗口还是加班窗口),我们把停工时间G对总成本结余的贡献记在中。关于Xnm定义的解释如下,窗口Wk的拥有者获得的总收益,一部分(λ)来自于当其与所有前项窗口形成联盟时所产生的边际收益(除空闲时间外的净结余),另一部分(1-λ)来自于当其与所有后续窗口形成联盟时所产生的边际收益(除空闲时间外的净结余)。

此外,我们在模型设计时曾提到过的,第三方代工商会自己保留一部分因合作调度而重新空闲窗口的预订成本,即:

我们可以将这一部分收益理解为第三方代工商因向各生产商提供合作调度的平台而收取的租金。此外,如果大联盟的合作调度决策需要预定新的窗口,第三方会收取相应的预订成本 最终,我们将分配向量Xm定义为:

并且我们有以下结论:

定理1:Xnm、Xim和Xm分别是博弈(M,vi(S)),(M,vn(S))以及(M,v)博弈的一种均衡分配。

成本结余分配向量X=(X1,…,X|M|)满足均衡解的条件,即

需要注意的是,我们给出的这一分配原则,仅仅只定义了一组服从假设1 的可能的核仁分配。可以通过改变不同的限制条件,重新定义对于 σ0(S)而言可以接受的重新排序,从而得到其他可能的核仁分配。

结语

本文对考虑外包的生产调度问题及潜在的合作博弈的可能进行了建模研究。通过建立了考虑在制品库存成本和预订成本的生产模型,研究了相应的合作博弈问题,给出了一组均衡解的分配原则。

摘要：通过研究合作博弈理论在生产调度问题中的应用,介绍合作博弈的概念及其均衡解的存在条件,并给出一个生产调度模型下的实际应用。该生产调度模型模拟工序外包给第三方承包商的生产模型,并以在制品库存成本和生产窗口的预订成本作为复合目标函数。其中,生产窗口的预订成本非线性,通过模拟普通生产窗口和加班生产窗口的不同价格,将其设定为已知的分段函数;在制品库存成本使用加权流水时间表示,给出了该模型下的合作博弈问题的一组均衡解。

关键词：合作博弈,均衡解,生产调度,加权流水时间,应用

模糊非合作博弈的算法研究 篇2

自20世纪90年代以来，科学技术和经济快速发展，市场开始全球化，企业面临的竞争日趋激烈。技术的进步和需求的多样化，使产品寿命周期不断缩短，因而企业面临着缩短交货期、提高产品质量、降低成本和改进服务的压力。如何以更高的产品价值、更优的产品质量、更低廉的成本、更快捷的市场反应速度和更满意的服务与竞争者抗衡；如何占领尽可能大的市场份额，成为企业经营战略的核心，也成为企业面临的重要问题。供应链的产生改变了现代企业的竞争方式，使得企业间通过加强合作来提高竞争力，共同将利益蛋糕做大，建立一种“共赢”的战略合作伙伴关系。在建立合作伙伴关系中，由于利益的原因，双方之间往往存在着策略的对抗和竞争，或对某一种局面的对策选择，因此须对建立供应链合作伙伴关系采用非合作博弈的方法去分析。

现在非合作博弈在经济管理中已得到了广泛的应用，Nash均衡作为非合作博弈的一个重要概念，是所有应用领域中希望得到的最优状态。虽然理论上已经证明了它的存在性，但是并没有给出求解Nash均衡的一般性算法。尤其是对规模较大的问题，现有的方法很难给出解。随着现代优化算法的发展，人们开始把遗传算法引入到均衡求解中来。2001年，陈士俊等[1]提出了一种求解Nash均衡解的遗传算法。仝凌云等[2]运用双种群自适应遗传算法解决了虚拟企业伙伴选择的问题。王成山等[3]以改进的遗传算法为基础，提出了一种适用于输电网投资博弈的均衡分析方法。以上这些算法都是对经典的Nash均衡设计的。2004年，曾玲等[4]针对产品价格为模糊变量的一般递阶资源分配问题，设计了一个求解Stackelberg-Nash均衡解的基于模糊模拟的二层遗传算法。本文将在此基础上为模糊非合作博弈设计一个求解模糊均衡的基于模糊优先关系的遗传算法，并通过一个实例进行验证。

一、模糊非合作博弈

定义1局中人的集合为，局中人的策略集为，当每个局中人选定一个策略（）后，就形成了博弈的一个局势；对于每一个局势 ，局中人 有一个模糊支付函数，则为一个模糊非合作博弈。

定义2设是模糊非合作博弈的一个局势，如果

，

则称为的一个均衡局势。

定义3对于模糊非合作博弈，为局中人的模糊占优策略的隶属度为

.

定义4对于模糊非合作博弈，局势S为的模糊均衡的隶属度为

.

定义5对于模糊非合作博弈，如果对隶属函数有

，

则称局势为的最优模糊均衡。

二、求解模糊均衡的遗传算法

对于模糊非合作博弈，其最优模糊均衡满足。显然这是一个组合最优化问题，随着局中人数量以及策略集元素的增加，求解最优模糊均衡的计算量是指数增长的。这是一个NP-hard问题。

我们将每个局势看作自然界中的一个生物体，每个局中人的策略看作是生物体的不同染色体。正如生物体的生存性质与染色体组的基因关系，最优解也将是算法过程中的最优模糊均衡，从而获得有限n人非合作模糊博弈的最优模糊均衡。在此我们假设所有局中人均有m个策略。

首先我们对问题进行编码。根据非合作模糊博弈的特点，本文采用常规码，对于局中人，其策略集为，向量是局中人的决策向量，其中表示局中人没有选取第个策略，表示局中人选择了第个策略。所有局中人的选择构成了博弈的一个局势，则局势可以用向量表示。

随机选择个局势作为初始群体，

由定义4，可知衡量最优模糊均衡的指标函数为：

又由定义2，3，局势为模糊均衡的隶属度是：

现在问题转化为求的最大值。作适应函数：

计算概率

并以此概率分布从中随机选一些染色体构成一个种群（集中可能重复选中的一个元素）。

因为前面采用了常规编码，而局势的变化随每一个局中人策略选择的变化而变化，所以选择交配规则时，我们采用单亲遗传法。

从1到中随机选取个数，对于每一个，将第个分量与第个分量交换当时，；得到新的，组成新的局势。将中所有染色体进行上述交配，得到。

以某个较小的概率p发生变异，得到，令，，形成新的群体，循环计算。

当或者迭代次数达到某个次数时，终止程序。

简单遗传算法有可能不收敛到全局最优解，因此需要简单遗传算法作一点改动，每次记下当前最优解并在群体状态最前增加一维存放当前最优解，则遗传算法收敛到最优解。

改进后的遗传算法其主要特征是：进化的每一代，记录前面各代遗传的最优解并存放在群体的第一位，这个染色体只起到一个记录的功能不参加遗传运算。

现将模糊均衡的改进遗传算法叙述如下：

步骤一：给定群体规模，初始群体；

步骤二：对群体中的每一个染色体计算它的适应函数

，；

步骤三：若停止规则满足，则算法停止；否则，计算概率

，

以此概率分布从中随机选一些染色体构成一个种群；

步骤四：通过单亲遗传法进行交配，交配概率为，得到；

步骤五：以一个较小的概率p，使得一个染色体的一个基因发生变异，形成；在中记录当前最优解，，形成一个新的群体；

返回步骤二。

三、实际应用

下面通过一个具体的实例来验证一下算法的有效性。

假设现有同行业的两个制造商甲和乙，他们希望建立供应链的方式来提高自身的竞争力，在建立合作伙伴关系的过程中，各自有3个可供选择的供应商，他们的选择结果是互相影响的，根据不同的情况，甲和乙的收益矩阵如下：

遗传算法的参数选择：群体规模=3；交配概率为0.5；变异概率为0.2；算法终止条件为：迭代次数达到100或者当均衡隶属度高于0.5算法停止。通过计算，我们得到上述问题的最优均衡局势为甲选择策略3，乙选择策略3，即局势（3，3）为模糊均衡的隶属度为0.214。

四、小结

本文先给出了具有模糊支付的非合作博弈的定义，以及求解模糊均衡的定义，但是发现当局中人数量较多，或策略较多时，依靠枚举法进行求解是非常繁琐的，这是一个NP-hard问题。为了求得最优模糊均衡，在一个求解Stackelberg-Nash均衡解的基于模糊模拟的二层遗传算法的基础上，为模糊非合作博弈设计了一个求解模糊均衡的基于模糊优先关系的遗传算法，并给出了求解最优模糊均衡的改进遗传算法，最后通过一个实例进行了验证。

[1]陈士俊，孙永广，吴宗鑫.一种求解Nash均衡解的遗传算法[J].系统工程，2001.19

[2]仝凌云，陳增强，袁著祉，安利平.虚拟企业伙伴选择的双种群自适应遗传算法[J].计算机工程，2006.32

[3]王成山，吉兴全.输电网投资规划的Nash均衡分析（二）[J].电力系统自动化，2002.26

合作博弈调度 篇3

在突发事件常造成多个灾点的今天,能否迅速恢复灾后受损的通信网络系统以保证通信畅通,是整个应急救援行动在响应、指挥、调度等方面的成败关键。而多灾点应急通信资源调度的公平、合理、有效是整个救灾行动重要的前提和基础,关系到突发事件下应急通信保障工作的优劣,将对整个灾后应急救援行动造成影响。此时,应急决策者更倾向于运用决策分析工具构建简单的决策模型,故恰能满足上述要求的博弈论在应急资源调度决策中就有了用武之地。国内外一些学者已在该领域进行了相关研究,Shetty,Gupta和Ranganathan以博弈论作为工具,在对多事故点与多救援点之间应急资源配送关系进行分析后,建立了关于应急资源调度的博弈模型和求解算法,有效解决了资源合理调度的问题[1,2]。张婧等人为解决多事故同时存在时应急救灾中心的资源分配问题,设计了一种基于偏好序的改进效用函数,描述了各事故得到救援的有效性和及时性,最后建立了多事故应急资源调度博弈模型[15]。蒋一波、周鹏先后提出了流媒体监控系统中调度策略的非合作博弈模型,并对模型中Nash均衡点的存在性和唯一性进行了论证[5][16]。上述研究将博弈理论运用到资源调度中,但文献中尚未有专门针对突发事件后多灾点应急通信资源调度与分配的研究,本文基于非合作博弈理论建立多灾点应急通信资源调度模型,运用Nash均衡的迭代算法进行求解得到最佳调度方案。首先建立博弈模型并求解,然后对模型的解进行分析,最后通过实例对应急通信资源调度策略展开验证,为应急决策者提供最优策略方案。

1 多灾点应急通信资源调度的非合作博弈模型

突发事件发生后,往往造成移动、固定电话等通讯中断,此时急需合理调度应急通信资源以促进通信网络的恢复,常见的应急通信资源包括应急通信车、发电油机、卫星电话等。以下在模型假设的前提下建立应急通信资源调度的非合作博弈模型。

1.1 模型假设

在突发事件发生后应急通信资源有限的情况下,各灾点所需资源常相互冲突和对抗,各灾点间对应急通信资源的需求是非合作博弈的,博弈目的是尽量减少所获资源的成本。因此,对应急通信资源调度非合作博弈模型作出假设如下[13]:

(1)鉴于单个救援中心往往无法满足多个灾点的需求,需要其他救援中心协助配合共同完成救灾任务。当该区域内救援中心的资源不能满足自身需求时,可从邻近区域的救援中心获取援助,假设目的是为达到救灾成本最小化。

(2)根据各灾点灾情严重程度进行分级,Ⅰ表示灾情最高,依次为Ⅱ、Ⅲ、Ⅳ。

(3)资源配送最初未考虑救援中心资源数量,仅根据救灾成本最小原则进行初始分配。而作为一个多元复合函数,成本函数的影响因素包括灾情的严重程度、响应时间、平均速度和救援中心到灾点的距离,故首先需对各灾点向各救援中心支付的调度成本按大小依次排序。

1.2 建立模型

根据前述问题描述与假设,结合非合作博弈理论,构建多灾点应急通信资源调度的非合作博弈模型,该模型的标准形式定义如下:

G={t,N,(Sp(t))p∈N,(P(t)p)p∈N} . (1)

其中,t表示救灾时间段;N={1,2,…,n}为n个灾点的集合;Sp(t)为灾点p在t阶段全部可选策略的集合,即p可采取的行动方案;Pp(t)=Pp(s1,s2,…,sn)为灾点p在t阶段由调度成本倒数映射得到的效用函数;s=(s1,s2,…,sn)为n个灾点的一个组合策略。为了突出第p个灾点的行动策略,记s={sp,S-p},其中S-p表示除灾点p外其它所有灾点采取的组合策略;全部行动策略的集合undefined构成博弈的策略空间。

下面列出博弈模型的相关因素与数学表达式[13]:

(1) 应急通信资源调度速度vundefined(t)

在特定时段,灾点p的调度速度vundefined(t)与灾区路况密切相关,通常采用从救援中心k到灾点p的平均速度undefinedundefined(t)间接求取:

undefined. (2)

其中,μ(t)为路况系数,反映救援中心k到灾点p的道路好坏状况,μ(t)∈[0,1],路况越好,μ(t)越大。

(2)应急通信资源调度总成本函数Cp,q

对灾点p的第q个调度策略sp,q=(uundefined,uundefined,…uundefined,…,uundefined),其调度总成本函数表示为:

undefined. (3)

其中,M为所有救援中心的集合;h为所有灾点的集合;uundefined表示灾点p采用第q个策略时从救援中心k调度的资源量;cundefined为灾点p从救援中心k调度资源的救灾单位成本,作为调度依据,cundefined的函数如下:

其中,Dundefined表示救援中心k到灾点p的距离;Lp表示灾点p的灾情级别;∞表示从博弈范围外的救援中心调度资源时的单位成本为无穷大。

(3)收益函数

博弈中,一个特定策略组合下各灾点所期望得到的效用水平用收益函数表示,在调度过程中,用调度单位成本的倒数表示灾点p选择从救援中心k调度资源而获得的效用:

undefined. (5)

其中,Δcp为灾点p在救援中心k未得到满足的资源需到下一个救援中心进行调度而增加的成本。

灾点p从所有救援中心M调度所需资源的效用满足叠加定理,函数如下:

undefined. (6)

(4)目标函数

应急通信资源调度旨在对各灾点实现公平调度的情况下,最大化总效用。目标函数定义如下:

undefined. (7)

2 应急通信资源调度的非合作博弈模型的算法求解

2.1 基于Nash均衡算法的应急通信资源调度求解步骤

基于Nash均衡算法的应急通信资源调度求解按下列步骤进行[13]:

(1) 首先,进行资源初始分配,确定各灾点向各应急救援中心调度所需应急通信资源应支付的成本;

(2) 在不考虑各应急救援中心最大供给量的前提下,按成本最小原则分配各灾点所需资源;

(3) 考虑单个应急救援中心k的实际资源量,若资源数量能满足同级(同级指灾点的调度支付成本和灾情级别处于同一级,如模型假设表2中的灾点2、3)各灾点,则按各灾点需求直接进行分配;若k的资源最大供给量小于同级灾点的资源总需求量,则同级各灾点会针对k的资源存在竞争,构成一个博弈关系;

(4) 建立多灾点应急通信资源调度博弈模型,利用Nash均衡算法进行求解,并按Nash均衡解对救援中心资源进行调配;

(5) 同级灾点若依照Nash均衡解进行分配后仍存在未满足需求的部分,按成本次最小原则从下一救援中心调度所需资源,直至满足需求;

(6) 重复(3)完毕。

2.2 应急通信资源调度策略的Nash均衡存在性及迭代求解

在非合作博弈中的Nash均衡点上,任一理性参与者都不会有单独改变策略的冲动,因为当其他人的行动策略不变时,每一个局中人若单独改变自身策略都不会增加其效用。这样既能保证各灾点的收益最大化,也从总体上体现了应急通信资源调度方面的社会公平性。因此,利用Nash均衡算法所得到的解堪称对各灾点进行应急通信资源调度的最优可行策略。

由非合作博弈Nash均衡存在性定理及相应迭代算法可得到:

定理1:在n灾点的非合作博弈中,若每个灾点的最佳反应函数Op(S-p)满足下述条件:

(1) 对灾点q的每个调度策略sq(∀q≠p),Op(S-p)是sq的可微函数;

(2)undefined

则此次n灾点非合作博弈必定存在Nash均衡点。

证明:首先,定义S=Rn中的距离,选取任意两点s(1)={sundefined,sundefined,…,sundefined},s(2)={sundefined,sundefined,…,sundefined},则两点间距离为d(s(1),s(2))=undefined。

另外,∀S=(s1,s2,…,sn)∈S(策略空间),定义Xs=(O1(s-1),O2(s-2),…,sn(s-n)),很显然,X是S→S的算子。于是:

undefined

根据中值定理得:

undefined

其中,φp是sundefined和sundefined连线上的一点。

undefined

其中,由定理条件得到0≤λ0≤1,故X是S到自身的一个压缩因子;由压缩映像定理可得:S中一定存在满足Xs*=s*的不动点s*={s*1,s*2,…,s*n},即Op(s*-p)=s*p(p=1,2,…,n),由此可知s*为n灾点非合作博弈的Nash均衡点。

由上述证明过程可知,在实际迭代计算中可从任意点s(0)∈S开始,设初始点s(0)与Nash均衡点s*之间的距离为d(0),经m次迭代后,d(s(m),s*)≤λundefinedd(s(0),s*)=λundefinedd(0),由于0≤λ0≤1,故可用迭代公式s(m+1)=Xs(m)来任意逼近非合作博弈的Nash均衡点s*。

上述定理同时也说明当各灾点所选择的策略对其他灾点的策略选择影响不大(undefined表示收敛因子)时,多灾点非合作博弈的Nash均衡点一定存在且唯一[12]。

3 算例分析

2010年4月14日,青海玉树藏族自治州发生7.1级大地震,造成多地区受灾,选取玉树县、杂多县、曲麻莱县作为3个灾点(分别编号1、2、3),根据突发事件分级标准设3灾点灾情级别分别为Ⅰ、Ⅱ、Ⅲ。灾点所在区域玉树州内有2个应急通信救援中心(A、B)向各灾点提供应急通信资源(以应急通信车为例),另外,该区域附近有1个应急救援中心,位于甘肃省(C)境内。假设各灾点和各救援中心之间资源供需关系如表1。

假设3灾点从各应急救援中心进行应急通信车调度所支付的单位成本相同,分别为:

Cundefined=Cundefined=Cundefined=2,Cundefined=Cundefined=Cundefined=3,Cundefined=Cundefined=Cundefined=5

从上表可看出,玉树州内的救援中心A和B不能同时满足3县的需求,因为SA、B供给量=18

依据1.1中模型假设知,各灾点的最优调度方案都是从调度成本最低的救援中心调度所需资源,本例中,出现了多个对应急资源需求的竞争,如3灾点从A调度资源的成本最低,同为2单位,在不考虑灾情级别的情况下则存在三方资源竞争。

通过2.2中迭代算法算得该博弈的纯策略Nash均衡解:

s*1=(8,5,0),s*2=(0,5,3),s*3=(0,0,7)

那么,3救援中心向3灾点调度应急通信车的最终调度策略如表2:

按公式(3),带入Nash均衡解计算3灾点的资源调度总成本分别为:

C1,q=2×8+3×5+5×0=31;C2,q=2×0+3×5+5×3=30;C3,q=2×0+3×0+5×7=35

通过上述分析可以得最佳的应急通信车调度方案,即:灾点1受灾最为严重,应优先考虑,先从救援中心A调度8个单位所需资源到灾点1,然后再从B调度5单位,此时调度总成本最少,达到最大效用;灾点2的灾害程度低于灾点1,则先从B调度5单位资源,然后从C调度3个单位来满足需求;灾点3灾情最轻,应最后考虑,因A和B的应急通信车已率先满足较严重的2个灾点,故灾点3从C调度全部所需应急通信车7台。这样,可得到为玉树、杂多、曲麻莱3县调度应急通信车的总成本Cp,q=C1,q+C2,q+C3,q=31+30+35=96,此时,组合策略达到应急通信车调度总成本最少,为96个单位。

根据公式(5)、(6),计算3个灾点的收益函数分别为:

undefined

将单个灾点的收益结果代入公式(7),可得总的效用目标函数值:

undefined

计算结果表明,在该Nash均衡解策略组合下向玉树、杂多、囊谦3县调度应急通信车的总收益值达到最大,为28/3。

综上,可知按照通过迭代算法计算得出的Nash均衡解s*1=(8,5,0),s*2=(0,5,3),s*3=(0,0,7)向玉树、杂多、曲麻莱3县进行应急通信车公平调度,可实现全部3灾点应急通信车调度成本最小化和效用最大化。

4 结束语

合作博弈调度 篇4

传统的军事通信抗干扰聚焦于电磁空间内部, 而网络中心战的转型带来了针对组网体制上的干扰与毁伤, 使得如Link-16这类传统基于中心管理的数据链无法应对单点失效风险。为了解决组网体制上的抗干扰问题, 基于移动自组织网络技术的战术自组网应运而生。

移动自组织网络起源于1972年美国防部预研局 (DARPA) 启动的研究在战场环境下利用无线网络进行数字分组通信的PRNET项目。1983年DARPA启动了SURAN项目, 研究如何将PRNET研究成果支持更大规模网络。1994年DARPA启动了GloMo项目, 旨在对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究。IEEE802.11标准委员会采用“Ad Hoc Network”一词来描述这种特殊的自组织对等式多跳移动通信网络。

从“平台中心战”向“网络中心战”转型的驱动器就是战术数据链 (TDL) 。作为C4ISR系统的重要组成部分, TDL具有信息传输实时、信息传输安全可靠、传输手段多样、信息流程自动化、链接关系紧密等明显特征。美国防部为了将各军兵种研制的通信装备统一起来, 要求通信装备必须满足联合战术无线电系统 (JTRS) 规范, JTRS作战单元能够进行横向互通和纵向链接, 为实现美国防部的作战单元进化目标提供移动自组织组网 (MANET) 的能力。具有自组网能力的数据链是今后军事通信装备的研发热点。BBN、通用动力、哈里斯、诺·格、雷声、罗·科、洛·马等军工企业都展开了自组网数据链的研发, 并推出了各自的产品。

近年来, 我军也逐渐展开了这方面的工作, 但是长期以来的惯性思维一直将提高物理层调制解调器性能作为工作的重心, 对战术组网的研究投入不足, 还停留在传统有中心模式下的时分多址或基于信道竞争方式的组网, 无法满足自组网数据链的业务需求, 我们迫切需要一种能够满足要求的组网新算法并基于此进行新装备的研制, 本文就是在此过程中的一次有益尝试。

2 自组网数据链的优势

自组网是实现网络中心战的核心技术, 是为了满足战术数据链系统需具备的抗干扰、抗毁性、自组织性和机动性而作为基本出发点设计的, 具有如下的特点:

1.现代战争中的通信系统是首要打击目标, 军事通信系统要能抵御一定程度的攻击。若采用集中式通信系统, 一旦通信中心受到破坏, 将导致整个系统瘫痪。自组网采用分布式无中心控制, 当某些节点或链路发生故障, 其它子系统和节点还可以保持最大限度的通联。

2.战场环境下很难保证有可靠的有线通信设施, 自组网由移动节点自主、自由组合, 不依赖于有线设备, 因此, 具有较强的自组织性, 适合战场的恶劣通信环境。

3.机动性是部队战斗力的重要部分, 这就要求通信系统能够根据战事需求快速组建和拆除。自组网建立简单迅速, 具有很高的机动性。

自组网满足了战术通信系统的上述需求。研究自组网对战术通信系统的发展具有重要的应用价值和长远意义。因其特有的无需架设网络设施、可快速展开、抗毁性强等特点, 是分布式网络化控制作战的首选技术。美军JTRS中的士兵电台波形 (SRW) 、宽带组网波形 (WNW) 、联合空基组网-战术边缘 (JAN-TE) 等装备都基于自组网技术而研发。

3 自组网数据链协议分析

3.1 现有自组网协议的问题

近十年来自组网数据链装备的研发表明, 研究领域最为密集的自组网路由协议并非影响自组网性能的关键因素, 物理层的调制解调技术和信道访问控制 (MAC) 协议才能从根本上提升通信质量, 而无视物理层和MAC层特性的路由算法必定无法充分发挥通信网络的性能, 所以我们的研究重点放在了先进调制解调技术与MAC协议的性能提升。

MAC算法通常有两种解决思路:基于竞争的异步方式和基于预留的同步方式。由于竞争方式无需基础网络设施, 特别适用于移动环境中, 所以长期以来应用于无线组网中, 其提供的低访问延时使其适用于小规模按讲话音业务和突发数据业务需求。目前最为常用的协议基于载波侦听多路访问 (CSMA) 机制, 为解决CSMA的隐藏终端问题, IEEE 802.11协议标准引入了RTS/CTS握手机制。为了使基于类CSMA的组网协议能够支持网络QoS要求, 人们做了大量的努力。尽管对原有CSMA进行了改进, 但是无法对时延敏感的实时话音和视频业务提供令人满意的效果。

随着近年来多媒体通信技术的成熟, 为战术环境中提供实时视频、VoIP、地图、作战协同白板等新的业务也进入日程, 网络负荷急剧加重, 恶劣环境下无线通信提供的带宽和速率总是无法满足高层业务的增长需求, 此时以往的基于竞争方式的组网协议就会导致网络信道利用率急剧下降。这就迫使我们把目光重新放回基于预留机制的时分多址TDMA方式。而传统的静态TDMA机制, 如Link-16数据链, 是典型的预分配网络, 无法自适应网络拓扑和业务流量的变化, 而且会有单点失效效应导致网络瘫痪。1982年IBM公司的Nelson等人最早提出了分布式动态TDMA的思想, 指出同时达到高吞吐量和提供端对端延时保证的组网协议就是分布式动态TDMA协议。

3.2 分布式动态TDMA研究进展

分布式动态TDMA涉及的问题很多, 如时间同步、时隙分配、流量预测、时隙调度、耦合路由等。从上个世纪90年代开始, 针对Link-16数据链有中心TDMA存在的抗毁伤能力差、单点失效风险等问题, 罗·科公司展开了分布式动态TDMA调度算法的研究, 发表了一系列的论文, 提出了基于统一时隙分配协议的调度算法, 已经确立成为JTRS中多种波形的MAC基础协议。基于其开发的TTNT波形作为与Link-16数据链兼容的未来替代者, 并成为JAN-TE波形的标准。BAE公司就采用了分布式调度算法作为其分布式算法原型。雷声公司的最新型增强型定位报告系统 (EPRLS) 基于其自组网协议栈, 也采用分布式动态TDMA思想, 已装备美军并取得了预期效果。挪威国防部、美国海军研究实验室、瑞典国防部、美国陆军学院等军事部门都发表了相关研究成果。

4 自组网数据链资源调度

4.1 资源调度模型

我们所关心分布式动态TDMA自组网数据链组网模型如图1所示, 其承载业务具有高带宽、实时性、低功耗这样的互为牵制的QoS要求, 同时还要支持大量的组播业务, 所以寻找一条或几条满足时延、带宽和功耗需求的单播和组播路由具有很大的挑战, 还涉及节点之间的分布式时隙竞争和分配机制。

我们考虑转发节点和其邻居之间竞争时隙分配的非合作博弈模型。转发节点i和其邻居节点之间竞争时隙, 用于满足源节点业务流对带宽要求, 为自身获利。

参与者集合={1, 2, 3, …, N}。参与者i策略集合Si, 所有参与者的策略集合为

参与者在没有进行议价行为或议价失败的情况下, 获得的最小的收益向量为:

节点i两跳以内邻居节点个数为Li, 节点i两跳以内邻居节点集合, 那么该博弈参与者共有Li+1个。转发节点从源节点获利m, 扣除转发消耗pi, i+1和竞争消耗, 节点i的收益为:

若存在收益向量满足:

那么唯一确定。纳什议价解是满足纳什议价公理的唯一函数。

定义转发节点i收益和其所有两跳以内的邻居收ui益函数的乘积为:

那么纳什均衡策略向量

根据博弈参与者的理性原则, 可得:

为计算纳什均衡, 需寻找满足限制条件下使得取得最大值的fi, k。

4.2 纳什议价解

纳什议价模型的解是一个函数, 该函数将映射到解集上。纳什证明, 存在着唯一的一个解u满足以下四条公理, 解的存在性和唯一性分别由效用向量集合是紧集和凸集的性质保证:

公理1:弱帕累托最优性质 (Weak Pareto Optimality) :

公理2:对称性 (Symmetry) :如果d1=d2且 (u1, u2) ∈φ (u2, u1) ∈φ, 则:

公理3:规模转换不变性 (Scale Transformation Covariance) :, 如果我们定义函数g是将所有向量 (u1, u2) 映射到 (u1', u2') 的函数, 例如ui'=aiui+bi (i=1, 2) , 则:

公理4:无关选择的无关性 (Independence of Irrelevant Alternatives) :ϕ⊂φ, 并且f (ϕ, d) ∈ϕ, 则:

在满足以上四个公理的情况下, 可以证明, 纳什议价的唯一解便是使纳什积 (u1-d1) (u2-d2) 最大化的效用向量:

4.3 纳什均衡存在性

为计算是一个严格凹函数, 需证明多元函数的偏微分二阶导数组成Li+1的阶Hessian对称矩阵负定。令X=fi, k, 则g (u) 变为:

令

二阶导数

二阶偏导数

则的Hessian矩阵

首先计算的梯度

令

解得:

而xk=0时, H (g) 非负定, 故舍去。现证明取局部最优值时, H (g) 负定。

计算此处的Hessian矩阵

其中:

矩阵A的特征值为:

至此, 证明了矩阵H (g) 负定。使其梯度为0的点

为局部最大值。对于定义在开放凸集上的凹函数, 每一个局部最大值都是该开放凸集上的全局最大值。所以为全局最大值, 也是纳什均衡点。

从上述结果可以看出, 转发节点i从源节点得到的奖赏m减去必要的转发开销以后, 剩余的收益需要和与其竞争时隙分配的所有共个两跳以内邻居共享, 在平均分配时候任何参与竞争的节点都不会有怨言, 达到一个公平分配的稳定状态。

5 结语

本文引入经济学博弈理论中的纳什议价解函数, 证明了战术自组网资源分配存在纳什均衡, 为后续的启发式调度算法提供了理论依据。根据本文得到的结论可知, 节点之间对时隙的竞争将会导致一个纳什均衡的产生, 即达到一个公平分配的稳定状态。据此, 我们就可以设计邻居节点之间的时隙分配避免冲突的算法, 并将时隙资源分配给最为需要的节点, 从而实现自组网数据链资源的按需动态分配, 提高信道利用率, 这对于当前物理速率较低的电台现实情况而言具有重要的意义。

摘要：随着无线自组网技术的发展, 必须解决在该网络结构下的动态资源分配问题。本文引入经济学博弈理论中的纳什议价解函数, 证明了基于启发式的自组网数据链资源的调度算法存在纳什均衡, 且分配结果与支付函数成比例公平。该结论为设计自组网数据链终端间的资源竞争和调度策略, 实现资源的按需动态分配提供了理论依据。

关键词：自组网,数据链,博弈论,纳什均衡

参考文献

[1]J.Jubin and J.D.Tornow, ‘‘The DARPA packet radio network protocols, ’’Proceedings of the IEEE, January, 1987.