基于多策略離散差分進(jìn)化的移動(dòng)互聯(lián)網(wǎng)個(gè)性化服務(wù)組合

許斌，亓?xí)x，印溪，王野，常瑞云

（南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院，江蘇南京210003）

研究與開發(fā)

基于多策略離散差分進(jìn)化的移動(dòng)互聯(lián)網(wǎng)個(gè)性化服務(wù)組合

許斌，亓?xí)x，印溪，王野，常瑞云

（南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院，江蘇南京210003）

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

Web服務(wù)組合；差分進(jìn)化；多策略變異

1 引言

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

當(dāng)前服務(wù)組合的研究多集中于Web服務(wù)組合［8-11］。在Web服務(wù)組合的研究中，一般采用服務(wù)的QoS指標(biāo)來(lái)評(píng)價(jià)和區(qū)分服務(wù)。QoS指標(biāo)主要包括服務(wù)執(zhí)行時(shí)間、代價(jià)、可用性、可靠性以及信譽(yù)度等?；赒oS的Web服務(wù)組合問(wèn)題，是從若干個(gè)服務(wù)候選集中分別選擇出候選服務(wù)進(jìn)行組合，使得組合后的服務(wù)既能滿足用戶的需求，又具有良好的QoS。Web組合服務(wù)的QoS計(jì)算模型和服務(wù)組合優(yōu)選算法是目前研究的熱點(diǎn)問(wèn)題［12，13］。

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

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

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

2 問(wèn)題建模

2.1 Web服務(wù)的QoS屬性

為了區(qū)分和評(píng)價(jià)Web服務(wù)，現(xiàn)有的研究一般采用QoS指標(biāo)。在QoS指標(biāo)中，有些參數(shù)值由服務(wù)生產(chǎn)者提供，有些則由用戶（服務(wù)使用者）決定。本文選取響應(yīng)時(shí)間、可用性和執(zhí)行代價(jià)這3個(gè)具有代表性的QoS屬性來(lái)評(píng)估Web服務(wù)［15］。

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

（1）響應(yīng)時(shí)間T

表示用戶請(qǐng)求服務(wù)后到接受服務(wù)響應(yīng)所經(jīng)過(guò)的總時(shí)間。

其中，Ttrans表示請(qǐng)求消息和響應(yīng)消息在網(wǎng)絡(luò)上的傳輸時(shí)間，容易受到網(wǎng)絡(luò)狀況影響；Tproc表示處理服務(wù)請(qǐng)求所使用的時(shí)間。

（2）可用性A

表示服務(wù)可訪問(wèn)的概率。

其中，∑tsucess表示在調(diào)用一定次數(shù)的服務(wù)后，服務(wù)被成功調(diào)用的總時(shí)間；∑t表示所用的總時(shí)間。實(shí)際環(huán)境中，服務(wù)的可用性受到網(wǎng)絡(luò)環(huán)境、服務(wù)器狀態(tài)、客戶端狀態(tài)等因素影響，具有隨機(jī)不確定性。

（3）執(zhí)行代價(jià)C

表示用戶執(zhí)行一個(gè)Web服務(wù)所需的代價(jià)。

上述各個(gè)QoS屬性中，執(zhí)行代價(jià)和執(zhí)行時(shí)間的屬性值越大，表明Web服務(wù)質(zhì)量越差，稱為成本型指標(biāo)，屬于負(fù)指標(biāo)；可用性越大，則表明Web服務(wù)質(zhì)量越好，稱為效益型指標(biāo)，屬于正指標(biāo)。

2.2 基于QoS的Web服務(wù)組合模型

Web服務(wù)組合是將現(xiàn)有的小粒度的Web服務(wù)按照一定的邏輯組合起來(lái)使得獲得的整體服務(wù)功能更強(qiáng)。Web服務(wù)組合的模式可以分為順序結(jié)構(gòu)、選擇結(jié)構(gòu)、并行結(jié)構(gòu)和循環(huán)結(jié)構(gòu)這4種結(jié)構(gòu)模式，在實(shí)際應(yīng)用中大部分組合服務(wù)都可以由這4種基本結(jié)構(gòu)復(fù)合而成。由參考文獻(xiàn)［23］的研究結(jié)果可知，4種結(jié)構(gòu)模式可以轉(zhuǎn)換為串聯(lián)結(jié)構(gòu)（如圖1所示），因此本文僅考慮串聯(lián)結(jié)構(gòu)下的Web服務(wù)組合問(wèn)題。

圖1 Web服務(wù)的串聯(lián)結(jié)構(gòu)

圖1中WSi表示組合中使用的各服務(wù)。

相應(yīng)地，Web服務(wù)組合的QoS計(jì)算模型［21］見(jiàn)表1。

