基于文化遺傳算法的QoS感知的服務(wù)組合

柳正利，李兵，強(qiáng)保華，王靜

基于文化遺傳算法的QoS感知的服務(wù)組合

柳正利1，李兵1，強(qiáng)保華2，王靜3

(1. 武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢，430079；2. 桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林，541004； 3. 中國(guó)電子技術(shù)標(biāo)準(zhǔn)化研究院，北京，100007)

為了提高服務(wù)組合的效率，提出1種改進(jìn)的基于文化遺傳算法的QoS感知的服務(wù)組合方法。首先構(gòu)建社會(huì)種群和信仰雙層空間，然后利用接收函數(shù)從社會(huì)種群中提取種群進(jìn)化學(xué)習(xí)到的知識(shí)并更新信仰空間，進(jìn)而利用信仰空間來引導(dǎo)社會(huì)種群進(jìn)化，加快算法的收斂性，提高組合效率。研究結(jié)果表明：與傳統(tǒng)的文化遺傳算法和經(jīng)典的遺傳算法相比，本文提出的算法收斂所需的迭代次數(shù)明顯降低，執(zhí)行效率和收斂速度均有所提高。

服務(wù)組合；QoS感知；文化遺傳算法；服務(wù)選擇

隨著Web服務(wù)技術(shù)的成熟，軟件系統(tǒng)的架構(gòu)模式逐漸從傳統(tǒng)的面向組件演變?yōu)槊嫦蚍?wù)的計(jì)算模式。憑借強(qiáng)大的可擴(kuò)展性和良好的異構(gòu)資源整合能力，Web服務(wù)為企業(yè)之間進(jìn)行的無縫業(yè)務(wù)集成提供了可能。隨著大量具有相同功能的開放Web服務(wù)的不斷匯聚，服務(wù)合成的關(guān)鍵問題不再是找到所需服務(wù)，如何從海量Web服務(wù)中快速挑選出滿足用戶需求、可信度高、具有良好質(zhì)量保障的Web服務(wù)，成為服務(wù)組合領(lǐng)域的新課題[1]?，F(xiàn)代商業(yè)生態(tài)系統(tǒng)變得日益龐大與復(fù)雜，企業(yè)業(yè)務(wù)環(huán)境復(fù)雜多變，這對(duì)組合服務(wù)的功能需求和非功能需求都提出了越來越高的要求。對(duì)于業(yè)務(wù)系統(tǒng)下的每個(gè)工作流節(jié)點(diǎn)，都存在眾多功能類似但服務(wù)質(zhì)量不同的服務(wù)可供選擇。從服務(wù)質(zhì)量的角度出發(fā)，對(duì)這些候選服務(wù)集進(jìn)行篩選與組合，在服務(wù)數(shù)量龐大的情況下，可能會(huì)出現(xiàn)“組合爆炸”，這是一個(gè)典型的NP難問題。遺傳算法通過借鑒生物進(jìn)化原理，運(yùn)用選擇、交叉、變異等自然進(jìn)化過程對(duì)個(gè)體執(zhí)行遺傳操作，并借助適應(yīng)度函數(shù)對(duì)種群個(gè)體實(shí)行“優(yōu)勝劣汰”評(píng)價(jià)，這樣經(jīng)過不斷地迭代，最終適應(yīng)度最高的個(gè)體勝出。由于遺傳算法具備良好的可擴(kuò)展性和較強(qiáng)的全域搜索能力，適合用于解決像服務(wù)組合這樣的NP難問題[2]。但是，由于遺傳算法采用隨機(jī)進(jìn)化策略，迭代過程缺乏知識(shí)指導(dǎo)，導(dǎo)致算法搜索方向呈現(xiàn)一定的盲目性。而文化算法是一種基于知識(shí)的雙層進(jìn)化系統(tǒng)，能夠從進(jìn)化的種群中抽取待解決問題的知識(shí)，并反饋這些知識(shí)以指導(dǎo)搜索過程，從而加快算法收斂，防止算法出現(xiàn)“早熟”現(xiàn)象。將文化算法和遺傳算法相結(jié)合來處理組合優(yōu)化問題，已成為眾多研究者的選擇。KO等[3]從服務(wù)組合方案的角度出發(fā)，將基于QoS(quality of service)感知的Web服務(wù)組合分為基于工作流、基于QoS語義和基于QoS屬性計(jì)算這3類?；诠ぷ髁鞯姆?wù)組合方式，一般是將工作流和QoS結(jié)合，利用動(dòng)態(tài)服務(wù)組合技術(shù)，在流程運(yùn)行過程中動(dòng)態(tài)綁定Web服務(wù)[4?5]；或者是利用Web語義技術(shù)和工作流結(jié)構(gòu)，完成Web服務(wù)組合任務(wù)[6]；或者是將綠色計(jì)算和工作流有機(jī)結(jié)合，考慮服務(wù)組合過程中的能耗感知，求得能耗優(yōu)化的組合服務(wù)[7]?；诠ぷ髁鞯姆?wù)組合方式，實(shí)質(zhì)上是一種靜態(tài)綁定機(jī)制：當(dāng)流程模板確定以后，從節(jié)點(diǎn)功能出發(fā)，為每個(gè)流程節(jié)點(diǎn)綁定可滿足其功能需求的具體服務(wù)，而不考慮服務(wù)的全局QoS信息；即使考慮了QoS信息，也多是局部服務(wù)選擇?；谡Z義的服務(wù)組合方式，一般是將Web語義技術(shù)[8?9]和其他機(jī)制(如智能算法[10]、智能體[11]、描述邏輯[12]和本體[13]等)相結(jié)合，實(shí)現(xiàn)服務(wù)匹配，或者是借助人工智能規(guī)劃來實(shí)現(xiàn)Web服務(wù)組合[14]。基于QoS語義的服務(wù)組合，大多是根據(jù)服務(wù)的QoS語義信息，從候選服務(wù)集中查找與用戶功能要求相匹配的服務(wù)，其本質(zhì)仍舊是一種基于功能的服務(wù)組合，雖然其支持考慮服務(wù)質(zhì)量的單一服務(wù)選擇，但無法根據(jù)用戶對(duì)服務(wù)質(zhì)量的需求處理具有全局QoS約束的服務(wù)組合問題?；赒oS屬性計(jì)算的方式從QoS約束的角度可分為局部?jī)?yōu)化目標(biāo)下的服務(wù)組合和全局優(yōu)化目標(biāo)下的服務(wù)組合。局部?jī)?yōu)化方法主要是采用層次分析方法[15]和多屬性決策[16]來實(shí)現(xiàn)局部服務(wù)選擇。相對(duì)于全局QoS約束的服務(wù)組合方法，局部?jī)?yōu)化方法計(jì)算量較小，但是求得的解僅為局部最優(yōu)解，無法有效處理全局約束問題。而全局優(yōu)化的方法通常是借助效用函數(shù)將組合服務(wù)的QoS屬性歸一化，通過反復(fù)迭代運(yùn)算，最后求得全局最優(yōu)解。全局優(yōu)化方法主要采用遺傳算法[1]、粒子群算法[17?18]、蟻群算法[19]、模擬退火算法[20]、整數(shù)規(guī)劃[21]和人工智能[22]等方法。除了上述提到的方法外，其他諸如最佳路徑算法、剪枝法等也常被用于處理服務(wù)組合問題。本文作者將遺傳算法和文化算法相結(jié)合，用遺傳算法來實(shí)現(xiàn)文化算法的社會(huì)種群空間進(jìn)化，運(yùn)用信仰空間提取的知識(shí)來指導(dǎo)社會(huì)種群空間的進(jìn)化，以期提高算法的收斂速度和服務(wù)組合效率。

