基于KD45閉包的群組角色指派研究

張 巍，仝 茹，吳詩(shī)玨，王子奇，滕少華

（廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006）

新興技術(shù)與制造業(yè)不斷融合應(yīng)用，使得發(fā)展智能制造模式與系統(tǒng)成為了制造業(yè)的發(fā)展需求[1]。在智能制造模式與系統(tǒng)中，人、機(jī)等各類智能體于同一智能制造空間內(nèi)，生產(chǎn)制造需要人、機(jī)等各類智能體協(xié)同工作完成[2]。人機(jī)協(xié)同調(diào)度通常涉及多人、多機(jī)協(xié)作，個(gè)體需協(xié)同執(zhí)行任務(wù)，并在任務(wù)執(zhí)行中扮演關(guān)聯(lián)角色。人機(jī)協(xié)同調(diào)度根據(jù)任務(wù)需求和特點(diǎn)，完成從任務(wù)到多協(xié)作成員的優(yōu)化分配。通過(guò)優(yōu)化分配，能有效保障任務(wù)質(zhì)量管控、成本節(jié)約，提高服務(wù)與盈利水平。

指派是解決任務(wù)分配的重要方法。數(shù)學(xué)建模是指派的關(guān)鍵。在文獻(xiàn)[3-5]中就運(yùn)用了數(shù)學(xué)建模的方式來(lái)進(jìn)行指派。群組角色指派(Group Role Assignment,GRA)是指派建模的通用方法，旨在根據(jù)代理評(píng)價(jià)結(jié)果尋找角色對(duì)代理的最優(yōu)分配[6-8]。群組角色指派的作用已經(jīng)有了很好的驗(yàn)證[6,8-10]。但由于合作約束和沖突約束的存在，計(jì)算復(fù)雜性大幅增加，群組角色指派空間組合爆炸，給建模與計(jì)算帶來(lái)困難。

避免沖突的群組角色指派GRACAR/G[10]就是以沖突矩陣(AC)的形式引入群組角色指派中，有效解決上述問題。但是由于信息不透明問題——沖突信息的不對(duì)稱性或個(gè)體存在認(rèn)知問題、關(guān)系障礙、關(guān)聯(lián)性和推理性不足等問題，獲取的AC矩陣是局部的、不完善的，需要更合理的方法得到。

本文希望通過(guò)KD45邏輯閉包原理解決AC矩陣的不完善問題。在實(shí)際的生產(chǎn)和工作中既存在沖突約束，也存在合作約束，所以本文將合作約束也引入到AC矩陣中，一并通過(guò)KD45邏輯閉包原理進(jìn)行約束關(guān)系的完善。

1 真實(shí)案例

針對(duì)上述問題，本文以一個(gè)真實(shí)案例進(jìn)行描述。在某公司中，首席執(zhí)行官剛剛簽署一個(gè)價(jià)值不菲的合同。他吩咐人力資源經(jīng)理組建一個(gè)由公司員工構(gòu)成的項(xiàng)目組。人力資源經(jīng)理為該項(xiàng)目組草擬一份職位列表，如表1所示。并草擬一份候選人員名單，如表2所示。括號(hào)中的數(shù)字分別是崗位索引和候選人索引。接下來(lái)，人力資源經(jīng)理開展候選人能力評(píng)估工作，吩咐每個(gè)候選人的業(yè)務(wù)主管對(duì)候選人在各個(gè)崗位上進(jìn)行評(píng)估，得到一份候選人在各個(gè)崗位上的評(píng)分表。一些員工可能會(huì)因?yàn)樾愿瘛⒐ぷ黠L(fēng)格、情感問題、政治信仰等不同原因而產(chǎn)生合作意向或沖突意向，即約束。這些合作和沖突約束在工作中對(duì)員工的滿意度和團(tuán)隊(duì)的協(xié)同效率存在很大影響。

表1 崗位需求Table 1 Required positions

表2 候選人在各個(gè)崗位上的評(píng)分Table 2 Candidates and evaluations on position

人力資源經(jīng)理需要考慮這些重要約束。人力資源經(jīng)理需要候選員工填寫一份關(guān)于該候選人在某崗位上對(duì)其他候選員工在某崗位上合作意向或沖突意向的調(diào)查問卷。最后，人力資源經(jīng)理在整合了候選人填寫的調(diào)查問卷后，得到如表3所示的合作和沖突約束表。

表3 合作和沖突關(guān)系表Table 3 Cooperation and conflict

