基于殘缺歷史數(shù)據(jù)信息的需方參與的協(xié)同設(shè)計沖突消解博弈模型

高長元，欒兆東，張樹臣,王 京

(哈爾濱理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院 管理信息系統(tǒng)實驗室，黑龍江 哈爾濱 150040)

0 引言

協(xié)同設(shè)計[1]指在計算機(jī)的支持下，各設(shè)計小組圍繞一個設(shè)計項目承擔(dān)相應(yīng)的設(shè)計任務(wù)，最終得到符合要求的設(shè)計結(jié)果。由于協(xié)同設(shè)計各個小組開發(fā)產(chǎn)品時的設(shè)計角度、評價標(biāo)準(zhǔn)、領(lǐng)域知識不盡相同，協(xié)同設(shè)計過程中會產(chǎn)生沖突，從某種意義上說，協(xié)同設(shè)計過程就是一個沖突產(chǎn)生和消解的過程[2]。

目前不少學(xué)者對協(xié)同設(shè)計過程中的沖突消解問題進(jìn)行了研究。Avruch等[3]總結(jié)了一系列協(xié)同設(shè)計過程中的沖突消解方法；Chen等[4]針對多類型沖突問題提出一種混合沖突消解方法；Wang等[5]提出CCR(concurrency and coordination runtime)方法，不但解決了實時協(xié)同編輯系統(tǒng)中存在的問題，而且可以為用戶提供合適的沖突消解方案；Yu等[6]為防止協(xié)同設(shè)計過程中設(shè)計者的操作沖突，利用X3D操作模型提出一種基于對稱的協(xié)同設(shè)計框架；Bao等[7]對沖突檢測和沖突消解技術(shù)進(jìn)行研究，建立了一套完整的沖突管理體系；Yao等[8]對工業(yè)化住宅的協(xié)同設(shè)計問題進(jìn)行了分類，提出一種基于BIM(building information modeling)的沖突消解方法；Fan等[9]為了使協(xié)同設(shè)計系統(tǒng)中的設(shè)計變更數(shù)據(jù)流自動化，提高了協(xié)同設(shè)計系統(tǒng)的運行效率；談龍兵等[10]分析了協(xié)同設(shè)計過程中沖突的特點，提出一種混合型沖突消解模型；孟秀麗等[11]從方案層次進(jìn)行沖突消解，提出一種基于多目標(biāo)決策的協(xié)同設(shè)計過程中的沖突消解方法；陳洪轉(zhuǎn)等[12]基于經(jīng)典沖突模型提出一種具有超級支配者的超沖突分析模型；王麗萍等[13]針對協(xié)同設(shè)計過程中的目標(biāo)沖突問題，提出一種基于模糊集和多目標(biāo)進(jìn)化算法的沖突消解方法；楊亢亢等[14]針對無法準(zhǔn)確全面檢測協(xié)同設(shè)計沖突的問題，提出一種基于約束的沖突檢測模型；Yin等[15]提出一種基于模糊物元粒子群算法的沖突協(xié)商模型，利用模糊物元將多目標(biāo)問題轉(zhuǎn)換為單目標(biāo)問題，然后通過粒子群算法進(jìn)行求解；姚剛[16]提出一種BIM軟件檢測的沖突消解方法；陳立杉等[17]為解決同步協(xié)同設(shè)計技術(shù)面臨的資源沖突，提出一種基于相關(guān)度的標(biāo)準(zhǔn)滿意度沖突消解策略；陳永當(dāng)?shù)萚18]認(rèn)為沖突產(chǎn)生的原因是知識缺乏有效溝通，從知識協(xié)同的角度提出知識推理與推送的集成化沖突消解方法。