1 問題描述

2 基于文化遺傳算法的服務(wù)組合

2.1 算法總體框架

文化遺傳算法框架如圖1所示。其中，社會(huì)種群空間由遺傳算法的個(gè)體來構(gòu)造；更新函數(shù)主要用來更新信仰空間的知識(shí)；接收函數(shù)用于從社會(huì)群體空間接收一定數(shù)量的個(gè)體進(jìn)入信仰空間以形成知識(shí)；影響函數(shù)主要通過信仰空間的知識(shí)來影響社會(huì)群體空間的進(jìn)化方向；生成函數(shù)主要用于生成種群；選擇函數(shù)主要用于遺傳操作中選擇交叉的個(gè)體；評(píng)價(jià)函數(shù)用于評(píng)價(jià)當(dāng)前種群的適應(yīng)度。

圖1 文化遺傳算法框架

2.2 編碼

結(jié)合服務(wù)組合的特點(diǎn)，采用矩陣編碼方式來表示染色體的結(jié)構(gòu)。矩陣的每1列表示同一類抽象服務(wù)，每1行表示1個(gè)組合路徑，每個(gè)組合路徑包含多個(gè)具體服務(wù)，每個(gè)具體服務(wù)對(duì)應(yīng)著其QoS屬性記錄。染色體編碼結(jié)構(gòu)如圖2所示。其中，為組合路徑中的所有具體服務(wù)數(shù)，每1個(gè)具體服務(wù)的QoS信息包括價(jià)格(cost)、響應(yīng)時(shí)間(time)、信譽(yù)度(reputation)、可用性(availability)共4種屬性；w，h，l和s分別為某一類抽象服務(wù)(,=1, 2, …,)。

