李　琳，應(yīng)　時，趙　翀，董　波

(1.武漢大學(xué)軟件工程國家重點實驗室，湖北武漢430072; 2.武漢大學(xué)計算機學(xué)院，湖北武漢430072)

?

基于蟻群算法的面向服務(wù)軟件的部署優(yōu)化方法

李琳，應(yīng)時，趙翀，董波

(1.武漢大學(xué)軟件工程國家重點實驗室，湖北武漢430072; 2.武漢大學(xué)計算機學(xué)院，湖北武漢430072)

摘要：面向服務(wù)軟件的部署優(yōu)化問題是典型的NP難題.本文構(gòu)建了基于性能改善的軟件部署優(yōu)化模型，設(shè)計了一種蟻群優(yōu)化算法ACO-DO進行近似最優(yōu)解的快速求解.該算法通過設(shè)計基于部署優(yōu)化問題的啟發(fā)式、改進部署方案的構(gòu)建順序、增加局部搜索過程實現(xiàn)蟻群算法求解效率的提升.通過不同規(guī)模的實例實驗，驗證了ACO-DO算法能夠取得比現(xiàn)有的混合整數(shù)線性規(guī)劃算法、蟻群算法和遺傳算法更好的性能.

關(guān)鍵詞：面向服務(wù)的軟件;部署優(yōu)化;蟻群算法;性能

1　引言

應(yīng)用和系統(tǒng)環(huán)境的變化將會使面向服務(wù)的軟件在長時間運行后出現(xiàn)性能降級問題，對軟件部署方案進行調(diào)整與優(yōu)化是解決該問題的常用方法［1］.由于可能的部署方案總數(shù)通常非常巨大，探索可行的部署空間需耗費大量的計算成本;且評估性能的指標(biāo)之間以及不同用戶對同一指標(biāo)的評價之間常常存在沖突［2］，搜尋最優(yōu)的軟件部署方案常常需要衡量這些沖突因素.因此，設(shè)計和開發(fā)能夠表現(xiàn)優(yōu)異性能的部署方案成為一項具有挑戰(zhàn)性的任務(wù).

目前，國內(nèi)外專家學(xué)者在軟件部署方案的優(yōu)化與評估方面開展了大量研究，提出了許多創(chuàng)新性的解決方法，包括利用多目標(biāo)遺傳算法E3-R［3］解決面向服務(wù)等級協(xié)議的服務(wù)部署優(yōu)化問題，利用CDOXplore算法［4］處理云環(huán)境下的軟件部署優(yōu)化問題，基于結(jié)構(gòu)化約束敏感的軟件部署方法［5］實現(xiàn)大規(guī)模的軟件部署與優(yōu)化過程，基于用戶偏好與多維QoS指標(biāo)相結(jié)合的可擴展的部署優(yōu)化框架［6］，基于啟發(fā)式裝箱算法和粒子群演化算法相結(jié)合的混合型空間部署優(yōu)化算法ScatterD［7］，基于進化優(yōu)化的移動感知節(jié)點部署算法［8］從網(wǎng)絡(luò)覆蓋和能量消耗兩個方面優(yōu)化移動傳感器網(wǎng)絡(luò)中節(jié)點部署，以滿足用戶個性化需求為目標(biāo)的基于體系結(jié)構(gòu)驅(qū)動和網(wǎng)絡(luò)化移動應(yīng)用的客戶端軟件部署方案優(yōu)化方法ADCA［9］，基于P-ACO蟻群算法自動搜索嵌入式軟件系統(tǒng)的部署優(yōu)化策略［10］.這些方法雖然都可以實現(xiàn)軟件部署優(yōu)化過程，但針對軟件性能優(yōu)化的部署框架與模型的研究還很少，且優(yōu)化算法主要采用傳統(tǒng)的演化算法，而構(gòu)造性算法作為一種最快的近似方法［11］，目前還沒在軟件部署優(yōu)化領(lǐng)域得到同等的重視.

