Ｗｅｂ服務平臺下基于遺傳算法的制造資源服務選擇

（1. 西南交通大學 機械工程學院， 成都 610031； 2.貴州大學 現代制造技術重點實驗室， 貴陽 550003）

摘 要：

針對基于Web的制造資源服務平臺中的制造資源服務選擇優化問題，建立了制造資源的質量屬性模型，提出了一種基于質量的遺傳算法。該算法設計了一種資源—任務關系矩陣編碼方式；選擇、交叉、變異等遺傳操作只對矩陣主對角線上的任務位進行；適應度函數的設計采用制造資源服務組合的質量屬性來描述。應用MATLAB遺傳算法工具箱編程驗證了該算法的合理性和實用性。

關鍵詞：Web服務； 制造資源； 遺傳算法； 服務選擇； MATLAB

中圖分類號：TP391.9文獻標志碼：A

文章編號：1001-3695(2009)04-1266-03

Genetic algorithm model of manufacturing resource services selection under Web service platform

YUAN Qing-ni1， 2， XIE Qing-sheng2， XU Ming-heng1， ZHOU Gui-xian2

(1. School of Mechanical Engineering， Southwest Jiaotong University， Chengdu 610031， China; 2. Key Laboratory of Advanced Manufacturing Technology， Guizhou University， Guiyang 550003， China）

Abstract:

This paper studied manufacturing resource management system of Web service platform， genetic algorithm， and quality property of service. In order to choose the best combination of services， and to meet the requirement from manufacturing resource service requestors， put forward the QoS-based genetic algorithm model. The algorithm used resources-task matrix coding. Chromosome was a specific performance of task on the main diagonal， which was a combination. Choice， crossover and mutation were only operated on the task bits of the main diagonal matrix. Described the fitness function in quality. In addition， tested the modelits feasibility and practicability by MATLAB.

Key words：Web service; manufacturing resources; genetic algorithm; services selection; MATLAB

隨著計算機技術和網絡技術的發展，全球范圍內的信息資源共享更加便利，Web制造資源服務數量激增。企業只有通過柔性的整合制造資源，加強企業間的合作，才能全面提升競爭力[1，2]。基于Web的制造資源管理平臺以企業間業務過程集成為特征實現制造資源整合，它為企業間業務集成提供一個基于開放標準、響應動態更改、支持異構系統以及安全性強的制造資源管理系統，為不同類型企業及客戶發布交易數據、提供和選擇可用共享制造資源、實現端到端業務集成提供基礎平臺支持[3]。該服務平臺主要依賴于Web技術及基于知識的管理技術來實現。如何在眾多Web服務中找到最優的制造資源Web服務，是Web服務平臺關鍵的問題。

1 問題的提出

在該服務平臺中，基于Web的制造資源共享服務描述模型為WS = { S， C，P}。其中:S是服務的制造企業、制造資源、制造對象等；C是制造任務；P是屬性描述，主要包括成本(cost) 、響應時間(time) 、質量（quality）、服務優先級(priorities) 等。在上述描述模型中，內容描述S往往是概要性的描述；功能描述C是服務請求者判斷Web服務能否滿足其功能需求的主要依據，希望行為足夠嚴格以及交互時有精確的和可預見的輸出；屬性描述P為服務請求者選擇服務提供積極、有意義的參考[4，5]。

從制造資源共享的Web服務描述模型可以看出，許多制造資源具有相同的基本描述S和制造任務C，但它們的屬性描述P是不同的。因此，可以根據屬性計算來進行制造資源的選擇，使制造資源選擇問題轉換為優化組合問題，而解決優化問題最好的方法是遺傳算法。

2 Web服務平臺中制造資源質量描述模型

制造資源Web描述模型中的屬性描述（P）主要對制造資源的質量（QoS）進行描述，可表示為

RQoS={QT，QQ，QC，QS，QE，QL，Qr}

其中： QT 、 QQ、QC、QS、QE、QL 和QY 分別表示資源信息中與時間相關的屬性集、與質量相關的屬性集、與成本相關的屬性集、與服務相關的屬性集、與信譽度相關的屬性集、與可靠性相關的屬性集，以及該資源在策略管理器中發布的對外提供服務的策略(圖1) [6]。

根據QoS計算模型，得出制造資源服務選擇組合基于質量的數學模型：

max∑7i=1(wi×Qi)（1）

其中：wi為相應QoS屬性的權值，表示用戶對QoS屬性的關注程度，并且0≤wi≤1，∑7i=1wi=1；Qi為個體i項QoS的屬性值。



3 基于資源—任務關系矩陣編碼方式的遺傳算法

根據在Web服務平臺下的制造資源服務選擇組合的特性，提出了資源—任務關系矩陣編碼方式，即將關系矩陣主對角線具體化為不同的組合來構成種群的個體，并按照基于質量的適應度函數進行個體選擇。由于種群是由屬于不同組合路徑構成的，交叉或變異操作需要依據矩陣的任務關系位判斷新生成組合是否存在，直到生成新種群；新種群再次經歷選擇、交叉、變異生成下一代種群；如此迭代，直到滿足算法終止條件后算法終止。

3.1 染色體關系矩陣編碼方式

3.1.1 制造資源的服務選擇

制造資源服務選擇是根據用戶提交的任務進行選擇。任務是用戶提交的，通過Web服務平臺進行資源搜索而提供一個任務所需的資源組合。任務可以分解為子任務，一個任務可以有多個不同的子任務組合方案，每個子任務會有多個制造資源服務組件與之對應，這些服務組件具有對應任務所要求的功能但具有不同的QoS屬性，因此每條路徑又存在多個具有不同QoS屬性的服務選擇組合方案[7]。最優的制造資源服務選擇方案是從眾多路徑、眾多方案中選出的一個符合用戶QoS限制與需求的服務組合方案。

以用戶提交的咖啡機底座的快速成型加工任務為例進行制造資源選擇，經任務分解與規劃后，該任務需Pro/Engineer三維造型設計軟件、仿真資源和RP設備共三種類型快速成型制造資源，分別完成咖啡上底座和下底座的造型及裝配設計、仿真分析、成型加工等子任務。假設現有四類不同路徑的服務組合方案，可完成以上加工任務（圖2）。在圖2中，ti表示制造任務中的第i項任務。其中：t1，t4對應設計任務；t2對應仿真分析任務；t3，t5對應成型加工任務，也表示完成服務組合的某個制造資源服務。從起始任務到終止任務路徑上的任務關系可以用工作流來表示，即圖2中的箭頭線。

設咖啡機底座的快速成型加工任務的制造資源服務組合Ts由五個子任務組成，表示為

 Ts={t1，t2，t3，t4，t5}

3.1.2 關系矩陣編碼

資源—任務染色體關系矩陣的編碼采用圖論中鄰接矩陣的思想，設計出既能反映制造資源服務組合關系，又能反映制造任務路徑信息的編碼方式。對咖啡機底座的快速成型加工任務的制造資源選擇的遺傳算法編碼方式如下：

βij=1100001101000000100001001；i=1，…，5； j=1，…，5

βii對應組合中的所有任務。矩陣主對角線上的位置表示基因位，并且固定對應于制造資源組合服務中的任務。

βii=1 表示本次服務組合中包含該任務0 表示本次服務組合中未包含該任務

βij是任務關系位，表示任務i與任務j在組合服務工作流中的直接前后關系，在工作路徑確定后，位取值不再發生改變。

βij=1 表示任務i在工作流中是任務j的直接前趨0 表示任務i在工作流中不是任務j的直接前趨

由此可知，基因位為矩陣主對角線上的元素，代表制造資源服務組合中工作流的任務；染色體為矩陣主對角線上任務排列的具體表現，代表組合服務的一個組合方案；種群是組合服務方案集合中的一部分；交叉、變異操作只對矩陣主對角線上的任務位進行操作。βij的位置矩陣編碼如下：

t110000t210100t300010t400100t5

在具體的編碼中，矩陣的主對角線由具體數值取代。

3.2 咖啡機底座快速成型加工任務的遺傳算法適應度函數

用戶一般會對制造資源服務的選擇提出QoS要求或限制，如時間不能超過一年，成本小于150萬等，目標函數值大且滿足QoS限制的個體具有競爭力。罰函數法是一種通用的處理受限優化問題的方法，采用罰函數法將限制條件與目標函數綜合在一起，構成適應度函數fit。對于咖啡機底座的快速成型加工任務的制造資源選擇，采用與時間相關、與成本相關、與服務相關的屬性集作為限制條件構造罰函數。其適應度函數fit為

fit=∑7i=1(wi×Q′i)-λ∑nj=1[ΔPj/（Rjmax-Rjmin)]2