表1 Web服務(wù)組合QoS計(jì)算模型

在表1中，Ti、Ai、Ci分別表示在組合服務(wù)中第i個(gè)服務(wù)的響應(yīng)時(shí)間、可用性和執(zhí)行代價(jià)這3個(gè)QoS屬性值，n表示服務(wù)的總數(shù)目。

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

其中，ωi表示各個(gè)屬性的權(quán)值，應(yīng)取其歸一化值。

3 離散差分進(jìn)化算法

DE算法是一種原理簡(jiǎn)單、實(shí)現(xiàn)有效的基于群體進(jìn)化的算法。DE采用與遺傳算法相似的進(jìn)化步驟，包括變異、交叉、選擇3種操作。與傳統(tǒng)遺傳算法不同的是，DE算法在當(dāng)前代隨機(jī)選擇不同的個(gè)體，使其生成一個(gè)或幾個(gè)比例差分矢量，再利用差分矢量對(duì)當(dāng)前代種群的個(gè)體進(jìn)行擾動(dòng)，從而進(jìn)行變異。

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

其中，r1、r2為從集合｛1，2，…，NP}中隨機(jī)選取的兩個(gè)整數(shù)，且r1≠r2。為當(dāng)前種群中適應(yīng)度值最好的個(gè)體，該種策略以當(dāng)前代全局最優(yōu)值引導(dǎo)目標(biāo)矢量的變異，收斂速度快，但極易陷入局部最優(yōu)。

為了挖掘出種群潛在的多樣性，DE算法將目標(biāo)矢量Xit與相應(yīng)的變異矢量Vit進(jìn)行交叉操作生成一個(gè)試驗(yàn)矢量U。DE算法中通常使用的是二項(xiàng)式交叉方式。該交叉策略如下：

其中，υit為第i個(gè)變異矢量的第t個(gè)元素，uit為交叉之后產(chǎn)生的第i個(gè)試驗(yàn)矢量的第t個(gè)元素。randit為第i個(gè)矢量對(duì)應(yīng)的t維隨機(jī)數(shù)。該式?jīng)Q定了試驗(yàn)矢量中的元素是由變異矢量還是由目標(biāo)矢量提供，t=trand確保了至少一個(gè)元素由變異矢量提供。

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

在進(jìn)行交叉操作后，先對(duì)試驗(yàn)矢量進(jìn)行取值范圍的檢查，確保其取值在給定范圍中。為了保持后代種群的規(guī)模不變，將經(jīng)過(guò)變異和交叉的試驗(yàn)矢量Uit與目標(biāo)矢量Xit進(jìn)行競(jìng)爭(zhēng)，以確定更優(yōu)的矢量進(jìn)入下一代。本文將試驗(yàn)矢量Uit與目標(biāo)矢量Xit混合排序，選取最優(yōu)秀的NP個(gè)進(jìn)入下一代。據(jù)此，重復(fù)變異、交叉、選擇操作，直至達(dá)到停止條件。

DE有多種不同的變化形式，演化出具有不同特性的變異策略，有的策略側(cè)重全局搜索能力，有的策略則強(qiáng)調(diào)收斂速度。本文結(jié)合多種DE變異策略，提出一種離散多策略DE，并將其應(yīng)用于Web服務(wù)組合問(wèn)題。

3.1 離散解編碼

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

3.2 多策略隨機(jī)選擇框架

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

（1）DE/rand/2

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

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

（2）DE/current_to_rand/1

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

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

（3）DE/best/2

DE/best/2變異策略中，以兩個(gè)差分矢量對(duì)當(dāng)前代全局最優(yōu)解進(jìn)行擾動(dòng)，具有很強(qiáng)的局部搜索能力，收斂速度快，但極易陷入局部最優(yōu)。其變異策略公式為：

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

基于上述3種策略，本文引入多策略隨機(jī)選擇框架，每次進(jìn)化隨機(jī)選擇策略池中的策略，即設(shè)定｛1，2，3}中每個(gè)整數(shù)對(duì)應(yīng)一個(gè)變異策略，每次進(jìn)行變異操作前，隨機(jī)生成｛1，2，3}中任意一個(gè)整數(shù)，調(diào)用相應(yīng)的變異策略。

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

步驟1初始化

置進(jìn)化代數(shù)計(jì)數(shù)器g=1，并在搜索空間中隨機(jī)初始化種群。

步驟2依據(jù)式（3），計(jì)算初始化種群的目標(biāo)矢量的適應(yīng)度值。

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

Fori=1：NP

步驟3.1變異操作

