基于改進NSGA-Ⅱ算法的科技服務鏈推薦

陳冬林，王 蕾，劉 晶

(1.武漢理工大學經濟學院，2.湖北省電子商務大數據工程技術研究中心，湖北武漢 430070)

2014 年10 月，國務院印發了《關于加快科技服務業發展的若干意見》（以下簡稱《意見》），提出了重點發展研究開發、技術轉移、檢驗檢測認證、創業孵化、知識產權、科技咨詢、科技金融、科學技術普及等專業科技服務和綜合科技服務，并強調“發展全鏈條的科技服務，形成集成化總包、專業化分包的綜合科技服務模式”。在該《意見》和相關政策的促進下科技服務業蓬勃發展，大量科技服務機構和科技服務滋生。與此同時，用戶需求日趨復雜化和鏈式化，單一科技服務往往難以滿足用戶的需求。因此，為響應國家號召和滿足用戶復雜需求，需組合單一科技服務構建綜合科技服務鏈。然而，海量的科技服務使得用戶難以選擇合適的科技服務來構建綜合科技服務鏈。在這種背景下，進行綜合科技服務鏈推薦相關研究，向用戶推薦滿足其復雜需求的最佳科技服務鏈具有重要意義。

1 相關研究工作

目前，“科技服務鏈”［1-2］這一概念僅在少量文獻中出現過，科技服務鏈的相關研究處于萌芽階段。但科技服務鏈推薦與云制造服務組合優化較為相似，二者均以構建滿足某復雜任務需求的最優服務鏈為目標，且均需考慮線上和線下場景，本質上都是多目標優化問題。在現有關于云制造服務組合優化的研究中，Bouzary 等［3］使用分類算法和TFIDF 算法檢索候選服務，并使用元啟發式算法獲取最佳服務組合；Wang［4］等考慮了云制造服務之間的相關性，提出了一種多目標文化基因算法，可有效消除不可行的搜索空間和提供高QoS 服務組合；Yuan 等［5］構建了以時間、可組合性、質量、可用性、可靠性和成本為指標的服務質量評價指標體系，采用灰色關聯分析法求解云制造服務組合模型；楊欣等［6］建立了考慮不確定性以及能耗的雙目標規劃模型，并采用改進的NSGA-II 算法對模型進行求解；陳友玲［7］等建立了考慮供需雙方要求的約束模型，并使用改進的NSGA-II 算法對模型進行求解；Yang等［8］構建時間、成本、可靠性、可用性綜合最優的服務質量評估模型，通過動態蟻群遺傳混合算法求解最優云制造服務組合；Hong［9］等提出了一種綜合的基于質量相關性的云制造服務描述模型，通過基于遺傳算法的最優服務選擇方法對模型進行求解；Zhou 等［10］構建了以時間、成本、可靠性和可用性為評價指標的評價模型，運用混合人工蜂群算法求解出最佳服務組合；馬文龍等［11］構建服務質量計算模型，運用改進蟻群算法求解云制造動態服務組合優化問題；Lartigau 等［12］基于質量評估模型，同時考慮云服務的地理位置，通過改進的人工蜂群算法求解出最優的云制造服務組合。

上述研究在很大程度上解決了云制造服務組合優化問題，而科技服務鏈推薦過程與云制造服務組合優化過程具有很大相似性，因此上述模型和方法對解決科技服務鏈推薦問題具有很高的參考價值。但目前，少有研究使用上述模型和方法來求解科技服務鏈推薦問題。從模型方面來看，云制造服務組合優化模型僅考慮時間、成本、可靠性等通用指標，并未考慮云制造服務組合中不同類型服務的特有屬性。服務的特有屬性是區分不同類型服務的核心特性，是衡量服務質量最有力的指標，也是用戶進行服務選擇時最關注的指標。科技服務鏈推薦模型需依據不同類型科技服務所具有的特有屬性來進行服務質量評估，從而確保科技服務鏈最大程度上滿足用戶對特定科技服務的要求。比如檢驗檢測服務需要考慮檢驗結果有效率，以確保檢驗結果被其他機構認可；知識產權服務需要考慮其安全性，以保證知識產權信息不被泄露。從算法方面來看，NSGA-II算法是目前求解云制造服務組合優化問題較為常用的算法，但已有研究未考慮云制造服務組合優化過程中因候選服務數量有限而容易產生重復服務鏈的問題，因此需要在NSGA-II 算法中引入去重操作去除重復服務鏈，以提高算法的收斂性和多樣性，從而提高Pareto 解集的準確性，進而提高推薦結果的準確性。

