基于元胞自動機(jī)的部門間復(fù)雜合作的推廣仿真

王先甲，曾冠天，陳振頌

(1.武漢大學(xué) 經(jīng)濟(jì)與管理學(xué)院，湖北 武漢 430072;2.武漢大學(xué) 土木建筑工程學(xué)院，湖北 武漢 430072)

0 引言

隨著工業(yè)4.0概念的提出，工業(yè)制造系統(tǒng)涉及的制造場景越來越復(fù)雜，集成維度越來越豐富，縱向集成、端到端集成和網(wǎng)絡(luò)化制造系統(tǒng)將不同層次的企業(yè)和部門關(guān)聯(lián)起來[1]，產(chǎn)生更多更新的活動領(lǐng)域和合作模式[2-3]。產(chǎn)品的設(shè)計(jì)、制造、創(chuàng)新需要跨越的部門越來越多，不再是單一部門，或成員之間兩兩對接就能完美解決的問題，在實(shí)際中表現(xiàn)出更多的三方關(guān)系[4]。復(fù)雜事務(wù)指的是需要當(dāng)前部門以及相鄰部門的若干個(gè)成員同時(shí)參與其中的合作事務(wù)，隨著合作模式的改變，部門間的合作動態(tài)也會呈現(xiàn)出新的動力學(xué)特征，在新的平臺和新的業(yè)務(wù)出現(xiàn)時(shí)，將會產(chǎn)生新的合作模式。如何讓合作行為在部門之間擴(kuò)散，強(qiáng)化部門之間的合作，促進(jìn)部門功能的整合以及部門之間資源的共享，從而最大程度地提升組織的整體績效，已經(jīng)成為公共領(lǐng)域和生產(chǎn)領(lǐng)域均不得不面對的挑戰(zhàn)[6]。

在關(guān)于管理部門間合作的問題研究中，孫瑋等[4]利用指數(shù)隨機(jī)圖模型研究集體行動中合作擴(kuò)散的效應(yīng)，強(qiáng)調(diào)了公眾與管理層之間協(xié)商渠道的重要性；高世萍等[7]利用Moran過程發(fā)現(xiàn)正負(fù)激勵及其反饋對合作涌現(xiàn)的作用差異；汪明月等[8]運(yùn)用復(fù)制動態(tài)對區(qū)域合作減排的演化博弈進(jìn)行研究，分析了整體發(fā)展水平和協(xié)同收益對合作演化的影響。但這些研究大多過于抽象，與現(xiàn)實(shí)中的合作演化出入較大，轉(zhuǎn)向?qū)嵶C的可行性低。元胞自動機(jī)(Cellular-Automaton，CA)是一種具有離散時(shí)間、空間均屬性和時(shí)空計(jì)算特征的網(wǎng)絡(luò)動力學(xué)模型。元胞自動機(jī)作為一種研究系統(tǒng)復(fù)雜性的工具，最初被用于生物學(xué)、生態(tài)學(xué)、信息科學(xué)、物理學(xué)、化學(xué)、地理、環(huán)境等領(lǐng)域。近年來，部分學(xué)者利用元胞自動機(jī)分析管理學(xué)領(lǐng)域的研究問題[9-10]，鄧青等[11]和梅晉銘等[12]將元胞自動機(jī)用于研究網(wǎng)絡(luò)輿情傳播和謠言干預(yù)問題；田景紅等[13]按制造服務(wù)選擇指數(shù)設(shè)置元胞狀態(tài)，用于分析制造服務(wù)系統(tǒng)的自組織過程；安相華等[14-15]利用元胞自動機(jī)改進(jìn)聚類算法，用于產(chǎn)品的模塊化結(jié)構(gòu)規(guī)劃和集對關(guān)系中的產(chǎn)品質(zhì)量-成本控制問題，建立了基于元胞自動機(jī)的大規(guī)模復(fù)雜問題分析方法。其中，陳波[10]在對元胞自動機(jī)的符號動力學(xué)研究中，剖析了元胞自動機(jī)應(yīng)用于合作演化分析的可能性，但該研究以及前述各文獻(xiàn)對于演化的狀態(tài)轉(zhuǎn)移方程的設(shè)置，大多基于直覺設(shè)置，或直接進(jìn)行假設(shè)，缺少計(jì)量手段，或缺少對微觀過程的設(shè)置，這都增加了研究的實(shí)證難度，削弱了研究結(jié)果對現(xiàn)實(shí)問題的指導(dǎo)作用。