圖2 染色體編碼結(jié)構(gòu)

2.3 遺傳算子

1) 選擇算子。

每次從上一代種群選擇2個(gè)染色體進(jìn)行交叉，這里采用輪盤賭算法選擇2條染色體。具體選擇過程描述如下。

①=(1,2,3,…,f)，表示上1代種群中每個(gè)個(gè)體的適應(yīng)度，其中為種群數(shù)量。

②分別計(jì)算每個(gè)個(gè)體x被選中并進(jìn)入下一代遺傳的概率。

③計(jì)算累計(jì)概率。

④每次產(chǎn)生1個(gè)隨機(jī)數(shù)，若在[(x),(x1))區(qū)間內(nèi)，則第個(gè)個(gè)體被選中。

2) 相似染色體排斥交叉策略。

同源染色體在交叉之后對(duì)種群多樣性的影響有限，為了避免不必要的交叉操作，提高交叉效率，本文作者提出1種相似染色體排斥機(jī)制。設(shè)1=(1,1,1,1)，2=(2,2,2,2)，分別表示被選中的2條染色體，2條染色體的相似度用歐幾里得距離來表征。

情形1：若2條染色體的相似度≤0.5，則認(rèn)為2條染色體相似度過高，不進(jìn)行交叉，采取變異策略，通過引入外部基因以擴(kuò)大種群多樣性。

情形2：若2條染色體的相似度＞0.5，則認(rèn)為2條染色體極不相似，可以進(jìn)行交叉操作。

3) 變異算子。

在變異操作過程中，主要采用隨機(jī)變異策略。1=Rand(1,)，選擇要變異的染色體，其中為種群數(shù)量；2=Rand(1,)，其中為抽象服務(wù)種類。

生成隨機(jī)數(shù)(0.01≤≤1.00)，將其作為該染色體的變異概率，給定種群變異概率mu(0.01＜mu＜1.00)。若＜mu，則在第代種群里隨機(jī)選取1個(gè)基因位P[1][2]，然后將該基因位替換掉+1代種群對(duì)應(yīng)染色體的等位基因，即P1[1][2]=P[1][2]；若＞mu，則不進(jìn)行變異操作。

4) 精英個(gè)體保留。

在遺傳算法執(zhí)行過程中，每進(jìn)化1代，就將當(dāng)前種群的最優(yōu)個(gè)體與歷史最優(yōu)個(gè)體比較，若當(dāng)前代的最優(yōu)個(gè)體比歷史最優(yōu)個(gè)體的適應(yīng)度高，則用當(dāng)前代的最優(yōu)個(gè)體替換掉歷史最優(yōu)個(gè)體，并將當(dāng)前代的最優(yōu)個(gè)體復(fù)制到下一代種群的第0個(gè)位置，并且該最優(yōu)個(gè)體不參與交叉、變異操作，同時(shí)用歷史適應(yīng)度最大的個(gè)體替換當(dāng)前代適應(yīng)度最小的個(gè)體。