上述文獻(xiàn)沒有針對具體的沖突環(huán)節(jié)對沖突進(jìn)行消解，而且都是先將多目標(biāo)規(guī)劃沖突問題轉(zhuǎn)換為單目標(biāo)，然后利用經(jīng)典決策理論方法進(jìn)行求解，這種間接性的算法在進(jìn)行目標(biāo)轉(zhuǎn)換時，往往會丟失其中的某些目標(biāo)，無法求出全部最優(yōu)解。在實際設(shè)計過程中，不同的設(shè)計小組對自己負(fù)責(zé)的設(shè)計部分可以提供最優(yōu)的方案，但是無法保證整體設(shè)計最優(yōu)，然而求出設(shè)計問題的最佳設(shè)計方案對整個沖突消解非常重要。通過總結(jié)發(fā)現(xiàn)，鮮有文獻(xiàn)從歷史數(shù)據(jù)信息出發(fā)分析如何消解沖突，而歷史數(shù)據(jù)信息對于整個設(shè)計方案的參考價值非常重要甚至不可或缺，在協(xié)同設(shè)計過程中如何通過歷史數(shù)據(jù)信息建立一個可參考的最佳方案顯得尤為重要。因此本文提出一種基于歷史數(shù)據(jù)的協(xié)同設(shè)計博弈模型，通過博弈的思想將工程問題轉(zhuǎn)換為博弈問題進(jìn)行優(yōu)化求解。

1 需方參與的協(xié)同設(shè)計沖突分析

從沖突產(chǎn)生的原因出發(fā)，本文將需方參與的協(xié)同設(shè)計沖突劃分為3類：①設(shè)計沖突，指協(xié)同設(shè)計過程中有關(guān)產(chǎn)品相互矛盾、相互對立的關(guān)系，設(shè)計沖突又分為結(jié)果沖突和目標(biāo)沖突，前者指某一決策變量違反約束關(guān)系的情況，后者指設(shè)計方案或者屬性無法同時滿足特定目標(biāo)的情況；②過程沖突，指產(chǎn)品開發(fā)過程中，由于在時間和空間上的信息傳遞存在矛盾而產(chǎn)生的沖突；③質(zhì)量成本沖突，在需方參與的協(xié)同設(shè)計過程中，供需雙方都以最終形成的設(shè)計成果可交付為目標(biāo)，然而以該目標(biāo)為基礎(chǔ)，需求方更希望支付更少的資金而達(dá)到一個較好的目標(biāo)，在項目收入一定的情況下，供方更希望在誤差允許范圍內(nèi)以最大化誤差交付設(shè)計成果，由此引發(fā)供需雙方設(shè)計成果的質(zhì)量成本沖突?；诖?，本文引入博弈理論，將協(xié)同設(shè)計過程中的需方和供方(設(shè)計小組)之間的質(zhì)量成本沖突問題轉(zhuǎn)換為動態(tài)聯(lián)盟下的博弈問題，通過多元回歸將不完備的博弈效用矩陣完備化，最后通過聯(lián)盟博弈中的Shapley值法(Shapley Value Method, SVM)對矩陣進(jìn)行求解，得到一種質(zhì)量成本綜合最優(yōu)的最佳設(shè)計方案，該方案在某一個質(zhì)量標(biāo)準(zhǔn)下的生產(chǎn)成本相對最低，從而消除了需方與供方(設(shè)計小組)之間的質(zhì)量成本沖突。

2 博弈效用矩陣的構(gòu)建

博弈理論[19]是為了解決沖突環(huán)境中各博弈方之間的行為決策均衡問題而產(chǎn)生的理論。該理論通過抽象復(fù)雜競爭環(huán)境中的必要因素構(gòu)建數(shù)學(xué)模型，從博弈的角度詮釋結(jié)果的合理性，為解決工程環(huán)境中的多目標(biāo)優(yōu)化問題開拓了新的思路[20]。在求解多目標(biāo)優(yōu)化問題時，首先需要建立博弈模型，博弈模型可以用一種博弈效用矩陣[21]表示，以兩博弈方為例，用αi∈R1(i=1,2,…,p),βj∈R2(j=1,2,…,q)分別表示博弈雙方的策略選擇，其中R1,R2表示可選擇的策略集合，對于每一組策略組合(αi,βj)，各博弈方的效用分別為u1(αi,βj)和u2(αi,βj)。效用矩陣

