支持擴展QoS約束的動態虛擬企業伙伴選擇模型

張以文 倪志偉 王 力 李志東

1．合肥工業大學過程優化與智能決策教育部重點實驗室，合肥，230009 2．安徽大學，合肥，230039

0 引言

虛擬企業以其低成本、快速響應市場機遇以及良好的適應能力，越來越受到業界的重視。合理的伙伴選擇是虛擬企業成功的關鍵。目前，虛擬企業的伙伴選擇研究主要有兩條技術路線：①基于多屬性決策方法研究［1－3］，基于 A HP（層次分析法）、DEA（數據包絡分析）、模糊決策等方法和理論來進行伙伴選擇，這些方法還只是局部搜索的優化方法，可操作性較差；②基于智能算法的伙伴選擇［4－7］，但已有研究大多是基于靜態虛擬企業背景下進行的，不能很好地體現伙伴選擇的動態性。傳統的靜態虛擬企業組織結構相對固定，成員數量相對穩定，在建立虛擬組織時，需要一致的成員企業的業務接口以及相互之間統一的文件交互格式［8］，代價高，可伸縮性差。企業間異構的應用系統平臺、不一致的數據格式、信息集成和共享困難是導致靜態虛擬企業滯后的合作伙伴發現和選擇的重要原因。隨著信息技術與網絡技術的飛速發展，網絡經濟已成為重要的經濟模式，動態虛擬企業成為網絡經濟的主要表現形式，動態虛擬企業具有松散耦合、異構性、不穩定性和動態性等特點。但隨著網絡中潛在的虛擬企業合作伙伴明顯增多，使得動態虛擬企業對于合作伙伴的選擇、評價和動態綁定變得更加復雜。Web服務（WS）技術是良好的解決方案，基于Web服務技術的動態虛擬企業集成已成為人們研究的熱點。Web服務技術為企業集成雙方提供了一種松散藕合的機制，特別是統一描述、發現和集成（universal description discovery and integration，UDDI）機制能為企業的注冊提供統一的管理平臺，使企業能夠實時動態地發現現有的和潛在的合作伙伴，集成新的企業合作伙伴，從而使虛擬企業合作伙伴的動態選擇成為可能。但目前的研究還只主要集中在解決企業間系統異構性和提高信息集成及共享等方面［9－10］，較少涉及 Web服務架構下的動態虛擬企業伙伴選擇問題，尤其是已有UDDI的研究工作缺乏對注冊企業服務能力的評價機制，未能充分發揮Web服務架構的顯著優勢，對動態虛擬企業合作伙伴的選擇產生了嚴重障礙。本文提出一種基于Web服務架構的動態虛擬企業伙伴選擇擴展模型（dynamic virtual enterprise partner selection extended model，DVEPSEM）來支持大規模的動態虛擬企業伙伴選擇，通過實驗驗證了模型的有效性和合理性。

圖1 動態虛擬企業伙伴選擇擴展模型

1 動態虛擬企業伙伴選擇擴展模型

Web服務技術的出現為動態虛擬企業伙伴選擇提供了技術支撐，但現有Web服務架構下的服務發現算法研究主要考慮應答時間、服務器負載、服務成本和網絡延遲等因素。在動態虛擬企業伙伴選擇中更重要的是應考慮商務合作層面的因素，如成本因素、生產時間、合作信任度、風險因素等，需要對現有 Web服務架構進行擴展，提出了一種動態虛擬企業伙伴選擇擴展模型，如圖1所示。

1．1 DVEPSEM模型分析

定義1 WS＝｛Function，QoS｝。WS為企業Web服務，其中，Function是企業服務的功能屬性集合，表示企業的某種服務能力，QoS是服務質量（QoS）的屬性集合。

定義2 QoS ＝ ｛QoStrad，QoSextr｝。QoStrad是指傳統服務質量（QoStrad）屬性集合（如應答時間、服務器負載等），QoSextr是指企業商務合作層面的服務質量屬性集合（如成本因素、產品質量和合作信譽度等），為伙伴選擇提供依據。本文主要研究基于擴展QoS（QoSextr）的動態虛擬企業伙伴選擇問題。

定義3 WS類（即企業服務類）是由不同企業發布、具有實現相同功能的一組企業服務集合，同一個企業服務類中企業功能相同，但各自的QoSextr性能不同。

