基于多策略離散差分進化的移動互聯網個性化服務組合

許斌，亓晉，印溪，王野，常瑞云

（南京郵電大學物聯網學院，江蘇南京210003）

研究與開發

基于多策略離散差分進化的移動互聯網個性化服務組合

許斌，亓晉，印溪，王野，常瑞云

（南京郵電大學物聯網學院，江蘇南京210003）

移動互聯網技術的普及使人們不再滿足于單一功能的服務，而更傾向于按需定制的個性化服務或服務組合。提出了一種應用于Web服務組合的多策略離散差分進化（multi-strategy discrete differential evolution，MDDE）算法。該算法采用隨機選擇框架，調用具有不同特性的變異策略，是一種搜索能力和收斂速度均衡的離散差分進化算法。實驗結果表明，MDDE算法在求解Web服務組合優化問題中比原始DE算法的收斂精度更高，穩定性更好。

Web服務組合；差分進化；多策略變異

1 引言

移動互聯網、云計算、網絡融合等技術的飛速發展促進了多種類業務環境的快速融合［1］。智能移動終端除了基本網頁瀏覽、定位等基本數據業務能力外，還需要混合支付、旅游規劃等相對復雜的混合服務能力［2］，以使用戶更好地享用信息化服務。近年來，隨著云計算技術的飛速發展和廣泛應用，資源的使用方式發生了根本性變化，即通過網絡就可使用處于不同空間的任意軟件和硬件資源。所以人們不再強烈關注各類設備和應用本身，轉而對處于云上的一系列資源能夠提供的服務類型、服務質量以及服務體驗和個性化更為感興趣［3］。同時，移動互聯網技術的普及，使人們不再滿足于單一功能的服務，或僅僅是在數量上的服務集成，而更傾向于按需定制的個性化服務或服務組合［4-6］。滿足該需求的一種策略是，將當前互聯網環境中存在的功能相對單一的服務進行有機選擇并有序組合，依據服務質量指標給出最佳的個性服務組合。由于一個服務的成功實施涉及服務器、網絡、軟件等各類資源的整體協調使用［7］，實際資源代價相當高。因此，通過采用上述策略，重復利用現有互聯網各種服務，避免資源過度開發和浪費，是發展綠色節能移動互聯網的有效手段。

當前服務組合的研究多集中于Web服務組合［8-11］。在Web服務組合的研究中，一般采用服務的QoS指標來評價和區分服務。QoS指標主要包括服務執行時間、代價、可用性、可靠性以及信譽度等。基于QoS的Web服務組合問題，是從若干個服務候選集中分別選擇出候選服務進行組合，使得組合后的服務既能滿足用戶的需求，又具有良好的QoS。Web組合服務的QoS計算模型和服務組合優選算法是目前研究的熱點問題［12，13］。

［14］從用戶需求角度出發，提出了Web服務QoS主要應滿足可用性（availability）、可達性（accessibility）、完整性（integrity）、性能（performance）、可靠性（reliability）、規范性（regulatory）、正確性（accuracy）、頑健性（robustness）、安全性（security）等方面的需求。參考文獻［15］研究了帶QoS約束的Web服務選擇問題，提出了一個新的QoS模型來更靈活地選擇服務，并引入Top k的排名策略來反映用戶的個人需求，保證了新模型的有效性和實用性。參考文獻［16］用服務價格、響應時間、可用性、可靠性和信譽度等屬性來描述QoS，并提出了基于整數線性規劃的服務選擇算法，實現了在滿足約束條件的前提下，計算服務組合的QoS。參考文獻［17］提出了一種通過用戶協作來預測Web服務的QoS方法。該方法通過研究用戶以往Web服務使用經驗來收集QoS數據，在此基礎上采用鄰域綜合矩陣分解的方法來獲得個性化的QoS預測值。

