王 娜，衛(wèi) 波，王晉東，張恒巍

?

基于混沌多目標(biāo)粒子群優(yōu)化算法的云服務(wù)選擇

王 娜，衛(wèi) 波，王晉東，張恒巍

(解放軍信息工程大學(xué)密碼工程學(xué)院，鄭州 450001)

隨著云計(jì)算環(huán)境中各種服務(wù)數(shù)量的急劇增長(zhǎng)，如何從功能相同或相似的云服務(wù)中選擇滿足用戶需求的服務(wù)成為云計(jì)算研究中亟待解決的關(guān)鍵問(wèn)題。為此，建立帶服務(wù)質(zhì)量約束的多目標(biāo)服務(wù)組合優(yōu)化模型，針對(duì)傳統(tǒng)多目標(biāo)粒子群優(yōu)化(MOPSO)算法中解的多樣性差、易陷入局部最優(yōu)等缺點(diǎn)，設(shè)計(jì)基于混沌多目標(biāo)粒子群優(yōu)化(CMOPSO)算法的云服務(wù)選擇方法。采用信息熵理論來(lái)維護(hù)非支配解集，以保持解的多樣性和分布的均勻性。當(dāng)種群多樣性丟失時(shí)，引入混沌擾動(dòng)機(jī)制，以提高種群多樣性和算法全局尋優(yōu)能力，避免陷入局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，與MOPSO算法相比，CMOPSO算法的收斂性和解集多樣性均得到改善，能夠更好地解決云計(jì)算環(huán)境下服務(wù)動(dòng)態(tài)選擇問(wèn)題。

云計(jì)算；服務(wù)選擇；服務(wù)質(zhì)量；多目標(biāo)粒子群優(yōu)化算法；信息熵；混沌

1 概述

云計(jì)算[1]是一種新興的計(jì)算模式，它通過(guò)將大量的網(wǎng)絡(luò)資源(計(jì)算資源、存儲(chǔ)資源與軟件資源等)以服務(wù)的形式鏈接在一起，形成巨大規(guī)模的共享虛擬資源池，為用戶和應(yīng)用系統(tǒng)提供“能力無(wú)限”的云服務(wù)資源。在云計(jì)算環(huán)境中有大量功能相同、非功能屬性各異的云服務(wù)，而單個(gè)云服務(wù)的功能有限，因此，如何將云計(jì)算環(huán)境中多個(gè)云服務(wù)組合起來(lái)形成新的、增值的大粒度組合服務(wù)來(lái)滿足復(fù)雜多變的應(yīng)用需要，是當(dāng)前迫切需要解決的問(wèn)題。

服務(wù)組合指將現(xiàn)有服務(wù)按照一定的業(yè)務(wù)邏輯進(jìn)行無(wú)縫集成，從而更好地滿足用戶的需求。服務(wù)組合廣義上可以分為靜態(tài)組合、半自動(dòng)組合和自動(dòng)組合[2]。云計(jì)算環(huán)境是一個(gè)動(dòng)態(tài)開(kāi)放的環(huán)境，云服務(wù)的狀態(tài)隨時(shí)可能發(fā)生變化，靜態(tài)的組合無(wú)法滿足實(shí)際的應(yīng)用需求。同時(shí)，由于完全智能的自動(dòng)組合是一個(gè)十分復(fù)雜的過(guò)程，因此很多關(guān)于服務(wù)組合的應(yīng)用和研究工作都側(cè)重于半自動(dòng)方式[3]。半自動(dòng)組合的實(shí)現(xiàn)，首先由業(yè)務(wù)人員根據(jù)特定的任務(wù)需求建立服務(wù)組合流程模型。服務(wù)組合模型由多個(gè)服務(wù)節(jié)點(diǎn)組合，每個(gè)節(jié)點(diǎn)有多個(gè)功能相同、服務(wù)質(zhì)量(Quality of Service, QoS)不同的候選服務(wù)。如何從眾多的候選服務(wù)中動(dòng)態(tài)地選擇合適的服務(wù)實(shí)例，形成一個(gè)QoS全局最優(yōu)的可執(zhí)行組合服務(wù)來(lái)完成用戶的需求，成為服務(wù)組合中的一個(gè)關(guān)鍵問(wèn)題，本文稱其為QoS全局最優(yōu)動(dòng)態(tài)服務(wù)選擇。

