基于離散人工群算法的云制造服務組合

常瑞云,周井泉,許 斌,亓 晉

(1.南京郵電大學 電子科學與工程學院，江蘇 南京 210003；2.南京郵電大學 物聯網學院，江蘇 南京 210003)

基于離散人工群算法的云制造服務組合

常瑞云1,周井泉1,許 斌2,亓 晉2

(1.南京郵電大學 電子科學與工程學院，江蘇 南京 210003；2.南京郵電大學 物聯網學院，江蘇 南京 210003)

隨著互聯網、云計算等網絡技術的快速發展，單一制造服務已無法滿足用戶日益復雜的制造任務，所以云制造服務組合問題一直是近年來應用和研究的熱點，為典型NP難題。文中針對云制造服務組合優選問題，改進原始人工蜂群算法(Artificial Bee Colony,ABC)，提出了一種基于局部搜索離散蜂群算法(Location Search Discrete Artificial Bee Colony,LSDABC)，從而為用戶選擇服務質量(Quality of Service,QoS)最優的服務組合執行路徑。該算法引入種群的選擇概率和對最優解的局部搜索策略，提升算法的開采能力、收斂速度，同時避免出現搜索停滯陷入局部最優。最后將LSDABC應用于云制造服務組合優選中進行仿真實驗，并將結果與原始ABC、DE、PSO算法進行對比。實驗結果表明，LSDABC具有較好的求解質量和魯棒性。

云制造服務組合；ABC算法；LSDABC算法；QoS；局部搜索

1 概 述

21世紀是一個全球化合作、競爭、共贏的新時代，我國制造企業向服務型轉換是大勢所趨。隨著互聯網技術特別是云計算技術的發展，應用中出現越來越多功能相似或相同的服務，組合這些功能單一的服務，使其高效完成復雜制造任務已成為應用熱點。云制造[1]中用戶利用網絡和云制造平臺，根據自身需求調用位于不同位置的服務資源或能力，完成制造任務。云制造服務組合[2]克服地理位置上的障礙，將分散的制造資源通過云制造系統集中管理，當用戶有需要時通過云服務中心對制造服務及資源進行調用。所以，如何針對用戶的制造任務，構建滿足各項需求和約束條件且整體QoS最優的組合云服務執行路徑，是云制造服務環節中必需解決的關鍵問題。

QoS是當前普遍采用的評價組合服務優劣的指標。基于QoS的服務組合[3]建模是從非功能屬性角度來評價云服務的質量，通常從云制造服務的成本(Cost,C)、時間(Time,T)、可靠性(Reliability,Rel)、滿意度(Satisfaction,Sa)、可用性(Availability,A)、信譽度(Trust,Tr)、可維護度(Maintainability,Ma)等幾個方面來描述。基于QoS的服務組合問題是一個帶有QoS約束的多目標服務組合優化問題。

近年來研究者已經開發和改進了一些智能算法來解決這些NP難的組合優化問題。例如，向峰[4]提出了基于群領導算法(GLA)的多目標優化算法，解決了基于能耗及QoS的多目標云制造資源服務組合優化問題；鄭偉針對人工蜂群在組合優化當中的應用進行研究，并以0-1背包問題對智能算法在組合優化當中的應用進行仿真測試[5]；劉衛寧等[6]針對云制造系統中云服務組合優化中多目標優化問題進行建模、分析、求解，利用改進的自適應粒子群算法實現組合優化中的多目標規劃問題；敬石開等[7]提出一種離散粒子群智能優化算法，保證在惡意服務占比較高時，算法也能保持較高的服務可靠性；陶飛等[8]開發了一種基于并行自適應混沌優化與反射遷移(PC-PACO-RM)的并行算法，針對于云制造服務組合不規則、大規模的優化空間，獲得云制造中資源分享的高效策略；Xia等[9]提出了多信息動態更新的蟻群優化算法，用以適應當服務失效或QoS改變的情況。