由于Web服務組合問題實質為NP難的組合優化問題，當前針對Web服務組合優選采用的算法主要是智能優化算法。參考文獻［18］將啟發式的模擬退火以及和聲搜索作為遺傳算法的智能變異算子，獲得了更快的收斂速度以及更高的平均適應度值。參考文獻［19］提出一種改進的遺傳算法用于QoS感知的Web服務組合，采用兩種不同的算法進行服務選擇，避免了隨機生成初始種群帶來的負面影響，并將路徑模板化以減少服務組合的工作量，用染色體可變長的編碼方式來解決組合服務的多路徑選擇問題。利用PSO算法作為Web服務選擇算法，體現了PSO算法并行計算的優勢，全局搜索能力也得到很大提升。參考文獻［20］提出了基于PSO的多目標優化策略，用于解決Web服務組合中基于QoS的服務選擇全局優化問題，將服務組合全局最優問題轉化為一個帶QoS約束的多目標服務組合優化問題，然后利用多目標粒子群算法同時優化多個QoS，最終得到一組較優的服務組合方案。參考文獻［21］改進了PSO算法，并應用于Web服務組合之中。該算法使用基于粒子圓周軌道和零慣性權重，基于三角函數的動態學習因子，控制粒子群的行為，使粒子的局部認知和全局搜索能力達到較好的平衡。參考文獻［22］改進了人工蜂群算法，通過引入混沌策略產生新的解來代替面臨丟棄的解使得算法跳出局部最優解，引入禁忌搜索策略避免跟隨蜂的重復搜索，提高了算法的成功率以及搜索效率。

本文提出了一種多策略離散差分進化（multi-strategy discrete differential evolution，MDDE）算法，并將MDDE算法應用于基于QoS的Web服務組合優化問題。MDDE算法采用隨機選擇框架，調用具有不同特性的變異策略，是一種搜索能力和收斂速度均衡的離散差分進化算法。仿真實驗表明，MDDE算法在求解Web服務組合優化問題中比原始DE算法的收斂精度更高，證實了多種變異策略的混合會增加種群中個體的多樣性，避免了過早收斂及陷入局部最優。

2 問題建模

2.1 Web服務的QoS屬性

為了區分和評價Web服務，現有的研究一般采用QoS指標。在QoS指標中，有些參數值由服務生產者提供，有些則由用戶（服務使用者）決定。本文選取響應時間、可用性和執行代價這3個具有代表性的QoS屬性來評估Web服務［15］。

因此，單個服務的QoS可用一個向量表示：Q=（T，A，C）。

（1）響應時間T

表示用戶請求服務后到接受服務響應所經過的總時間。

其中，Ttrans表示請求消息和響應消息在網絡上的傳輸時間，容易受到網絡狀況影響；Tproc表示處理服務請求所使用的時間。

（2）可用性A

表示服務可訪問的概率。

其中，∑tsucess表示在調用一定次數的服務后，服務被成功調用的總時間；∑t表示所用的總時間。實際環境中，服務的可用性受到網絡環境、服務器狀態、客戶端狀態等因素影響，具有隨機不確定性。

（3）執行代價C

表示用戶執行一個Web服務所需的代價。

上述各個QoS屬性中，執行代價和執行時間的屬性值越大，表明Web服務質量越差，稱為成本型指標，屬于負指標；可用性越大，則表明Web服務質量越好，稱為效益型指標，屬于正指標。

2.2 基于QoS的Web服務組合模型

Web服務組合是將現有的小粒度的Web服務按照一定的邏輯組合起來使得獲得的整體服務功能更強。Web服務組合的模式可以分為順序結構、選擇結構、并行結構和循環結構這4種結構模式，在實際應用中大部分組合服務都可以由這4種基本結構復合而成。由參考文獻［23］的研究結果可知，4種結構模式可以轉換為串聯結構（如圖1所示），因此本文僅考慮串聯結構下的Web服務組合問題。

圖1 Web服務的串聯結構

圖1中WSi表示組合中使用的各服務。

相應地，Web服務組合的QoS計算模型［21］見表1。

表1 Web服務組合QoS計算模型

在表1中，Ti、Ai、Ci分別表示在組合服務中第i個服務的響應時間、可用性和執行代價這3個QoS屬性值，n表示服務的總數目。

基于QoS的Web服務組合模型定義如下：

其中，ωi表示各個屬性的權值，應取其歸一化值。

3 離散差分進化算法

DE算法是一種原理簡單、實現有效的基于群體進化的算法。DE采用與遺傳算法相似的進化步驟，包括變異、交叉、選擇3種操作。與傳統遺傳算法不同的是，DE算法在當前代隨機選擇不同的個體，使其生成一個或幾個比例差分矢量，再利用差分矢量對當前代種群的個體進行擾動，從而進行變異。