在表3中-1表示沖突關(guān)系，1表示合作關(guān)系。表3中一行數(shù)據(jù)表示位于x崗位的A員工認(rèn)為他與位于y崗位的B員工有合作或沖突關(guān)系。例如，表3的第一行信息表示位于0號(hào)崗位的2號(hào)員工認(rèn)為與位于0號(hào)崗位的8號(hào)員工有合作約束關(guān)系；表3的第二行信息表示位于2號(hào)崗位上的11號(hào)員工認(rèn)為與位于1號(hào)崗位的1號(hào)員工有沖突約束關(guān)系。

合作和沖突約束信息收集越多，越容易促成高效的協(xié)同，避免沖突。人力資源經(jīng)理希望用目前能夠獲得的信息組建一個(gè)更高效的項(xiàng)目組。由于調(diào)查問卷的填寫是采用自愿的方式，調(diào)查問卷填寫都是單方面的，基于員工的主觀意愿，局部的，非對(duì)稱的。局部是因?yàn)閱柧淼奶顚懯亲栽傅?。非?duì)稱是因?yàn)閱T工填寫時(shí)是獨(dú)立的，該員工并不能知道他填寫的合作或沖突對(duì)象是否也持有和他相同的觀點(diǎn)?？梢圆捎媒?jīng)典的邏輯閉包關(guān)系KD45進(jìn)行豐富(在第三部分展開)。并且豐富后的合作和沖突因素信息是目前現(xiàn)有信息能夠推論的約束關(guān)系集合的并集，無(wú)法再次豐富。

例如，位于0號(hào)崗位(項(xiàng)目經(jīng)理)的2號(hào)員工(Abbott)認(rèn)為與位于0號(hào)崗位(項(xiàng)目經(jīng)理)的8號(hào)員工(Bella)有合作約束關(guān)系；位于0號(hào)崗位(項(xiàng)目經(jīng)理)的2號(hào)員工(Abbott)認(rèn)為與位于1號(hào)崗位(高級(jí)程序員)的1號(hào)員工(Tom)有合作約束關(guān)系；則可以推論出位于0號(hào)崗位(項(xiàng)目經(jīng)理)的8號(hào)員工(Bella)認(rèn)為與位于1號(hào)崗位(高級(jí)程序員)的1號(hào)員工(Tom)有合作約束關(guān)系。

據(jù)此人力資源經(jīng)理需要竭盡全力將最合適的候選人指派到最需要他的崗位上。人力資源經(jīng)理考慮后，告訴首席執(zhí)行官這樣的問題可能需要很長(zhǎng)一段時(shí)間才能得到滿意的解決方案。經(jīng)驗(yàn)豐富的首席執(zhí)行官了解情況并允許合理的響應(yīng)時(shí)間。人力資源經(jīng)理指派后，能得到最優(yōu)相對(duì)項(xiàng)目績(jī)效8.34。表2中，加粗?jǐn)?shù)字是被指派的員工及其崗位。

在此場(chǎng)景中，首席執(zhí)行官和人力資源經(jīng)理實(shí)際上遵循E-CARGO模型的子模型考慮合作和沖突的群組角色指派(GRACAR/G)[10]的初始步驟，人力資源經(jīng)理遇到了一個(gè)可基于KD45邏輯閉包完善的約束關(guān)系問題。

2 建模與問題解決

E-CARGO模型是加拿大華裔學(xué)者朱海濱提出的角色協(xié)同計(jì)算模型。E-CARGO模型用9元組∑::=＜C,O,A,M,R,E,G,S0,H＞抽象并描述了協(xié)作系統(tǒng)的組成部分[7,11]。其中C 表示類，O 是對(duì)象，兩者使E-CARGO建?？梢砸朊嫦?qū)ο蟮姆椒?；A(Agent)表示協(xié)作個(gè)體的單元集合；M (Message)表示消息集合； R (Role)表示角色集合(即任務(wù)需求抽象)；E(Environment)用于抽象協(xié)作環(huán)境；G(group)表示群組集合，可用于表示團(tuán)隊(duì)。

根據(jù)E-CARGO模型，可對(duì)第一節(jié)提出的問題建模[6-7]。

定義1[6-7,12-15]role(角色)，r::=＜id,?＞。其中id是角色的標(biāo)識(shí)號(hào)，不同角色id不一致，?是代理扮演角色的要求。

定義2[6-7,12-15]agent(代理)a::=＜id, ? ＞。其中id是代理的標(biāo)識(shí)號(hào)，?是代理?yè)碛械哪芰稀?/p>

進(jìn)一步地，使用A 表示指派為該角色的代理集，即某崗位的候選員工集。 R 表示代理曾經(jīng)扮演過(guò)的角色集。如曾經(jīng)是程序員、高級(jí)程序員等。