綜上所述，利用智能優化算法解決云制造服務組合優選問題是一種非常有應用價值的研究思路。文中用適應度值表述組合服務的QoS，通過引入種群選擇概率和對最優解的局部搜索策略，提出一種基于局部搜索的離散人工蜂群算法，并將其應用于云制造服務組合優選問題中。

實驗結果表明，該算法的求解速度和求解質量都優于原始ABC、PSO、DE算法。

2 問題描述與相關定義

云制造服務的模型如圖1所示。在云制造環境中，服務提供方將自身富余的資源(如知識、數據、制造設備、計算設備、軟件工具等)通過計算機系統、物聯網等進行虛擬化，之后再將這些資源進行服務化封裝，發布到云制造平臺上；然后，服務請求方通過選擇、組合云制造平臺中的云服務，構建滿足生產制造任務需求的云制造服務組合。

圖1 云制造服務模型

2.1 制造云服務組合描述

云制造服務組合的具體過程如圖2所示。從服務請求方提交任務到滿足需求，要經歷三個階段，即分解任務、為子任務搜索并匹配子服務、候選服務組合及組合路徑優選。

圖2 云制造服務組合的具體過程

2.2 云制造服務組合QoS評估模型

從服務組合方法和工作流基本模式[10-12]來看，服務組合執行路徑(Composite Service Execution Paths,CSEP)的生成是一個面向服務的工作流，基本結構包含序列模式、并行模式、選擇模式和循環模式。而在服務組合中，其他三種模式都要轉化為序列模式進行服務質量評價。因此文中將在序列模式下，從云制造服務特點、QoS參數重要程度和可度量的角度出發，主要考慮成本、執行時間、能耗和可靠度，建立云制造服務QoS模型：QoS={時間，成本，能耗，可靠度}={T,C,E，Rel}。并用式(1)來評估CSEP的QoS。

其中，α,β,γ,φ分別表示相應的參量(時間、花費、能耗、可靠性)的權重，且α+β+γ+φ=1。

求解最優路徑的數學模型為：

3 算法描述

3.1 基本人工蜂群算法

人工蜂群[13-14](Artificial Bee Colony,ABC)算法是模擬蜂群內部分工和覓食行為的一種較為新穎的群體智能算法。目的是讓蜂群中各種類蜂更好地進行協作，從而實現蜜蜂采蜜量的最大化，即找到優化問題的最優解。在該智能行為中，蜂群分為引領蜂、跟隨蜂和偵查蜂三類，蜜源的位置代表優化問題的潛在解，花蜜的豐富程度代表解的質量即適應度。蜂群完成一次迭代分為3步:

(1)引領蜂對當前蜜源按式(2)進行鄰域搜索，并選擇蜜源較為豐富的目標。

vij=xij+r(xij-xkj)

(2)

式中，xij，xkj表示種群中的兩個蜜源；vij是新產生的蜜源。

(2)跟隨蜂根據引領蜂分享的信息，按式(3)計算的概率選擇蜜源并進行鄰域搜索，保留較好蜜源信息。

(3)

式中，fiti是個體i的適應度值。

(3)如果經過limit次搜索之后，蜜源的質量仍未提高，則該雇傭蜂將變成偵察蜂，按式(4)尋找新的蜜源。

xij=lb+r(ub-lb)

(4)

其中，r是(-1,1)中的隨機數；ub，lb是種群蜜源的上下限；xij是隨機產生的新個體。

3.2 改進人工蜂群算法

在ABC中，影響優化效果的關鍵是算法的局部“開采”與全局“探測”。而原始ABC算法局部搜索中，跟隨蜂根據式(3)的概率選擇蜜源，較差蜜源幾乎得不到更新，種群多樣性無法保障，同時在全局搜索中，對當前找到的最優解沒有充分開發，使得蜂群接近最優蜜源時搜索效率明顯下降，從而算法的收斂速度變得很慢。

3.2.1 基于種群的概率選擇

