基于NSGA-III的眾包設計服務資源優選方法研究

尹 超，石志立

(重慶大學 機械工程學院機械傳動國家重點實驗室，重慶 400000）

0 引言

隨著社會生產力的不斷發展，傳統企業的創新模式已經越來越難以滿足社會上對于各類產品的個性化需求，而同時社會上存在著眾多可利用的設計資源，“眾包設計”這一新型的創新模式應運而生。眾包設計模式將海量的設計服務資源匯聚到眾包設計平臺，在服務需求方和服務提供方之間建立合作渠道，從而為各類設計需求方提供服務，充分發揮了群眾的智慧[1,2]。

眾包設計模式根據任務類型可以劃分為簡單任務型眾包和復雜任務型眾包兩種模式。簡單任務眾包包括Logo設計、海報設計、UI設計、軟件測試等需求，其特點為任務粒度小，并行性好，當前眾包設計平臺方主要采用的任務分配模式分為競標型和一對一型；復雜任務眾包則包括軟件開發、家裝設計、個性化定制產品等需求，其特點為任務粒度大、服務周期長、服務流程可解耦等，往往需要通過眾包設計平臺協調多個服務提供方共同完成，因而，研究眾包設計任務的組合優選問題就成為提高眾包設計模式可靠性與高效性的重要途徑。現有的文獻對不同類型制造資源的優化選擇進行了探索，并取得了一定的成果。如文獻[3]提出了一種考慮服務可靠性、可信性、組合復雜度、協同度、執行時間和執行費用的云制造資源綜合QOS評價模型，并采用EEPSO算法對制造任務組合模型求解；文獻[4]構建了面向資源供應方、服務需求方和平臺運營方的制造資源服務組合模型，并采用云遺傳算法求解；文獻[5]考慮了制造資源虛假信息對服務組合優選的影響，并提出了基于可信度的制造資源優選方法；文獻[6]建立了一種面向新產品開發的云服務資源組合優選模型，并采用灰色關聯度分析方法對模型進行求解；文獻[7]在定義制造云服務的基礎上，提出了MCS混合粒度組合優選方法，構建了基于服務成本、服務質量和交易周期的多目標優化模型，并通過ε-SPEA2算法進行求解；文獻[8]構建了面向航天復雜產品的制造系統體系架構，并提出了支持制造資源/制造能力的多視圖描述和組合優選模型；文獻[9]構建了包含時間、成本、能源消耗、可靠性、可維護性和服務評價的制造服務六維評價模型，并采用自適應混沌優化算法求解；文獻[10]從資源服務、功能服務和流程服務三個層次對制造資源進行建模，通過構建服務執行時間、服務花費成本和服務用戶評價三個方面的質量評估函數，并通過改進的NSGA算法對制造服務的優化組合模型進行求解。

上述文獻關于制造資源的服務組合優選方法對研究眾包設計服務組合優選具有一定的參考作用，然而眾包設計服務資源具有增值性、邊際性和共享性等典型知識資源特征[11]，在資源的匹配優選過程中難以對服務質量做出準確評判。當前關于眾包設計服務過程中的服務資源組合優選研究較少，尚未建立比較完善的眾包設計服務資源搜索匹配評價指標體系以及組合優選評價指標體系。因此，本文在以上研究成果的基礎上，針對眾包設計服務過程特點及服務需求方和服務方不同屬性，對服務資源的評價指標體系和優選模型以及求解方法進行探索和研究，并結合實例進行驗證。

1 眾包設計服務模式及特點

1.1 復雜任務型眾包設計服務模式

復雜任務型眾包設計主要包括任務設計、任務推薦、服務匹配、服務組合、服務優選等流程，如圖1所示。服務需求方在眾包設計平臺發布需求，并填寫任務需求。眾包設計平臺根據任務需求文檔和案例數據庫對復雜任務需求進行分解，平臺技術團隊保證各子任務的低耦合性。平臺將需求匹配的服務提供方加入待選資源，對各種不同的資源組合優選，得到最終的任務執行序列。

圖1 復雜任務型眾包設計服務模式

1.2 眾包設計服務特點

眾包設計服務模式通過將創新的來源由組織或企業內部擴展到組織外部的群眾中，激發和融合擁有大量專業知識的大眾群體的創造力，極大擴展了創新的知識來源。根據復雜任務型眾包設計服務流程，可以總結出其具有如下典型特征：

1）服務組合性。復雜任務型眾包設計服務模式中，單個復雜設計任務一般可以劃分為多個階段或流程，并且各階段或流程具有較低耦合性，因此，可以通過將不同類型的眾包設計服務提供方有序組合在一起，協作完成通過將不同的階段或者流程分配給多個眾包設計服務提供方協作完成，以提高設計效率和產品迭代速度。

2）依賴傳遞性。復雜任務型眾包設計模式中由于多個設計服務資源共同完成整體流程，某一階段的設計任務需要根據前一階段的設計結果作為基礎，因此服務需求方對各個環節的服務質量提出了較高要求，需要盡可能規避風險以免延誤整體設計進度。

3）主客觀性。眾包設計服務模式中任務要求包含客觀要求和主觀要求，客觀要求易通過各項測試得出結果；而各主觀要求則必須考慮到服務需求方的個體傾向，因此，資源需求個體的評價傾向會影響服務資源個體對眾包任務的接受和實施。

2 考慮供需雙方約束的眾包設計服務資源搜索匹配評價指標體系

在對眾包設計服務資源的優選之前，需要先根據任務需求對服務需求方進行搜索匹配，但是在大多服務組合優選的研究中往往只考慮服務需求方的指標約束，而在眾包設計服務模式中，任務需求的傳遞依賴性決定了服務提供方的重要地位，因此，本文結合眾包設計服務模式特點和供需雙方的需求屬性，提出眾包設計服務資源搜索匹配評價指標體系。

2.1 服務需求方約束指標

服務需求方是眾包任務的發起方，因此在服務過程中占據主動地位。服務需求方通過和眾包設計平臺的技術團隊協作對眾包任務設計環節，主要包括任務屬性確定、任務完成時間、任務激勵機制，任務分解等。因此服務需求方對眾包任務搜索匹配的約束指標主要包括：服務類型：包括功能設計、結構設計、外觀設計、布局設計等，可以根據用戶的任務需求，選擇合適的服務類型；服務可用性：指當前眾包設計服務資源能否在平臺中提供服務，若不能，則不會被納入匹配結果以及優化選擇的范疇；歷史信譽：指的是服務需求方對眾包任務完成情況的歷史評價，可以體現其服務方服務能力的高低。

2.2 服務提供方約束指標

經過眾包設計平臺分解后的各子任務會被推送到符合要求的服務提供方一端，然而考慮到該任務本身的綜合收益風險比和服務需求方的滿意傾向，服務提供方不會選擇接受所有的眾包任務服務請求。服務提供方對眾包設計服務搜索匹配的約束指標主要包括：服務風險收益比：指的是接受服務承擔的風險水平，若某一任務超過了服務提供方設置的風險收益比，則不會被匹配到；服務需求方的滿意傾向：主要指任務提交后，雇主的評價傾向，由于可以根據歷史評價記錄獲得。

2.3 復雜任務型眾包設計服務優選評價指標體系

眾包設計平臺通過聚集各類分散的眾包設計服務資源，可為廣大服務需求方提供相應的設計服務，有效利用提高了各類設計業務效率。然而眾包設計服務資源屬于抽象的知識資源，傳統的對實體資源的定量評價指標體系難以對眾包設計資源準確評價。因此本文提出一種包括服務時間（T）、服務成本（C）、服務能力（Ca）和服務有效性（Re）的眾包設計服務資源優選評價指標體系，如圖2所示。

圖2 眾包設計服務資源優選評價指標體系

1）服務時間T

服務時間T主要包括眾包平臺上進行的任務分解、任務推薦、服務匹配的等待時間Tmatch，以及服務提供方完成任務耗費的時間Tseruice，還有眾包平臺同供需雙方協調任務設計、專家技術團隊對眾包任務的技術審核等花費時間Tmanage，即T(S)=Tmatch(S)+Tservice(S)+Tmanage(S)其中S代表服務提供方，下文同義。

2）服務成本C

服務成本指服務需求方從提出需求到任務完成過程中所支付的費用,主要包括支付給服務提供方的傭金酬勞Cseruice和在眾包設計服務過程中購買的增值服務花費Conline，如風控保險、專家咨詢等，即C(S)=Cseruice(S)+Conline(S)。

3）服務能力Ca

服務能力主要衡量服務提供方在專業技能、服務經驗、技術專利等知識方面的飽有量和共享度[12]。假設某服務服務提供方Sj包含的知識總數為sum(Sj)，其服務能力Ca(S)，知識飽有量為μj，知識共享度為uj，則Ca(S)=ωμμj+ωuuj，其中vj=sum(Sj)，ωμ和ωu分別為知識飽有量和知識共享度的權重，并且ωμ+ωu=1，m為眾包設計服務過程中同類型的服務提供方總數，sum(Sj)代表服務提供方通過眾包設計平臺共享的知識總量。

4）服務可靠性Re

服務可靠性指的是服務提供方在面臨突發情況時能按時完成任務的能力，主要包括服務提供方的任務成功率Resuccess、服務提供方的任務準時完成率Reontime以及服務方收到的歷史評價記錄Reevaluation，即，其中：Rei,j為服務提供方第i個滿意度指標的第j次評估值，λi為服務提供方的第i個滿意度指標的權重，并且0≤λi≤1,，n為服務提供方第i個滿意度指標的評價次數。

2.4 眾包設計服務資源組合優選模型

考慮到眾包設計服務供需雙方約束指標，因此，眾包設計服務資源組合優選問題的多目標數學模型為：

式(1)中的tmax表示最大預期服務時間，cmax表示最大預期服務成本，Camin和Remin分別表示最小服務質量預期和最小服務可靠性預期。對于多目標優化選擇模型中的各項指標的值，可以通過式(2)進行歸一化。其中qj表示資源評價指標，分別表示資源評價指標的最大值和最小值。在眾包設計服務資源評價指標中，服務時間和服務成本通過（2b）歸一化；服務質量和服務可靠性通過（2a）進行歸一化。

3 基于NSGA-III的眾包設計服務資源組合優選算法

NSGA-III算法是在帶精英策略的NSGA-II算法的基礎上提出的一種新的多目標優化求解算法[13]。兩者的算法求解框架大體相同，區別在于NSGA-II通過計算個體擁擠度距離對同一非支配等級的個體進行選擇，認為擁擠個體距離越大也好，該方法適合求解2個或3個目標函數的優化問題，但是隨著優化問題目標維數的增大，種群中非支配個體數量呈指數增大，并且通過擁擠度距離排序選擇個體在非支配層上分布不均勻，容易陷入局部最優，影響算法的有效性和收斂性，應用NSGA-III算法的步驟如圖3所示。

圖3 NSGA-III算法流程

在眾包設計服務資源優化選擇模型中應用NSGA-III算法的關鍵在于種群基因編碼、種群的自適應標準化和個體的保留操作。

1）種群的基因編碼、交叉和變異

在遺傳算法中，需要將目標問題的可行解編碼成染色體，染色體上的各元素基因。通過對基因的選擇、交叉、變異等操作，篩選出適應力更強的后代，最后一次迭代得到的種群即是目標問題的Pareto解集。在具體的應用場景中，可以根據使用者的需要和偏好選擇，選擇出對應的個體作為問題的最優解。本文中的染色體由眾包設計服務資源個體序列組成，編碼規則為十進制編碼，例如設計服務資源組合CSR1,3-CSR2,1-CSR3,5-CSR4,4-CSR5,2，所對應的十進制編碼為3-1-5-4-2，如圖4所示；交叉策略采用重合點交叉，對隨機選擇的兩個染色體，選擇編碼中對應位置相同的元素進行交換，若無重合點，則不進行交叉操作，重合點交叉的優點在于不會產生新的無效解，如圖5所示；變異算子在個體中隨機選擇一個序號，用另一個隨即產生的序號替代，如圖6所示。

圖4 基因編碼

圖5 交叉操作示意圖

圖6 變異操作示意圖

2）種群的自適應標準化

種群標準化的目的是將參考點放在一個標準化的超平面上，首先將當前種群Si中個體的每一維目標的最小值構成當前種群的理想點集合-z，對種群St做平移操作使得理想點變為原點，將式(3)的最小值記為zi,max,使用M個極值點通過式(4)構成M維標準化空間；設置參考向量zt，并關聯種群和參考點，關聯操作具體見文獻[14]。

式中ωi為坐標軸的單位方向向量；ai為每一維在對應坐標軸上的截距。

3）個體的保留

經過標準化關聯操作后，可能出現一個參考點關聯多個個體。將參考點j在集合Pt+1=St/Fl關聯的個體的數量記為ρj；首先選擇關聯數目最少的參考點，若其ρj=0，則將離參考點對應的參考線最近的個體加入Pt+1，若臨界區Fl中不存在個體與參考點關聯，則將參考點刪除；若ρj≥1，則從隨機選擇一個參考點并將關聯的個體加入Pt+1。重復上述步驟直到種群的規模達到N。

4 實例驗證

為了驗證論文中的模型的算法的有效性，本節以復雜家電產品個性化眾包設計平臺中的電冰箱開發為背景。服務需求方在眾包設計平臺中提交新款個性化冰箱的設計需求，眾包設計平臺通過平臺的創意征集板塊，確定了需求的若干個新特點并加工形成設計文檔；根據產品需求及特性將該個性化冰箱設計任務劃分為如圖7所示的五個子任務。其具體的評價指標值如表1所示，指標約束參數規定如下：tmax=500h,cmax=8000元，camin=0.7500，remin=0.8000。

表1 眾包設計服務待選資源指標參數

圖7 個性化冰箱設計流程圖

眾包設計服務優選模型中的各項參數由服務提供方和服務需求方決定，本文采用的各項參數如下表：N0=30，Pc=0.92,Pm=0.06,最大迭代次數maxFE=100，在上述實驗環境下，通過Matlab編程對多目標優化模型進行求解運算。經過19次迭代后，程序在各目標上的適應度趨于穩定，到達收斂狀態，各可行解在四個目標函數上適應度的平均值如圖8所示。

圖8 目標函數平均適應度值

眾包設計服務資源優化模型求解結果如表3所示，根據實際設計情形分析，服務成本和服務質量在設計過程中占據相對重要，因此，令ω={0.3,0.2,0.3,0.2}，計算Pareto解集中的解的適應度值并排序，計算結果如表2所示，各指標向量采用式(2)歸一化：

表2 眾包設計資源綜合評價

根據眾包設計資源綜合評價結果可以看出，在指標權重預設為ω的情形時，最優的服務組合為CSR1,3-CSR2,1-CSR3,5-CSR4,4-CSR5,4。實際應用中，可以根據不同的客觀條件確定指標權重ω，進而得到相應的的眾包設計服務資源組合序列。

5 結語

本文通過分析復雜任務型眾包設計模式服務流程及特點，提出了一種考慮供需雙方約束的眾包設計服務資源搜索匹配評價指標體系，以及包含服務時間(T)、服務成本(C)、服務質量(Ca)和服務可靠性(Re)的眾包設計服務資源優選評價指標體系，并對各項指標進行了量化評估；在此基礎上建立資源優選的數學模型，通過NSGA-III算法對模型進行求解，驗證了所提方法的有效性。下一步將針對眾包設計服務資源全信息描述模型以及服務過程中的資源匹配算法展開研究。