上述過程具體描述如下。

算法1：精英個(gè)體保留機(jī)制。

輸入：當(dāng)前代服務(wù)個(gè)體組成的種群c，歷史最優(yōu)個(gè)體C()，當(dāng)前代最優(yōu)個(gè)體C(+1)。

輸出：新一代種群c+1。

算法流程如下。

步驟1：比較當(dāng)前代最優(yōu)個(gè)體的適應(yīng)度值fit(C(+1))與歷史最優(yōu)個(gè)體的適應(yīng)度(C())的大??；

步驟2：若(C(+1))＞(C())，則用當(dāng)前代最優(yōu)個(gè)體C(+1)替換掉歷史最優(yōu)個(gè)體C()，用歷史最優(yōu)個(gè)體C()替換掉當(dāng)前代種群最差個(gè)體b(+1)。

步驟3：若(C(+1))＜(C())，則用歷史最優(yōu)個(gè)體C()替換掉當(dāng)前代最優(yōu)個(gè)體C(+1)，用當(dāng)前代適應(yīng)度最優(yōu)個(gè)體C(+1)替換掉當(dāng)前代適應(yīng)度最差個(gè)體b(+1)。

步驟4：將歷史最優(yōu)個(gè)體復(fù)制到新種群。

2.4 信仰空間

1) 信仰空間的設(shè)計(jì)。

在文化框架中，信仰空間主要用來保存進(jìn)化過程中種群形成的知識(shí)。基于QoS感知的服務(wù)組合問題是1個(gè)離散優(yōu)化問題，因此，采用環(huán)境知識(shí)來表示文化算法的信仰空間。信仰空間定義為二元組<,[]>，其中為最優(yōu)個(gè)體集合，[]為第最優(yōu)個(gè)體對(duì)應(yīng)的適應(yīng)度。

2) 信仰空間的更新。

算法2：信仰空間更新算法。

輸出：新的信仰空間。

算法流程如下。

步驟1：對(duì)當(dāng)前代種群c執(zhí)行進(jìn)化操作，記錄進(jìn)化代數(shù)。

步驟2：用進(jìn)化代數(shù)對(duì)進(jìn)行求模運(yùn)算，若計(jì)算結(jié)果為0，則計(jì)算當(dāng)前代種群c的每個(gè)個(gè)體的適應(yīng)度(c(I))，并對(duì)適應(yīng)度進(jìn)行排序。

步驟4：更新信仰空間。

2.5 適應(yīng)度函數(shù)設(shè)計(jì)

為評(píng)估當(dāng)前種群的適應(yīng)度，構(gòu)建效用函數(shù)如下：

(4)

若QoS屬性為正屬性(如信譽(yù)度和可用性)，則

若QoS屬性為負(fù)屬性(如價(jià)格和響應(yīng)時(shí)間)，則

2.6 算法執(zhí)行流程

利用改進(jìn)的文化遺傳算法求解服務(wù)組合問題的基本步驟如下。

步驟1：構(gòu)造初始社會(huì)種群，進(jìn)而利用適應(yīng)度函數(shù)評(píng)價(jià)種群空間的所有個(gè)體的適應(yīng)度。

步驟2：對(duì)所有個(gè)體的適應(yīng)度進(jìn)行排序，利用接收函數(shù)從初始種群中選擇若干適應(yīng)度較高的個(gè)體，產(chǎn)生和初始化信仰空間。

步驟3：對(duì)社會(huì)種群個(gè)體執(zhí)行遺傳進(jìn)化操作。

步驟4：每到1個(gè)進(jìn)化周期，借助影響函數(shù)引導(dǎo)社會(huì)種群空間個(gè)體的交叉、變異等遺傳操作，使種群向適應(yīng)度高的方向進(jìn)化，并生成相應(yīng)個(gè)數(shù)的下一代個(gè)體。

步驟5：對(duì)當(dāng)前代社會(huì)種群空間個(gè)體進(jìn)行評(píng)估，并利用接收函數(shù)將較優(yōu)個(gè)體輸送到信仰空間，更新信仰空間的知識(shí)。