原始ABC算法中，概率選擇僅依據適應度值，使得包含有用信息但適應度值較差的超常個體易被淘汰，而這些漏選的信息將會直接影響算法的全局收斂能力。而基于種群的方法選擇蜜源進行更新，不考慮目標函數值，保持了種群多樣性。位于第k位蜜源的個體按式(5)計算被選概率，這種基于種群的概率選擇，使得較差蜜源被選擇的概率增加，避免超常個體對選擇過程的負面影響。

(5)

其中，a(t)為自適應參數；Max_cycle最大迭代次數。

進化前期，設置較小的a(t)值來保證種群多樣性；進化后期，個體差異變小，為避免陷入局部最優，出現搜索停滯狀態，a(t)的值應較大。

3.2.2 局部搜索策略

為解決ABC算法“開采”能力差的問題，現引進局部搜索算子對當前最優解進行鄰域搜索，使其快速找到最優蜜源。同時，原始ABC算法中的搜索算子每次只改變一個變量，而局部搜索算子可以同時改變多個變量，這樣的搜索方式能夠有效加快算法的收斂速度。

局部搜索算法的執行步驟如下：

Step1：參數設置。局部搜索迭代E次，初始搜索步長α0，局部搜索迭代計數器epoch=0,k=0,xcurrent=xbest；

Step2：迭代計數器n=0；

Step3：生成隨機向量dx，且-αk≤dx≤αk；

Step4：更新epoch，epoch=epoch+1；

Step5：fnew=f(xcurrent+dx)，若fnew≤fcurrent，則fbest=fnew，xbest=xcurrent+dx,n=n+1，轉Step7；

Step6：fnew=f(xcurrent-dx)，若fnew≤fbest，則fbest=fnew，xbest=xcurrent-dx,n=n+1，轉Step7；

Step7：如果n

Step8：k=k+1；

Step9:αk=αk-1×0.5；

Step10:如果epoch=E，則終止,否則轉Step2。

為了充分發揮局部搜索算子的開采能力，初始搜索步長α0與當前最優解的數量級應盡量保持一致。文中取α0=xbest，同時在每一次更新解之后，都要對新解進行判定，保證其在設定范圍之內。

3.3 LSDABC解決云制造服務組合問題

應用LSDABC算法求解云制造服務組合，首先是優化解與蜂群成員的映射，即蜂群的初始化。文中以序列模式為例進行實驗論證。目標函數用式(1)表示，函數值越小，證明該組解的QoS越好。

假設制造任務共包含n個子任務，每個子任務都對應m個候選服務數Sij(T,C,E,Rel)，i表示第i個子任務，j表示第j個子服務。蜂群的每個成員(解)代表一條服務組合路徑，用向量X=[x1,x2,…,xD]表示，其中解的序列組合的維度與組合問題中子任務數一致。如：服務組合路徑S16→S23→S31→S47→…→Sn4和S18→S24→S32→S49→…→Sn6，可以用X=[6,3,1,7,…,4]和X=[8,4,2,9,…,6]來表示解向量。

基于局部搜索離散人工蜂群算法首先設置相關參數，初始化種群產生新蜜源，利用式(1)計算每組蜜源的適應度值，記錄最好適應度值及對應蜜源，然后進入迭代。引領蜂根據式(2)去更新解，并對新解進行評估，然后用式(5)計算每個蜜源被選擇的概率，跟隨蜂依概率更新蜜源，并做出評估保留較好的，偵察蜂根據limit的值，即每次更新中解的變化情況，有選擇性地淘汰蜜源，并重新產生新蜜源，最后對得到的最優解利用局部搜索算子進行局部搜索，得到最優解。多次重復以上的迭代過程，找到最優解。

改進算法的具體步驟如下:

Step1：設置相關參數。引領蜂個數=跟隨蜂個數=SN，最大迭代次數maxCycle，控制參數limit。

Step2：隨機產生初始解集xij，i=1,2,…,SN;j=1,2,…,D，其中1≤xij≤100。

Step3：計算初始化蜜源的適應度。