QoS全局最優(yōu)動(dòng)態(tài)服務(wù)選擇問(wèn)題已被證明為NP完全問(wèn)題[4]，受到國(guó)內(nèi)外眾多學(xué)者的關(guān)注。文獻(xiàn)[5-6]把服務(wù)節(jié)點(diǎn)的候選服務(wù)的QoS屬性進(jìn)行加權(quán)排序，然后選擇加權(quán)和最大的服務(wù)實(shí)例來(lái)完成服務(wù)節(jié)點(diǎn)的功能，但沒(méi)有考慮服務(wù)節(jié)點(diǎn)之間的邏輯關(guān)系，屬于局部最優(yōu)的服務(wù)選擇方法，無(wú)法得到QoS全局最優(yōu)的組合；文獻(xiàn)[7-8]雖然引入智能優(yōu)化算法，但需要把組合服務(wù)的各個(gè)QoS參數(shù)線性加權(quán)轉(zhuǎn)化為一個(gè)單目標(biāo)函數(shù)，轉(zhuǎn)化時(shí)難以協(xié)調(diào)各目標(biāo)函數(shù)值，加權(quán)系數(shù)的設(shè)定具有盲目性，且無(wú)法產(chǎn)生多個(gè)可行解，用戶沒(méi)有可選擇余地；文獻(xiàn)[9-10]將QoS全局最優(yōu)動(dòng)態(tài)服務(wù)選擇問(wèn)題轉(zhuǎn)換為多目標(biāo)優(yōu)化問(wèn)題，但前者采用較復(fù)雜的遺傳算法，收斂速度較慢；后者利用粒子群算法求解，但對(duì)非支配解集的多樣性考慮不足，優(yōu)化解的質(zhì)量有待提高。

針對(duì)多目標(biāo)粒子群算法存在非支配解集多樣性差、易陷入局部最優(yōu)等缺陷，本文改進(jìn)傳統(tǒng)多目標(biāo)粒子群優(yōu)化(Multi-objective Particle Swarm Optimization, MOPSO)算法，提出一種基于混沌多目標(biāo)粒子群優(yōu)化算法(Chaotic MOPSO,CMOPSO)的動(dòng)態(tài)服務(wù)選擇實(shí)現(xiàn)方法。將云計(jì)算環(huán)境下的服務(wù)動(dòng)態(tài)選擇問(wèn)題轉(zhuǎn)化為帶QoS約束的多目標(biāo)服務(wù)組合優(yōu)化問(wèn)題，通過(guò)同時(shí)優(yōu)化組合服務(wù)的多個(gè)QoS參數(shù)，產(chǎn)生一組滿足約束條件的非支配解。用戶可以根據(jù)實(shí)時(shí)需求選擇最滿意的解，而未被選中的非支配解則作為備選方案，以供所選組合服務(wù)失效時(shí)啟用，保證用戶獲得滿足要求的高質(zhì)量云服務(wù)。

2 服務(wù)組合優(yōu)化問(wèn)題描述

在云計(jì)算環(huán)境下的服務(wù)選擇問(wèn)題中，服務(wù)組合流程是由一組服務(wù)節(jié)點(diǎn)按照一定的邏輯關(guān)系組成的，服務(wù)節(jié)點(diǎn)并不是具體的服務(wù)實(shí)例，而是一組具有相同功能描述和接口信息的候選服務(wù)實(shí)例的抽象，各候選服務(wù)擁有不同的QoS。假設(shè)一服務(wù)組合流程模型包含個(gè)服務(wù)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)S有n個(gè)候選服務(wù)，服務(wù)組合流程模型如圖1所示。

圖1 服務(wù)組合流程模型

表1 基本結(jié)構(gòu)的QoS計(jì)算公式

QoS全局最優(yōu)的服務(wù)動(dòng)態(tài)選擇就是在組合流程模型執(zhí)行過(guò)程中，從各個(gè)服務(wù)節(jié)點(diǎn)對(duì)應(yīng)的候選服務(wù)集中選擇具體的服務(wù)實(shí)例組成一個(gè)可執(zhí)行的組合服務(wù)，使組合服務(wù)在滿足特定的QoS約束情況下，多個(gè)目標(biāo)(QoS參數(shù))達(dá)到最優(yōu)。為闡述方便，本文將執(zhí)行時(shí)間，執(zhí)行費(fèi)用作為2個(gè)目標(biāo)準(zhǔn)則，希望得到最小的執(zhí)行時(shí)間和最少的執(zhí)行費(fèi)用。將服務(wù)可靠性、服務(wù)信譽(yù)作為2個(gè)約束條件，表明該組合服務(wù)的所要求的最低可靠性和信譽(yù)度。一個(gè)帶約束的多目標(biāo)服務(wù)組合優(yōu)化模型可描述為：