在DE算法中，有不同特性的變異操作能夠用于為當前種群的目標矢量創建變異矢量。以DE/best/1為例：

其中，r1、r2為從集合｛1，2，…，NP}中隨機選取的兩個整數，且r1≠r2。為當前種群中適應度值最好的個體，該種策略以當前代全局最優值引導目標矢量的變異，收斂速度快，但極易陷入局部最優。

為了挖掘出種群潛在的多樣性，DE算法將目標矢量Xit與相應的變異矢量Vit進行交叉操作生成一個試驗矢量U。DE算法中通常使用的是二項式交叉方式。該交叉策略如下：

其中，υit為第i個變異矢量的第t個元素，uit為交叉之后產生的第i個試驗矢量的第t個元素。randit為第i個矢量對應的t維隨機數。該式決定了試驗矢量中的元素是由變異矢量還是由目標矢量提供，t=trand確保了至少一個元素由變異矢量提供。

在執行二項式交叉時，對于D個變量中的每一個變量，均生成［0，10］的隨機數，若隨機數小于或等于預先給定的交叉概率CR時，該變量進行交叉操作。因其變異矢量貢獻給試驗矢量的參數個數近似二項式分布而稱之為二項式交叉。由式（5）可知，當CR越大，則對V的貢獻越大，此時有利于局部搜索和加速收斂。反之，當CR越小，此時DE算法更側重于保持群體多樣性和全局搜索能力。本文CR取0.5。

在進行交叉操作后，先對試驗矢量進行取值范圍的檢查，確保其取值在給定范圍中。為了保持后代種群的規模不變，將經過變異和交叉的試驗矢量Uit與目標矢量Xit進行競爭，以確定更優的矢量進入下一代。本文將試驗矢量Uit與目標矢量Xit混合排序，選取最優秀的NP個進入下一代。據此，重復變異、交叉、選擇操作，直至達到停止條件。

DE有多種不同的變化形式，演化出具有不同特性的變異策略，有的策略側重全局搜索能力，有的策略則強調收斂速度。本文結合多種DE變異策略，提出一種離散多策略DE，并將其應用于Web服務組合問題。

3.1 離散解編碼

將DE算法應用到Web服務組合問題中，首要解決的是該問題中子任務子服務到DE算法個體的映射。本文對服務組合編碼的方法如下，假定服務組合問題包含n個子任務，且每個子任務待選Web服務的個數均為m，那么每個待選服務可用WSij（T，A，R）表示，i為子任務的編號，j為完成該子任務的子服務的編號。設定DE算法的每個個體代表一條服務組合路徑，個體的維度與服務組合問題的子任務數一致。舉例來說，服務組合路徑WS12→WS21→WS32→…→WSn5和WS15→WS24→WS39→…→WSn3可以分別用和來表示。

3.2 多策略隨機選擇框架

根據變異過程的不同，DE算法演化出了多種不同的變異策略。本文為求解Web服務組合問題，以DE/rand/2、DE/current_to_rand/1和DE/best/2 3種變異策略構建變異策略選擇池。

（1）DE/rand/2

DE/rand/2變異策略中，將兩個差分矢量和一個基矢量相加，表現出類高斯擾動，使得個體變異具有更好的全局搜索能力，不易出現過早收斂的現象，但收斂速度相對較慢。其變異策略公式為：

其中，Vit代表經過變異之后的新矢量（下文同），r1、r2、r3、r4、r5是從｛1，2，…，NP}（NP為解種群規模）中隨機選取的整數，且其值互不相同，分別是r1、r2、r3、r4、r5對應的個體的第t維差分矢量縮放因子，F控制著變異矢量對基矢量的影響，本文中F取0.5。

（2）DE/current_to_rand/1

DE/current_to_rand/1變異策略中，兩個差分矢量的規模因子分別為［0，1］、［0.6，1］區間均勻分布的隨機變量，使得該變異策略保持了種群多樣性，同時也具備了一定的局部搜索能力。其變異策略公式為：

其中r1、r2、r3、r4是從｛1，2，…，NP}（NP為解種群規模）中隨機選取的整數，且其值互不相同分別是r1、r2、r3、r4對應的個體的第t維。Xit是基矢量，該策略中以等待變異的原個體的矢量作為基矢量。差分矢量縮放因子F控制著變異矢量對基矢量的影響，本文中F取［0.6，1］。rand是均勻分布的隨機變量，范圍為［0，1］。