（1）企業聯盟UDDI機制接受WS的發布，并在領域本體的支持下（圖1中彎曲虛線表示領域本體到相應服務類的映射）將企業WS按其服務功能進行分類，使得每個企業服務（或原子企業服務組合，考慮可能有若干小型企業合作完成一項子任務，看成一個服務）屬于某個服務類（圖1中矩形虛線表示一個服務類），利用本體對企業服務功能明確的形式化的規范說明，提高企業服務分類的精確性，消除信息語義的多重性以及信息關系的匱乏和非統一性問題。

（2）QoS監控系統負責企業服務類各服務QoSextr標準量化工作，并對企業服務QoSextr動態監督，接受客戶企業反饋信息并實時動態更新企業QoSextr，為企業能力公正合理的評價提供保障，為伙伴選擇提供決策信息（如服務質量、信譽度等）支持。

（3）核心企業是虛擬企業的發起者，將實現目標劃分成若干個子任務，子任務之間可以并行執行，通過工作流引擎建立任務間的先序關系，如圖2所示。其中，TKi表示目標任務組合中第i項子任務，從起始任務到終止任務路徑表示虛擬企業實現目標任務的工作流程。伙伴選擇的任務是為每類子任務從相應服務類中選擇一個理想的企業服務共同構成一個企業服務組合，優化的企業服務組合即為動態虛擬企業伙伴選擇的目標，以期達到以最快的速度、最低的成本、最好的質量實現企業目標，提高企業的敏捷性和快速響應市場的能力，成員組合一經確定，核心企業建立私有UDDI并向伙伴成員發送注冊邀請。

圖2 虛擬企業任務狀態圖

（4）伙伴企業為尋求市場機遇，將自己的能力封裝成WS，發布到企業聯盟UDDI，以期待與其他企業的合作，提高企業自身的競爭能力，當被某核心企業邀請時，對核心企業和合作目標進行評估，若接受邀請則在核心企業私有UDDI內注冊，否則，反饋拒絕接受邀請的消息。

虛擬企業各個成員通過基于XML的SOAP協議作為標準通信協議，完成各個成員間應用程序的無縫集成。虛擬企業解散時各成員企業反饋相關合作企業信譽度等QoSextr信息。

為實現伙伴企業快速精確的查找，可選用OWL－S（語義 Web服務標識語言）來描述企業服務的知識本體，提供企業服務的詞匯表，描述服務的語義，根據服務的Function進行推理。OWL－S主要通過Service Profile、Service Model和Ser vice Gr ounding三個類來描述服務做什么、如何做以及如何訪問等三方面的語義，從而允許服務的自動發現、執行、組合和運行的監視。每一個服務輪廓都是Profile Ontology（輪廓本體）中定義的輪廓類（Class Ser vicePr ofile）的一個實例。如〈profile：profile r df：ID＝ “Profile Enterprise Web＿Ser vice”〉，在OWL－S中規范了一系列的屬性來描述服務Profile Ontology，在原有屬性的基礎上進行屬性擴展，利用“f unction Description”屬性來描述服務的Function信息，利用“Qos Constraints”來描述企業QoSextr信息。企業服務類在“ServiceCategory”中加以描述。擴展Ser vice Pr ofile結構如圖3所示。

圖3 擴展Service Profile本體

1．2 基于DVEPSEM的伙伴選擇數學模型

設TK ＝ ｛TKi｜i＝1，2，…，n｝為虛擬企業需要完成的n類子任務的集合，WSi＝｛wsij｜j＝1，2，…，mi｝為UDDI內能夠完成子任務TKi的某候選企業服務類，mi為該服務類中服務數量。設Ii＝ ｛ti，qi，ci，…｝為服務類WSi的 QoSextr評價指標集合，其中，ti為時間指標，qi為質量指標，ci為價格指標，省略號為其他可選指標。每個服務類指標集合不同，但可取ti、qi、ci作為動態虛擬企業（因為動態虛擬企業要求快速的市場應變能力下以低廉的成本創造高質量的產品或服務）各服務類公共評價指標，即QoSextr＝｛生產時間，產品質量，生產成本｝。設核心企業對TKi類子任務合作伙伴的QoSextr約束為生產時間不超過tmaxi、產品質量不低于qmini、生產成本不高于cmaxi，則動態虛擬企業伙伴選擇問題可描述為滿足約束的多目標決策問題：

s．t．?i，若 ?j使得dij＝1，那么wsij必須滿足：