Step4：引領蜂搜索新蜜源vi，計算其適應度。

Step5：如果新蜜源f(vi)≤f(xi)，則xi=vi;否則保留xi。

Step6：計算蜜源的選擇概率P。

Step7：跟隨蜂根據概率P選擇蜜源，搜索新蜜源vi，計算其適應度。

Step8：如果新蜜源f(vi)≤f(xi)，則xi=vi，否則保留xi。

Step9：記憶最優蜜源。

Step10：如果達到迭代間隔tstep，則利用局部搜索算子對當前最優位置進行局部搜索，更新最優位置。

Step11：判斷是否存在要放棄的蜜源，若存在，該處的引領蜂變為偵查蜂。

Step12：如果滿足終止條件，算法終止，輸出結果，否則轉步驟3。

4 實驗與分析

為驗證LSDABC對于解決云制造服務組合問題的有效性，選擇序列結構模型進行實驗，對該算法進行性能測試。文中以三個典型案例：10，20，30個子任務，作為實驗數據集，數據集中所有候選云服務QoS屬性的范圍均為[0.1,10]，采用隨機的方式生成。

實驗中，LSDABC算法參數設置：種群規模SN=100，最大迭次數maxCycle=100，算法運行次數runtime=100，limit=100，候選服務數據集是4維(響應時間、成本、能耗、可靠度)，且每個子任務均有相同數目的候選服務。服務組合優選中每項評價指標設置相同的權重，α=β=γ=φ=1/4。在滿足以上約束條件的情況下，仿真實驗，并與原始ABC、PSO、DE算法進行比較。記錄算法運行中的適應度平均值和標準差。

表1～3分別表示在任務數分別是10，20，30，候選服務數目在500～5 000中變化時，四種算法運行100次時最優解適應度值的平均值及方差。

表1 LSDABC算法在候選服務為500～5 000時解決10任務服務組合對應的均值和方差

表2 LSDABC算法在候選服務為500～5 000時解決20任務服務組合對應的均值和方差

表3 LSDABC算法在候選服務為500～5 000時解決30任務服務組合對應的均值和方差

從表中可以看出，LSDABC算法在候選服務數增加時，適應度值與其他算法之間的差距更加明顯，且方差變化不大；同時，當任務數增加時，LSDABC能兼備適應度值較好情況下，保持較好的穩定性。

圖3表示的是在統一每個子任務候選服務數為100的情況下，在任務數分別為10、20、30時，四種算法的平均適應度值隨迭代次數變化的趨勢。由圖可知，無論子任務數目是10、20或是30，改進算法的平均適應度值和穩定性均優于其他三種算法。

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

從數據分析可知，LSDABC算法在迭代前期，跟隨蜂基于種群概率對蜜源進行選擇性更新，保持種群多樣性，避免陷入局部優化；在迭代后期，對最優解周圍進行局部搜索，使其快速找到最優解。所以文中提出的LSDABC算法開采能力強、收斂速度快、魯棒性好，避免陷入局部最優，且對復雜問題的適應性較強。

5 結束語

文中基于服務組合QoS評估組合服務的好壞，并構建了云制造服務組合優化的QoS數學模型。通過基于種群的概率選擇及對最優解的局部搜索策略改進人工蜂群算法，提出具有更好收斂能力和全局搜索能力的基于局部搜索的離散人工蜂群算法來解決云制造服務組合問題。實驗仿真證實了LSDABC的有效性及可行性。然而，基于QoS的評估模型僅僅考慮了服務的技術指標，忽略了服務使用者的感受，因此仍有待改進。所以下一步的研究工作將集中于兼顧用戶體驗質量綜合考慮，優化云制造服務組合路徑。

[1] 李伯虎,張 霖,柴旭東.云制造概論[J].中興通訊技術,2010(4):5-8.

[2] 陶 飛,張 霖,郭 華,等.云制造特征及云服務組合關鍵問題研究[J].計算機集成制造系統,2011,17(3):477-486.