ACO算法是構(gòu)造性算法的典型代表，是專門用來求解復(fù)雜組合優(yōu)化難題的，目前已在諸多領(lǐng)域取得了很好的求解效果［12］.ACO算法能夠使用基于問題導(dǎo)向的啟發(fā)式，指導(dǎo)螞蟻快速朝向全局最優(yōu)解的方向前進［13］.因此，本文將ACO算法引入面向服務(wù)的軟件部署優(yōu)化問題之中，研究和設(shè)計了基于ACO算法和單目標(biāo)優(yōu)化策略的面向服務(wù)軟件部署優(yōu)化方法ACO-DO(Ant Colony Optimization for Deployment Optimization，ACO-DO).該方法通過設(shè)計問題的啟發(fā)式，提高算法的收斂速度;通過考慮方案組件的選擇順序，提高部署方案的構(gòu)建質(zhì)量;通過增加局部搜索過程，避免過早收斂于局部最優(yōu)解.

2　問題模型

本文構(gòu)建的部署優(yōu)化模型主要包含四部分:應(yīng)用軟件模型(Application Software Model，ASM)、運行平臺模型(Runtime Platform Model，RPM)、應(yīng)用場景(Application Scenarios，AS)、約束(Constraint，CON).其中，ASM提供部署的軟件信息，RPM提供用于部署的硬件節(jié)點信息，AS提供軟件性能評估的其它相關(guān)因素信息，CON提供軟件部署過程中所需滿足的約束條件.

定義1應(yīng)用軟件模型ASM是一個五元組ASM =(S，TR，SR，CW，ES):

①S = { s1，s2，…，sSN}，SN∈N，為一個非空有限服務(wù)集，表示組成軟件的所有服務(wù).

②TR: S→R為一個服務(wù)時間需求函數(shù)，指定每個服務(wù)請求對單位計算能力的平均服務(wù)時間需求.

③SR: S→R為一個空間需求函數(shù)，指定每個服務(wù)運行時占用的內(nèi)存空間.

④CW = { w1，w2，…，wWN}，WN∈N，為一個非空有限控制流集，其中wi為一個控制流，描述了實現(xiàn)一個組合服務(wù)時服務(wù)之間的交互關(guān)系.

⑤ES: S×S→R為一個事件規(guī)模函數(shù)，指定兩個服務(wù)間交互的事件的平均規(guī)模.

定義2運行平臺模型RPM是一個四元組RPM =(N，CP，AS，CC):

①N = { n1，n2，…，nHN}，HN∈N，為一個非空有限硬件節(jié)點集，表示可供軟件部署的所有硬件節(jié)點.

②CP: N→N為一個計算能力函數(shù)，指定每個硬件節(jié)點的計算能力.

③AS: N→R為一個可用空間函數(shù)，指定每個硬件節(jié)點上可用的內(nèi)存空間.

④CC: N×N→R為一個通信能力函數(shù)，指定任意兩個硬件節(jié)點之間的通信能力.

定義3應(yīng)用場景AS是一個五元組AS =(RA，IF，UC，PM，UF):

①RA: S→R為一個請求到達函數(shù)，指定服務(wù)集S中的每個服務(wù)接收的請求的平均到達率，即服務(wù)在單位時間內(nèi)接收的平均請求數(shù).

②IF: S×S→R為一個交互頻率函數(shù)，指定任意兩個服務(wù)之間的交互頻率.如果si= sj或si與sj之間不存在交互，則IF(si，sj)=0.

③UC =(uc1，uc2，…，ucUN)，UN∈N，是一個非空有限用戶集，表示使用該軟件的所有的用戶.

④EM = { m1，m2，…，mMN}，MN∈N，是一個非空有限指標(biāo)集，表示用于評估性能的所有指標(biāo).

⑤UF = { UF1，UF2，…，UFMN}為一個非空有限效用函數(shù)集，UFi指定第i個性能指標(biāo)對應(yīng)的效用函數(shù).

定義4約束CON是一個二元組CON =(LC，CLC):

①LC: S×N→{ 0，1}為位置約束函數(shù)，用于約束服務(wù)到硬件節(jié)點的分配.如果服務(wù)si可以部署在硬件節(jié)點nj上，則LC(si，nj)=1，否則LC(si，nj)=0.

②CLC: S×S→{ -1，0，1}為同位約束函數(shù)，用于約束兩個服務(wù)之間的位置關(guān)系.如果服務(wù)si和sj必須被部署在同一個硬件節(jié)點上，則CLC(si，sj)=1;如果服務(wù)si和sj不能被部署在同一個硬件節(jié)點上，則CLC(si，sj)= -1，如果si和sj之間不存在這一約束，則CLC(si，sj)=0.