步驟6：若不滿足停止條件，則重復(fù)步驟3至步驟5，直到滿足最大進(jìn)化代數(shù)或達(dá)到算法終止條件 為止。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)介紹

3.2 實(shí)驗(yàn)結(jié)果及分析

1) 適應(yīng)度對(duì)比。

本組實(shí)驗(yàn)中共有4類抽象服務(wù)，每類抽象服務(wù)數(shù)為50，進(jìn)化代數(shù)在500~5 000之間，適應(yīng)度對(duì)比結(jié)果分別如圖3和圖4所示。

1—TCGA；2—ICGA；3—IGA。

1—TCGA；2—ICGA；3—IGA。

從圖3和圖4可以看出：在不同進(jìn)化代數(shù)和不同候選服務(wù)數(shù)量的情況下，本文提出的ICGA所求的最優(yōu)服務(wù)的適應(yīng)度均比TCGA和IGA的高，這說明ICGA比TCGA和IGA具有更好強(qiáng)搜索能力。從圖3還可以看出：本文提出的ICGA算法相較于TCGA算法和IGA算法具有更好的收斂性。這是因?yàn)楸疚奶岢龅母倪M(jìn)文化遺傳算法在進(jìn)化過程中，采用了最優(yōu)個(gè)體保留的精英主義策略與相似染色體排斥機(jī)制，既能避免同源染色體之間的無效交叉，又能利用信仰空間的知識(shí)引導(dǎo)社會(huì)種群向最優(yōu)解方向靠近，使得社會(huì)種群空間的進(jìn)化呈現(xiàn)一定的方向性。由此可見，與其他2種方法相比，采用本文提出的ICGA方法求得的種群的適應(yīng)度更高，而且收斂性更好。

2) 執(zhí)行時(shí)間對(duì)比。

圖5所示為不同服務(wù)數(shù)量下3種算法執(zhí)行時(shí)間的比較。本組實(shí)驗(yàn)共有4類抽象服務(wù)，每類抽象服務(wù)對(duì)應(yīng)的具體服務(wù)數(shù)量范圍為100~500，進(jìn)化代數(shù)均為500。

1—ICGA；2—TCGA；3—IGA。

從圖5可以看出：ICGA的執(zhí)行時(shí)間比TCGA以及IGA的略多。這是因?yàn)镮CGA增加了染色體相似度計(jì)算和精英個(gè)體保留機(jī)制，需要花費(fèi)額外的計(jì)算時(shí)間。

4 結(jié)論

1) 提出1種改進(jìn)的文化遺傳算法(ICGA)用于Web服務(wù)組合，并采用信仰空間和種群空間的雙層進(jìn)化機(jī)制。

2) 在進(jìn)化過程中，采用精英保留策略和相似染色體排斥策略來控制種群的交叉，有效地防止近親染色體的無效交叉；通過在當(dāng)前種群外部引入基因片段的方式，擴(kuò)大了種群染色體的多樣性。

3) ICGA算法能夠有效地實(shí)現(xiàn)服務(wù)組合，并具有較強(qiáng)的搜索能力和較高的收斂速度。

[1] CHEN Wuhui, PAIK I. Toward better quality of service composition based on a globe social service network[J]. IEEE Transaction on Service Computing, 2015, 26(5):1466?1476.

[2] ALRIFAI M, SKOUTAS D, RISSE T. Selecting skyline services for QoS-based web service composition[C]// Proceedings of 19th International Conference on World Wide Web. North Carolina, USA: ACM, 2010: 11?20.

[3] KO J M, KIM C O, KWON I H. Quality-of-service oriented web service composition algorithm and planning architecture[J]. Journal of System and Software, 2008, 81(11): 2079?2090.

[4] 苑迎春, 王克儉, 韓憲忠, 等. 基于工作流的Web服務(wù)組合多視圖模型[J].計(jì)算機(jī)集成制造系統(tǒng), 2010, 16(1): 30?36. YUAN Yingchun, WANG Kejian, HAN Xianzhong, et al. Multi-view model for web service composition based on workflow[J]. Computer Integrated Manufacturing Systems, 2010, 16(1):30?36.