隨機(jī)產(chǎn)生｛1，2，3}中任意一個(gè)整數(shù)x，調(diào)用相應(yīng)的變異策略生成變異矢量Vit，進(jìn)行越界修正。

步驟3.2交叉操作

變異矢量Vit與目標(biāo)矢量Xit進(jìn)行二項(xiàng)交叉操作，根據(jù)式（5）生成試驗(yàn)矢量Uit=（ui1t，…，uiDt），進(jìn)行越界修正。

步驟3.3選擇操作

計(jì)算目標(biāo)矢量和試驗(yàn)矢量的適應(yīng)度值，將其混合排序比較，取最優(yōu)的NP個(gè)矢量。

End For

g=g+1

End While

4 實(shí)驗(yàn)和分析

由于目前尚未有標(biāo)準(zhǔn)的實(shí)驗(yàn)平臺(tái)以及測(cè)試數(shù)據(jù)，因此本文在實(shí)驗(yàn)的時(shí)候采取隨機(jī)產(chǎn)生QoS數(shù)據(jù)來(lái)仿真驗(yàn)證算法的性能。實(shí)驗(yàn)中使用的Web服務(wù)數(shù)據(jù)具有如下特性：一個(gè)功能相對(duì)復(fù)雜的個(gè)性化服務(wù)由10個(gè)功能相對(duì)單一的服務(wù)WS1～WS10組合而成，每個(gè)服務(wù)的候選服務(wù)數(shù)為100，各候選服務(wù)的3維QoS指標(biāo)數(shù)據(jù)（響應(yīng)時(shí)間、可用性、執(zhí)行代價(jià)）隨機(jī)產(chǎn)生取值范圍均是，各維對(duì)應(yīng)權(quán)重分別設(shè)置為1/3、1/3、1/3。

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

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

圖2 算法平均適應(yīng)度值演變趨勢(shì)

圖3描述了兩種算法運(yùn)行100次，所得解適應(yīng)度的最大值、最小值、平均值的對(duì)比情況。對(duì)比柱狀圖，能夠發(fā)現(xiàn)，同樣的運(yùn)行次數(shù)100，同樣的最大迭代次數(shù)100，MDDE算法在適應(yīng)度最大值、最小值、平均值都全面優(yōu)于原始算法。更優(yōu)的最大值、最小值表明MDDE算法擁有更好的全局以及局部尋優(yōu)能力；更優(yōu)的平均值說(shuō)明MDDE算法的穩(wěn)定性更好。

圖3 算法運(yùn)行100次數(shù)據(jù)統(tǒng)計(jì)

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

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

參考文獻(xiàn)：

［1］張平.移動(dòng)泛在融合的通信業(yè)務(wù)發(fā)展趨勢(shì)［J］.電信工程技術(shù)與標(biāo)準(zhǔn)化，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］沈晶歆.移動(dòng)互聯(lián)網(wǎng)關(guān)鍵技術(shù)及典型業(yè)務(wù)產(chǎn)品研究［J］.電信科學(xué)，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］曾桂根，韓小燕，陳伏州，等.基于模式感知的無(wú)線異構(gòu)網(wǎng)絡(luò)融合方案［J］.南京郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，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服務(wù)核心支撐技術(shù)：研究綜述［J］.軟件學(xué)報(bào)，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服務(wù)組合功能與QoS的形式化統(tǒng)一建模和分析［J］.軟件學(xué)報(bào)，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服務(wù)選擇［J］.計(jì)算機(jī)學(xué)報(bào)，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］溫濤，盛國(guó)軍，郭權(quán)，等.基于改進(jìn)粒子群算法的Web服務(wù)組合［J］.計(jì)算機(jī)學(xué)報(bào)，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

中國(guó)博士后科學(xué)基金資助項(xiàng)目（No.2015M571790）；南京郵電大學(xué)引進(jìn)人才科研啟動(dòng)基金和校級(jí)科研基金資助項(xiàng)目（No.NY213047，No.NY213050，No.NY214102）

許斌（1981-），男，博士，南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院講師，主要研究方向?yàn)橹悄苡?jì)算。

亓?xí)x（1983-），男，博士，南京郵電大學(xué)物聯(lián)網(wǎng)學(xué)院講師，主要研究方向?yàn)樾乱淮W(wǎng)絡(luò)、大數(shù)據(jù)管理與智能計(jì)算、云計(jì)算。

印溪（1992-），女，南京郵電大學(xué)碩士生，主要研究方向?yàn)橹悄苡?jì)算。

王野（1991-），男，南京郵電大學(xué)碩士生，主要研究方向?yàn)榉?wù)組合。

常瑞云（1992-），女，南京郵電大學(xué)碩士生，主要研究方向?yàn)橹悄茉浦圃臁?/p>