嚴(yán)良達(dá)

摘要：隨著Web服務(wù)技術(shù)的快速發(fā)展和廣泛應(yīng)用，單個(gè)Web服務(wù)的功能已經(jīng)無(wú)法滿足復(fù)雜應(yīng)用的需求，因而需要將原子服務(wù)進(jìn)行組合，從而形成功能強(qiáng)大的組合服務(wù)以完成復(fù)雜事務(wù)。該文提出了改進(jìn)的遺傳算法，來(lái)解決基于QoS感知的Web服務(wù)組合問(wèn)題，算法從編碼方式、初始化種群、適應(yīng)度函數(shù)、進(jìn)化選擇策略等方面對(duì)進(jìn)行改進(jìn)，使得服務(wù)選擇算法具有更好的收斂速度和搜索尋優(yōu)能力。

關(guān)鍵詞：Web服務(wù)；遺傳算法；QoS

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）35-8574-02

1 Web服務(wù)的定義

Web服務(wù)是一個(gè)獨(dú)立于平臺(tái)、自包含、松耦合、基于可編程的Web應(yīng)用程序，可以使用開(kāi)放的XML標(biāo)準(zhǔn)描述、發(fā)布、協(xié)調(diào)和配置這些應(yīng)用程序，用于開(kāi)發(fā)分布式的互操作的應(yīng)用程序。通俗的來(lái)講，對(duì)于Web服務(wù)訪問(wèn)者而言，Web服務(wù)就是一種部署在Web上的對(duì)象或組件，具備對(duì)象的良好封裝性，用戶只能通過(guò)服務(wù)接口對(duì)服務(wù)進(jìn)行訪問(wèn)；Web服務(wù)基于標(biāo)準(zhǔn)的協(xié)議和規(guī)范被發(fā)布、部署和調(diào)用；當(dāng)一個(gè)Web服務(wù)接口不發(fā)生變化，對(duì)于該服務(wù)的調(diào)用就不會(huì)發(fā)生變化，實(shí)現(xiàn)了調(diào)用的透明化；由于Web服務(wù)采用簡(jiǎn)單易于理解的標(biāo)準(zhǔn)協(xié)議作為組件界面描述，完全屏蔽了不同平臺(tái)的差異，實(shí)現(xiàn)了當(dāng)前環(huán)境下的高度集成性。

2 遺傳算法概述

遺傳算法是一種借鑒達(dá)爾文生物進(jìn)化論和遺傳學(xué)機(jī)理的生物進(jìn)化計(jì)算模型，它通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的算法。1975年，遺傳算法由美國(guó)Michigan大學(xué)J.Holland教授所提出，他提出的為最初的遺傳算法，即簡(jiǎn)單遺傳算法?，F(xiàn)在遺傳算法廣泛應(yīng)用在很多學(xué)科中，應(yīng)用領(lǐng)域主要有函數(shù)優(yōu)化、生產(chǎn)調(diào)度、自動(dòng)控制、機(jī)器人智能控制、組合優(yōu)化、圖像處理好熱模式識(shí)別以及機(jī)器學(xué)習(xí)等，并且在工程技術(shù)和社會(huì)經(jīng)濟(jì)中的大量的應(yīng)用。

在遺傳算法中，主要使用的術(shù)語(yǔ)有以下幾種：

組合路徑：組合路徑由一組抽象服務(wù)根據(jù)一定邏輯關(guān)系組合而成。

組合計(jì)劃：組合計(jì)劃是指組合路徑中抽象服務(wù)被其對(duì)應(yīng)的具體服務(wù)替換后形成的服務(wù)序列。

個(gè)體：在本文中，個(gè)體是指能完成用戶請(qǐng)求的單個(gè)組合計(jì)劃，也即問(wèn)題可能潛在的解。

基因：在遺傳算法的Web服務(wù)組合中，基因指的是Web服務(wù)組合中每個(gè)抽象服務(wù)。

基因位：Web服務(wù)組合中抽象服務(wù)在組合服務(wù)中的位置。

染色體：在遺傳算法的Web服務(wù)組合中，染色體對(duì)應(yīng)的是不同組合路徑上的組合計(jì)劃。

種群：在本文中，種群是代表問(wèn)題一個(gè)可能潛在的解的集合，它具有一定數(shù)量組合計(jì)劃，而且這些組合計(jì)劃符合用戶需求。

3 遺傳算法的特點(diǎn)和運(yùn)行過(guò)程

3.1遺傳算法的特點(diǎn)

遺傳算法作為一種有別于傳統(tǒng)算法的搜索和優(yōu)化方法，主要區(qū)別有下面幾點(diǎn)：

1）遺傳算法與傳統(tǒng)算法最大的區(qū)別在于它行問(wèn)題解的串集開(kāi)始搜索，而不是從單個(gè)解開(kāi)始。遺傳算法從串集開(kāi)始搜索，覆蓋范圍廣，利于全局選優(yōu)。傳統(tǒng)的優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解，容易陷入局部最優(yōu)解。

