基于元胞自动机的部门间复杂合作的推广仿真

王先甲，曾冠天，陈振颂

(1.武汉大学 经济与管理学院，湖北 武汉 430072;2.武汉大学 土木建筑工程学院，湖北 武汉 430072)

0 引言

随着工业4.0概念的提出，工业制造系统涉及的制造场景越来越复杂，集成维度越来越丰富，纵向集成、端到端集成和网络化制造系统将不同层次的企业和部门关联起来[1]，产生更多更新的活动领域和合作模式[2-3]。产品的设计、制造、创新需要跨越的部门越来越多，不再是单一部门，或成员之间两两对接就能完美解决的问题，在实际中表现出更多的三方关系[4]。复杂事务指的是需要当前部门以及相邻部门的若干个成员同时参与其中的合作事务，随着合作模式的改变，部门间的合作动态也会呈现出新的动力学特征，在新的平台和新的业务出现时，将会产生新的合作模式。如何让合作行为在部门之间扩散，强化部门之间的合作，促进部门功能的整合以及部门之间资源的共享，从而最大程度地提升组织的整体绩效，已经成为公共领域和生产领域均不得不面对的挑战[6]。

在关于管理部门间合作的问题研究中，孙玮等[4]利用指数随机图模型研究集体行动中合作扩散的效应，强调了公众与管理层之间协商渠道的重要性；高世萍等[7]利用Moran过程发现正负激励及其反馈对合作涌现的作用差异；汪明月等[8]运用复制动态对区域合作减排的演化博弈进行研究，分析了整体发展水平和协同收益对合作演化的影响。但这些研究大多过于抽象，与现实中的合作演化出入较大，转向实证的可行性低。元胞自动机(Cellular-Automaton，CA)是一种具有离散时间、空间均属性和时空计算特征的网络动力学模型。元胞自动机作为一种研究系统复杂性的工具，最初被用于生物学、生态学、信息科学、物理学、化学、地理、环境等领域。近年来，部分学者利用元胞自动机分析管理学领域的研究问题[9-10]，邓青等[11]和梅晋铭等[12]将元胞自动机用于研究网络舆情传播和谣言干预问题；田景红等[13]按制造服务选择指数设置元胞状态，用于分析制造服务系统的自组织过程；安相华等[14-15]利用元胞自动机改进聚类算法，用于产品的模块化结构规划和集对关系中的产品质量-成本控制问题，建立了基于元胞自动机的大规模复杂问题分析方法。其中，陈波[10]在对元胞自动机的符号动力学研究中，剖析了元胞自动机应用于合作演化分析的可能性，但该研究以及前述各文献对于演化的状态转移方程的设置，大多基于直觉设置，或直接进行假设，缺少计量手段，或缺少对微观过程的设置，这都增加了研究的实证难度，削弱了研究结果对现实问题的指导作用。

目前国外的文献研究中，关于合作策略的演化，一般基于个体策略的突变假设，或者各成员之间的模仿动态和生灭动态假设[16]。SANTOS等[17]假定元胞具有有限的生命力，基于元胞消亡时被随机取代的原则建立元胞自动机规则，研究囚徒困境群体的演化问题；SAVERIO等[18]引入合作的正激励作用建立元胞自动机规则，总结了正激励对复杂的合作策略涌现的意义；SCHIMIT[19]将连续概率元胞自动机与遗传算法结合，建立了一种群体合作的数值分析方法。但这些方法同样没有很好地解决部门间合作扩散的实证基础问题。假设各个部门在方格网络上相邻排布，每个部门由稠密的成员组成，成员同一时间可以处于“合作策略状态”或“消极策略状态”，则每个部门的合作状态就由其成员中的合作策略状态与消极策略状态的占比决定。部门与部门的成员之间不断发生复杂事务的三方合作博弈，博弈带来的不同收益使得采取不同策略的成员数量上升或下降，进而使得部门的合作状态随时间推移而改变，合作策略在部门间扩散或萎缩。制造系统越复杂，达成广泛合作的扩散就越困难[20]，外生激励的影响就显得越发重要，激励形式可以分为分散式激励和集中式激励[7]。本文考虑动态的、强效的集中式激励作用于少量部门的合作状态并在部门与部门之间移动，并借鉴兰顿蚂蚁模型[21-22]，建立了面向部门间合作扩散的带蚂蚁的元胞自动机模型，通过仿真实验，分析复杂事务合作成本与激励效果之间的关系，为制造系统监督部门合作以及企业内的合作文化建设提供理论参考。

1 基本假设与模型建立

1.1 元胞结构

元胞自动机由元胞、元胞状态、邻域和状态更新规则构成，设定元胞空间为规则的无向二维网格，将每个元胞的邻域定义为与元胞邻接或斜接的元胞的集合[21]。假设各部门在方格网络上分布，每个部门都由规模相似的稠密的成员构成，相邻部门之间的成员会发生复杂事务的合作，因此可以用元胞空间描述部门间的互动关系：