式（1）中，當子任務間是并行關系時，取并行任務間的最大時間（圖2中子任務TK2和TK3）。式（2）中，C1為虛擬企業各子任務花費（主要是企業自身成本估計）之和，C2為虛擬企業相鄰任務（i→i＋1）間企業連接成本（如運輸費用等），lwsij，ws（i＋1）k為 服 務 類 WSi中 的 服 務j 和 服 務 類WSi＋1中的服務k之間的連接成本，若wsij被選中則dij為1，否則為0。twsij、cwsij和qwsij分別為服務類WSi中的第j個服務所需的生產時間、生產成本和能夠提供的服務質量。

以上指標可能在數量級上存在很大差異，為防止在決策中發生“大數吃小數現象”，按下式將各指標進行歸一化處理：

按照式（5）負作用指標將式（3）轉化為最小化問題：

對于?wsi服務類集合，若wsij被選中，必須滿足下式，即DVEPSEM模型下伙伴選擇（多目標決策問題）轉換為下式的組合優化問題：

其中，｛λi1，λi2，λi3｝為指標權重，滿足，并行任務間求解時的最大時間。

2 基于DVEPSEM的伙伴選擇改進算法

基于多約束的虛擬企業伙伴選擇問題已被證明是NP問題［11］。自適應遺傳算法（AGA）能夠有效地解決此類問題，遺傳算法具有很好的全局尋優能力。但是，隨著信息技術與網絡技術的飛速發展，網絡中潛在的企業合作伙伴明顯增多，問題的搜索空間變得越來越大，本文利用伙伴選擇企業QoSextr約束問題本身的數學特征，在制定相關規則的基礎上，較大程度地降低問題求解空間，提出了一種改進的IAGA算法，利用理想點法和歐氏距離構造相應的適應度函數，最后返回q個最優企業組合信息，為企業領導層或領域專家的進一步決策提供信息支持。

2．1 伙伴初步篩選

為減少服務類WSi搜索空間中的服務數量，制定以下規則：

規則1 在任一服務類WSi中，對于?wsij（j＝1，2，…，mi），若合取式（4）不成立，則刪除wsij。

規則2 在任一服務類WSi中，如果（qwsij≥qwsik）∧ （twsij≤twsik）∧ （c′wsij≤cwsik），j≠k，則刪除wsik。其中，c′wsij＝cwsij＋max lwsij，ws（i＋1）k；k＝1，2，…，mi＋1。

2．2 算法準備

（1）編碼方法。令 X ＝ ｛x1，x2，…，xn｝（xi＝1，2，…，mi）為任一染色體，xi為服務類WSi中的某一服務，如染色體｛2，4，1，5，3｝，表示子任務TK1選中了可完成該子任務的某服務類WSi中的企業服務wsi2，其余類似。

（2）交叉概率Pc和變異概率Pm：

式中，fmax和f為群體最大適應度和平均適應度；f′為兩交叉個體較大的適應度；f為要變異個體的適應度；k1、k2、k3、k4取（0，1）區間的值。

對于不同的個體，適應度高的個體應給予保護，每個個體擁有不同的Pc和Pm。

（3）適應度函數設計。選用理想點法構造適應度函數，設有n個子任務構成的業務流程f1（x），f2（x），…，fn（x），對于每個目標函數分別有其最優值為f＋i。那么，可以將向量（f＋1，f＋2，…，f＋n）看作向量函數（f1（x），f2（x），…，fn（x））的正理想點。同理，將向量（f－1，f－2，…，f－n）看作向量函數（f1（x），f2（x），…，fn（x））的負理想點。基于歐式距離構造適應度函數為：

式中，l為目標函數個數（本文中l＝3）。

關于指標權重λij，對于同一個指標，不同的服務類由于企業完成任務性質不同可以賦以不同的權重。

2．3 算法描述

（1）按照規則進行伙伴初步篩選；

（2）初始化種群大小n，prior f itness［q］；

（3）隨機產生初始種群X0；

（4）選擇操作，采用輪盤選擇策略進行個體選擇；

（5）交叉操作，以概率Pc決定個體是否進行交叉操作，采用簡單的雙子雙親法，交配位隨機取位；

（6）變異操作，以變異概率Pm指定其變異點，對變異點的基因值由除該基因值以外的隨機產生的［1，mi］之間的數值取代；

（7）計算每個個體適應度值，進行適應度排序，將當前種群適應度前q個適應度值和相應個體信息保存到數組prior f itness［q］中；