綜上所述，本文借鑒云制造服務組合優化相關研究，結合科技服務的行業特色，建立考慮科技服務特有屬性的質量評價指標體系，構建時間、成本、服務質量總體最優的數學模型，運用引入去重操作的NSGA-II 算法求解模型，得到一組Pareto 解集。最后，基于用戶偏好構建以時間、成本和服務質量為指標的評價函數，對Pareto 最優解集中的服務鏈進行排序，為用戶推薦最優服務鏈，從最大程度上滿足服務需求方對時間、成本和服務質量的要求。

2 綜合科技服務鏈推薦模型構建

在科技服務業中，用戶對科技服務鏈的需求往往產生于科技成果的形成與轉化過程，該過程的實現基于創新鏈的各活動環節［13］，會涉及多項科技服務，從而形成科技服務鏈。服務需求方對科技服務鏈的總完成時間、總成本以及總質量存在一定要求。為在最大程度上滿足服務需求方的上述要求，下文將以基于創新鏈的科技成果形成與轉化過程為背景，構建考慮服務特有屬性并以用戶需求為約束的科技服務鏈推薦模型。

2.1 綜合科技服務鏈推薦問題描述

如圖1 所示。綜合科技服務平臺由科技服務提供方、科技服務平臺運營方和科技服務需求方3 類主體構成。科技服務提供方在科技服務平臺注冊后將閑置的研究開發、技術轉移、檢驗檢測等科技服務發布到綜合科技服務平臺上；科技服務需求方根據自身的科技成果形成與轉化目標提交任務需求，科技服務平臺運營方基于創新鏈的活動環節將任務分解成N個子任務，并為每個子任務匹配服務，形成滿足任務需求的最優綜合科技服務鏈；最后，由服務鏈中每個服務對應的提供方共同完成總任務。

圖1 綜合科技服務平臺

從任務的提交到完成包含科技任務分解、科技子任務搜索匹配、科技服務鏈推薦、科技服務執行4 個階段。在任務分解階段，科技服務平臺基于創新鏈的活動環節將服務需求方提交的任務T分解為N個子任務ST，是ST 的第i個子任務，i=1，2，…，N；在搜索匹配階段，科技服務平臺為每個搜索匹配一個候選服務集其中為子任務的第j個候選服務，M為子任務的候選服務個數；在科技服務鏈推薦階段，科技服務平臺為服務需求方生成一組Pareto 最優服務鏈，計算出每條服務鏈各評價指標的值并根據服務需求方對服務鏈各評價指標的偏好挑選最優綜合科技服務鏈以執行總任務T，最優綜合科技服務鏈可表示為：其中在服務執行階段，服務需求根據推薦的服務鏈調用服務以完成相應子任務。

2.2 綜合科技服務鏈推薦的多目標數學模型

為求解出最優綜合科技服務鏈，本文基于用戶需求，構建以時間、成本、服務質量總體最優的多目標推薦模型，同時將用戶對時間、成本、服務質量的要求作為模型的約束條件。

2.2.1 考慮特有屬性的服務質量約束

服務質量(Q)由科技服務的共有屬性以及不同服務的特有屬性共同決定。共有屬性是所有服務都具備的屬性，如可靠性和可用性；特有屬性指某一類服務特有的最能夠反映該服務質量且最受用戶關注的屬性。在科技服務業中，本文定義的科學技術普及、科技咨詢、檢驗檢測、科技金融、研究開發、創業孵化、技術轉移和知識產權的特有屬性分別為科普經費、有效咨詢率、檢驗結果有效率、融資總額、新開發產品或服務數、新孵企業數、技術人才數量以及安全性。上述服務屬性的定義及符號表示如表1 所示。

表1 服務屬性定義表

表1 （續）

2.2.2 時間約束

2.2.3 成本約束

科技服務鏈的結構主要有順序結構、并行結構、循環結構和選擇結構四種，如圖2 所示。其中順序結構為最基本的結構，其他三種結構均可以通過一定方式等效轉換成順序結構。因此，本文以順序結構的科技服務鏈作為科技服務鏈推薦的研究對象。

圖2 科技服務鏈結構

綜上所述，綜合科技服務鏈推薦模型的目標函數如下：

（1）總完成時間最小化。

（3）總質量最優化。

為了計算每一條服務鏈的總質量，同時消除屬性變化的不一致性，需對每一個候選服務的服務屬性值進行歸一化處理。本文采用文獻［7］中歸一化方法：

然后將服務鏈中所有候選服務的質量求和取均值，得到服務鏈的總質量Q。

則服務鏈總質量最優可以表示為：

2.3 數學模型

根據上述目標函數和約束條件，科技服務鏈推薦模型可以描述如下：

公式（8）表示該模型以時間最短、成本最小、服務質量最高為目標，公式（9）、公式（10）、公式（11）分別表示需求方對服務鏈的時間、成本和服務質量的約束。公式（12）表示對于每一個子任務只能選取一個候選服務。

3 綜合科技服務鏈推薦算法求解與服務鏈評估

