社會化產(chǎn)品開發(fā)眾包設(shè)計任務(wù)間加權(quán)網(wǎng)絡(luò)建模與模塊劃分

劉電霆，胡浩平，吳丹玲

(1.桂林理工大學(xué) 機械與控制工程學(xué)院，廣西 桂林 541004；2.深圳信息職業(yè)技術(shù)學(xué)院 財經(jīng)學(xué)院，廣東 深圳 518172)

社 會 化 產(chǎn) 品 開 發(fā)(social product development,SPD)[1]借助社會化的計算技術(shù)、工具和媒體，為充分利用企業(yè)及社會上的人才、技術(shù)和資源等，進行開放式創(chuàng)新創(chuàng)造了機遇。而采用眾包(crowdsourcing)[2]技術(shù)進行設(shè)計是SPD的主要特征之一，稱之為眾包設(shè)計[3]。

當(dāng)代產(chǎn)品一般比較復(fù)雜，采用眾包設(shè)計方式時，需要將總設(shè)計任務(wù)劃分為若干子任務(wù)，通過眾包平臺分配給合適的承包方，便于設(shè)計工作順利開展。因此，產(chǎn)品眾包設(shè)計任務(wù)模塊的合理劃分，就成為了眾包式社會化產(chǎn)品開發(fā)過程的首要關(guān)鍵問題[1，3-4]。

一般來說，產(chǎn)品眾包設(shè)計任務(wù)模塊的劃分，首先采用功能分解法和結(jié)構(gòu)分解法，進行產(chǎn)品任務(wù)分解[5]。然后，采用設(shè)計結(jié)構(gòu)矩陣(design structure matrix, DSM)[6]及其改進的區(qū)間數(shù)設(shè)計結(jié)構(gòu)矩陣IDSM[7]和模糊設(shè)計結(jié)構(gòu)矩陣FDSM[8]等對產(chǎn)品零部件的原子設(shè)計任務(wù)之間的關(guān)系進行描述；再依據(jù)原子設(shè)計任務(wù)之間的關(guān)系的緊密度，按一定的規(guī)則進行重組，得到產(chǎn)品設(shè)計的若干任務(wù)模塊。最后，對這些任務(wù)模塊進行描述，包裝構(gòu)成相應(yīng)的產(chǎn)品眾包設(shè)計任務(wù)。

由于DSM的直觀性不強，人們尋找其他方法來描述原子設(shè)計任務(wù)間關(guān)系。最常采用的是圖論的方法，如Duin等[9]和胡從林等[10]用有向圖表示原子設(shè)計任務(wù)間關(guān)系，從有向圖中得到各原子設(shè)計任務(wù)間的可達矩陣，再由可達矩陣對原子設(shè)計任務(wù)進行耦合聚類劃分為若干任務(wù)模塊。陳健等[11]采用權(quán)重有向圖表示原子設(shè)計任務(wù)間信息交互的強弱關(guān)系，并將原子設(shè)計任務(wù)信息交互強弱關(guān)系定量地映射轉(zhuǎn)化為設(shè)計結(jié)構(gòu)矩陣DSM，再由DSM計算得出各原子設(shè)計任務(wù)間耦合關(guān)系，并重組為若干任務(wù)模塊。

采用圖論法來描述原子設(shè)計任務(wù)之間的關(guān)系，直觀明了，易于理解。但是，目前還是要轉(zhuǎn)化為可達矩陣或設(shè)計結(jié)構(gòu)矩陣等；并與采用設(shè)計結(jié)構(gòu)矩陣及其改進形式描述原子設(shè)計任務(wù)之間的關(guān)系一樣，最終都要計算轉(zhuǎn)為各原子設(shè)計任務(wù)間的定量耦合關(guān)系，由此來進行聚類重組為任務(wù)模塊。