（8）判斷是否滿足結束條件（文中將連續30代個體最大適應度值不變作為結束條件），如不滿足則返回步驟（4），否則，返回q個最優個體及其相應適應度值信息prior f itness［q］（q＞1），算法結束。

算法最后返回q個最優個體，這q個個體滿足成本低、響應速度快和服務質量高的要求，適應度值非常接近。然而適應度最高的個體并不一定是動態虛擬企業最理想的組合，因為在實際目標實施過程中，企業的合作信譽度、創新能力和服務水平等也是不容忽視的商務合作因素。另外，也可能出現返回的個體中，有一個或若干個企業服務由于企業自身某種客觀原因不能接受核心企業請求，即可能出現若干企業服務不可用的情況。所以，返回q個最優個體一方面可以避免服務不可用而重新選擇，核心企業決策層還可對這q個最優個體進行進一步的決策（如可采用模糊A HP等決策方法對企業合作信譽度、創新能力和服務水平等綜合評價）以選擇更為理想的個體，發揮領導決策層或領域專家的主觀能動性，以使動態虛擬企業具有更強的競爭優勢。

3 實驗分析

由于目前還沒有標準企業服務測試數據集，故本文采用隨機數進行驗證。按照圖2所示組合流程對動態虛擬企業伙伴選擇進行實驗，實驗平臺為Eclipse3．2，算法源碼用Java語言實現。為不同服務類隨機生成相應指標數據，同一服務類中，生產時間和成本指標設定為某區間［a，b］內的隨機數，質量指標設置為［1，10］之間的隨機整數，各指標權重λij為0到1之間的隨機數，針對權重的約束條件為：0．5］），i＝1，2，…，5。針對生產時間和成本指標的約束條件為：生產時間和成本指標在范圍［a，b］內不高于（a＋（b－a＋1）×0．7），質量指標不低于4。針對算法進化代數的約束條件為：連續30代最 大 適 應 度 不 變，k1＝ 0．3， k2＝0．9，k3＝0．01，k4＝0．5。

對自適應遺傳算法AGA和IAGA算法在不同服務數規模下進行實驗對比分析（相同規模服務數兩種算法采用相同隨機數），同時，為了分析兩種算法查找到的最佳個體是否是實際最優個體，設計了窮盡查找算法（br utalf orce search，BS）求解不同服務數規模下的實際最佳適應度，BS算法可在初步篩選前或篩選后執行。

（1）種群規模1000，每個服務類候選服務數規模從1變化到50時實驗對比結果如圖4所示。IAGA算法最佳適應度和實際最佳適應度吻合率（指適應度值相同的比率）為96%，在圖4中IAGA算法最佳適應度曲線基本被實際最佳適應度曲線所覆蓋，終止世代數平均為79．9，最佳適應度大小為0．8752。AGA算法最佳適應度和實際最佳適應度吻合率為84%，終止世代數平均為104．44，最佳適應度大小為0．8706。由于利用篩選機制，IAGA算法在終止世代數和適應度方面表現出了良好的性能。可以看出，隨著每個服務類候選服務數量的增加，最大適應度總體呈上升趨勢，這說明基于DVEPSEM模型的伙伴選擇，隨著企業發布的服務數量的增加，核心企業能夠查找到更為優化的伙伴組合，從而提高動態虛擬企業市場應變能力和核心競爭力。

圖4 在不同服務數規模下的對比實驗

（2）種群規模的大小直接影響到IAGA算法和AGA算法最佳適應度和實際最佳適應度吻合率，種群規模從100變化到1000（步長100），對服務類候選服務數從1到50進行200次實驗，計算各種群規模下的平均吻合率，實驗結果如圖5所示。隨著種群大小的變化，IAGA算法在適應度吻合率方面始終保持明顯的優勢，本實驗表明，IAGA算法能夠解決大規模的伙伴選擇，具有很強的全局尋優能力，種群規模應設置為一個較大的值（文中實驗應大于600），保證獲取的最佳個體為全局最優解。

圖5 種群規模對適應度吻合率的影響實驗