目前國外的文獻(xiàn)研究中，關(guān)于合作策略的演化，一般基于個(gè)體策略的突變假設(shè)，或者各成員之間的模仿動態(tài)和生滅動態(tài)假設(shè)[16]。SANTOS等[17]假定元胞具有有限的生命力，基于元胞消亡時(shí)被隨機(jī)取代的原則建立元胞自動機(jī)規(guī)則，研究囚徒困境群體的演化問題；SAVERIO等[18]引入合作的正激勵作用建立元胞自動機(jī)規(guī)則，總結(jié)了正激勵對復(fù)雜的合作策略涌現(xiàn)的意義；SCHIMIT[19]將連續(xù)概率元胞自動機(jī)與遺傳算法結(jié)合，建立了一種群體合作的數(shù)值分析方法。但這些方法同樣沒有很好地解決部門間合作擴(kuò)散的實(shí)證基礎(chǔ)問題。假設(shè)各個(gè)部門在方格網(wǎng)絡(luò)上相鄰排布，每個(gè)部門由稠密的成員組成，成員同一時(shí)間可以處于“合作策略狀態(tài)”或“消極策略狀態(tài)”，則每個(gè)部門的合作狀態(tài)就由其成員中的合作策略狀態(tài)與消極策略狀態(tài)的占比決定。部門與部門的成員之間不斷發(fā)生復(fù)雜事務(wù)的三方合作博弈，博弈帶來的不同收益使得采取不同策略的成員數(shù)量上升或下降，進(jìn)而使得部門的合作狀態(tài)隨時(shí)間推移而改變，合作策略在部門間擴(kuò)散或萎縮。制造系統(tǒng)越復(fù)雜，達(dá)成廣泛合作的擴(kuò)散就越困難[20]，外生激勵的影響就顯得越發(fā)重要，激勵形式可以分為分散式激勵和集中式激勵[7]。本文考慮動態(tài)的、強(qiáng)效的集中式激勵作用于少量部門的合作狀態(tài)并在部門與部門之間移動，并借鑒蘭頓螞蟻模型[21-22]，建立了面向部門間合作擴(kuò)散的帶螞蟻的元胞自動機(jī)模型，通過仿真實(shí)驗(yàn)，分析復(fù)雜事務(wù)合作成本與激勵效果之間的關(guān)系，為制造系統(tǒng)監(jiān)督部門合作以及企業(yè)內(nèi)的合作文化建設(shè)提供理論參考。

1 基本假設(shè)與模型建立

1.1 元胞結(jié)構(gòu)

元胞自動機(jī)由元胞、元胞狀態(tài)、鄰域和狀態(tài)更新規(guī)則構(gòu)成，設(shè)定元胞空間為規(guī)則的無向二維網(wǎng)格，將每個(gè)元胞的鄰域定義為與元胞鄰接或斜接的元胞的集合[21]。假設(shè)各部門在方格網(wǎng)絡(luò)上分布，每個(gè)部門都由規(guī)模相似的稠密的成員構(gòu)成，相鄰部門之間的成員會發(fā)生復(fù)雜事務(wù)的合作，因此可以用元胞空間描述部門間的互動關(guān)系：

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

(1)

(2)

整個(gè)空間的狀態(tài)可以表示為：

(3)

空間鄰域采用Moore鄰域規(guī)則，即一個(gè)部門中的成員與其鄰域部門中的成員發(fā)生交互：

?c0=(xc0,yc0)∈C，

(4)

有：

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

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

(5)

(6)

1.2 狀態(tài)轉(zhuǎn)移

假設(shè)從t期到t+1期的時(shí)刻足夠長，部門中的復(fù)制動態(tài)的速度足夠快，協(xié)力者的數(shù)量足夠小(僅影響博弈而不做停留，不融入本地的成員比例)即將其視作一種“信號”而不是移民，令本問題中所描述的博弈形式為G，可以用本地個(gè)體在博弈中取得的適合度來描述G(如表1)，忽略協(xié)力者在博弈中的適合度。