（3）DE/best/2

DE/best/2變異策略中，以兩個差分矢量對當前代全局最優解進行擾動，具有很強的局部搜索能力，收斂速度快，但極易陷入局部最優。其變異策略公式為：

其中，r1、r2、r3、r4是從｛1，2，…，NP}（NP為解種群規模）中隨機選取的整數，且其值互不相同，分別是r1、r2、r3、r4對應的個體的第t維。是基矢量，該策略中以當代適應度值最優的個體的矢量作為基矢量。差分矢量縮放因子F控制著變異矢量對基矢量的影響，本文中F取［0.6，1］。rand是均勻分布的隨機變量，范圍為［0，1］。

基于上述3種策略，本文引入多策略隨機選擇框架，每次進化隨機選擇策略池中的策略，即設定｛1，2，3}中每個整數對應一個變異策略，每次進行變異操作前，隨機生成｛1，2，3}中任意一個整數，調用相應的變異策略。

變異策略池中，DE/rand/2有較強的全局搜索能力，不易陷入局部最優；DE/current_to_rand/1保持了種群多樣性；而DE/best/2具有很強的局部搜索能力，收斂速度快，本文算法引入多策略隨機選擇框架，調用具有不同特性的變異策略，以隨機的方式進行搜索能力和收斂速度的均衡，增加了種群中個體的多樣性，避免了過早收斂及陷入局部最優。同時，增加多策略隨機選擇框架的改進DE算法與原始DE算法的時間復雜度相同O（NP·D），與原始DE算法一樣簡單，便于實現。MDDE算法流程具體如下。

步驟1初始化

置進化代數計數器g=1，并在搜索空間中隨機初始化種群。

步驟2依據式（3），計算初始化種群的目標矢量的適應度值。

步驟3While終止條件不滿足Do

Fori=1：NP

步驟3.1變異操作

隨機產生｛1，2，3}中任意一個整數x，調用相應的變異策略生成變異矢量Vit，進行越界修正。

步驟3.2交叉操作

變異矢量Vit與目標矢量Xit進行二項交叉操作，根據式（5）生成試驗矢量Uit=（ui1t，…，uiDt），進行越界修正。

步驟3.3選擇操作

計算目標矢量和試驗矢量的適應度值，將其混合排序比較，取最優的NP個矢量。

End For

g=g+1

End While

4 實驗和分析

由于目前尚未有標準的實驗平臺以及測試數據，因此本文在實驗的時候采取隨機產生QoS數據來仿真驗證算法的性能。實驗中使用的Web服務數據具有如下特性：一個功能相對復雜的個性化服務由10個功能相對單一的服務WS1～WS10組合而成，每個服務的候選服務數為100，各候選服務的3維QoS指標數據（響應時間、可用性、執行代價）隨機產生取值范圍均是，各維對應權重分別設置為1/3、1/3、1/3。

實驗中選取原始DE算法作為比較對象。設置原始DE算法以DE/best/1為變異策略，差分矢量縮放因子取0.5，MDDE算法中的差分矢量縮放因子以及一些參數均在第4.2節給出，MDDE算法和原始DE算法的交叉概率均取0.5，且使用相同的選擇策略，最大迭代次數同為100，種群規模均為100。鑒于智能算法的隨機性，每次試驗運行100次，記錄算法求解的最大值、最小值、平均值。

圖2表示的是原始DE算法以及MDDE算法求得的解的平均適應度值隨著迭代次數增加的收斂過程。原始的DE算法雖然具有很強的局部搜索能力，收斂速度快，但容易陷入局部最優，體現在折線圖上是，在迭代60次以后，原始DE算法求解得平均適應度值已不再變化。MDDE算法在算法初期收斂相對緩慢，在60代之前其平均適應度值不大于原始DE算法，經過60次迭代以后，與原始DE算法陷入局部最優解不同，MDDE算法仍然能夠繼續提升求解精度直至到達算法終止條件。出現這種情況的原因在于：MDDE算法中采用了多策略和隨機選擇機制，意味著算法具備多種演化能力，可以有效避免單一進化機制導致的局部收斂，具備全局探索能力，維持了解種群的多樣性，避免了過早收斂。