眾所周知，對于產(chǎn)品開發(fā)，尤其是新產(chǎn)品的設(shè)計或?qū)ΜF(xiàn)有產(chǎn)品的改型設(shè)計，原子設(shè)計任務(wù)之間的關(guān)系、信息交流程度難以準(zhǔn)確把握，常具有含糊性。本文研究采用11級標(biāo)度加權(quán)網(wǎng)絡(luò)來描述其關(guān)系，主要依據(jù)任務(wù)模塊內(nèi)聚合度、模塊間耦合度、協(xié)作設(shè)計難度等對原子設(shè)計任務(wù)進行聚類，重組為若干眾包設(shè)計任務(wù)模塊。

1 基于加權(quán)網(wǎng)絡(luò)的產(chǎn)品眾包設(shè)計任務(wù)關(guān)系建模與模塊劃分方法

1.1 劃分產(chǎn)品眾包設(shè)計任務(wù)模塊原則與過程

現(xiàn)代產(chǎn)品變得越來越復(fù)雜，在社會化產(chǎn)品開發(fā)中，復(fù)雜的產(chǎn)品常分解為數(shù)量合理、功能獨立和結(jié)構(gòu)完整的模塊。而采用眾包設(shè)計時，需要適當(dāng)控制任務(wù)模塊的粒度，以便能順利地由設(shè)計方接受。

根據(jù)產(chǎn)品模塊的定義和社會化開發(fā)模式的特點，眾包設(shè)計任務(wù)模塊劃分原則可確定為滿足該產(chǎn)品模塊功能獨立性和結(jié)構(gòu)完整性；眾包設(shè)計任務(wù)模塊內(nèi)的原子設(shè)計任務(wù)間信息交流聚合度盡量大，模塊間信息交流耦合度盡可能小，且協(xié)作設(shè)計難度盡量低[7]。

因此，社會化產(chǎn)品開發(fā)中眾包設(shè)計任務(wù)模塊劃分的主要步驟如下。

1) 按功能結(jié)構(gòu)信息交流程度，把產(chǎn)品分解成若干基本單元或稱為零部件，并將這些零部件的設(shè)計設(shè)為原子設(shè)計任務(wù)。

2) 按功能和結(jié)構(gòu)關(guān)聯(lián)，計算產(chǎn)品零部件相關(guān)度；并以原子設(shè)計任務(wù)為節(jié)點、產(chǎn)品零部件相關(guān)度為邊，構(gòu)造描述原子設(shè)計任務(wù)之間關(guān)系的加權(quán)網(wǎng)絡(luò)。

3) 按各種的粒度，對上述加權(quán)網(wǎng)絡(luò)進行剪枝，形成若干任務(wù)模塊劃分方案；并計算各個方案中各模塊內(nèi)的聚合度、模塊之間的耦合度、協(xié)作設(shè)計的難度。

4) 根據(jù)產(chǎn)品眾包設(shè)計任務(wù)模塊劃分原則，建立模塊劃分的優(yōu)化模型；并應(yīng)用智能算法求解該模型，得到最終的任務(wù)劃分方案。

其中，第1) 步要滿足產(chǎn)品模塊的功能獨立性和結(jié)構(gòu)完整性，這相對簡單也較成熟。本文重點研究后面3個步驟的實現(xiàn)方法。

1.2 原子設(shè)計任務(wù)之間關(guān)系的加權(quán)網(wǎng)絡(luò)描述

1.2.1 原子設(shè)計任務(wù)之間的相關(guān)度

產(chǎn)品零部件或基本單元存在功能和結(jié)構(gòu)方面的關(guān)聯(lián)。其中，功能上的關(guān)聯(lián)主要體現(xiàn)在功能接口的能量流、物料流和信息流(包括機電信號和作用力等信息交互)的傳遞上；而結(jié)構(gòu)上的關(guān)聯(lián)主要體現(xiàn)在接觸、聯(lián)接和配合的空間和幾何接口關(guān)系上。