定義3[6-7,12-15]角色需求矩陣L，n表示的角色數(shù)量。

在本文案例中，表示項(xiàng)目完成此任務(wù)需要的角色種類及數(shù)量。L[j](0≤j＜n)表示j號(hào)角色需要的數(shù)量。

定義4[6-7,12-15]代理資格評(píng)估矩陣Q[i,j](0≤i＜m,0≤j＜n)，m表示候選代理數(shù)量。

在本文案例中，表示候選員工在各個(gè)崗位上的工作能力評(píng)分值，Q[i,j]∈[0,1]。

定義5 代理角色合作與沖突矩陣ACC，是一個(gè)(m×n)×(m×n)的矩陣。

定義6[6-7,12-15]角色分配矩陣T[i,j](0≤i＜m, 0≤j＜n)表示該角色是否被分配給某個(gè)代理，T[i,j]∈{0,1}。

在本文案例中，T[i,j]=1表示為i號(hào)員工分配j號(hào)崗位，T[i,j]=0表示沒有為i號(hào)員工分配j號(hào)崗位。

定義7 群組角色指派的線性求解，即尋找一個(gè)可行的分配矩陣T。

針對(duì)第一節(jié)提出的問題，提出如下約束函數(shù)目標(biāo)函數(shù)：

因?yàn)橐哉{(diào)查問卷的方式收集員工主觀意愿信息，并進(jìn)一步整合得到ACC矩陣，所以ACC矩陣是局部的，非對(duì)稱。ACC矩陣的局部性造成了該矩陣的稀疏。表4的合作和沖突約束矩陣就是第二部分案例中員工主觀信息整合得到的一個(gè)ACC矩陣的一部分。從表4可知，ACC矩陣是非常稀疏的矩陣。本文只需要用到其中的非零元素。故可以將其中的非零元素提取出來(lái)減少計(jì)算時(shí)間。

表4 合作或沖突約束表1)Table 4 Cooperation or conflict factors

第一節(jié)的指派問題是一個(gè)非線性的規(guī)劃問題[16-18]，也是二次分配問題的一個(gè)特殊情況[19-20]。優(yōu)化第一節(jié)提出的問題還有很多方法，如文獻(xiàn)[21]通過(guò)Pareto差熵控制種群的交流來(lái)進(jìn)行優(yōu)化。在文獻(xiàn)[22]中，朱海濱提出一種很巧妙的優(yōu)化類似本文的非線性規(guī)劃問題，即引入一個(gè)新的未知數(shù)來(lái)解決這個(gè)問題。本文學(xué)習(xí)這種方式作出了以下定義。

定義9 約束效果矩陣T A[k] (0≤k＜nc)表示第k個(gè)約束關(guān)系是否發(fā)揮作用，T A[k]∈{0,1}。T A[k]=1表示第k個(gè)約束發(fā)揮作用；T A[k]=0表示第k個(gè)約束沒有發(fā)揮作用。

針對(duì)實(shí)例，依照上述定義，得到關(guān)系矩陣ACC、資格評(píng)估(Q)、分配矩陣(T)與角色需求矩陣(L)

3 基于KD45閉包的GRA

3.1 KD45邏輯

約束矩陣是由員工基于自愿的方式填寫的調(diào)查問卷整理得到。由于這種獲得方式，約束矩陣ACC是稀疏的、局部的和非對(duì)稱的。而約束矩陣ACC在團(tuán)隊(duì)的協(xié)同工作中發(fā)揮重要作用。所以約束矩陣越完整，群組角色指派時(shí)考慮會(huì)越全面，在團(tuán)隊(duì)協(xié)同工作時(shí)才能獲取更快的效率和更多的收益。

在人機(jī)協(xié)同時(shí)，利用模態(tài)邏輯從語(yǔ)義和公理上刻畫了信念、信息獲取和信任之間的關(guān)系。一個(gè)典型的基本的系統(tǒng)公理中，可以這么理解，如果代理i相信代理j告訴他的真相p，他相信代理j在真相p的判斷，則他相信真相p。KD45就是模態(tài)邏輯中的經(jīng)典的認(rèn)知邏輯。

3.2 KD45閉包算法

KD45公理及其對(duì)應(yīng)定理如表5所示。

表5 KD45公理及其對(duì)應(yīng)定理Table 5 KD45 axiom and its corresponding theorem

公理K存在于符合Kripke關(guān)系語(yǔ)義的關(guān)系中。本文的應(yīng)用場(chǎng)景就存在公理K。