[3]XiangF,HuY,YuY,etal.QoSandenergyconsumptionawareservicecompositionandoptimal-selectionbasedonParetogroupleaderalgorithmincloudmanufacturingsystem[J].CentralEuropeanJournalofOperationsResearch,2014,22(4):663-685.

[4] 向 峰.云制造系統中基于能耗的服務組合關鍵技術研究[D].武漢:武漢理工大學,2013.

[5]HuoY,ZhuangY,GuJ,etal.Discretegbest-guidedartificialbeecolonyalgorithmforcloudservicecomposition[J].AppliedIntelligence,2015,42(4):661-678.

[6] 劉衛寧,李一鳴,劉 波.基于自適應粒子群算法的制造云服務組合研究[J].計算機應用,2012,32(10):2869-2874.

[7] 敬石開,姜 浩,許文婷,等.考慮執行可靠性的云制造服務組合算法[J].計算機輔助設計與圖形學學報,2014,26(3):392-400.

[8]TaoF,LaiLiY,XuL,etal.FC-PACO-RM:aparallelmethodforservicecompositionoptimal-selectionincloudmanufacturingsystem[J].IEEETransactionsonIndustrialInformatics,2013,9(4):2023-2033.

[9]XiaYM,ChengB,ChenJL,etal.Optimizingservicescompositionbasedonimprovedantcolonyalgorithm[J].JisuanjiXuebao(ChineseJournalofComputers),2012,35(2):270-281.

[10]FanY,ZhaoD,ZhangL,etal.Manufacturinggrid:needs,concept,andarchitecture[M]//Gridandcooperativecomputing.Brilin:Springer,2004:653-656.

[11]TaoF,HuYF,ZhouZ.Studyonmanufacturinggrid&itsresourceserviceoptimal-selectionsystem[J].TheInternationalJournalofAdvancedManufacturingTechnology,2008,37(9-10):1022-1041.

[12]TaoF,ZhaoD,HuY,etal.Resourceservicecompositionanditsoptimal-selectionbasedonparticleswarmoptimizationinmanufacturinggridsystem[J].IEEETransactionsonIndustrialInformatics,2008,4(4):315-327.

[13] 秦全德,程 適,李 麗,等.人工蜂群算法研究綜述[J].智能系統學報,2014,9(2):127-135.

[14] 張 平,劉三陽,朱明敏.基于人工蜂群算法的貝葉斯網絡結構學習[J].智能系統學報,2014,9(3):325-329.

Could Computing Service Composition Based on Discrete Artificial Bee Colony Algorithm

CHANG Rui-yun1,ZHOU Jing-quan1,XU Bin2,QI Jin2

(1.College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.College of Internet of Things,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

With the rapid development of network technology such as Internet,cloud computing and so on,single manufacturing service has already not satisfied the increasingly complex tasks for users.So,cloud manufacturing service composition,as a NP hard problem,has been the applied and research hotspot in recent years.As to service composition optimal selection,a Location Search Discrete Artificial Bee Colony (LSDABC) is proposed in this paper based on improvement of original ABC to provide the service composition execution path with optimal QoS for users.This algorithm introduces selection probability based on population and local search strategy to improve the exploitation ability and convergence speed and to avoid falling into local optimum.Finally,LSDABC is applied to the cloud manufacturing service composition.The experiment shows that the LSDABC has better quality and robustness compared with the original ABC,DE and PSO.

cloud manufacturing service composition;ABC;LSDABC;QoS;location search

2015-10-12

2016-01-19

時間：2016-05-25

國家自然科學基金資助項目(61401225)；中國博士后科學基金資助項目(2015M571790)

常瑞云(1992-)，女，碩士研究生，研究方向為云制造服務組合；周井泉，博士，教授，碩士生導師，研究方向為通信網絡的信息管理和控制。

http://www.cnki.net/kcms/detail/61.1450.TP.20160525.1711.072.html

TP301.6

A

1673-629X(2016)07-0177-06

10.3969/j.issn.1673-629X.2016.07.038