（3）種群規模1000，設定每個服務類候選服務數為30時，圖6所示為IAGA算法某次運行返回的5個最大適應度值及個體信息。從圖6可以看出，5個最優個體中最大適應度值為0．8260，最小適應度值為0．8124，子任務T K3、T K4和T K5的候選服務均相同，為｛16，8，29｝，T K1有兩個候選服務16和25，T K2有三個候選服務1、17和23可供選擇，為領導層或領域專家進一步決策提供信息支持。IAGA算法查找到的最優伙伴組合｛16，17，16，8，29｝和BS算法查找結果相同，結果是精確解。在算法中還設計了計算任意選取個體適應度值的功能，如果核心企業不選用IAGA算法推薦的這q個個體，還可以在企業DSS支持下選擇新個體，如輸入個體｛23，14，21，6，18｝，該個體適應度經計算結果為0．3898，可反復輸入。圖6中distribution（1）含義是經初步篩選以后BS算法計算出的所有個體的適應度值的分布情況，總的個體數為192192，未篩選總個體數為24 300 000，可見IAGA算法能夠較大程度地減小伙伴選擇搜索空間，從而提高伙伴選擇效率和查找準確性。

圖6 返回q個最佳個體信息實驗

4 總結

采用Web服務技術解決動態虛擬企業系統集成已成為一種完美的解決方案，因此，研究基于Web服務的動態虛擬企業伙伴選擇具有非常重要的意義。文中提出了一種動態虛擬企業伙伴選擇的擴展模型DVEPSEM，充分考慮了Web服務架構下服務數量會不斷變化和動態更新以及服務QoSextr指標約束和監督機制等問題，設計了基于DVEPSEM模型的IAGA算法，通過企業QoSextr約束等規則進行伙伴篩選，減小了搜索空間，利用理想點法和歐氏距離構造適應度函數，同時考慮到企業服務可能出現不可用的情況，返回q個適應度高的優良個體，一方面可以充分發揮領導層或領域專家的決策能力，提高虛擬企業的競爭力，另一方面避免了因個別服務不可用而重新選擇，提高效率。實驗表明，本文提出的DVEPSEM模型是合理可行的，IAGA算法在進化代數和最佳適應度方面均表現出了明顯的優勢，支持基于DVEPSEM模型的大規模動態虛擬企業伙伴選擇。

［1］ Zhu H，Liu S Y，Fang X R．Method f or Uncertain Multi－attribute Decision Making with Preference Inf or mation in the For m of Inter val Nu mbers Co mplementary Judgment Matrix［J］．Journal of Systems Engineering and Electronics，2007，18（2）：265－269．

［2］ Ye Fei，Li Y N．Group Multi－attribute Decision Model to Partner Selection in the For mation of Virtual Enter prise under Inco mplete Infor mation［J］．Expert Systems with Applications，2009，36（5）：9350－9357．

［3］ 張成考，聶茂林，吳價寶．基于改進型灰色評價的虛擬企業合作伙伴選擇［J］．系統工程理論與實踐，2007，27（11）：54－60．

［4］ 李劍，景博，牛少彰，等．基于自適應遺傳算法的企業動態聯盟伙伴選擇模型［J］．通信學報，2009，30（8）：78－83．

［5］ 蔣建國，夏 娜，張國富，等．基于蟻群算法的敏捷供應鏈伙伴選擇［J］．系統仿真學報，2006，18（12）：3377－3379．

［6］ Zhao F Q，Hong Y，Yu D M，et al．A Novel Genetic Algorithm f or Partner Selection Problem in Virtual Enter prise［C］／／Proceedings of t he ICMA’04．Chengelu，China，2004：477－482．

［7］ 蘇兆品，蔣建國，夏娜，等．一種基于免疫的敏捷虛擬企業伙伴選擇算法［J］．中國機械工程，2008，19（8）：925－928．

［8］ Y Rezgui．Role－based Service－oriented Implementation of a Virtual Enterprise：a Case Study in the Constr uction Sector［J］．Co mputers in Industry，2007，58（1）：74－86．

［9］ 張明寶，夏安邦．基于面向服務體系架構的敏捷虛擬企業信息系統框架［J］．計算機集成制造系統，2004，10（8）：985－990．

［10］ Shen W M，Hao Q，Wang S，et al．An Agentbased Service－oriented Integration Architecture f or Collaborative Intelligent Manufacturing［J］．Robotics and Computer－integrated Manufacturing，2007，23（3）：315－325．

［11］ Zeng Z B，Li Y，Zhu W．Partner Selection with a Due Date Constraint in Virtual Enter prises［J］．Applied Mathematics and Co mputation，2006，175（2）：1353－1365．