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

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

?

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

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

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

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

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

1 概述

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

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

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

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

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

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

圖1 服務組合流程模型

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

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

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

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

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

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

3.1 粒子群初始化

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

3.2 粒子速度和位置的更新

3.3 非支配解集的更新與維護

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

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

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

3.5 混沌擾動操作

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

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

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

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

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

3.6 算法流程

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

圖2 CMOPSO算法流程

4 仿真實驗與分析

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

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

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

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

圖3 迭代收斂性比較

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

5 結(jié)束語

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

[1] 羅軍舟, 金嘉暉, 宋愛波, 等. 云計算: 體系架構(gòu)與關(guān)鍵技術(shù)[J]. 通信學報, 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] 古凌嵐, 孫素云. 基于遺傳算法的組合服務選擇方法[J]. 計算機工程與設計, 2011, 32(11): 3877-3880.

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

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

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

[11] 鄭金華. 多目標進化算法及其應用[M]. 北京: 科學出版社, 2007.

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

[13] 崔遜學, 林 闖. 基于多目標遺傳算法的多播服務質(zhì)量路由優(yōu)化[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)計劃基金資助項目(122102310003)。

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

2013-09-25

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

10.3969/j.issn.1000-3428.2014.03.005