其中:Rjmax、Rjmin分別為第j個約束條件中的最大值和最小值;n為約束條件個數（n=3）;λ為系數，屬于經驗值（取λ=0.35）;Pj表示某個或某些Qi的運算值（因為某些限制條件是對多個Qi計算結果的限制），ΔPi定義為

ΔPi=Pj-Rjmax PjRjmax0Rjmin≤Pj≤RjmaxRjmin-pjpRjmin

3.3 咖啡機底座快速成型加工任務的初始種群的產生

完全隨機的方法產生初始群體p = ( p1 ， p2 ，…， ppopsize) ，popsize 為種群規模（popsize=100）。由于種群是由屬于不同組合路徑構成的，交叉或變異操作需要依據矩陣的任務關系位判斷新生成組合是否存在，直到生成新種群。

3.4 遺傳操作

1） 選擇 采用輪盤賭選擇方法。首先計算出群體中各個個體所對應的適應度總和 ∑ni=1fi，再計算出每一個個體的相對適應度大小 fi/∑ni=1fi。 它即為每一個個體遺傳到下一代群體中的概率，每一個概率的值組成一個區域，全部的概率和為1。最后再產生一個0~1的隨機數，依據該隨機數出現在上述的哪個概率區域來確定各個個體被選中的次數。采用精英法則， 強行將上一代的最優個體直接進入下一代。這樣，每進化一代，下一代的最優個體一定不劣于上一代。