β1β2…βq

(1)

利用博弈理論解決協(xié)同開發(fā)過程中的沖突問題的關(guān)鍵在于將沖突問題轉(zhuǎn)換為基于博弈理論的數(shù)學(xué)模型，提取博弈雙方、各博弈方策略及其效應(yīng)。模型構(gòu)建流程如圖1所示。

為完成產(chǎn)品開發(fā)項目，需方與供方(設(shè)計小組)組建了動態(tài)聯(lián)盟，因為在協(xié)同設(shè)計過程中需求方注重設(shè)計產(chǎn)品的質(zhì)量，而供方注重產(chǎn)品的成本，所以需方與供方間存在博弈行為。本文將動態(tài)聯(lián)盟下裝配產(chǎn)品的質(zhì)量需求(P1)和成本需求(P2)作為博弈主體，將零件的質(zhì)量水平(S1)和成本水平(S2)視為博弈方策略，將尺寸鏈裝配函數(shù)和“成本-公差”函數(shù)量綱化后作為博弈雙方的效應(yīng)函數(shù)，裝配產(chǎn)品的質(zhì)量水平(Z1)和成本水平(Z2)作為博弈方效用，建立博弈模型。因為各博弈方的策略與效應(yīng)是根據(jù)當(dāng)前環(huán)境抽象出來的，所以矩陣具有一定的柔性，當(dāng)某一博弈方策略隨環(huán)境發(fā)生變化時，矩陣中所對應(yīng)的策略會發(fā)生改變，矩陣的求解結(jié)果也會隨之變化。博弈模型如表1所示。

表1 博弈效應(yīng)矩陣

續(xù)表1

3 基于多元回歸的博弈效用矩陣完備化

由于搜集到的歷史數(shù)據(jù)是殘缺的，本文通過多元回歸擬合[22]將效用矩陣完備化。在協(xié)同設(shè)計過程中，質(zhì)量與成本數(shù)據(jù)的關(guān)系可用多元線性回歸模型模擬。例如，因變量y和p個自變量X1,X2,…,XP的n次觀測值如表2所示，其中Xij表示具體的觀測值。

表2 觀測數(shù)據(jù)表示

(2)

(3)

(4)

(5)

(6)

(7)

(8)

表3 完備的博弈效應(yīng)矩陣

(2)殘差圖上點的分布是否無規(guī)律。

4 基于Shapley值的博弈模型求解

協(xié)同開發(fā)過程中的供需雙方均以利益最大化為目標(biāo)，因此本文采用合作博弈[24]中的聯(lián)盟博弈法對模型進(jìn)行求解。其中SVM求解這類問題具有一定的優(yōu)勢，其能夠較全面地考慮不同博弈方之間的沖突，從而進(jìn)行綜合優(yōu)化與均衡協(xié)調(diào)，并且能夠求得唯一的Pareto最優(yōu)解。

4.1 聯(lián)盟博弈

聯(lián)盟博弈是以總體利益為基礎(chǔ)尋求各自利益最大化，通常用一個二元組G=N,v表示N上的聯(lián)盟博弈，其中：聯(lián)盟可由集合N的任何非空子集表示，N={1,2,…,n}；v表示特征函數(shù)。對于集合N的任意子集L都有一個實值函數(shù)v(s)滿足：①v(?)=0；②對所有L,T∈2N(即L,T?N)，若L∩T=?，則v(L∪T)≥v(L)+v(T)。

4.2 Shapley值的計算及其工程應(yīng)用意義

SVM的計算步驟如下：

(1)確定博弈方聯(lián)盟集合及子集N,L?N。

(2)計算聯(lián)盟特征函數(shù)。以本文所討論的兩博弈方博弈為例，單個博弈方(如P1)的博弈效應(yīng)矩陣可轉(zhuǎn)化為零和博弈效應(yīng)矩陣，即

β1β2…βn

(9)

該式滿足u2=-u1，故省略了u2。