通過相關(guān)性分析方法得到產(chǎn)品基本單元兩兩之間的關(guān)聯(lián)程度，一般很難準(zhǔn)確地給出其具體數(shù)值?？梢愿鶕?jù)人的經(jīng)驗和知識進行兩兩間的比較，用[0,1]區(qū)間的11級標(biāo)度含糊地表示，即為(0, 0.1, 0.2,0.3, ···, 0.9, 1.0)中某個值。

對于產(chǎn)品基本單元的原子設(shè)計任務(wù)，它們之間的相關(guān)度可由式(1)計算。

其中，ai j、fij和sij分別為兩原子設(shè)計任務(wù)之間的相關(guān)度及其基本單元間的功能信息交流相關(guān)度、結(jié)構(gòu)信息交流相關(guān)度，i,j=1, 2, ···,N(N表示產(chǎn)品基本單元的數(shù)量)； ωF和 ωS為功能關(guān)聯(lián)準(zhǔn)則的權(quán)重系數(shù)和結(jié)構(gòu)關(guān)聯(lián)準(zhǔn)則的權(quán)重系數(shù)，可以根據(jù)人類的知識和經(jīng)驗或者使用數(shù)學(xué)中層次分析法來獲得相應(yīng)權(quán)重。

1.2.2 原子設(shè)計任務(wù)間的加權(quán)網(wǎng)絡(luò)

1) 加權(quán)網(wǎng)絡(luò)的構(gòu)造。

以原子設(shè)計任務(wù)為節(jié)點、它們之間聯(lián)系為邊、信息交流相關(guān)度為邊的權(quán)值，則可以構(gòu)造原子設(shè)計任務(wù)間的加權(quán)網(wǎng)絡(luò)，如圖1所示。

圖1 加權(quán)網(wǎng)絡(luò)圖Figure 1 Fuzzy weighted graph

圖1中所示16節(jié)點，表示共16個原子設(shè)計任務(wù)；節(jié)點之間連接邊上的數(shù)字，表示原子設(shè)計任務(wù)間的信息交流相關(guān)度。

2) 加權(quán)網(wǎng)絡(luò)圖的剪枝。

按照一定的粒度閾值a0，對上述加權(quán)圖去掉相關(guān)度小于a0的邊，則得到相應(yīng)的剪枝圖，如圖2所示。

圖2 剪枝加權(quán)網(wǎng)絡(luò)圖Figure 2 Pruning weighted graph

圖2中取粒度閾值a0=0.6，剪掉權(quán)重小于0.6的連接邊后，得到剪枝加權(quán)網(wǎng)絡(luò)圖。這表示分為4個任 務(wù) 模 塊，分 別 為(1, 6, 8, 13, 16)、(4, 9, 10, 12,15)、(3)和(2, 5, 7, 11, 14)。

1.3 眾包設(shè)計任務(wù)模塊內(nèi)聚合度和模塊間耦合度

模塊內(nèi)聚合度是對模塊內(nèi)部基本任務(wù)之間相關(guān)度的總體描述。設(shè)模塊Uh有Ph個基本任務(wù)。由前面的分析知道，任意兩個基本任務(wù)i與j的關(guān)聯(lián)度為aij， 則所有M個模塊的總聚合度C1為[12]

以同樣的思路分析，一個模塊與另一個模塊的耦合度可以用這個模塊內(nèi)部的基本任務(wù)與另一模塊內(nèi)部的基本任務(wù)的相關(guān)度來描述。假設(shè)模塊Us有Ps個 基本任務(wù)，模塊Ut共有Pt個 基本任務(wù)，模塊Us內(nèi)任意一個基本任務(wù)i與 模塊Ut內(nèi)任意一個基本任務(wù)j的相關(guān)度為ai j， 可以得到模塊Us與Ut之間的耦合度為[12]

1.4 眾包設(shè)計任務(wù)模塊協(xié)作設(shè)計的難度

