張嚴(yán)凱，周井泉，李 強(qiáng)

(南京郵電大學(xué) 電子科學(xué)與工程學(xué)院，江蘇 南京 210003)

0 引 言

隨著科技的進(jìn)步，制造業(yè)的規(guī)范更加標(biāo)準(zhǔn)和統(tǒng)一。很多復(fù)雜產(chǎn)品由一家廠商完成轉(zhuǎn)向由多家廠商合作完成，達(dá)到制造任務(wù)和資源的共享。廠商不再僅限于提供單一的產(chǎn)品或零件，而是轉(zhuǎn)而提供制造能力。制造商的制造能力通過網(wǎng)絡(luò)集合形成資源池，即傳統(tǒng)的制造模式轉(zhuǎn)變?yōu)樵浦圃臁?/p>

云制造是2010年開始出現(xiàn)的概念，綜合國內(nèi)外對云制造概念的闡述[1-2]，定義如下：云制造(Cloud Manufacturing)是一種基于互聯(lián)網(wǎng)的面向服務(wù)、效率高、功耗低的新型制造模式。用戶可以根據(jù)自己的需求動態(tài)調(diào)整制造資源。云制造平臺有多種容錯技術(shù)。單個物理節(jié)點發(fā)生故障，云制造平臺都會在后臺將制造轉(zhuǎn)移到其他的資源上繼續(xù)完成，因此云制造模式比傳統(tǒng)的制造模式更具有安全性和可靠性。

關(guān)于蟻群算法和云制造服務(wù)組合已有不少研究成果，例如陶飛等[3]對云制造服務(wù)組合建模、結(jié)果評估和組合優(yōu)選等問題進(jìn)行了研究和討論；敬石開等[4]以服務(wù)模型庫為基礎(chǔ)通過粒子群算法得到了較好的云制造服務(wù)組合模型；TRUNK等[5]基于采樣語義匹配查找服務(wù)組合，并通過遺傳算法(PSO)進(jìn)行服務(wù)組合優(yōu)化；劉衛(wèi)寧等[6]提出了一種采用全局策略選擇基礎(chǔ)服務(wù)進(jìn)行組合的方案；夏亞梅等[7]提出一種多信息素動態(tài)更新的蟻群算法(MPDACO)，可以更好得適應(yīng)動態(tài)QoS變化的情況。

在此基礎(chǔ)上，文中提出了一種動態(tài)參數(shù)蟻群算法，在一定程度上改善了算法的收斂速度，減小了陷入局部最優(yōu)解的概率。

1 問題描述

1.1 云制造服務(wù)組合

云制造是信息技術(shù)、制造技術(shù)、物聯(lián)網(wǎng)技術(shù)相互融合的產(chǎn)品。各地閑置的制造資源聚合到資源云池中，用戶向云制造平臺發(fā)送制造任務(wù)需求，云制造平臺通過服務(wù)組合優(yōu)選為用戶匹配最優(yōu)制造資源[8-9]。三者的關(guān)系如圖1所示。

圖1 云制造模式結(jié)構(gòu)關(guān)系

1.2 評價模型

QoS(Quality of Service)模型[10-11]是當(dāng)前使用最多的評價模型之一。文中的QoS包含四個方面，分別是成本C(Cost)、時間T(Time)、質(zhì)量函數(shù)Q(Quality function)、滿意度S(Satisfaction)。由此可見，QoS評價模型是多目標(biāo)優(yōu)化模型。評價函數(shù)如下：

(1)

2 云制造服務(wù)組合優(yōu)化算法

2.1 基于蟻群算法的云制造服務(wù)組合優(yōu)化算法

蟻群算法于1992年首先被意大利學(xué)者DORIGO M提出，是一種為復(fù)雜的優(yōu)化問題選最優(yōu)解的種群智能算法。它的基本思想是利用蟻群的合作通過路徑上的信息素來尋找最短路徑。蟻群算法已經(jīng)普遍應(yīng)用于組合優(yōu)化問題[12-15]。云制造服務(wù)組合優(yōu)化過程如圖2所示。原始的云制造任務(wù)被分解為n個子任務(wù)CMT(Cloud Manufacturing Task)，每一個任務(wù)表示為CMTi,i∈[1,n]。

圖2 云制造資源的服務(wù)傳遞過程