[5] YU Genong, ZHAO Peisheng, DI Liping, et al. BPELPower-a BPEL execution engine for geospatial web service[J]. Computers and Geosciences, 2012, 47: 87?101.

[6] 趙松, 王紅, 閻嫕. Web服務(wù)組合工作流中擴(kuò)展UDDI的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2009, 30(1): 217?221. ZHAO Song, WANG Hong, YAN Yi. Design and implementation of extending UDDI in workflow composed of web services[J]. Computer Engineering and Design, 2009, 30(1): 217?221.

[7] 朱勇, 羅軍舟, 李偉.一種工作流環(huán)境下能耗感知的多路徑服務(wù)組合方法[J].計(jì)算機(jī)學(xué)報(bào), 2012,35(3): 627?638. ZHU Yong, LUO Junzhou, LI Wei. An approach for energy aware multipath service composition based on workflow[J]. Chinese Journal of Computers, 2012, 35(3): 627?638.

[8] MIER P R, PEDRINACI C, LAMA M, et al. An integrated semantic web service discovery and composition framework[J]. IEEE Transaction on Service Computing, 2016, 9(4):537?550.

[9] JEMIMA D D, KARPAGAM G R. Conceptual framework for semantic web service composition[C]//2016 Fifth International Conference on Recent Trends in Information Technologies. New York,USA: IEEE, 2016: 1?6.