2）遺傳算法強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是采用確定的轉(zhuǎn)換規(guī)則來(lái)指引它的搜索方向。

3）遺傳算法不必求導(dǎo)和其它方面的知識(shí)，僅僅使用一個(gè)適應(yīng)度函數(shù)來(lái)評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。

4）遺傳算法可以同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中多個(gè)解進(jìn)行評(píng)估，從而降低了陷入局部最優(yōu)解的幾率，同時(shí)遺傳算法易于實(shí)現(xiàn)并行。許多搜索算法都是單點(diǎn)搜索，易陷入局部的最優(yōu)解。

5）遺傳算法還具有自組織性、自學(xué)習(xí)和自適應(yīng)性。遺傳算法在確定了染色體編碼方式、遺傳算子和適應(yīng)度函數(shù)之后，就會(huì)利用演化過(guò)程中的信息進(jìn)行組織搜索。由于采用基于達(dá)爾文生物進(jìn)化論的選擇策略，所以存活幾率取決于個(gè)體適應(yīng)度的大小。適應(yīng)度越大的染色體個(gè)體將擁有更加適應(yīng)所處環(huán)境的基因，進(jìn)而通過(guò)基因重組、突變這些操作，可能會(huì)產(chǎn)生對(duì)環(huán)境有更加適應(yīng)特性的個(gè)體。

3.2遺傳算法的運(yùn)行過(guò)程

遺傳算法運(yùn)算對(duì)象為M個(gè)個(gè)體組成一個(gè)種群，其與生物自然進(jìn)化過(guò)程相似，算法運(yùn)算過(guò)程也是一個(gè)不斷循環(huán)迭代的過(guò)程。記第n代為P（n），經(jīng)過(guò)一代的遺傳演化后得到n+l代，記為P（n+1）。然后種群通過(guò)不斷地遺傳和進(jìn)化，按照生物進(jìn)化論的法則適應(yīng)度高的染色體個(gè)體將遺傳到下一代中，最后進(jìn)化后得到的種群接近或者達(dá)到問(wèn)題的最優(yōu)解。遺傳算法中，父代P（n）產(chǎn)生下一代，P（n+1）主要通過(guò)選擇、交叉和編譯操作來(lái)實(shí)現(xiàn)。選擇操作是根據(jù)個(gè)體適應(yīng)度進(jìn)行選擇進(jìn)入下一代的個(gè)體。交叉操作是隨機(jī)選擇種群中個(gè)體以一定概率交換染色體個(gè)體上的部分基因，以得到新個(gè)體。變異操作是對(duì)種群個(gè)體以一定概率改變其基因位上的基因來(lái)產(chǎn)生新個(gè)體。

遺傳算法的具體流程：

1）初始化種群：遺傳算法中基本的個(gè)體為染色體，初始化時(shí)，每一個(gè)染色體的基因的值是隨機(jī)產(chǎn)生的。隨機(jī)產(chǎn)生是為了希望種群能夠均勻的分布在整個(gè)解空間中。

2）計(jì)算適應(yīng)度函數(shù)：透過(guò)計(jì)算每一個(gè)染色體的適應(yīng)度值作為其在種群適應(yīng)程度的指標(biāo)，適應(yīng)度大的染色體就有較高的幾率進(jìn)入下一代繼續(xù)得以進(jìn)化，而適應(yīng)值低者則有較高幾率被淘汰。

3）選擇：依據(jù)母代中染色體之適應(yīng)值來(lái)決定哪些染色體得以進(jìn)入下一代或者被淘汰。即選擇幾率的大小取決于染色體適應(yīng)值的好壞。適應(yīng)值較差的染色體對(duì)于子代的貢獻(xiàn)度較小，被淘汰的幾率較大。與之相反，適應(yīng)值較大的染色體可以產(chǎn)生優(yōu)秀的子代，故有較高的幾率進(jìn)入下一代進(jìn)化，如此一來(lái)進(jìn)化的過(guò)程中，可以搜索的參數(shù)收斂至整體最優(yōu)解的幾率得到提高。

4）交配：通過(guò)選擇，可以使母代染色體中較優(yōu)秀的染色體在下一代中生存，但并未創(chuàng)造出新的個(gè)體，因此要通過(guò)交配和突變產(chǎn)生新的個(gè)體，以創(chuàng)造出更好的個(gè)體，基本做法為隨機(jī)選擇兩個(gè)母代染色體，并隨機(jī)獲取一個(gè)或者多個(gè)交配點(diǎn)嗎、，將染色體基因信息切割成多個(gè)片段，再通過(guò)兩個(gè)母代染色體交換其染色體基因信息片段來(lái)產(chǎn)生新的個(gè)體。