圖2 算法平均適應度值演變趨勢

圖3描述了兩種算法運行100次，所得解適應度的最大值、最小值、平均值的對比情況。對比柱狀圖，能夠發現，同樣的運行次數100，同樣的最大迭代次數100，MDDE算法在適應度最大值、最小值、平均值都全面優于原始算法。更優的最大值、最小值表明MDDE算法擁有更好的全局以及局部尋優能力；更優的平均值說明MDDE算法的穩定性更好。

圖3 算法運行100次數據統計

5 結束語

移動互聯網技術的普及，使人們不再滿足于單一功能的服務，或僅僅是在數量上的服務集成，而更傾向于按需定制的個性化服務或服務組合。本文首先提出了一種多策略離散差分進化算法，MDDE算法采用隨機選擇框架，調用具有不同特性的變異策略，具備較好全局探索能力，能維持解種群的多樣性，避免過早收斂。然后將MDDE算法應用于基于QoS的Web服務組合優化問題。仿真實驗表明，MDDE算法是一種搜索能力和收斂速度均衡的離散差分進化算法，在求解Web服務組合優化問題中比原始DE算法的收斂精度和穩定性更高。

參考文獻：

［1］張平.移動泛在融合的通信業務發展趨勢［J］.電信工程技術與標準化，2008（1）：1-5.ZHANG P.Towards mobile and ubiquitous convergent communication service［J］.Telecom Engineering Technics and Standardiziation，2008（1）：1-5.

［2］QIU X F，LIU J W，ZHAO P C.Secure cloud computing architecture on mobile internet［C］/The 2nd International Conference on Artificial Intelligence，Management Science and Electronic Commerce（AIMSEC），August 8-11，2011，Dengfeng，China.New Jersey：IEEE Press，2011：619-622.

［3］BENYAMINA D，HAFID A，GENDREAU M.Wireless mesh networks design-a survey［J］.Communications Surveysamp;Tutorials，2012，14（2）：299-310.

［4］沈晶歆.移動互聯網關鍵技術及典型業務產品研究［J］.電信科學，2010（10）：5-12.SHEN J X.Research of key technique and typical applications in mobile internet［J］.Telecommunications Science，2010（10）：5-12.

［5］FRANGOUDIS P A，POLUZOS G C，KEMERLIS V P.Wireless community networks：an alternative approach for nomadic broadband network access［J］.Communications Magazine，2011，49（5）：206-213.

［6］曾桂根，韓小燕，陳伏州，等.基于模式感知的無線異構網絡融合方案［J］.南京郵電大學學報：自然科學版，2011，31（3）：14-20.ZENG G G，HAN X Y，CHEN F Z，et al.Wireless heterogeneous network convergence scheme based on mode awareness［J］.Journal of Nanjing University of Posts and Telecommunications：Natural Science，2011，31（3）：14-20.

［7］KIM W，KIM K S.Trial of communication services based on wireless ubiquitous network［C］/The 40th International Conference on Computers and Industrial Engineering（CIE），July 25-28，2010，Hyogo，Japan.New Jersey：IEEE Press，2010：1-5.

［8］岳昆，王曉玲，周傲英.Web服務核心支撐技術：研究綜述［J］.軟件學報，2004，15（3）：428-442.YUE K，WANG X L，ZHOU A Y.Underlying techniques for Web services：A survey［J］.Journal of Software，2004，15（3）：428-442.

［9］肖芳雄，黃志球，曹子寧，等.Web服務組合功能與QoS的形式化統一建模和分析［J］.軟件學報，2011，22（11）：2698-2715.XIAO F X，HUANG Z Q，CAO Z N，et al.Unified formal modeling and analyzing both functionality and QoS of Web services composition［J］.Journal of Software，2011，22（11）：2698-2715.

［10］DUSTDAR S，SCHREINER W.A survey on web services composition［J］.International Journal of Web and Grid Services，2005，1（1）：1-30.

［11］SHENG Q Z，QIAO X，VASILAKOS A V，et al.Web services composition：A decade’s overview［J］.Information Sciences，2014（280）：218-238.

［12］DUAN Q.Network service description and discovery in ubiquitous and pervasive grids［C］/2008 IEEE GLOBECOM Workshops，November 30-December 4，2008，New Orleans，Louisiana，USA.New Jersey：IEEE Press，2008：1-5.