C={(xc,yc)∈N2|1≤xc≤a,1≤yc≤b}。

(1)

(2)

整个空间的状态可以表示为：

(3)

空间邻域采用Moore邻域规则，即一个部门中的成员与其邻域部门中的成员发生交互：

∀c0=(xc0,yc0)∈C，

(4)

有：

U(c0)={(xc,yc)≠(xc0,yc0)||xc-xc0|

=1 or |yc-yc0|=1}。

(5)

(6)

1.2 状态转移

假设从t期到t+1期的时刻足够长，部门中的复制动态的速度足够快，协力者的数量足够小(仅影响博弈而不做停留，不融入本地的成员比例)即将其视作一种“信号”而不是移民，令本问题中所描述的博弈形式为G，可以用本地个体在博弈中取得的适合度来描述G(如表1)，忽略协力者在博弈中的适合度。

表1 博弈形式G

(7)

(8)

(9)

当达到t+1期时，每个部门ci将在上一期的协力者群体的作用下，达到该条件下的复制动态的稳态，即

(10)

(11)

每一期t时刻，系统空间中的每一个部门ci∈C根据其邻域内的部门U(ci)所发送的信号，进行复制动态演化，并在t+1时期达到其均衡稳定点；此时，其邻域内的部门也发生了变化，因而传来新的信号，使得ci在新的条件下向新的均衡稳定点再次移动。

1.3 生命游戏条件

根据博弈形式G的不同，复制动态及其相位之间差距较大，种群在t与t+1之间的状态转移规则也会有很大区别，状态集合同样会受此影响，特别地，在状态集合只有两个元素的情况下，即I={0,1}，满足这一条件的元胞自动机演化过程常被称作生命游戏过程[24]。

观察1.2节复制动态的相位图，建立如下不等式：

(13)

(14)

当G满足如下条件时，复制动态有且只有两个均衡点，I={0,1}：

条件1：

(15)

(16)

(17)

(18)

基于前文，复杂事务合作的演化的元胞自动机的状态转移规则展开如下：

(19)

(20)

(21)

1.4 好蚂蚁

随着产业不断升级，新事务的合作可以由强势的管理者的激励主导，从局部开始，考虑模仿兰顿蚂蚁规则，将一种具有特定行走规则，并可以改变其路径上元胞状态的对象置入元胞空间[21]，这种对象称为“好蚂蚁”，在现实世界中即为系统中的推广团队和合作的监督者。在基础的元胞自动机模型CELL=(C,St)的基础上，将引入了好蚂蚁的元胞自动机描述为：CELLANT=(C,St,ANTt)。

(1)用“蚂蚁”来描述政府为了推进新型事务的合作而引入的强有力的规范或鼓励力量，可以想象，当一只好蚂蚁在某个部门中出现时，它的力量足以将此处的个体全部转化为策略s型的个体，因此，当好蚂蚁在元胞空间中运动时，它所经过的部门都会立刻进入s状态。

(2)当“蚂蚁”在元胞空间中游走时，它沿十字方向移动，但不会进入已经处于s状态的元胞，在剩下的方向中，蚂蚁以相等的概率选择自己的移动方向；当蚂蚁四周都是s部门时，蚂蚁完成了自己的使命而被移除。

(3)总系统空间规模是有限的，当蚂蚁来到元胞空间的边界而继续向元胞空间外移动时，蚂蚁也被移除。

基于以上假设，将带有“好蚂蚁”的元胞自动机的状态更新规则描述如下：

(22)

(23)

且：

(24)

2 实例：有参与成本的合作博弈

当把策略s视作合作，策略r视作消极(不参与合作)，前述模型就可以用来模拟网络种群中的合作演化的问题，用合作博弈的形式来描述该问题下的支付，

V(∅)=0，V(本地1)=V(本地2)=v1，V(协力)=v2，V(本地1,本地2)=v3，V(本地1,协力)=V(本地2,协力)=v4=1，V(本地1,本地2,协力)=v5。

(25)

根据参与到博弈中的合作者的组合，本地个体取得相对应的不同支付，当个体以合作策略参与其中时，会支付一定的成本k，根据情况的不同，成本可能有变化。

表2 博弈形式G

在一定的条件下，本博弈可以满足上一章中所描述的条件：

条件2

(1)以合作博弈观点看，该博弈在每一个局部都是满足超可加性的，若干个合作者的合作支付总和大于分别合作的支付：

v5>v3+v2，v5>v4+v1，v4>v1+v2，v3>2v1，

2v4>v2+v5。

(26)

(2)参与合作所需要的成本是可观的，特别地，当另一个本地成员已经使用合作策略，而协力者是消极策略时，剩余个体选择合作反而会降低它得到的支付，即v3-k