本文主要考慮三種重要的性能評價指標(biāo):組合服務(wù)的平均延遲時間(用l表示)、組合服務(wù)的平均吞吐量(用t表示)以及硬件資源的平均利用率(用u表示).因此，本文的目標(biāo)函數(shù)可以定義為:

其中，UFu、UFl和UFt分別表示硬件節(jié)點的利用率、組合服務(wù)的平均延遲時間、組合服務(wù)的平均吞吐量所對應(yīng)的效用函數(shù); lk和tk分別表示在部署方案d下第k類組合服務(wù)的平均延遲時間和平均吞吐量.由于組合服務(wù)由控制流定義，因此可以使用控制流wi表示第i個組合服務(wù); uj表示在部署方案d下第j個硬件節(jié)點的利用率.

3　基于蟻群優(yōu)化的ACO-DO算法

在軟件部署優(yōu)化的問題中，螞蟻構(gòu)建的每個解對應(yīng)一種部署方案，解組件對應(yīng)服務(wù)到硬件節(jié)點的一種分配，螞蟻一步步將每個服務(wù)分配到一個硬件節(jié)點來構(gòu)建部署方案，當(dāng)所有服務(wù)都被分配到一個相應(yīng)的硬件節(jié)點時，一個部署方案就構(gòu)建完成.

為提高蟻群算法在部署優(yōu)化問題中的求解效率，本文設(shè)計了基于問題的啟發(fā)式，考慮了部署方案的構(gòu)建順序，同時還設(shè)計了局部搜索過程.

3.1信息素與啟發(fā)式的設(shè)計

本文分別使用τ(i，j)和η(i，j)表示將服務(wù)si分配到硬件節(jié)點nj(可以用公式d(si)= nj表示)所對應(yīng)的信息素和啟發(fā)式.在部署軟件時，為減少通訊延遲，通常希望將相互交互的服務(wù)部署在同一硬件節(jié)點上，但這會引起服務(wù)間的資源競爭，從而產(chǎn)生計算延遲.為均衡這兩種開銷，本文定義啟發(fā)式為:

其中Sj為si以及當(dāng)前部署在硬件節(jié)點nj上的所有服務(wù)的集合，IF(sk，si)為服務(wù)sk與si之間的交互頻率，DN為已經(jīng)部署服務(wù)的硬件節(jié)點數(shù).

上述啟發(fā)式表明，先分配的服務(wù)將影響后續(xù)服務(wù)的分配.為保證部署方案的質(zhì)量，本文使用服務(wù)列表表示方案構(gòu)建過程中服務(wù)的分配順序，并對服務(wù)列表進行優(yōu)化.服務(wù)列表的優(yōu)化使用絕對位置模型表示信息素模型，即信息素τs(i，k)表示服務(wù)si位于服務(wù)列表中第k個位置的期望值.

在軟件運行過程中，具有較大請求量的服務(wù)的性能指標(biāo)的變化通常會對軟件的整體性能產(chǎn)生較大影響，如果能夠先滿足這些服務(wù)的性能需求，則軟件的整體性能將得到較大的提升.因此，本文為服務(wù)列表優(yōu)化問題設(shè)計的啟發(fā)式為:

3.2方案的構(gòu)建

根據(jù)3.1節(jié)的分析可知，方案的構(gòu)建主要分兩步:服務(wù)列表的構(gòu)建和部署方案的構(gòu)建.在構(gòu)建服務(wù)列表時，本文結(jié)合偽隨機比例規(guī)則［14］和Merkle等［15］提出的求和規(guī)則進行解組件的選擇，解決簡單使用τs(i，k)進行解組件選擇時算法容易收斂于局部最優(yōu)解的問題［16］;在構(gòu)建部署方案時，約束CON將被用來阻止螞蟻將服務(wù)分配到不滿足約束的硬件節(jié)點上.方案的構(gòu)建步驟如下:

(1)將所有服務(wù)都放置于列表Sun中，即Sun= { s1，s2，…，sSN}，且設(shè)sList = { }，k =1.

(2)從列表Sun中選擇一個服務(wù)si放置到服務(wù)列表sList的第k個位置.選擇規(guī)則如下:首先，產(chǎn)生［0，1］之間的一個隨機數(shù)q，并將其與用戶定義的參數(shù)qs進行比較，如果q＜qs，則為服務(wù)列表中第k個位置選擇的服務(wù)si為:

否則，采用輪盤選擇規(guī)則完成服務(wù)列表第k個位置的服務(wù)選擇，即選擇在服務(wù)列表的第k個位置放置服務(wù)si的概率pik被定義為:

(3)將服務(wù)si從列表Sun中移除，且k = k +1.如果k ＜SN，則跳轉(zhuǎn)到步(2).

(4)選擇服務(wù)列表sList中第一個服務(wù)sp，并利用偽隨機比例規(guī)則為服務(wù)sp選擇一個部署節(jié)點.選擇規(guī)則如下:首先產(chǎn)生［0，1］之間的一個隨機數(shù)q，并將其與用戶定義的參數(shù)qd進行比較，如果q＜qd，則服務(wù)sp分配的硬件節(jié)點nj為:

否則，采用輪盤選擇規(guī)則完成服務(wù)到硬件節(jié)點的分配.在輪盤選擇規(guī)則中，將服務(wù)sp分配給硬件節(jié)點nj的概率ppj為:

其中，α、β為參數(shù).

(5)如果將服務(wù)sp分配給硬件節(jié)點nj能夠滿足約束CON，則將服務(wù)sp從列表sList中移除.如果sList≠，則跳轉(zhuǎn)到步(4).

(6)輸出構(gòu)建的部署方案d.

3.3局部搜索過程

局部搜索過程應(yīng)用于螞蟻的一次迭代完成之后，并基于m個當(dāng)前最優(yōu)的部署方案和螞蟻本次迭代所構(gòu)建的部署方案實現(xiàn)，在螞蟻還沒有找到m個最優(yōu)部署方案之前，局部搜索過程將不會執(zhí)行.局部搜索過程的基本步驟如下:

(1)設(shè)當(dāng)前m個最優(yōu)部署方案和本次迭代所構(gòu)建的部署方案組成的方案列表為dList，在該列表中，第i個元素的目標(biāo)函數(shù)值為OBVi，并設(shè)k =1.

(2)根據(jù)部署方案的目標(biāo)函數(shù)值，采用輪盤選擇規(guī)則從列表dList中選擇一個部署方案di.其中選擇列表dList中的部署方案di的概率為:

(3)選取部署方案di的第k個解組件，并判斷如果將其作為新部署方案的解組件時是否能夠滿足約束CON，如果滿足，則將該解組件添加到新部署方案中，否則跳轉(zhuǎn)到步(2).

(4)k =k +1，如果k＜SN，則跳轉(zhuǎn)到步(2)，否則計算構(gòu)建的部署方案的目標(biāo)函數(shù)值，并將其與當(dāng)前最優(yōu)的部署方案進行比較，保留最優(yōu)的部署方案和目標(biāo)函數(shù)值.

4　實驗設(shè)計與結(jié)果分析

4.1實驗數(shù)據(jù)與環(huán)境

本文在8種不同規(guī)模的模擬實例上，將所提出的ACO-DO與混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming，MILP)、蟻群系統(tǒng)(Ant Colony System，ACS)、遺傳算法(Genetic Algorithm，GA)進行對比，以評估其有效性.實例規(guī)模如表1所示.

本文中各算法所使用的參數(shù)是通過為每個參數(shù)設(shè)置變化范圍和變化步長，并進行反復(fù)試驗得出的.得出的最優(yōu)參數(shù)組合為:蟻群算法(即ACO-DO和ACS)的種群數(shù)AN =10，參數(shù)α= 1，局部搜索過程中的參數(shù)m =10，信息素更新率ρ= 0.1，參數(shù)β= 2，偽隨機比例參數(shù)q = qs= qd=0.5;遺傳算法種群數(shù)P = 100，雜交率pc=0.9，變異率pm=0.1.

表1　測試實例的規(guī)模

4.2ACO-DO算法的有效性分析

本文主要從兩個方面評價ACO-DO算法的有效性:(1)性能，即算法的執(zhí)行時間;(2)準確度，即目標(biāo)函數(shù)值.三種近似算法(ACO-DO、ACS和GA)的終止條件是，如果在連續(xù)的5000次評估(即ACO-DO算法的連續(xù)250次迭代或ACS算法的連續(xù)500次迭代或遺傳算法的連續(xù)50次進化)過程中沒有找到更好的解，則算法終止.圖1和圖2分別顯示了這四種算法在本文生成的模擬實例上運行所花費的執(zhí)行時間和得到的目標(biāo)函數(shù)值的平均值.MILP算法的復(fù)雜性使得它不能求解較大規(guī)模的問題，因此，在圖1和圖2中，MILP只給出了它能夠求解的問題的結(jié)果.