表1 博弈形式G

(7)

(8)

(9)

當(dāng)達(dá)到t+1期時(shí)，每個(gè)部門ci將在上一期的協(xié)力者群體的作用下，達(dá)到該條件下的復(fù)制動態(tài)的穩(wěn)態(tài)，即

(10)

(11)

每一期t時(shí)刻，系統(tǒng)空間中的每一個(gè)部門ci∈C根據(jù)其鄰域內(nèi)的部門U(ci)所發(fā)送的信號，進(jìn)行復(fù)制動態(tài)演化，并在t+1時(shí)期達(dá)到其均衡穩(wěn)定點(diǎn)；此時(shí)，其鄰域內(nèi)的部門也發(fā)生了變化，因而傳來新的信號，使得ci在新的條件下向新的均衡穩(wěn)定點(diǎn)再次移動。

1.3 生命游戲條件

根據(jù)博弈形式G的不同，復(fù)制動態(tài)及其相位之間差距較大，種群在t與t+1之間的狀態(tài)轉(zhuǎn)移規(guī)則也會有很大區(qū)別，狀態(tài)集合同樣會受此影響，特別地，在狀態(tài)集合只有兩個(gè)元素的情況下，即I={0,1}，滿足這一條件的元胞自動機(jī)演化過程常被稱作生命游戲過程[24]。

觀察1.2節(jié)復(fù)制動態(tài)的相位圖，建立如下不等式：

(13)

(14)

當(dāng)G滿足如下條件時(shí)，復(fù)制動態(tài)有且只有兩個(gè)均衡點(diǎn)，I={0,1}：

條件1：

(15)

(16)

(17)

(18)

基于前文，復(fù)雜事務(wù)合作的演化的元胞自動機(jī)的狀態(tài)轉(zhuǎn)移規(guī)則展開如下：

(19)

(20)

(21)

1.4 好螞蟻

隨著產(chǎn)業(yè)不斷升級，新事務(wù)的合作可以由強(qiáng)勢的管理者的激勵主導(dǎo)，從局部開始，考慮模仿蘭頓螞蟻規(guī)則，將一種具有特定行走規(guī)則，并可以改變其路徑上元胞狀態(tài)的對象置入元胞空間[21]，這種對象稱為“好螞蟻”，在現(xiàn)實(shí)世界中即為系統(tǒng)中的推廣團(tuán)隊(duì)和合作的監(jiān)督者。在基礎(chǔ)的元胞自動機(jī)模型CELL=(C,St)的基礎(chǔ)上，將引入了好螞蟻的元胞自動機(jī)描述為：CELLANT=(C,St,ANTt)。

(1)用“螞蟻”來描述政府為了推進(jìn)新型事務(wù)的合作而引入的強(qiáng)有力的規(guī)范或鼓勵力量，可以想象，當(dāng)一只好螞蟻在某個(gè)部門中出現(xiàn)時(shí)，它的力量足以將此處的個(gè)體全部轉(zhuǎn)化為策略s型的個(gè)體，因此，當(dāng)好螞蟻在元胞空間中運(yùn)動時(shí)，它所經(jīng)過的部門都會立刻進(jìn)入s狀態(tài)。

(2)當(dāng)“螞蟻”在元胞空間中游走時(shí)，它沿十字方向移動，但不會進(jìn)入已經(jīng)處于s狀態(tài)的元胞，在剩下的方向中，螞蟻以相等的概率選擇自己的移動方向；當(dāng)螞蟻四周都是s部門時(shí)，螞蟻完成了自己的使命而被移除。

(3)總系統(tǒng)空間規(guī)模是有限的，當(dāng)螞蟻來到元胞空間的邊界而繼續(xù)向元胞空間外移動時(shí)，螞蟻也被移除。

基于以上假設(shè)，將帶有“好螞蟻”的元胞自動機(jī)的狀態(tài)更新規(guī)則描述如下：

(22)

(23)

且：

(24)