在多數(shù)情況下，由于服務(wù)QoS屬性之間具有不可公度性和矛盾性等特點(diǎn)，造成服務(wù)組合優(yōu)化各目標(biāo)函數(shù)之間相互沖突，無(wú)法同時(shí)使多個(gè)目標(biāo)均達(dá)到最優(yōu)。因此多目標(biāo)組合優(yōu)化問(wèn)題的結(jié)果不是單一解，而是滿足約束條件下的一組非支配解。以下介紹多目標(biāo)優(yōu)化中常用的3個(gè)基本定義[11]：

定義3(非支配解集) 非支配解集是指所有非支配解的集合，也稱Pareto最優(yōu)解集，定義如下：

3 混沌多目標(biāo)粒子群優(yōu)化算法

MOPSO在求解多目標(biāo)優(yōu)化問(wèn)題時(shí)取得很好效果，但是仍存在以下問(wèn)題：優(yōu)化問(wèn)題的非支配解分布不均勻，難以保持解集的多樣性；容易陷入局部最優(yōu)，出現(xiàn)早熟收斂情況。因此，本文利用混沌序列初始化粒子群，采用基于信息熵的多樣性保持策略，確保非支配解分布均勻；在算法執(zhí)行后期，當(dāng)種群多樣性丟失時(shí)，引入混沌擾動(dòng)機(jī)制，增強(qiáng)種群多樣性，提高算法全局尋優(yōu)能力，避免陷入局部最優(yōu)。

3.1 粒子群初始化

粒子群的初始化需要使粒子均勻分布在解空間里，擴(kuò)展可行解的搜索范圍，有助于提高算法求解效率和解的質(zhì)量。混沌是自然界廣泛存在的一種非線性現(xiàn)象，具有隨機(jī)性和遍歷性等特性，已被廣泛應(yīng)用隨機(jī)優(yōu)化[12]。因此本文利用混沌序列初始化粒子群，提高種群的多樣性和搜索的遍歷性，這里采用簡(jiǎn)單的一維Logistic混沌映射模型進(jìn)行粒子群的初始化，其定義如下：

3.2 粒子速度和位置的更新

3.3 非支配解集的更新與維護(hù)

(2)根據(jù)粒子的信息熵計(jì)算2個(gè)粒子之間的相似程度：

通過(guò)基于信息熵的適應(yīng)度計(jì)算可知，非支配解集中相似個(gè)體越多則個(gè)體適應(yīng)度越小，因此將非支配解集內(nèi)的粒子按適應(yīng)度降序排列，當(dāng)解集中的粒子數(shù)目超過(guò)預(yù)定的閾值，則刪除排在后端的適應(yīng)度小的粒子，使非支配解集中的粒子能夠均勻分布，保證了解集的多樣性。

3.4 局部最優(yōu)位置和全局最優(yōu)位置的選擇

3.5 混沌擾動(dòng)操作

非支配解集中粒子適應(yīng)度越小相似個(gè)體越多，粒子越密集。當(dāng)多樣性較差時(shí)，種群容易陷入局部最優(yōu)，種群中的粒子速度會(huì)趨于0，并向解集中適應(yīng)度小的密集粒子聚集，導(dǎo)致種群出現(xiàn)停滯現(xiàn)象，從而失去尋優(yōu)能力。因此，為了提高種群多樣性，避免種群陷入局部最優(yōu)，將混沌的思想引入粒子群算法中。

當(dāng)種群的多樣性低于預(yù)先設(shè)定的閾值時(shí)，選擇解集中排在前端/2個(gè)適應(yīng)度大的稀疏粒子，對(duì)每個(gè)粒子進(jìn)行多次混沌擾動(dòng)，產(chǎn)生該粒子的多個(gè)鄰域點(diǎn)，并根據(jù)支配關(guān)系選出這些鄰域點(diǎn)中的非支配粒子，若存在多個(gè)非支配粒子，則隨機(jī)選取其中一個(gè)作為新的粒子。經(jīng)過(guò)混沌擾動(dòng)操作可得到/2個(gè)新粒子，隨機(jī)替代種群中的/2個(gè)粒子，且保持這些粒子當(dāng)前的搜索速度和局部最優(yōu)位置不變。具體實(shí)現(xiàn)過(guò)程如下：