從圖1和圖2中可以看出，ACS算法與ACO-DO算法都具有較短的執(zhí)行時間，但ACS算法的準確度明顯低于ACO-DO算法，且在規(guī)模較大的問題中尤為明顯; GA算法與ACO-DO算法都具有較高的準確度，但GA算法的執(zhí)行時間較長，且問題規(guī)模越大，它們之間的時間差距越大.因此，ACO-DO相比其它算法，能夠花費較短的時間找到較好的解.

4.3啟發(fā)式的影響

為了評估本文引入的啟發(fā)式對算法性能的影響，本文設(shè)置ACO-DO算法中的啟發(fā)式參數(shù)β= 0，將得到的算法記為ACO-DO/H(ACO-DO without Heuristic)，將基于ACS算法且使用本文定義的啟發(fā)式的算法記為ACS-H(ACS with Heuristic)，然后分別對比ACO-DO和ACO-DO/H、ACS-H和ACS.

本實驗在前面生成的各實例上分別對ACO-DO、ACO-DO/H、ACS-H和ACS四種算法獨立執(zhí)行30次，每次執(zhí)行30000次評估，記錄每次實驗迭代過程中得到的目標(biāo)函數(shù)值，畫出這四種算法的演化曲線.圖3(a)和圖3(b)分別顯示了這兩組算法在實例6上運行的演化曲線圖(演化曲線上的值為30次獨立實驗得到的平均值).

從圖3中可以看出，當(dāng)執(zhí)行相同次數(shù)的評估時，ACO-DO總是能夠比ACO-DO/H找到擁有更優(yōu)目標(biāo)函數(shù)值的部署方案，且ACS-H總是能夠比ACS找到擁有更優(yōu)目標(biāo)函數(shù)值的部署方案，這說明本文定義的啟發(fā)式能夠有效地幫助算法找到更好的解.此外，從圖3中還可以看出，ACO-DO和ACS-H的收斂速度分別快于ACO-DO/H和ACS，且ACO-DO和ACS-H最終找到的解分別優(yōu)于ACO-DO/H和ACS，這說明本文的啟發(fā)式能夠指導(dǎo)螞蟻快速找到較好的部署方案.

4.4方案構(gòu)建順序的影響

為了評估ACO-DO算法中引入的方案構(gòu)建順序?qū)λ惴ㄐ阅艿挠绊?，本文將基于ACO-DO算法、但不考慮方案構(gòu)建順序(即僅根據(jù)偽隨機比例規(guī)則和信息素、啟發(fā)式的值進行部署方案的構(gòu)建)的算法記為ACO-DO/ BO(ACO-DO without Build Order)，將基于ACO-DO算法且使用本文定義的構(gòu)建順序的算法記為ACS-BO(ACS with Build Order)，并在前面生成的各實例上分別對ACO-DO、ACO-DO/BO、ACS-BO和ACS四種算法各獨立執(zhí)行30次，每次執(zhí)行30000次評估，記錄每次實驗迭代過程中得到的目標(biāo)函數(shù)值，畫出這四種算法的演化曲線.圖4(a)和圖4(b)分別顯示了這兩組算法在實例7上運行的演化曲線圖(演化曲線上的值為30次實驗的平均值).

從圖4可以看出，算法開始執(zhí)行的較短時間內(nèi)，兩組算法中的兩類算法得到的目標(biāo)函數(shù)值都相差不大;這是由于在算法執(zhí)行的初始階段，構(gòu)建順序還處于尋優(yōu)階段，優(yōu)勢不能完全得以體現(xiàn).而隨著算法的演化，兩組算法中的兩類算法得到的目標(biāo)函數(shù)值的差值越來越大，直到算法最終收斂;這是由于隨著算法的演化，構(gòu)建順序越來越優(yōu)，在后續(xù)的尋找最優(yōu)部署方案的過程中發(fā)揮的作用越來越大.