2 實(shí)例：有參與成本的合作博弈

當(dāng)把策略s視作合作，策略r視作消極(不參與合作)，前述模型就可以用來模擬網(wǎng)絡(luò)種群中的合作演化的問題，用合作博弈的形式來描述該問題下的支付，

V(?)=0，V(本地1)=V(本地2)=v1，V(協(xié)力)=v2，V(本地1,本地2)=v3，V(本地1,協(xié)力)=V(本地2,協(xié)力)=v4=1，V(本地1,本地2,協(xié)力)=v5。

(25)

根據(jù)參與到博弈中的合作者的組合，本地個(gè)體取得相對應(yīng)的不同支付，當(dāng)個(gè)體以合作策略參與其中時(shí)，會支付一定的成本k，根據(jù)情況的不同，成本可能有變化。

表2 博弈形式G

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

條件2

(1)以合作博弈觀點(diǎn)看，該博弈在每一個(gè)局部都是滿足超可加性的，若干個(gè)合作者的合作支付總和大于分別合作的支付：

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

2v4>v2+v5。

(26)

(2)參與合作所需要的成本是可觀的，特別地，當(dāng)另一個(gè)本地成員已經(jīng)使用合作策略，而協(xié)力者是消極策略時(shí)，剩余個(gè)體選擇合作反而會降低它得到的支付，即v3-k

(3)參與合作的成本不至于太高，當(dāng)另一個(gè)本地成員已經(jīng)采用合作策略，且協(xié)力者也是合作策略時(shí)，當(dāng)前個(gè)體使用合作策略能獲得相比消極更高的支付，即v5-k>v4。

定理1條件2是條件1的充分條件。即，在上述合作條件下，發(fā)生在系統(tǒng)中的演化符合廣義生命游戲的條件。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)條件

隨機(jī)過程表明，對于二維網(wǎng)格上的隨機(jī)游走，變量總能以1的概率離開出發(fā)點(diǎn)任意遠(yuǎn)的距離[26]，因此在實(shí)驗(yàn)中，“螞蟻”的運(yùn)動可以視為一種帶限制的隨機(jī)游走，這種限制會加大游走的方差，以使得“螞蟻”也能以1的概率最終離開實(shí)驗(yàn)中的有限網(wǎng)格，因此，以

(27)

即所有螞蟻都被移除的期望時(shí)間，來衡量對應(yīng)規(guī)則下管理者向元胞網(wǎng)絡(luò)投送外界干預(yù)的效率。螞蟻的持續(xù)時(shí)間越短，說明外來干預(yù)完成自己任務(wù)所需的成本越低，效率越高；反之，螞蟻的持續(xù)時(shí)間越高，說明外來干預(yù)需要在整個(gè)系統(tǒng)中長期地活動，而它的周圍長期缺乏合作部門，干預(yù)的效率越低。

如前所述，本文的元胞自動機(jī)規(guī)則由3個(gè)轉(zhuǎn)化常數(shù){l,m,n}構(gòu)成，作為一種簡化的情形，假設(shè)消極部門轉(zhuǎn)化為合作元胞所需的(m,n)太窄，以致于自然狀態(tài)下，處于消極狀態(tài)下的部門幾乎不可能在周圍部門的任何影響下轉(zhuǎn)化為合作部門，當(dāng)且僅當(dāng)在螞蟻的影響下，消極部門才會轉(zhuǎn)化為合作部門，則在這種假設(shè)下，演化規(guī)則簡化為：

(28)

3.2 仿真

考慮a在[0,4]的范圍內(nèi)變化及b在[-1,3]的范圍內(nèi)變化，當(dāng)b<-1時(shí)，沒有任何一個(gè)合作部門會存活超過一期。

3.2.1 一只螞蟻的情形

在15×15的方格網(wǎng)絡(luò)[-7,7]×[-7,7]中，在最初讓一只“螞蟻”出現(xiàn)在網(wǎng)絡(luò)中心，即(0,0)，t*的等高線圖和表面圖如圖3所示。

可以直觀看出，螞蟻的持續(xù)時(shí)間隨b，即狀態(tài)更新規(guī)則的寬度的增加，是單調(diào)遞減的；隨a的增長則會減弱后增強(qiáng)，對于b的任意取值，使得持續(xù)時(shí)間最低的a的取值都在2附近。