本節對科技服務鏈推薦問題的求解算法和科技服務鏈評估函數進行介紹。

3.1 算法選擇及改進

本文提出的綜合科技服務鏈推薦是一個多目標優化問題，而NSGA-II 算法是目前使用較廣的求解多目標優化問題的算法之一。NSGA-II 降低了算法難度，提高了種群進化水平，但在求解科技服務鏈推薦問題時，由于候選服務數量限制，種群中容易產生重復服務鏈，降低種群多樣性。因此，本文對基本的NSGA-II 算法進行改進，設計了有效的整數編碼方式，引入了去重操作，改進后的算法稱為i-NSGA-II 算法。

首先對編碼方式進行改進，采用整數編碼構建與科技服務相對應的個體。例如，一項科技任務可分解成5 個子任務，每個子任務有5 個候選服務，當候選科技服務鏈為其對應的整數編碼即為［5,8,14,16,22］。在基本的NSGA-II 算法中引入去重操作［14］，剔除重復的服務鏈保留獨特的服務鏈，一方面可降低冗余計算量，提高算法收斂速度；另一方面，可提高算法的收斂性和多樣性，從而提高Pareto 解集的準確性，進而提高推薦結果的準確性。

i-NSGA-II 算法求解科技服務鏈推薦模型的流程如圖3 所示。

圖3 推薦流程圖

3.2 綜合科技服務鏈評估函數

為了根據用戶偏好對求得的Pareto 最優解集進行排序，從而向用戶推薦最滿足其需求的服務鏈，本文構建以時間、成本和服務質量為指標的評估函數對Pareto 解集中的各服務鏈進行評估。首先使用1.2.1 中歸一化公式對每條Pareto 最優服務鏈的時間、成本和服務質量進行歸一化處理，消除不同量綱的影響，然后按一定權重將三個指標加權，得到第i條服務鏈的評價函數：

式中 表示第i條服務鏈的評價值，分別表示第i條服務鏈的時間、成本和服務質量經過歸一化所得的值。為服務需求方根據自身偏好設置的權重值。最后，根據服務鏈評價值對服務鏈排序，將評價值最高的服務鏈推薦給服務需求方。

4 算例論證

本文設計了算法測試實驗和算例論證實驗，以驗證模型的可行性，測試i-NSGA-II 算法的各項性能。

4.1 實驗數據與環境

以豬八戒網中某公司需要研發一個替代紙質作業本，具備讀寫、批注、文件傳輸的電子作業本的科技服務項目為例，對本文所提出的綜合科技服務鏈推薦模型、算法及評估函數進行驗證。服務需求方向科技服務平臺提交電子作業本開發任務需求，科技服務平臺根據創新鏈的活動環節將任務分解為如圖4 所示的5 個子任務，在科技咨詢環節為該公司尋找提供可行性分析服務的咨詢機構，為項目撰寫可行性研究報告；在創業孵化環節為該公司尋找撰寫商業計劃書的機構；在科技金融環節為該公司匹配融資中介助力其融資；在研究開發環節為該公司尋找提供相關技術的機構；在檢驗檢測環節為其尋找可為電子作業本進行品質檢測的檢測機構，為上述子任務搜索匹配對應的候選服務集。候選服務相關參數依據豬八戒網和其他科技服務網站的相關數據確定，如表2 所示。服務需求方的相關信息為：總時間不超過25 天，總成本不超過80 000 元，服務質量不低于0.8。根據上述信息構建算例模型。實驗環境：MATLAB R2018b 軟件，Windows10，3.60GHz，16GB RAM。

圖4 科技成果形成與轉化任務分解圖

表2 候選服務相關參數

對于每一個候選服務，首先對其服務屬性值進行歸一化處理，然后將候選服務的特有屬性與可用性、可靠性按進行加權，得到該候選服務的質量，質量的取值范圍為［0,1］。

4.2 算法測試

首先，本文選取常用的多目標優化測試函數ZDT1，ZDT2 以種群數為100，迭代次數為500 對i-NSGA-II 算法進行測試，圖5 為本文算法求解ZDT1 函數和ZDT2 函數所得的 Pareto 最優前沿與其理論上的 Pareto 最優前沿的分布圖，“-”為理論解，“*”為算法求解出來的解。可以看出，本算法能收斂到各類問題的 Pareto 最優前沿并且分布較均勻。

圖5 ZDT1 函數測試結果

然后，采用Deb 等［15］給出的兩個算法評價指標：收斂性和多樣性，來評估Pareto 解集的準確性和i-NSGA-II 算法的性能。

（1）收斂性指標γ。在測試函數已知的Pareto最優前沿上均勻地取一些點（下文實驗取 500 個點），計算由算法獲得的解與這些點之間距離的最小值，所有最小距離的平均值就是收斂性指標：