對比圖4(a)和圖4(b)可以看出，圖4(b)中構(gòu)建順序的優(yōu)勢明顯低于圖4(a)，這是因為圖4(b)中對比的兩種算法沒有使用本文定義的啟發(fā)式，構(gòu)建順序?qū)ψ罱K構(gòu)建的部署方案的影響僅依賴于約束，這使得構(gòu)建順序的優(yōu)勢無法得以完全發(fā)揮.上述對比可以說明，本文提出的方案構(gòu)建順序能在一定程度上提高軟件部署方案的構(gòu)建質(zhì)量.

4.5局部搜索過程的影響

為了評估ACO-DO算法中引入的局部搜索過程對算法性能的影響，本文將不帶本文定義的局部搜索方法的ACO-DO算法記為ACO-DO/LS(ACO-DO without Local Search)，將基于ACS算法且使用本文定義的局部搜索方法的算法記為ACS-LS(ACS with Local Search)，并在前面生成的各實例上分別對ACO-DO、ACO-DO/ LS、ACS-LS和ACS四種算法各獨立執(zhí)行30次，每次執(zhí)行40000次評估，記錄每次實驗迭代過程中得到的目標(biāo)函數(shù)值，畫出這四種算法的演化曲線(如圖5所示).

從圖5中可以看出，使用局部搜索過程的算法(ACO-DO和ACS-LS)比沒有使用局部搜索過程的算法(ACO-DO/LS和ACS)能夠更快地找到較好的解，且能夠最終得到較優(yōu)的目標(biāo)函數(shù)值，這說明局部搜索方法能夠進一步提高ACO-DO算法的性能.

5　結(jié)論

本文研究了蟻群算法在軟件部署優(yōu)化領(lǐng)域的應(yīng)用，構(gòu)建了面向服務(wù)軟件的部署優(yōu)化模型，并基于經(jīng)典ACS算法，提出了基于蟻群優(yōu)化的ACO-DO算法.該算法結(jié)合軟件工程領(lǐng)域的具體知識，設(shè)計了基于問題的啟發(fā)式和部署方案的構(gòu)建順序，指導(dǎo)螞蟻快速朝著最優(yōu)解的方向前進.此外，本文還將ACO-DO算法與局部搜索過程相結(jié)合，避免算法過早收斂于局部最優(yōu)解.通過在不同規(guī)模的部署優(yōu)化實例上進行的一系列試驗，以及與ACS和GA算法的性能比較，驗證了ACO-DO算法在求解軟件部署優(yōu)化問題中具有較好的求解性能.

參考文獻

［1］Vittorio C，Antinisca D M，Paola I.Model-Based SoftwarePerformance Analysis［M］.Berlin Heidelberg: Springer，2011.

［2］胡劍軍，官荷卿，魏峻，等.一種基于性能模型的中間件自配置框架［J］.軟件學(xué)報，2007，18(9): 2117 -2129.Hu Jian-jun，Guan He-qing，Wei Jun，et al.A performance model-based self-configuration framework for middleware［J］.Journal of Software，2007，18(9): 2117 -2129.(in Chinese)

［3］Wada H，Suzuki J，Yamano Y，et al.Evolutionary deployment optimization for service-oriented clouds［J］.Software Practice and Experience，2011，41(5): 469 -493.

［4］Frey S，F(xiàn)ittkau F，Hasselbring W.Search-based genetic optimization for deployment and reconfiguration of software in the cloud［A］.Proceedings of the 2013 International Conference on Software Engineering［C］.San Francisco: IEEE，2013.512 -521.

［5］Jayasinghe D，Pu C，Eilam T.Improving performance and availability of services hosted on IaaS clouds with structural constraint-aware virtual machine placement［A］.Proceedings of the 2011 IEEE International Conference on Services Computing［C］.Washington DC: IEEE，2011.72 -79.

［6］Malek S，Medvidovic N，Mikic-Rakic M.An extensible framework for improving a distributed software system＇s deployment architecture［J］.IEEE Transactions on Software Engineering，2012，38(1): 73 -100.

［7］White J，Dougherty B，Thompson C，et al.ScatterD: Spatial deployment optimization with hybrid heuristic/evolutionary algorithms［J］.ACM Transactions on Autonomous and A-daptive Systems，2011，6(3): 123 -154.