(3)参与合作的成本不至于太高，当另一个本地成员已经采用合作策略，且协力者也是合作策略时，当前个体使用合作策略能获得相比消极更高的支付，即v5-k>v4。

定理1条件2是条件1的充分条件。即，在上述合作条件下，发生在系统中的演化符合广义生命游戏的条件。

3 仿真实验

3.1 实验条件

随机过程表明，对于二维网格上的随机游走，变量总能以1的概率离开出发点任意远的距离[26]，因此在实验中，“蚂蚁”的运动可以视为一种带限制的随机游走，这种限制会加大游走的方差，以使得“蚂蚁”也能以1的概率最终离开实验中的有限网格，因此，以

(27)

即所有蚂蚁都被移除的期望时间，来衡量对应规则下管理者向元胞网络投送外界干预的效率。蚂蚁的持续时间越短，说明外来干预完成自己任务所需的成本越低，效率越高；反之，蚂蚁的持续时间越高，说明外来干预需要在整个系统中长期地活动，而它的周围长期缺乏合作部门，干预的效率越低。

如前所述，本文的元胞自动机规则由3个转化常数{l,m,n}构成，作为一种简化的情形，假设消极部门转化为合作元胞所需的(m,n)太窄，以致于自然状态下，处于消极状态下的部门几乎不可能在周围部门的任何影响下转化为合作部门，当且仅当在蚂蚁的影响下，消极部门才会转化为合作部门，则在这种假设下，演化规则简化为：

(28)

3.2 仿真

考虑a在[0,4]的范围内变化及b在[-1,3]的范围内变化，当b<-1时，没有任何一个合作部门会存活超过一期。

3.2.1 一只蚂蚁的情形

在15×15的方格网络[-7,7]×[-7,7]中，在最初让一只“蚂蚁”出现在网络中心，即(0,0)，t*的等高线图和表面图如图3所示。

可以直观看出，蚂蚁的持续时间随b，即状态更新规则的宽度的增加，是单调递减的；随a的增长则会减弱后增强，对于b的任意取值，使得持续时间最低的a的取值都在2附近。

3.2.2 以2只为例：多只蚂蚁的情形

在长宽15×15的合作方格网络上，让2只蚂蚁分别同时出现在(1,0)和(-1,0)，t*的等高线图和表面图如图4所示。

仿真结果显示，当有多只“蚂蚁”同时出现在系统中时，由于可以共同加速系统合作扩散的进程，各自的持续时间也会有所缩短，使得t*相比于3.2.1节中的情形显得更小，但效率变化和参数a,b的关系基本不变，蚂蚁持续时间仍然随着b的增长而单调降低；使得t*最高的a的取值仍然在2附近。这个特点并没有随着出现的蚂蚁数量的增多而发生变化。

考虑到在前述参数设置中，a由合作成本k决定，b由合作成本k和v2共同决定，即与直觉的合作成本越低越好相反，一个较小但不是过分小的合作成本，可能更有利于合作在若干合作部门聚集的团块边缘向外传播。

4 结束语

考虑制造系统逐渐复杂化的背景下，事务合作变为多方合作时合作策略在多部门系统中的演化和扩散，利用带蚂蚁的元胞自动机模型，考虑了方格网络下的一个简化情形。已有文献对部门间合作扩散的特点进行了分析，但使用的模型往往过于抽象，难以扩展到更实际的场景中去。本文通过局部动态模仿解释元胞自动机的演化规则，所提假设更具体合理，可进一步拓展到复杂网络的研究中。结合自动机理论，分析了在新平台合作模式下，合作策略对部门间扩散速度与合作成本等参量的影响。证明了当三成员的合作事务满足局部超可加、个人合作成本可观且不过高的条件下，部门间合作策略的演化满足广义的生命游戏规则：即一种两状态的元胞自动机，而且这类自动机系统的“生(萌发合作)”条件是“存(维持合作)”条件的真子集，两者都是连续区间，并在对应的元胞自动机规则下对种群的合作演化问题进行了仿真。

假设管理者为了推广新复杂事务的合作采取强有力的局部激励，仿照兰顿蚂蚁引入 “蚂蚁模型”，在一个简化情形下，仿真证明了，当随着合作成本的增加，使得自动机规则中的“存”规则下界，即a*随之增加，外界干预的效果会先上升再下降。由于a*的决定因素是参与博弈的合作成本，即一个较低但不是过分低的合作成本，可能反而更有利于复杂事务合作的推广。

最后，本文构造了从部门内的复制动态到部门间的元胞自动机系统规则的推理，为从成员的合作收益到部门合作演化提供实证分析的依据。在未来的研究主要从两个方面进行拓展：①从实证的角度考虑成员到部门的演化博弈；②研究复杂网络中的元胞自动机系统规则设计。