根據(jù)Von Neumann的最小最大值準(zhǔn)則，稱N(αi,βj)為鞍點，當(dāng)且僅當(dāng)?(i*,j*),1≤i*≤m,1≤j*≤n，有

(10)

(11)

(3)設(shè)X=(x1,x2,…,xn)=(φ1(v),φ2(v),…,φn(v))為聯(lián)盟博弈的一種分配方案，xi的計算方法為

[v(S)-v(S(〗i})]。

(12)

(4)假設(shè)Shapley值向量為Φ=(φ1,φ2,…,φn)，效用組合構(gòu)成的向量為U=(u1,u2,…,un)，定義范數(shù)

d=‖U-Φ‖。

(13)

結(jié)合上述分析，可以根據(jù)協(xié)同開發(fā)過程中的所有質(zhì)量、成本效用組合結(jié)果，給出最能反映兩者之間沖突關(guān)系的分配方案，表示質(zhì)量和成本綜合最優(yōu)的一種貢獻(xiàn)度估計。本文通過一種基于貢獻(xiàn)度控制范圍的定量的貢獻(xiàn)度評估方法來計算各博弈方貢獻(xiàn)度。以式(1)的博弈效用矩陣為例，定義博弈方Pk在策略組合(αm,βn)下的貢獻(xiàn)度為

(14)

式中：i=1,2，m=1,2,…,p，n=1,2,…,q，p,q為各博弈方的策略數(shù)。

當(dāng)博弈方P2選定某策略β*時，博弈方P1的貢獻(xiàn)度控制范圍為

Scal(p1;β*)=maxCont[p1;(αm,β*)]-

minCont[p1;(αm,β*)]。

(15)

將計算結(jié)果繪制為柱狀圖，從而更直接地得到SVM的最優(yōu)效用組合。

5 實例驗證

以某數(shù)控車床主軸設(shè)計為例說明多元回歸在博弈建模中的應(yīng)用，主軸精度設(shè)計如圖2所示，圖中MP1，MP2，MP3是主軸上的測點，零件生產(chǎn)后主軸與其外接零件之間需滿足質(zhì)量-成本要求。該車床主軸的歷史數(shù)據(jù)信息如表4所示。

表4 主軸設(shè)計歷史數(shù)據(jù)

主軸共21個批次，采用主軸與內(nèi)孔的公差為主軸的質(zhì)量水平，零件的獲得成本為主軸的成本水平，整體契合度水平(由單位分項工程質(zhì)量檢驗評定表進(jìn)行打分)為主軸裝配后的產(chǎn)品質(zhì)量水平，工程實際中契合度分?jǐn)?shù)越高，質(zhì)量越好。

將質(zhì)量需求與成本需求作為博弈方，分別記為P1和P2；主軸的誤差與成本水平作為博弈方策略，分別記為S1,S2；主軸裝配區(qū)域整體契合度水平y(tǒng)1和裝配總成本y2作為博弈方效用。建立初始博弈模型為G={pi;si;ui(i=1,2)}，對應(yīng)的初始效應(yīng)矩陣如表5所示。

表5 初始效應(yīng)矩陣

續(xù)表5

通過多元回歸分析將表5完備化，采用MATLAB求解這一問題可得y1和y2對S1和S2的經(jīng)驗回歸方程為：

(16)

(17)

由圖3可見，殘差圖上的點呈無規(guī)律分布，利用經(jīng)驗回歸方程計算出需要補(bǔ)充的策略組合對應(yīng)的效用組合為(u1,u2),得到完備的效應(yīng)矩陣如表6所示。

表6 完備的效應(yīng)矩陣

裝配產(chǎn)品質(zhì)量需求(P1)-S1裝配產(chǎn)品成本需求(P2)-S2123456S2=500S2=520S2=530S2=540S2=555S2=5601 S1=388 80392 83892 79589 8072 S1=683 88990 88782 84588 8263 S1=1086 79985 80282 83585 82386 8094 S1=1484 86290 87486 82186 81485 8025 S1=1890 84386 78687 82285 8756 S1=2486 82885 80286 81088 880