［8］南國芳，陳忠楠.基于進化優(yōu)化的移動感知節(jié)點部署算法［J］.電子學(xué)報，2012，40(5): 1017 -1022 NAN Guo-fang，CHEN Zhong-nan.Deployment algorithm of mobile sensing nodes based on evolutionary optimization［J］.Acta Electronica Sinica，2012，40(5): 1017 -1022.(in Chinese)

［9］張曉薇，曹東剛，陳向群，等.一種網(wǎng)絡(luò)化移動應(yīng)用部署方案優(yōu)化方法［J］.軟件學(xué)報，2011，22(12): 2866 -2878.Zhang X W，Cao D G，Chen X Q，et al.Deployment solution optimization for mobile network application［J］.Journal of Software，2011，22(12): 2866 -2878.(in Chinese)

［10］Aleti A，Grunske L，Meedeniya I，et al.Let the ants deploy your software-an ACO based deployment optimization strategy［A］.Proceedings of the 24th IEEE/ACM International Conference on Automated Software Engineering［C］.Auckland: IEEE，2009.505 -509.

［11］Dorigo M，Stützle T.Ant colony optimization: Overview and recent advances［A］.International Series in Operations Research＆Management Science(Handbook of Metaheuristics，Volume 146)［M］.US: Springer，2010.227 -263.

［12］柳長安，鄢小虎，劉春陽，等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法［J］.電子學(xué)報，2011，39(5): 1220 -1224.LIU Chang-an，YAN Xiao-hu，LIU Chun-yang，et al.Dynamic path planning for mobile robot based on improved ant colony optimization algorithm［J］.Acta Electronica Sinica，2011，39(5): 1220 -1224.(in Chinese)

［13］Chen W N，Zhang J.Ant colony optimization for software project scheduling and staffing with an event-based scheduler［J］.IEEE Transactions on Software Engineering，2013，39(1): 1 -17.

［14］Dorigo M，Gambardella L M.Ant colony system: A cooperative learning approach to the traveling salesman problem［J］.IEEE Transactions on Evolutionary Computation，1997，1(1): 53 -66.

［15］Merkle D，Middendorf M，Schmeck H.Ant colony optimization for resource-constrained project scheduling［J］.IEEE Transactions on Evolutionary Computation，2002，6(4): 333 -346.

［16］Dorigo M，Birattari M.Ant colony optimization［A］.Encyclopedia of Machine Learning［M］.US: Springer，2010.36-39.

李琳女，1988年出生于湖北隨州，武漢大學(xué)博士生，主要研究方向為面向服務(wù)的軟件開發(fā)、云計算、智能算法.

E-mail: linl2012@ whu.edu.cn

應(yīng)時(通訊作者)男，1965年出生，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向為軟件工程中的智能分析與優(yōu)化、軟件工程的形式化理論與方法、云計算與軟件服務(wù)、大數(shù)據(jù)的處理與智能分析.

Deployment Optimization of Service-Oriented Software Based on Ant Colony Algorithm

LI Lin，YING Shi，ZHAO Chong，DONG Bo
(1.State Key Lab of Software Engineering，Wuhan University，Wuhan，Hubei 430072，China; 2.Computer School，Wuhan University，Wuhan，Hubei 430072，China)

Abstract:The deployment optimization of service-oriented software is well known to be NP hard.In this paper，a software deployment optimization model is built for improving the performance of service-oriented software，and an Ant Colony Algorithm for Deployment Optimization(ACO-DO)is designed to solve it so that the near-optimal solutions can be obtained quickly.The algorithm improves ant colony algorithm by designing a heuristic based on the considered problem，optimizing the orders of constructing deployment solutions and adding a local search procedure.A series of instances with different sizes are tested and analyzed.The experimental results show that the designed ACO-DO algorithm performs better than the existing Mixed Integer Linear Programming，ant colony and genetic algorithms.

Key words:service-oriented software; deployment optimization; ant colony algorithm; performance

作者簡介

基金項目:國家自然科學(xué)基金(No.61373038，No.61070012);國家863高技術(shù)研究發(fā)展計劃(No.2012AA011204-01)

收稿日期:2014-09-25;修回日期: 2015-03-12;責(zé)任編輯:孫瑤

DOI:電子學(xué)報URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.018

中圖分類號：TP311

文獻標(biāo)識碼：A

文章編號：0372-2112(2016)01-0123-07