2）交叉 采用均勻交叉操作，設S1、S2 是兩個待交叉的父個體， 隨機產生與父個體等長的兩個0~1 掩碼（掩碼中的片段表明了哪個父個體向新個體提供變量值），利用掩碼形成兩個新個體。

3）變異 采用均勻變異操作，均勻變異率取0.1 ，可以隨著項目的個數增加而增加。

咖啡機底座的快速成型加工任務的資源—任務關系矩陣編碼方式遺傳算法的計算過程如圖3所示。

4 應用MATLAB編程實現制造資源的選擇

為了選出咖啡機底座的快速成型加工任務最優的制造資源服務組合方案，其適應度函數中以服務組合的QoS屬性為評價標準，即RQoS={RT，RQ，RC，RE，RL，RY}。假設經過專家打分法，該加工任務的服務組合的各質量屬性權向量為 W={0.272，0.252，0.132，0.172，0.172}。參數設置為：種群數100、均勻交叉率0.7、均勻變異率0.1[8] 、終止迭代數100。其結果如圖4所示。



f(11001)= 31.31為最優適應度值，則關系矩陣編碼為

1100001101000000100001001

解碼得到ts→t1→t2→t5→te為最優路徑的服務組合。

通過基于Web的制造資源管理平臺找到t1（對應設計任務）、t2（仿真分析任務）、t5（成型加工任務），相對應的制造資源組件的提供商，用戶即能找到最優的制造資源，完成加工任務。

5 結束語

Web服務以其特有優勢具有廣泛的應用前景。本文針對制造資源服務平臺中制造資源的Web服務選擇，提出了一種基于質量的遺傳算法。該算法采用資源—任務關系的編碼方式，體現了染色體特征由基因及基因關系共同決定的特點，通過一次搜索就可以從所有工作流路徑中選出滿足用戶QoS需求的Web服務組合。為豐富Web服務組合遺傳算法進行了有益的探討。

參考文獻：

[1]XIE Qing-sheng.Study on manufacture resource evaluating system of the ASP-based platform[C]//Proc of IPROMS 2005. 2005:315-320.

[2]XIE Qing-sheng， LI Shao-bo. Framework desing of the ASP based network manufacturing system[C]//Proc of e-ENGDET2006.2006:206-211.

[3]SHEVCHENKO A. Formal requirements specification for e-HUBs (D1)[R].Springfield: Delft University of Technology， 2003.

[4]周丹晨，殷國富. 面向網絡化制造的資源共享服務平臺研究[J]. 計算機集成制造系統，2005，11(6):781-786.

[5]孫家坤，李兆前，黃傳真，等. 網絡化制造中的制造資源建模研究[J].機床與液壓，2005(10):37-39.

[6]劉麗蘭，俞濤，施戰備. 制造網格中基于服務質量的資源調度研究[J]. 計算機集成制造系統，2005， 11(4):475-480.

[7]胡建強，鄒鵬，王懷民，等. Web 服務描述語言QWSDL 和服務匹配模型研究[J].計算機學報，2005，28(4):506-512.

[8]雷英杰. MATLAB-遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社，2005.