公理D也就是和持續(xù)性。事物之間都有聯(lián)系，沒有孤立存在的事物。代理也是，它可能有與其沖突的代理或者合作的代理。

公理4指的是傳遞性。如果存在于事物x和事物y之間的關(guān)系與存在于事物y和事物z的關(guān)系相同，那么根據(jù)公理4，可以推論出事物x和事物z之間也存在上述關(guān)系。即如果代理x認(rèn)為與代理y之間存在合作關(guān)系，代理y認(rèn)為與代理z之間存在合作關(guān)系，則可以推論出代理x應(yīng)該認(rèn)為與代理z之間存在合作關(guān)系。

本文定義了一些特殊符號(hào)，來(lái)更好描述算法。

G為經(jīng)過(guò)關(guān)系分類后的同類關(guān)系的有向連通圖。V是G中的頂點(diǎn)的集合。E是G中的邊的集合。(a,b)表示起始頂點(diǎn)為a，終點(diǎn)為b的邊。s為起始頂點(diǎn)，u為中間頂點(diǎn)，v為終點(diǎn)。R表示兩兩可達(dá)的頂點(diǎn)對(duì)集合。

算法1：基于公理4的關(guān)系閉包算法。

算法1基于同類關(guān)系集的傳遞性進(jìn)行完善。將可以通過(guò)傳遞閉包推論出的該類隱性關(guān)系挖掘出來(lái)，并將其加入到現(xiàn)有的關(guān)系集中。

補(bǔ)充定義了以下特殊符號(hào)，以更好描述算法：V′(x)是G中的x頂點(diǎn)的鄰接頂點(diǎn)集合；l表示集合中元素個(gè)數(shù)。

算法 2：基于公理5的關(guān)系閉包算法。

公理5指的是歐性。假設(shè)存在于事物x和事物y之間的關(guān)系與存在于事物x和事物z的關(guān)系相同，那么根據(jù)公理5，可以推論出事物y和事物z之間也存在上述關(guān)系。即如果代理x認(rèn)為與代理y之間存在合作關(guān)系，代理x認(rèn)為與代理z之間存在合作關(guān)系，則可以推論出代理y應(yīng)該認(rèn)為與代理z之間存在合作關(guān)系，或者是代理z應(yīng)該認(rèn)為與代理y之間存在合作關(guān)系。

算法2基于同類關(guān)系集的歐性進(jìn)行完善。將可以通過(guò)歐性閉包推論出的該類隱性關(guān)系挖掘出來(lái)，并將其加入到現(xiàn)有的關(guān)系集中。

KD45是模態(tài)邏輯中的經(jīng)典的認(rèn)知邏輯。約束關(guān)系就是某候選員工對(duì)其他候選人在某崗位上的認(rèn)知。合作約束關(guān)系和沖突約束關(guān)系都符合KD45邏輯閉包。下面提出來(lái)基于上述算法1和算法2的KD45邏輯閉包算法。

算法3：基于KD45邏輯的關(guān)系閉包算法。

針對(duì)第一節(jié)所舉出的實(shí)際應(yīng)用場(chǎng)景，在KD45-GRACAR中的團(tuán)隊(duì)相對(duì)績(jī)效為10.52。表2中劃線部分為指派結(jié)果。第二節(jié)矩陣實(shí)例集中的T矩陣為它的指派矩陣。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)過(guò)程

為了獲得一個(gè)實(shí)際的解決方案，使用ILOG包來(lái)解決基于KD45邏輯的群組角色指派問題，這與IBM ILOG CPLEX優(yōu)化工作室最初使用的優(yōu)化編程語(yǔ)言(OPL)不同。通過(guò)設(shè)計(jì)Java程序來(lái)使用包可以繞過(guò)OPL編譯器，從而獲得更好的性能。

要使用ILOG包提供解決方案，主要工作是收集4個(gè)必需的元素，并將目標(biāo)和約束轉(zhuǎn)換為ILOG所需的表單。

步驟1：將ACC關(guān)系矩陣進(jìn)行KD45閉包處理。

對(duì)于每一組，在定義范圍內(nèi)隨機(jī)選擇以下數(shù)據(jù)。(1)Q[i,j] ∈ [0, 1](0 ≤i＜m, 0 ≤j＜n)，即資格評(píng)估矩陣中的元素；

(2)ACC[k,4] ∈ {1，-1}(0≤k＜nc)，即合作或沖突

(3)L[j](0 ≤j＜n), 1 ≤L[j] ≤m/n使得m≥na。

對(duì)于每一組，都收集一下數(shù)據(jù)項(xiàng)：