(1)監(jiān)測(cè)種群多樣性是否滿足預(yù)定閾值，種群的多樣性測(cè)量公式如下：

(3)求粒子每一維位置變量上產(chǎn)生的擾動(dòng)偏差：

通過(guò)以上混沌擾動(dòng)機(jī)制，在解集的稀疏粒子附近產(chǎn)生許多新的粒子，引導(dǎo)種群向解集的稀疏空間探索，增強(qiáng)了種群的多樣性，避免種群陷入局部最優(yōu)的束縛，使種群重新獲得尋優(yōu)能力，快速地向Pareto最優(yōu)解集收斂，克服了算法易陷入局部最優(yōu)的缺點(diǎn)。

3.6 算法流程

求解服務(wù)組合優(yōu)化的CMOPSO算法流程如圖2所示。

圖2 CMOPSO算法流程

4 仿真實(shí)驗(yàn)與分析

本文從算法收斂性和優(yōu)化解的質(zhì)量2個(gè)方面對(duì)CMOPSO與MOPSO的求解結(jié)果進(jìn)行對(duì)比分析。圖3和圖4分別顯示了2種算法的迭代收斂過(guò)程和優(yōu)化解的分布情況。

從算法迭代收斂過(guò)程來(lái)看，在迭代前期，CMOPSO和MOPSO收斂曲線基本一致，隨著迭代過(guò)程的進(jìn)行，CMOPSO搜索到的最優(yōu)解數(shù)量明顯多于MOPSO，CMOPSO在第35代收斂到非支配解規(guī)模上限，而MOPSO在第43代才完成算法收斂，因此，CMOPSO的收斂速度要優(yōu)于MOPSO。

從優(yōu)化解分布情況來(lái)看，MOPSO求的解分布比較集中，個(gè)體相似度比較高，部分可行解區(qū)域內(nèi)不存在非支配解，相比之下，CMOPSO搜索到的非支配解分布比較均勻，保持了較好的多樣性，優(yōu)化結(jié)果更接近理想Pareto最優(yōu)解集，求得組合優(yōu)化解的質(zhì)量好，能更好地滿足用戶的多樣性需求。

通過(guò)以上實(shí)驗(yàn)分析可知，本文算法在求解服務(wù)選擇問(wèn)題時(shí)有較好的優(yōu)化性能，有效避免算法早熟收斂現(xiàn)象，具有良好的全局尋優(yōu)能力，能夠快速地向理想的非支配解集收斂，并且保持優(yōu)化解的多樣性和分布的均勻性，最終得到一組滿足約束條件的非支配解，用戶可以根據(jù)不同偏好或?qū)嶋H情況，靈活地從非支配解集中選擇合適的優(yōu)化解。

圖3 迭代收斂性比較

圖4 非支配解分布情況比較

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

本文將云計(jì)算環(huán)境下的服務(wù)動(dòng)態(tài)選擇問(wèn)題轉(zhuǎn)化為帶QoS約束的多目標(biāo)服務(wù)組合優(yōu)化問(wèn)題，設(shè)計(jì)基于CMOPSO算法的動(dòng)態(tài)服務(wù)選擇求解方法，采用信息熵的理論保持了解集的多樣性。在算法執(zhí)行后期，當(dāng)種群多樣性丟失時(shí)，引入混沌擾動(dòng)機(jī)制在解集的稀疏粒子附近產(chǎn)生許多新的粒子，提高種群的多樣性和全局尋優(yōu)能力，避免陷入局部最優(yōu)，快速地向理想的非支配解集收斂。實(shí)驗(yàn)結(jié)果表明，相比傳統(tǒng)MOPSO算法，CMOPSO算法的收斂性和解集多樣性更好，能更有效地解決云計(jì)算環(huán)境下的服務(wù)動(dòng)態(tài)選擇問(wèn)題。

[1] 羅軍舟, 金嘉暉, 宋愛(ài)波, 等. 云計(jì)算: 體系架構(gòu)與關(guān)鍵技術(shù)[J]. 通信學(xué)報(bào), 2011, 32(7): 3-21.

[2] Majithia S, Walker D W, Gray W A. A Framework for Automated Service Composition in Service-oriented Archi- tectures[C]//Proc. of ESWS’04. Berlin, Germany: Springer- Verlag, 2004: 269-283.

[3] Zeng Liangzhao, Benatallah B, Dumas M. Quality Driven Web Service Composition[C]//Proc. of the 12th International Conference on World Wide Web. Budapest, Hungary: ACM Press, 2003: 411-421.