[10] 張佩云, 黃波, 孫亞民.一種基于語義與QoS感知的Web服務(wù)匹配機(jī)制[J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(5): 780?787. ZHANG Peiyun, HUANG Bo, SUN Yamin. A web services matching mechanism based on semantics and QoS-aware aspect[J]. Journal of Computer Research and Development, 2010,47(5):780?787.

[11] 劉華鵬, 劉勝全, 劉艷, 等.基于主體和QoS的語義Web服務(wù)組合方法[J].計(jì)算機(jī)工程, 2013, 39(10): 227?232. LIU Huapeng, LIU Shengquan, LIU Yan, et al. Semantic web service composition method based on agent and QoS[J]. Computer Engineering, 2013, 39(10): 227?232.

[12] 彭暉, 陳立民, 常亮, 等.基于動(dòng)態(tài)描述邏輯的語義Web服務(wù)匹配研究[J].計(jì)算機(jī)研究與發(fā)展, 2008, 45(12): 2102?2109. PENG Hui, CHEN Limin, CHANG Liang, et al. Semantic web service matching based on dynamic description logic[J]. Journal of Computer Research and Development, 2008, 45(12): 2102?2109.

[13] 李曼, 王大治, 杜小勇, 等. 基于領(lǐng)域本體的Web服務(wù)動(dòng)態(tài)組合[J]. 計(jì)算機(jī)學(xué)報(bào), 2005, 28(4): 644?650. LI Man, WANG Dazhi, DU Xiaoyong, et al. Dynamic composition of web service based on domain ontology[J]. Chinese Journal of Computers, 2005, 28(4):644?650.

[14] RAFIEE A, EMADI S. An integrated method for semantic web service composition using planning based on qualitative parameters[C]//2016Second International Conference on Web Research. New York,USA:IEEE,2016: 84?89.

[15] 李玲,劉敏,成國(guó)慶.一種基于FAHP的多維QoS局部最優(yōu)服務(wù)選擇模型[J].計(jì)算機(jī)學(xué)報(bào), 2015, 38(10): 1997?2010. LI Ling, LIU Min, CHENG Guoqing. A local optimal model of service selection of Multi-QoS based on FAHP[J]. Chinese Journal of Computers, 2015, 38(10): 1997?2010.

[16] 馮艷, 陳富贊. 基于QoS多屬性決策的Web服務(wù)組合優(yōu)化方法[J].計(jì)算機(jī)工程, 2015, 41(6):33?38. FENG Yan, CHEN Fuzan. Web service composition optimization method based on QoS multi-attribute decision making[J]. Computer Engineering, 2015, 41(6):33?38.

[17] 溫濤, 盛國(guó)軍, 郭權(quán), 等. 基于改進(jìn)粒子群算法的Web服務(wù)組合[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(5): 1031?1046. WEN Tao, SHENG Guojun, GUO Quan, et al. Web service composition based on modified particle swarm optimization[J]. Chinese Journal of Computers, 2013, 36(5): 1031?1046.

[18] 夏亞梅, 程渤, 陳俊亮, 等.基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(2): 270?281. XIA Yamei, CHENG Bo, CHEN Junliang, et al. Optimizing service composition based on improved ant colony algorithm[J]. Chinese Journal of Computers, 2012, 35(2): 270?281.

[19] WU Quanwang, ZHU Qingsheng. Transactional and QoS-aware dynamic service composition based on ant colony optimization[J]. Future Generation Computer Systems, 2013, 29(5): 1112?1119.

[20] 曹云健, 董晶. 基于模擬退火遺傳算法的服務(wù)選擇[J].計(jì)算機(jī)工程與設(shè)計(jì), 2011, 32(10): 3507?3511. CAO Yunjian, DONG Jing. Services selection based on simulated annealing genetic algorithm[J]. Computer Engineering and Design, 2011, 32(10): 3507?3511.

[21] PAGANELLI F, AMBRA T, PARLANTI D, et al. A semantic-driven integer programming approach for QoS-aware dynamic services composition[C]//2011 50th FITCE Congress.New York, USA: IEEE, 2011: 1?6.

[22] ZOU Guobing, GAN Yanglan, CHEN Yixin, et al. Dynamic composition of web services using efficient planners in large-scale service repository[J]. Knowledge-Based Systems, 2014, 62: 98?112.

[23] ZHANG Miao, LIU Li, LIU Songtao. Genetic algorithm based QoS-aware service composition in multi-cloud[C]//2015 IEEE Conference on Collaboration and Internet Computing. New York, USA: IEEE, 2015:113?118.

(編輯 伍錦花)

QoS-aware service composition based on culture genetic algorithm

LIU Zhengli1, LI Bing1, QIANG Baohua2, WANG Jing3

(1. School of Computer Science, Wuhan University, Wuhan 430079, China; 2. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin 541004, China 3. China Electronics Standardization Institute, Beijing 100007, China)

To improve the efficiency of service composition, an improved QoS-aware service composition approach was proposed based on cultural genetic algorithm. A double space include social population and belief was constructed. The reception function was used to extract knowledge from the social population and to update the belief space. Then the belief space of cultural algorithm was utilized to guide the evolution of social population, accelerate the convergence and improve the efficiency of combination. The results show that compared with traditional culture genetic algorithm and improved genetic algorithm, the number of iterations required for convergence of the proposed algorithm can be significantly reduced, and the execution efficiency and convergence speed are improved.

service composition; QoS-aware; culture genetic algorithm; service selection

10.11817/j.issn.1672-7207.2018.11.013

TP311

A

1672?7207(2018)11?2731?07

2017?12?11；

2018?01?28

國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB0800401，2017YFB1400602)；國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(973計(jì)劃)項(xiàng)目(2014CB340401)；國(guó)家自然科學(xué)基金資助項(xiàng)目(61572371)；國(guó)家博士后科學(xué)基金資助項(xiàng)目(2015M582272)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(2042016kf0033)；湖北省自然科學(xué)基金資助項(xiàng)目(2016CFB158)；武漢市黃鶴英才(專項(xiàng))計(jì)劃項(xiàng)目(2017) (Projects (2016YFB0800401, 2017YFB1400602) supported by the National Key Research and Development Program of China; Project(2014CB340401) supported by the National Basic Research Development Program(973 Program) of China; Project(61572371) supported by the National Natural Science Foundation of China; Project(2015M582272) supported by the National Science Foundation for Postdoctoral Scientists of China; Project(2042016kf0033) supported by the Fundamental Research Funds for the Central Universities; Project(2016CFB158) supported by the Natural Science Foundation of Hubei Province; Project(2017) supported by the Wuhan Yellow Crane Special Talents Program)

李兵，博士，教授，博士生導(dǎo)師，從事服務(wù)計(jì)算、人工智能、軟件工程研究；E-mail: bingli@whu.edu.cn