產(chǎn)品眾包設(shè)計任務(wù)劃分為多個模塊后，分發(fā)給各承包方。若模塊包含多個設(shè)計任務(wù)，則需要由多人組成團隊進行協(xié)作設(shè)計。一般來說，模塊規(guī)模越大、網(wǎng)絡(luò)結(jié)構(gòu)越復(fù)雜，團隊內(nèi)交流和沖突也越多。所以，協(xié)作設(shè)計的難度，可用模塊規(guī)模、網(wǎng)絡(luò)結(jié)構(gòu)為指標(biāo)。

1) 模塊規(guī)模難度。

模塊規(guī)模用所包含原子設(shè)計任務(wù)的數(shù)目表示。按項目管理知識，團隊所含人數(shù)越多，越難溝通管理；為使團隊有較高的效率，管理者一般對團隊總?cè)藬?shù)有所限制。對應(yīng)的眾包模塊內(nèi)含原子設(shè)計任務(wù)數(shù)量，也應(yīng)當(dāng)作同樣的限制。所以，在進行加權(quán)網(wǎng)絡(luò)圖的剪枝時，假設(shè)模塊所含原子設(shè)計任務(wù)的最大數(shù)目為Pmax，則規(guī)模難度指標(biāo)定義為

其中，DP為 規(guī)模難度；pi為第i個模塊所含原子設(shè)計任務(wù)數(shù)；M為模塊總數(shù)。

2) 網(wǎng)絡(luò)結(jié)構(gòu)難度。

若眾包模塊存在核心的原子設(shè)計任務(wù)，則模塊內(nèi)部網(wǎng)絡(luò)結(jié)構(gòu)特征具有網(wǎng)絡(luò)中心性(centrality)。通過子圖匹配等方式，在尋找到現(xiàn)有的設(shè)計團隊或即將組建的設(shè)計團隊中，一般存在具有高中介中心性(betweenness centrality)的節(jié)點，是一種“領(lǐng)導(dǎo)者+骨干成員”的團隊組織形式。模塊的網(wǎng)絡(luò)中心性越高，則對應(yīng)的設(shè)計團隊具有較高的中介中心性的節(jié)點越明顯，團隊內(nèi)協(xié)作和沖突消解的難度也就越低。

其中， ωP和 ωL為模塊規(guī)模難度指標(biāo)的權(quán)重系數(shù)和鏈接難度指標(biāo)的權(quán)重系數(shù)，可以根據(jù)人類的知識和經(jīng)驗或者使用數(shù)學(xué)中層次分析法來獲得相應(yīng)權(quán)重。

2 產(chǎn)品眾包設(shè)計任務(wù)模塊劃分的優(yōu)化

2.1 產(chǎn)品眾包設(shè)計任務(wù)模塊劃分的優(yōu)化模型

根據(jù)產(chǎn)品眾包設(shè)計任務(wù)劃分的原則，模塊內(nèi)部信息交流的聚合度最大，模塊之間的信息交流耦合度最小，且任務(wù)協(xié)作的難度最低。則產(chǎn)品眾包設(shè)計任務(wù)劃分的優(yōu)化模型為

2.2 產(chǎn)品眾包設(shè)計任務(wù)劃分模型的求解

任務(wù)模塊劃分屬于典型的組合最優(yōu)化問題，是NP-Hard問題，適宜采用智能的蟻群算法求解。

步驟1 初始化各個參數(shù)以及矩陣值，螞蟻數(shù)，迭代次數(shù)，初始化信息素；存儲好功能結(jié)構(gòu)信息交流相關(guān)值。

步驟2 迭代開始。

步驟3 把螞蟻隨機放在各個頂點上，相關(guān)數(shù)據(jù)做好記錄。

步驟4 按式(11)，選擇轉(zhuǎn)移概率最大的那個作為下一個選擇，如果所得的轉(zhuǎn)移概率大于rand()，則歸為上一個頂點所屬模塊，否則作為另一模塊。