式中，Z為算法所獲得的Pareto 解集，為理論上的Pareto 解集。收斂性指標γ越小，算法逼近Pareto 最優解集的程度越好。

（2）多樣性指標Δ。將種群中所有個體按某個目標函數值的大小有序地分布在目標空間上，是Z中連續兩個非劣解向量的歐式距離為的均值，分別表示集合中的極值解和Z的邊界解之間的歐式距離。

極值解指某一目標函數值最大而其它目標函數值最小的解。當算法獲得的非劣解完全均勻地分布在均衡面上，這時Δ=0。因此，Δ指標能反映非劣解能否均勻地分布在整個均衡面上。

分別使用NSGA-II 和i-NSGA-II 算法對ZDT1，ZDT2 測試函數進行求解，以種群數為100，迭代次數分別為50,75,100 各運行30 次，求得2 種算法對2 個測試函數收斂性和多樣性的均值，如圖6 和圖7所示。實驗結果表明，與 NSGA-II 相比，i-NSGAII 對2 個測試函數的收斂性和多樣性都較好，因此i-NSGA-II 求得的解更逼近最優解，從而更能滿足服務需求方的要求。

圖6 多樣性均值對比圖

圖7 收斂性均值對比圖

4.3 算例求解及分析

在上述實驗環境下，分別采用NSGA-II 算法和i-NSGA-II 算法按種群規模最大迭代次數，交叉概率變異概率對算例模型進行求解。實驗結果分別如圖8 和圖9 所示，圖中每一點代表一個Pareto 最優解，可以看出i-NSGA-II 算法和NSGA-II 算法求解模型所得的滿足用戶要求的服務鏈的數量分別為100 個和16 個，i-NSGA-II 算法能夠求得更多滿足用戶需求的服務鏈。因此，i-NSGA-II 算法在求解科技服務鏈推薦模型上優于NSGA-II 算法。

圖8 NSGA-II 求解所得Pareto 解集

圖9 i-NSGA-II 求解所得Pareto 解集

首先采用公式（3）（4）對i-NSGA-II 算法求得的Pareto 解集中各候選服務鏈的時間、成本和服務質量進行歸一化處理，再按照服務需求方綜合考慮時間、成本、服務質量，只考慮時間，只考慮成本，只考慮服務質量四種偏好情況對i-NSGA-II 算法求得的Pareto 最優服務鏈進行排序，則四種情況的時間、成本、服務質量對應的權重分別為W1=(1/3,1/3,1/3)，W2=(1,0,0)，W3=(0,1,0)，W4=(0,0,1)，表3 展示了每種情況下經過排序所得的5 條最優服務鏈的信息。

表3 考慮不同權重的科技服務鏈評估結果

從結果來看，綜合考慮時間、成本、服務質量的情況與只考慮時間的情況對比，前者求得的服務鏈的平均成本小于后者、平均服務質量高于后者；綜合考慮時間、成本、服務質量的情況與只考慮成本的情況對比，前者求得的服務鏈的平均時間小于后者、平均服務質量高于后者；綜合考慮時間、成本、服務質量的情況與只考慮服務質量的情況對比，兩種情況求得的服務鏈的平均時間相同、平均成本前者小于后者。此外，服務需求方可以根據自身偏好重新向綜合科技服務平臺提交權重要求，綜合科技服務平臺只需根據新的權重重新對Pareto 解集中的服務鏈進行排序，而無需重新進行Pareto 最優服務鏈選擇，節約了大量時間，使得服務鏈的選擇更具靈活性。

5 結束語

本文針對科技服務業中科技服務鏈推薦問題，構建了以科技服務特有屬性、可靠性和可用性為指標的服務質量評價指標體系，建立了考慮科技服務特有屬性的科技服務鏈推薦模型，在NSGA-II 算法中引入去重操作對算法進行改進，并使用改進的算法對科技服務鏈推薦模型求解，得到一組Pareto 最優服務鏈，最后構建科技服務鏈評估函數對服務鏈進行評估和排序，向用戶推薦最符合其需求的服務鏈。實驗結果證明，本文提出的i-NSGA-II 算法求得的滿足服務需求方要求的服務鏈的數量遠多于NSGA-II 算法求得的合格解的數量，i-NSGA-II 算法在收斂性和多樣性上也優于NSGA-II 算法，因此i-NSGA-II 算法求得的Pareto 最優服務鏈的準確性也較高。此外，服務鏈評估函數允許服務需求方根據自身偏好靈活更改權重要求。未來，科技服務鏈將集成更多科技服務，會愈發復雜。后續研究應該結合科技服務的應用場景，考慮不同結構的科技服務鏈，同時構建更加完善的科技服務鏈質量評價指標體系，提高推薦精準度，進一步推動科技服務業的發展。