［13］PENG K，BAO F.A design of secure ubiquitous network service［C］/The 4th International Conference on Ubiquitous Information Technologiesamp;Applications，December 20-22，2009，HongKong，China.New Jersey：IEEE Press，2009：327-331.

［14］LEE K，JEON J，LEE W，et al.Qos for web services：requirements and possible approaches［J］.W3C Working Group Note，2003，25（3）：1-9.

［15］HAO Y，ZHANG Y，CAO J.A novel QoS model and computation framework in web service selection［J］.World Wide Web，2012，15（5-6）：663-684.

［16］ZENG L Z，BENATALLAH B，NGU A H H，et al.QoS-aware middleware for Web services composition［J］.IEEE Transactions on Software Engineering，2004，30（5）：311-327.

［17］ZHENG Z，MA H，LYU MR，et al.Collaborative web service QoS prediction via neighborhood integrated matrix factorization［J］.IEEE Transactions on Services Computing，2013，6（3）：289-299.

［18］YILMAZ A E，KARAGOZ P.Improved genetic algorithm based approach for QoS aware web service composition［C］/2014 IEEE 21st International Conference on Web Services（ICWS 2014），June 27- July 2，2014，Anchorage，Alaska，USA.New Jersey：IEEE Press，2014：463-470.

［19］張成文，蘇森，陳俊亮.基于遺傳算法的QoS感知的Web服務選擇［J］.計算機學報，2006，29（7）：1029-1037.ZHANG C W，SU S，CHEN J L.Genetic algorithm on Web services selection supporting QoS［J］.Chinese Journal of Computers，2006，29（7）：1029-1037.

［20］XU T，WANG X H.Web service composition based on multi-objective particle swarm optimization algorithm［J］.Computer Engineering and Design，2010，31（18）：4076-4081.

［21］溫濤，盛國軍，郭權，等.基于改進粒子群算法的Web服務組合［J］.計算機學報，2013，36（5）：1031-1046.WEN T，SHENG G J，GUO Q，et al.Web service composition based on modified particle swarm optimization［J］.Chinese Journal of Computers，2013，36（5）：1031-1046.

［22］HE J，CHEN L，WANG X，et al.Web service composition optimization based on improved artificial bee colony algorithm［J］.Journal of Networks，2013，8（9）：2143-2149.

［23］WANG P.QoS-aware web services selection with intuitionistic fuzzy set under consumer’s vague perception［J］.Expert Systems with Applications，2009，36（3）：4460-4466.

Personalized service com position based on multi-strategy discrete differential evolution in mobile internet

XU Bin，QI Jin，YIN Xi，WANG Ye，CHANG Ruiyun
School of Internet of Things，Nanjing University of Posts and Telecommunications，Nanjing 210003，China

With the popularity of mobile internet technology，people are not satisfied with the service that provides a single function and hope to gain the personalized or composition service according to their needs.A muti-strategy discrete differential evolution（MDDE）algorithm applied in Web service composition was put forward.The algorithm，which adopts a random selection framework and multi-mutation strategies with different properties，was the balance of search ability and convergence speed.The results indicate that the proposed algorithm is better than traditional differential evolution algorithm in solving Web service combination optimization problems in terms of the solution quality and stability.

Web service composition，differential evolution，multi-strategy mutation

s：China Postdoctoral Science Foundation Funded Project（No.2015M571790），NUPTSF（No.NY213047，No.NY213050，No.NY214102）

TP18

A

10.11959/j.issn.1000-0801.2016042

2015-09-01；

2015-12-21

中國博士后科學基金資助項目（No.2015M571790）；南京郵電大學引進人才科研啟動基金和校級科研基金資助項目（No.NY213047，No.NY213050，No.NY214102）

許斌（1981-），男，博士，南京郵電大學物聯網學院講師，主要研究方向為智能計算。

亓晉（1983-），男，博士，南京郵電大學物聯網學院講師，主要研究方向為新一代網絡、大數據管理與智能計算、云計算。

印溪（1992-），女，南京郵電大學碩士生，主要研究方向為智能計算。

王野（1991-），男，南京郵電大學碩士生，主要研究方向為服務組合。

常瑞云（1992-），女，南京郵電大學碩士生，主要研究方向為智能云制造。