制造商提供的資源節(jié)點稱作CRSN(Cloud Resource Service Node)。每一個資源節(jié)點表示為CRSNij,i∈[1,n],j∈[1,m]。這些資源服務(wù)節(jié)點被動態(tài)地匹配給每一個子任務(wù)，每個子任務(wù)對應(yīng)的云制造資源被稱為CMR(Cloud Manufacturing Resource)，它們分別表示為CMRj,j∈[1,m]。Lij,(i+1)k表示螞蟻可能的轉(zhuǎn)移路徑，即每一個子任務(wù)對應(yīng)的最優(yōu)云制造資源。

原始蟻群算法的具體實現(xiàn)步驟如下：

Step2：將M只螞蟻放于起始位置，令k=0，k為第k只螞蟻。

Step3：迭代次數(shù)增加一次，Nc=Nc+1。

Step4：螞蟻數(shù)量增加1，k=k+1。

(2)

Step6：如果螞蟻的數(shù)量大于最大值M，則進(jìn)入Step7；否則進(jìn)入Step4。

Step7：根據(jù)式(3)～(5)更新每條線路上的信息素。

τij,pq(t+1)=ρ·τij,pq(t)+Δτij,pq(t)

(3)

(4)

(5)

其中,ρ(0<ρ<1)表示信息素殘留系數(shù)，用1-ρ表示信息素的揮發(fā)系數(shù)。

Step8：如果Nc大于最大迭代次數(shù)，則輸出最優(yōu)評價函數(shù)F及分配方案，結(jié)束循環(huán)；否則進(jìn)入Step3。

2.2 算法改進(jìn)策略

2.2.1 不同階段參數(shù)動態(tài)改變

該算法可分為前期、中期和后期三個階段，前期選擇較高的信息素殘留因子ρ，較小的期望啟發(fā)式因子β；中期適當(dāng)降低ρ的大小，適當(dāng)增大β；后期選擇較小的ρ，選擇較高的β。前期較高的ρ和較低的β保證了算法能夠有較好的全局搜索能力，很難陷入局部最優(yōu)解;后期較低的ρ和較高的β加快了算法的收斂速度，提高了算法效率。

2.2.2 加入特殊螞蟻

(6)

前期使用較多的特殊螞蟻能夠有效地跳出局部最優(yōu)解，有利于尋找到全局最優(yōu)解。

2.3 基于動態(tài)參數(shù)蟻群算法的云制造服務(wù)組合優(yōu)化算法

動態(tài)參數(shù)蟻群算法(DPACO)的具體步驟如下：

Step2:前期階段將M只常規(guī)螞蟻和S1個特殊螞蟻放在起始位置；中期階段將M只常規(guī)螞蟻和S2個特殊螞蟻放在起始位置，S2可取S1/2；后期階段將M只常規(guī)螞蟻放在起始位置，此時無特殊螞蟻。

Step3:迭代次數(shù)加1，Nc=Nc+1。

Step4:常規(guī)螞蟻開始搜索，根據(jù)式(2)確定狀態(tài)轉(zhuǎn)移概率。前期階段β=βlow，將β設(shè)為較小值，可取2；中期階段β=βmid，將β設(shè)為中間值，可取3；后期階段β=βhigh，將β設(shè)為較大值，可取5。此時為常規(guī)螞蟻，選擇概率較大的服務(wù)，將螞蟻移動到該服務(wù)下。

Step6:常規(guī)螞蟻和特殊螞蟻都搜索完成時，根據(jù)式(3)～(5)更新每條路徑上的信息素。前期階段ρ=ρlow，ρ設(shè)為較小值，可取0.1；信息素范圍τij(t)∈[τmin,τmax]。中期階段ρ=ρmid，ρ設(shè)為中間值，可取0.25；信息素范圍τij(t)∈[τmin,τmax]。后期階段ρ=ρhigh，ρ設(shè)為較大值，可取0.4；信息素范圍τij(t)∈[0,+]。

Step7:判斷迭代次數(shù)是否達(dá)到最大，若達(dá)到，進(jìn)入Step8，否則進(jìn)入Step3。

Step8:再進(jìn)行5次迭代，并記錄5次迭代的適應(yīng)度值，求出5次適應(yīng)度值的方差。

Step9:如果方差大于所設(shè)定的方差S2(S2趨于0)，進(jìn)入Step8，否則在后期階段則輸出優(yōu)選結(jié)果，在其他階段則進(jìn)入下一個階段。

3 實驗分析

