（1. 西南交通大學(xué) 機(jī)械工程學(xué)院， 成都 610031； 2.貴州大學(xué) 現(xiàn)代制造技術(shù)重點(diǎn)實(shí)驗(yàn)室， 貴陽 550003）

摘 要：

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

關(guān)鍵詞：Web服務(wù)； 制造資源； 遺傳算法； 服務(wù)選擇； MATLAB

中圖分類號(hào)：TP391.9文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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

隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展，全球范圍內(nèi)的信息資源共享更加便利，Web制造資源服務(wù)數(shù)量激增。企業(yè)只有通過柔性的整合制造資源，加強(qiáng)企業(yè)間的合作，才能全面提升競爭力[1，2]?；赪eb的制造資源管理平臺(tái)以企業(yè)間業(yè)務(wù)過程集成為特征實(shí)現(xiàn)制造資源整合，它為企業(yè)間業(yè)務(wù)集成提供一個(gè)基于開放標(biāo)準(zhǔn)、響應(yīng)動(dòng)態(tài)更改、支持異構(gòu)系統(tǒng)以及安全性強(qiáng)的制造資源管理系統(tǒng)，為不同類型企業(yè)及客戶發(fā)布交易數(shù)據(jù)、提供和選擇可用共享制造資源、實(shí)現(xiàn)端到端業(yè)務(wù)集成提供基礎(chǔ)平臺(tái)支持[3]。該服務(wù)平臺(tái)主要依賴于Web技術(shù)及基于知識(shí)的管理技術(shù)來實(shí)現(xiàn)。如何在眾多Web服務(wù)中找到最優(yōu)的制造資源Web服務(wù)，是Web服務(wù)平臺(tái)關(guān)鍵的問題。

1 問題的提出

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

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

2 Web服務(wù)平臺(tái)中制造資源質(zhì)量描述模型

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

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

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

根據(jù)QoS計(jì)算模型，得出制造資源服務(wù)選擇組合基于質(zhì)量的數(shù)學(xué)模型：

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

其中：wi為相應(yīng)QoS屬性的權(quán)值，表示用戶對(duì)QoS屬性的關(guān)注程度，并且0≤wi≤1，∑7i=1wi=1；Qi為個(gè)體i項(xiàng)QoS的屬性值。



3 基于資源—任務(wù)關(guān)系矩陣編碼方式的遺傳算法

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

3.1 染色體關(guān)系矩陣編碼方式

3.1.1 制造資源的服務(wù)選擇

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

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

設(shè)咖啡機(jī)底座的快速成型加工任務(wù)的制造資源服務(wù)組合Ts由五個(gè)子任務(wù)組成，表示為

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

3.1.2 關(guān)系矩陣編碼

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

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

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

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

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

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

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

t110000t210100t300010t400100t5

在具體的編碼中，矩陣的主對(duì)角線由具體數(shù)值取代。

3.2 咖啡機(jī)底座快速成型加工任務(wù)的遺傳算法適應(yīng)度函數(shù)

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

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

其中:Rjmax、Rjmin分別為第j個(gè)約束條件中的最大值和最小值;n為約束條件個(gè)數(shù)（n=3）;λ為系數(shù)，屬于經(jīng)驗(yàn)值（取λ=0.35）;Pj表示某個(gè)或某些Qi的運(yùn)算值（因?yàn)槟承┫拗茥l件是對(duì)多個(gè)Qi計(jì)算結(jié)果的限制），ΔPi定義為

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

3.3 咖啡機(jī)底座快速成型加工任務(wù)的初始種群的產(chǎn)生

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

3.4 遺傳操作

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

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

3）變異 采用均勻變異操作，均勻變異率取0.1 ，可以隨著項(xiàng)目的個(gè)數(shù)增加而增加。

咖啡機(jī)底座的快速成型加工任務(wù)的資源—任務(wù)關(guān)系矩陣編碼方式遺傳算法的計(jì)算過程如圖3所示。

4 應(yīng)用MATLAB編程實(shí)現(xiàn)制造資源的選擇

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



f(11001)= 31.31為最優(yōu)適應(yīng)度值，則關(guān)系矩陣編碼為

1100001101000000100001001

解碼得到ts→t1→t2→t5→te為最優(yōu)路徑的服務(wù)組合。

通過基于Web的制造資源管理平臺(tái)找到t1（對(duì)應(yīng)設(shè)計(jì)任務(wù)）、t2（仿真分析任務(wù)）、t5（成型加工任務(wù)），相對(duì)應(yīng)的制造資源組件的提供商，用戶即能找到最優(yōu)的制造資源，完成加工任務(wù)。

5 結(jié)束語

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

參考文獻(xiàn)：

[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]周丹晨，殷國富. 面向網(wǎng)絡(luò)化制造的資源共享服務(wù)平臺(tái)研究[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2005，11(6):781-786.

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

[6]劉麗蘭，俞濤，施戰(zhàn)備. 制造網(wǎng)格中基于服務(wù)質(zhì)量的資源調(diào)度研究[J]. 計(jì)算機(jī)集成制造系統(tǒng)，2005， 11(4):475-480.

[7]胡建強(qiáng)，鄒鵬，王懷民，等. Web 服務(wù)描述語言QWSDL 和服務(wù)匹配模型研究[J].計(jì)算機(jī)學(xué)報(bào)，2005，28(4):506-512.

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