[4] Yu Tao, Lin K J. Service Selection Algorithms for Composing Complex Services with Multiple QoS Constraints[C]//Proc. of the 3rd International Conference on Service Oriented Computing. Amsterdam, Holland: Springer-Verlag, 2005: 130- 143.

[5] Ran Shuping. A Model for Web Services Discovery with QoS[J]. ACM SIGecom Exchanges, 2003, 4(1): 1-10.

[6] Liu Yutu, Ngu A H, Zeng Liangzhao. QoS Computation and Policing in Dynamic Web Service Selection[C]//Proc. of the 13th International Conference on World Wide Web. New York, USA: ACM Press, 2004: 66-73.

[7] 古凌嵐, 孫素云. 基于遺傳算法的組合服務(wù)選擇方法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2011, 32(11): 3877-3880.

[8] 董元元, 倪 宏, 鄧浩江, 等. QoS全局最優(yōu)化的服務(wù)選擇策略[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2011, 32(3): 455-459.

[9] 劉書雷, 劉云翔, 張 帆. 一種服務(wù)聚合中QoS全局最優(yōu)服務(wù)動(dòng)態(tài)選擇算法[J]. 軟件學(xué)報(bào), 2007, 18(3): 646-656.

[10] 孫黎陽(yáng), 林劍檸, 毛少杰. 基于改進(jìn)粒子群優(yōu)化算法的網(wǎng)絡(luò)化仿真任務(wù)共同體服務(wù)選擇[J]. 兵工學(xué)報(bào), 2012, 33(11): 1393-1403.

[11] 鄭金華. 多目標(biāo)進(jìn)化算法及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2007.

[12] 張春慨, 徐立云, 邵惠鶴. 改進(jìn)混沌優(yōu)化及其在非線性約束優(yōu)化問(wèn)題中的應(yīng)用[J]. 上海交通大學(xué)學(xué)報(bào), 2000, 34(5): 593-595.

[13] 崔遜學(xué), 林 闖. 基于多目標(biāo)遺傳算法的多播服務(wù)質(zhì)量路由優(yōu)化[J]. 計(jì)算機(jī)研究與發(fā)展, 2004, 41(7): 1144-1150.

[14] Mostaghim S, Teich J. Strategies for Finding Good Local Guides in Multi-objective Particle Swarm Optimization[C]// Proc. of 2003 IEEE Swarm Intelligence Symposium. Indianapolis, USA: IEEE Press, 2003: 26-33.

編輯 金胡考

Cloud Service Selection Based on Chaotic Multi-objective Particle Swarm Optimization Algorithm

WANG Na, WEI Bo, WANG Jin-dong, ZHANG Heng-wei

(Institute of Cipher Engineering, PLA Information Engineering University, Zhengzhou 450001, China)

With the explosive number growth of services in cloud computing environment, how to select the services that can meet user’s requirement from the services which have same or similar function becomes the key problem to be resolved in cloud computing. So a multi-objective service composition optimization model with Quality of Service(QoS) restriction is built, and since some disadvantages of the traditional Multi-objective Particle Swarm Optimization(MOPSO) algorithm, such as less diversity of solutions and falling into local extremum easily, a method of Chaotic MOPSO(CMOPSO) algorithm is proposed. This algorithm uses the information entropy theory to maintain non-dominated solution set so as to retain the diversity of solution and the uniformity of distribution. When the diversity of population disappears, it introduces chaotic disturbance mechanism to improve the diversity of population and the ability of global optimization algorithm to avoid falling into local extremum. Experimental result shows that the astringency and the diversity of solution set of CMOPSO algorithm are better than traditional MOPSO algorithm, and it can solve the problem of service dynamic selection under cloud computing environment more efficiently.

cloud computing; service selection; Quality of Service(QoS); Multi-objective Particle Swarm Optimization(MOPSO) algorithm; information entropy; chaotic

1000-3428(2014)03-0023-05

A

TP391.9

河南省科技攻關(guān)計(jì)劃基金資助項(xiàng)目(122102310003)。

王 娜(1970－)，女，副教授、碩士，主研方向：服務(wù)計(jì)算，信息安全；衛(wèi) 波，碩士研究生；王晉東，教授；張恒巍，講師、博士。

2013-09-25

2013-10-30 E-mail：weibo7516@sina.com

10.3969/j.issn.1000-3428.2014.03.005