通過一個鋼鐵制造企業(yè)的鋼鐵鍛造任務(wù)來驗證提出的基于動態(tài)參數(shù)的蟻群算法。由于任務(wù)需求和該企業(yè)自身能力的限制，此鍛造任務(wù)需要和其他企業(yè)合作完成。這個任務(wù)現(xiàn)在被分為5個子任務(wù)，即{CMT1,CMT2,CMT3,CMT4,CMT5}。每個子任務(wù)及對應(yīng)的制造資源如圖3所示。

圖3 鋼鐵鍛造任務(wù)云資源圖

使用的每一個制造資源都有對應(yīng)的成本、時間、質(zhì)量、滿意度，具體的數(shù)值見表1。

由表1可知，對于不同的參數(shù)值它們有不同的單位和數(shù)量級。為了方便數(shù)據(jù)處理，需要進(jìn)行歸一化，如下所示：

y=(x-min)/(max-min)

(7)

其中，y為歸一化后的新數(shù)據(jù)；x為原始數(shù)據(jù)；min、max分別表示此類參數(shù)的最小值和最大值。

歸一化后，使用不同的算法進(jìn)行求解。此次實驗的環(huán)境是宏基4750G，Intel(R) Core(TM) i5-2410M CPU 2.3 GHz主頻，軟件是MATLAB2014A，由經(jīng)驗設(shè)定初始參數(shù)M=20,α=1,β=5,ρ=0.4,P=20,w1=w2=0.2,w3=w4=0.3。不同算法的實驗結(jié)果見表2和圖4，從中可以看出DPACO比其他算法有更快的收斂速度，更好的穩(wěn)定性。

表1 云資源對應(yīng)的C、T、Q、S值

表2 不同算法的結(jié)果對比

圖4 不同算法的適應(yīng)度值對比

4 結(jié)束語

以基于成本C、時間T、質(zhì)量函數(shù)Q、滿意度S的QoS模型作為評價函數(shù)來評價改進(jìn)蟻群算法選擇結(jié)果的優(yōu)劣。提出的動態(tài)參數(shù)蟻群算法通過改變不同階段參數(shù)的值和加入特殊螞蟻等策略，改進(jìn)了收斂慢、易陷入局部最優(yōu)等缺點。通過實驗結(jié)果分析得知，改進(jìn)算法能夠有效地解決云制造服務(wù)組合問題，在效率上明顯優(yōu)于ACO、DE、PSO。下一步的研究工作將集中探索更高效率的群智能算法以解決服務(wù)組合問題。

[1] XU X.From cloud computing to cloud manufacturing[J].Robotics and Computer Integrated Manufacturing,2012,28(1):75-86.

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

[3] 陶 飛,張 霖，郭 華,等.云制造特征及云服務(wù)組合關(guān)鍵問題研究[J].計算機(jī)集成制造系統(tǒng),2011,17(3):477-486.

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

[5] TRUNK A.QoS-aware service composition:a survey[C]//Proceedings of the 8th IEEE European conference on web services.Washington D C,USA:IEEE,2010:67-74.

[6] 劉衛(wèi)寧，劉 波，孫棣華.面向多任務(wù)的制造云服務(wù)組合[J].計算機(jī)集成制造系統(tǒng)，2013,19(1):199-209.

[7] 夏亞梅，程 渤，陳俊亮,等.基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J].計算機(jī)學(xué)報,2012,35(2):270-281.

[8] 劉 波.云制造環(huán)境中面向多任務(wù)的服務(wù)組合與優(yōu)化技術(shù)研究[D].重慶:重慶大學(xué),2012.

[9] 常瑞云,周井泉,許 斌,等.基于離散人工群算法的云制造服務(wù)組合[J].計算機(jī)技術(shù)與發(fā)展,2016,26(7):177-182.

[10] 劉家良,孫俊麗,姜利群.一種面向云計算的QoS評價模型[J].電腦知識與技術(shù),2010,6(31):8801-8803.

[11] 齊 軒,劉茜萍.基于用戶偏好的可信QoS服務(wù)選擇方法[J].計算機(jī)技術(shù)與發(fā)展,2016,26(8):43-47.

[12] DORIGO M,GAMBARDELLA L M.Ant colonies for the travelling salesman problem[J].Biosystems,1997,43(2):73-81.

[13] BELL J E,MCMULLEN P R.Ant colony optimization techniques for the vehicle routing problem[J].Advanced Engineering Informatics,2004,18(1):41-48.

[14] MAIER H R.Ant colony optimization for design of water distribution systems[J].Journal of Water Resources Planning and Management,2003,129(3):200-209.

[15] MCMULLEN P R.An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives[J].Artificial Intelligence in Engineering,2001,15(3):309-317.