3.2.2 以2只為例：多只螞蟻的情形

在長寬15×15的合作方格網(wǎng)絡(luò)上，讓2只螞蟻分別同時(shí)出現(xiàn)在(1,0)和(-1,0)，t*的等高線圖和表面圖如圖4所示。

仿真結(jié)果顯示，當(dāng)有多只“螞蟻”同時(shí)出現(xiàn)在系統(tǒng)中時(shí)，由于可以共同加速系統(tǒng)合作擴(kuò)散的進(jìn)程，各自的持續(xù)時(shí)間也會有所縮短，使得t*相比于3.2.1節(jié)中的情形顯得更小，但效率變化和參數(shù)a,b的關(guān)系基本不變，螞蟻持續(xù)時(shí)間仍然隨著b的增長而單調(diào)降低；使得t*最高的a的取值仍然在2附近。這個(gè)特點(diǎn)并沒有隨著出現(xiàn)的螞蟻數(shù)量的增多而發(fā)生變化。

考慮到在前述參數(shù)設(shè)置中，a由合作成本k決定，b由合作成本k和v2共同決定，即與直覺的合作成本越低越好相反，一個(gè)較小但不是過分小的合作成本，可能更有利于合作在若干合作部門聚集的團(tuán)塊邊緣向外傳播。

4 結(jié)束語

考慮制造系統(tǒng)逐漸復(fù)雜化的背景下，事務(wù)合作變?yōu)槎喾胶献鲿r(shí)合作策略在多部門系統(tǒng)中的演化和擴(kuò)散，利用帶螞蟻的元胞自動機(jī)模型，考慮了方格網(wǎng)絡(luò)下的一個(gè)簡化情形。已有文獻(xiàn)對部門間合作擴(kuò)散的特點(diǎn)進(jìn)行了分析，但使用的模型往往過于抽象，難以擴(kuò)展到更實(shí)際的場景中去。本文通過局部動態(tài)模仿解釋元胞自動機(jī)的演化規(guī)則，所提假設(shè)更具體合理，可進(jìn)一步拓展到復(fù)雜網(wǎng)絡(luò)的研究中。結(jié)合自動機(jī)理論，分析了在新平臺合作模式下，合作策略對部門間擴(kuò)散速度與合作成本等參量的影響。證明了當(dāng)三成員的合作事務(wù)滿足局部超可加、個(gè)人合作成本可觀且不過高的條件下，部門間合作策略的演化滿足廣義的生命游戲規(guī)則：即一種兩狀態(tài)的元胞自動機(jī)，而且這類自動機(jī)系統(tǒng)的“生(萌發(fā)合作)”條件是“存(維持合作)”條件的真子集，兩者都是連續(xù)區(qū)間，并在對應(yīng)的元胞自動機(jī)規(guī)則下對種群的合作演化問題進(jìn)行了仿真。

假設(shè)管理者為了推廣新復(fù)雜事務(wù)的合作采取強(qiáng)有力的局部激勵，仿照蘭頓螞蟻引入 “螞蟻模型”，在一個(gè)簡化情形下，仿真證明了，當(dāng)隨著合作成本的增加，使得自動機(jī)規(guī)則中的“存”規(guī)則下界，即a*隨之增加，外界干預(yù)的效果會先上升再下降。由于a*的決定因素是參與博弈的合作成本，即一個(gè)較低但不是過分低的合作成本，可能反而更有利于復(fù)雜事務(wù)合作的推廣。

最后，本文構(gòu)造了從部門內(nèi)的復(fù)制動態(tài)到部門間的元胞自動機(jī)系統(tǒng)規(guī)則的推理，為從成員的合作收益到部門合作演化提供實(shí)證分析的依據(jù)。在未來的研究主要從兩個(gè)方面進(jìn)行拓展：①從實(shí)證的角度考慮成員到部門的演化博弈；②研究復(fù)雜網(wǎng)絡(luò)中的元胞自動機(jī)系統(tǒng)規(guī)則設(shè)計(jì)。