對y1和y2進(jìn)行量綱統(tǒng)一化處理，得到博弈雙方的效用函數(shù)ui：

(18)

式中n為所有可行策略組合的數(shù)量，n=26。通過式(18)將裝配產(chǎn)品質(zhì)量需求與裝配產(chǎn)品成本需求轉(zhuǎn)換為博弈效用矩陣，如表7所示。

表7 量綱統(tǒng)一化后的博弈效用矩陣

續(xù)表7

本文分別采用理想點法和Nash均衡法(Nash Equilibrium Method, NEM)進(jìn)行求解[21]，再與SVM比較來驗證其有效性和可靠性。通過理想點法(Ideal Point Method, IPM)求得質(zhì)量和成本博弈方的最優(yōu)效用組合(u1,u2)=(1.033,1.052)，最優(yōu)策略組合為(s1,s2)=(14,520)，如表8所示。

表8 SVM與其優(yōu)化方法的比較

通過NEM求得3個Nash均衡點：

(1)NEM-1 最優(yōu)效用組合為(u1,u2)=(0.982,0.977)，最優(yōu)策略組合為(s1,s2)=(14,555)。

(2)NEM-2 最優(yōu)效用組合為(u1,u2)=(0.958,1.082)，最優(yōu)策略組合為(s1,s2)=(6,530)。

(3)NEM-3 最優(yōu)效用組合為(u1,u2)=(0.994,0.993)，最優(yōu)策略組合為(s1,s2)=(14,530)。

由MATLAB仿真得到圖4，圖4a和圖4b分別是主軸公差、生產(chǎn)成本方案組合(s1，s2)影響下的適應(yīng)度打分與生產(chǎn)總成本的變化，可知對于精度由低到高逐漸變化的公差區(qū)域，生產(chǎn)總成本曲面圖較為平滑，而適應(yīng)度打分曲面圖的波動較大。另一方面，由4c可見，隨著所打分?jǐn)?shù)的增加，制造成本總體呈現(xiàn)上升的趨勢，NEM得到的均衡點并非Pareto最優(yōu)，而IPM法求得的最優(yōu)解雖然達(dá)到全局最優(yōu)，但是它沒有考慮博弈雙方的內(nèi)在聯(lián)系，一個極小的波動就會使解變得不穩(wěn)定。SVM解得的均衡點始終保持在(0.983,0.998)，其存在唯一的均衡點是因為數(shù)據(jù)模型微小的變化不足以影響博弈雙方的效用關(guān)系，所以博弈雙方對聯(lián)盟的影響不會變化。通過式(14)計算得到博弈雙方所有策略組合下的貢獻(xiàn)度，進(jìn)一步解釋了SVM所得的最優(yōu)解具有穩(wěn)定性，貢獻(xiàn)度矩陣如表9所示。

表9 貢獻(xiàn)度矩陣 %

通過式(15)計算P1在P2選定各個策略時的貢獻(xiàn)度控制范圍，以及P2在P1選定各個策略時的貢獻(xiàn)度控制范圍，并繪制柱狀圖，如圖5所示。

6 結(jié)束語

本文針對協(xié)同設(shè)計過程中存在的質(zhì)量成本沖突問題，引入博弈理論，將協(xié)同設(shè)計過程中的質(zhì)量成本沖突問題轉(zhuǎn)換為博弈問題，抽象博弈方、博弈方策略和博弈方策略，構(gòu)建了基于多元回歸分析的完備博弈效用矩陣，然后用SVM對博弈效用矩陣進(jìn)行求解，提出一種貢獻(xiàn)度控制范圍的定量評估方法，并通過仿真實例與其他求解方法進(jìn)行比較，驗證了該方法的有效性。目前對沖突消解的研究尚處于探索階段，本文從博弈的角度出發(fā)，提出一套公平合理的質(zhì)量和成本沖突的解決方案，該方案能夠為供應(yīng)商管理提供決策支持。