其中， γij(t)表 示頂點信息素； ηij(t)表示頂點功能結(jié)構(gòu)信息交流相關(guān)性； α為信息素啟發(fā)因子； β為相關(guān)性啟發(fā)因子。

步驟5 如果每只螞蟻所有頂點還沒有訪問完，則繼續(xù)步驟3；否則步驟6。

步驟6 更新信息素，根據(jù)模塊劃分遞增表所走過的路徑，按照式(12) ～ (14)對稱添加信息素。

其中，Q為常量；Lk是螞蟻在本次循環(huán)中獲得模塊劃分適應(yīng)度值，其適應(yīng)度值按照式(15)計算，同時保留適應(yīng)度最高的那個值以及模塊劃分。

步驟7 迭代次數(shù)未完則轉(zhuǎn)步驟2，否則結(jié)束，輸出最優(yōu)解。

3 實例分析

3.1 問題描述

以ZL50型輪式裝載機工作裝置為例[14]，其設(shè)計所含基本任務(wù)為1-鏟斗，2-螺栓，3、20-墊圈，4-搖臂銷軸，5-動臂，6-中搖臂銷軸，7、10、15、27-密封圈，8-搖臂鋼套，9-動臂鋼套，11-拉桿，12-齒套，13-斗齒固定銷，14-卡圈，16-拉桿鋼套，17-動臂上鋼套，18-油杯，19-螺栓，21-搖臂，22-墊片，23-鏟斗鋼套，24-鏟斗小銷軸，25-鏟斗上銷軸，26-搖臂上銷軸，27-定位環(huán)；分別用字母T1、T2、T3、T4、T5、T6、T7、T8、T9、T10、T11、T12、T13、T14、T15、T16、T17、T18、T19、T20、T21、T22、T23、T24、T25、T26、T27表示。相應(yīng)的基本任務(wù)功能信息交流相關(guān)度和結(jié)構(gòu)信息交流相關(guān)度如表1所示，分別對應(yīng)上下三角形數(shù)值，其中空白之處數(shù)值為0或者是經(jīng)過前期處理信息交流相關(guān)度忽略不計。

表1 信息交流相關(guān)度Table 1 Relevance of information exchange

3.2 實驗數(shù)據(jù)

采用C語言編寫程序，迭代次數(shù)均為1 000次，設(shè)置不同的參數(shù)，實驗結(jié)果如表2所示。

表2 實驗結(jié)果Table 2 The experimental results

4 結(jié)束語

通過兩次實驗，結(jié)果趨于快速穩(wěn)定，1 000次迭代后，共有6個不同的數(shù)字，故該裝置可劃分為6個模塊，其中相同數(shù)字劃分為同一模塊，不同數(shù)字歸屬不同模塊，得到裝載機工作裝置的模塊劃分結(jié)果：鏟斗模塊 (T1、T2、T3、T24、T25)、斗齒模塊 (T12、T13、T14)、動臂模塊 (T5、T6、T9、T10、T17、T19、T20、T22、T23、T27)、搖臂模塊 (T4、T7、T8、T21、T26)、拉桿模塊 (T11、T15、T16)和油杯組模塊 (T18)，得到模塊劃分與論文[14]結(jié)果相同，證實本文方法的可行性。

社會化產(chǎn)品開發(fā)眾包設(shè)計任務(wù)模塊劃分，是適應(yīng)當(dāng)前形勢的一種任務(wù)分配模式。蟻群算法具備收斂速度極快特點，在機械時效性方面具備一定優(yōu)勢。隨著眾包任務(wù)設(shè)計的復(fù)雜性增加，云計算大數(shù)據(jù)的軟硬件技術(shù)支撐，互聯(lián)網(wǎng) + 眾包任務(wù)分配必將更智能更科學(xué)合理。下一步作者將引入pareto最優(yōu)解尋求更合理的多目標(biāo)解，同時將更復(fù)雜的任務(wù)分配納入作者的研究當(dāng)中。