(1)σ1考慮合作和沖突因素的群組角色指派最大相對(duì)績(jī)效組

(2)σ2基于KD45邏輯考慮合作和沖突因素的群組角色指派最大相對(duì)績(jī)效組

為了觀察不同構(gòu)型之間的差異，本文還改變了顯著性數(shù)nc=mx，其中x從1到5，一步為1。為了使數(shù)據(jù)可信，為每個(gè)nc創(chuàng)建隨機(jī)組。最后，計(jì)算每個(gè)數(shù)據(jù)項(xiàng)的100個(gè)數(shù)字的平均值。表6展示了16人團(tuán)隊(duì)和17人團(tuán)隊(duì)的仿真結(jié)果。

表6 團(tuán)隊(duì)的績(jī)效對(duì)比Table 6 Comparison of team performance

4.2 規(guī)模性實(shí)驗(yàn)

表7 實(shí)驗(yàn)配置Table 7 Configuration for the experiment

圖1 KD45閉包時(shí)間趨勢(shì)(m=20, n=6)Fig.1 Time trends of KD45 closure (m=20, n=6)

圖2 KD45閉包補(bǔ)充效果(m=20, n=6)Fig.2 Complementary effects of KD45 closure (m=20, n=6)

第二個(gè)實(shí)驗(yàn)驗(yàn)證基于KD45邏輯閉包的群組角色指派方法(KD45-GRA)的實(shí)用性，展示KD45閉包的時(shí)間趨勢(shì)。在每個(gè)步驟中，重復(fù)測(cè)試100輪。在每一輪Q,L,ACC都是隨機(jī)產(chǎn)生的(均勻分布)，其中m通過(guò)一步從10變化到55，步長(zhǎng)為5，n為m/6，nc為mx。圖3、圖4和圖5分別為KD45閉包時(shí)間趨勢(shì)圖、指派時(shí)間趨勢(shì)圖和總實(shí)驗(yàn)時(shí)間趨勢(shì)圖。隨著m、n和nc的變化，總實(shí)驗(yàn)的時(shí)間主要由指派時(shí)間組成，受指派時(shí)間影響較大。圖6為考慮沖突的群組角色指派與基于KD45邏輯閉包的群組角色指派方法的相對(duì)團(tuán)隊(duì)績(jī)效對(duì)比圖。隨著m，n的增長(zhǎng)，即候選人數(shù)和崗位的增長(zhǎng)，KD45邏輯閉包算法對(duì)于最后的指派績(jī)效越來(lái)越重要。

圖3 KD45閉包時(shí)間趨勢(shì)Fig.3 Time trends of KD45 closure

圖4 指派時(shí)間趨勢(shì)Fig.4 Allocated time trends

圖5 總時(shí)間趨勢(shì)Fig.5 Overall time trends

圖6 相對(duì)團(tuán)隊(duì)績(jī)效Fig.6 Relative time performance

5 總結(jié)

上萬(wàn)次不同規(guī)模下的仿真實(shí)驗(yàn)表明，本文提出對(duì)群組角色指派的約束關(guān)系集完善后再進(jìn)行群組角色指派方法是可行的、有效的。通過(guò)KD45邏輯閉包算法對(duì)約束關(guān)系集進(jìn)行了補(bǔ)充與完善，從而優(yōu)化了群組角色指派模型。利用相關(guān)方法，能高效解決信息不透明情況下，難以獲取協(xié)作與沖突約束的人機(jī)協(xié)同任務(wù)分配及其優(yōu)化問題。

基于KD45邏輯閉包的群組角色指派可能需要沿著以下路線進(jìn)一步的研究。

(1) 基于KD45邏輯的群組角色指派中的合作和沖突約束可以是小數(shù)。即每個(gè)合作約束和沖突約束對(duì)損益的效果不同。這一問題在理論和實(shí)踐上都可能是非常復(fù)雜的。

(2) 可以考慮群組角色指派(GRA)的附加約束，例如，代理對(duì)角色的偏好，管理員對(duì)角色分配的偏好。

(3) 可以考慮合作約束和沖突約束的閾值。閾值分別為多少時(shí)，會(huì)產(chǎn)生最好的協(xié)作效率，即對(duì)社會(huì)學(xué)的很多理論進(jìn)行試驗(yàn)。從科學(xué)的角度分析問題，指導(dǎo)實(shí)際生活中的決策。

(4) 最后需要開發(fā)更有針對(duì)性的方法，將團(tuán)隊(duì)成員的主觀意見轉(zhuǎn)化為數(shù)值，以便應(yīng)用所提出的方法進(jìn)行角色分配。