5）突變：通過(guò)選擇交配雖然能夠有效的在已有的種群中搜尋，但其缺點(diǎn)是無(wú)法產(chǎn)生新的染色體，畢竟交配仍是交換原有的染色體基因，因此，必須利用突變來(lái)防止進(jìn)化的過(guò)程過(guò)早收斂至區(qū)域最佳解，為此用隨機(jī)選取一個(gè)母代染色體以及獲取突變位置，并置換該位置的基因代碼。過(guò)高的突變幾率將造成整個(gè)進(jìn)化的過(guò)程完全隨機(jī)化，導(dǎo)致無(wú)法收斂至整體最佳解。

6）終止：進(jìn)化過(guò)程是最后一步就是設(shè)置終止條件，否則進(jìn)化過(guò)程將如同死循環(huán)不斷運(yùn)行，而對(duì)于能否順利的收斂至最優(yōu)解，設(shè)置合適的終止條件也是相當(dāng)重要的一個(gè)環(huán)節(jié)。

4 改進(jìn)的遺傳算法流程

有了前面的理論基礎(chǔ)，該文在應(yīng)用遺傳算法基礎(chǔ)上進(jìn)行改進(jìn)，解決了基于QoS的服務(wù)組合中的關(guān)鍵問(wèn)題。利用改進(jìn)的一維染色體的編碼，同時(shí)也使用優(yōu)化的初始化種群生成策。在算法運(yùn)行整個(gè)過(guò)程里，該文設(shè)計(jì)了帶有動(dòng)態(tài)懲罰機(jī)制的適應(yīng)度函數(shù)對(duì)種群中的個(gè)體進(jìn)行選擇，相對(duì)傳統(tǒng)遺傳算法本文利用可動(dòng)態(tài)變化的選擇概率和交叉概率。算法流程圖如圖1所示。

算法具體流程描述如下：

1）染色體編碼。采用染色體樹(shù)型編碼方式進(jìn)行編碼。

2） 初始化操作。根據(jù)文中提出的初始化策略進(jìn)行種群初始化。

3） 個(gè)體評(píng)價(jià)。對(duì)種群中的所有個(gè)體進(jìn)行個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)操作。

4）最優(yōu)個(gè)體保存。找出種群中最優(yōu)的個(gè)體，并對(duì)其進(jìn)行保存。

5） 個(gè)體選擇操作?；诜N群中每個(gè)個(gè)體的適應(yīng)度大小進(jìn)行選擇操作，個(gè)體選擇的幾率與適應(yīng)度大小成正比例關(guān)系。

6） 交叉操作。對(duì)種群中的配對(duì)個(gè)體進(jìn)行自適應(yīng)的交叉操作。

7）變異操作。對(duì)種群中的個(gè)體進(jìn)行自適應(yīng)的變異操作。

8） 個(gè)體評(píng)價(jià)。對(duì)種群中的所有個(gè)體進(jìn)行個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)。

9） 如果當(dāng)前種群最優(yōu)個(gè)體的適應(yīng)度比歷史最優(yōu)個(gè)體的適應(yīng)度高，則用當(dāng)前種群最優(yōu)個(gè)體替換歷史最優(yōu)個(gè)體；否則，用歷史最優(yōu)的個(gè)體替換當(dāng)前群體中最差個(gè)體。

10）結(jié)束條件判斷。判斷條件是否達(dá)到終止條件，若達(dá)到則繼續(xù)下一步驟，否則轉(zhuǎn)到步驟（5）。

11）染色體解碼。將得到的染色體序列轉(zhuǎn)化為實(shí)際問(wèn)題的解，即可執(zhí)行的復(fù)合Web服務(wù)。

5 結(jié)束語(yǔ)

本文首先介紹了Web服務(wù)和遺傳算法的基本概念，詳細(xì)的闡述了遺傳算法的特點(diǎn)和運(yùn)行過(guò)程，針對(duì)Web服務(wù)組合中應(yīng)用遺傳算法的不足，從編碼方式、初始化種群、進(jìn)化策略等方面對(duì)服務(wù)選擇遺傳算法提出改進(jìn)，使算法滿足基于Qos感知的服務(wù)組合問(wèn)題。基于QoS感知的Web服務(wù)選擇是一個(gè)復(fù)雜的研究問(wèn)題，下一步要做的工作是結(jié)合服務(wù)語(yǔ)義，構(gòu)建更全面的QoS評(píng)價(jià)模型，使得服務(wù)選擇不僅具有通用性，而且還具有支持服務(wù)的領(lǐng)域特性。

參考文獻(xiàn)：

[1] 帕派佐格羅.Web服務(wù)原理和技術(shù)[M].龔玲，張?jiān)茲?，譯.北京：機(jī)械工業(yè)出版社，2010：169-202.

[2] 王陽(yáng)陽(yáng)，李俊.一種基于QoS全局最優(yōu)的服務(wù)選擇算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（5）：1659-1661.

[3] 張文博，史維峰.基于BPEL和QoS的動(dòng)態(tài)Web服務(wù)組合框架研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（11）：72-75.

[4] 程永上.Web服務(wù)組合建模與驗(yàn)證[M].北京：中國(guó)物資出版社，2011.