基于改進自適應(yīng)布谷鳥算法的云制造資源配置優(yōu)化研究*

楊喜娟 楊 博 武 福

(①蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070; ②蘭州交通大學(xué)機電工程學(xué)院，甘肅 蘭州 730070)

云制造資源配置優(yōu)化問題是實現(xiàn)云制造智能化、高效化的關(guān)鍵問題。資源配置的優(yōu)化可以解決目前大多數(shù)制造企業(yè)存在的資源閑置、能耗巨大、產(chǎn)能過剩等問題，改善制造業(yè)困境，提高服務(wù)質(zhì)量和效率[1-3]。近年來，圍繞云制造資源配置優(yōu)化的研究熱點主要集中在：①評價指標的研究；②服務(wù)評價綜合方法的研究；③求解資源優(yōu)化模型的方法研究。例如：文獻[2]用基于灰色關(guān)聯(lián)度分析的優(yōu)選分析方法探討了資源優(yōu)化組合的求解過程；文獻[4]基于模糊層次分析法建立了制造資源評價模型；文獻[5]針對制造云服務(wù)組合問題建立模型并利用改進遺傳算法求解；文獻[6]采用改進的進化多目標算法對云制造資源配置雙層規(guī)劃模型進行求解；文獻[7]提出用離散型粒子群遺傳混合算法對云制造配置模型進行求解。但是，遺傳算法參數(shù)多、收斂速度較慢、會產(chǎn)生大量冗余迭代；粒子群算法易早熟、易陷入局部最優(yōu)，搜索質(zhì)量不高；蟻群算法收斂速度慢、易停滯、易陷入局部最優(yōu)。因此需要更為簡單、可靠、高效的算法求解資源配置優(yōu)化問題。

基本布谷鳥搜索算法(CS)是2009年由劍橋大學(xué)Yang等學(xué)者提出的一種新的全局優(yōu)化啟發(fā)式算法，它主要模擬自然界布谷鳥飛行以及寄生行為，通過Levy飛行機制尋找寄主鳥窩，即更新每代解實現(xiàn)全局搜索，再經(jīng)過Biased隨機游走方式淘汰并改善部分解，以達到局部搜索最優(yōu)的目的。布谷鳥算法具有參數(shù)少、全局搜索能力強、不易陷入局部最優(yōu)、魯棒性好、通用性強、簡單高效、易操作等顯著優(yōu)勢，目前廣泛用于解決函數(shù)優(yōu)化、資源調(diào)度、工程結(jié)構(gòu)優(yōu)化、TSP等諸多問題中[8-9]。但是，基本布谷鳥算法也存在一些缺陷，例如：搜索后期收斂速度較慢、缺少活力等。因此有許多學(xué)者除了對算法的步長、參數(shù)和發(fā)現(xiàn)概率做積極改進之外，還在與其他算法相耦合方面不斷研究創(chuàng)新。文獻[10]提出的布谷鳥搜索增強算法采用逐維評價策略接收部分進化個體，增強算法的求精能力和收斂速度；文獻[11]引入動態(tài)慣性權(quán)重改進解的更新方式，依據(jù)動態(tài)慣性權(quán)重值保留上代鳥窩的最優(yōu)位置，并進行下一代位置更新，從而有效平衡種群探索能力和開發(fā)能力之間的關(guān)系；文獻[12]提出基于粒子群算法的布谷鳥搜索算法，進一步提高布谷鳥算法的求解精度和收斂速度；文獻[13]提出一種基于適應(yīng)值分配的自適應(yīng)步長和發(fā)現(xiàn)概率的布谷鳥搜索算法，提高了算法的計算精度；文獻[14]將混沌理論引入布谷鳥搜索算法，使混沌特性與基本布谷鳥算法相結(jié)合，進一步提高了布谷鳥算法性能。

針對其他啟發(fā)式算法易早熟、易陷入局部最優(yōu)、收斂質(zhì)量不高等問題，本文提出了一種改進自適應(yīng)布谷鳥搜索算法，并將其應(yīng)用于云制造資源配置模型的求解中，為云制造資源優(yōu)化配置提供了新的思路。

1 問題描述與模型建立

云制造資源配置優(yōu)化問題描述如下：一客戶企業(yè)在云制造平臺定制生產(chǎn)一套電氣設(shè)備，當客戶將制造需求和約束條件上傳至云制造平臺后，平臺首先將此套電氣設(shè)備生產(chǎn)任務(wù)視為總?cè)蝿?wù)J，并將其分解為n項生產(chǎn)分任務(wù),可以表示為N1,N2,N3,…,Nn,接著云制造平臺會從資源庫中搜索并收集滿足客戶需求的資源，每項分任務(wù)對應(yīng)若干個資源，可分別表示為N1M1,N1M2,N1M3,…,N2M1,N2M2,N2M3,…,NnMm，如果無合適資源，則客戶應(yīng)當修改約束條件進行重新搜索，最后云制造平臺將根據(jù)各資源的性能參數(shù)，運用資源精選數(shù)學(xué)模型予以計算，求得滿足客戶要求的最優(yōu)資源服務(wù)鏈。

資源精選數(shù)學(xué)模型主要由體現(xiàn)生產(chǎn)高效性的總時間值T、表現(xiàn)資源經(jīng)濟性的總成本值C、反映資源可靠性的總質(zhì)量值Q、體現(xiàn)服務(wù)高效性與準確性的總管理值M以及折射客戶資源滿意度和信任度的總反饋值F五項評價指標構(gòu)成。在將五項指標代入精選數(shù)學(xué)模型計算之前還需要對數(shù)據(jù)進行相應(yīng)處理：

步驟1 因為各指標間計量單位和數(shù)量級都不同，不能直接進行綜合分析，所以需要對指標數(shù)據(jù)去量綱化處理。方法是均值法：E=H/h，其中H為各指標參數(shù)，h表示所有備選資源每項指標的平均值。

步驟2T、C是成本型指標，必須轉(zhuǎn)化為效益型指標，方法是E0=Emax-E，其中Emax表示客戶允許的最大總時間T和最大總成本C。

步驟3 將效益型指標Q、M和F定量化處理，如表1所示，其中2、4、6、8 表示中間值。

表1 定量化賦值標準

為了簡化問題，從以上五指標出發(fā)，運用線性規(guī)劃法建立的最優(yōu)資源精選數(shù)學(xué)模型如下:

(1)

(2)

(3)

(4)

(5)

總目標函數(shù)：maxZ=w1T0+w2C0+w3Q+w4M+w5F

(6)

數(shù)學(xué)模型中：φij∈{0,1}為決策因子，當φij=1時，表示第i個子任務(wù)由第j個資源參與制造，否則φij=0；當δ=0時，表示分任務(wù)Ni對應(yīng)的制造資源Mj與分任務(wù)Ni+1對應(yīng)的制造資源Mq之間存在著信息流，δ=1時，兩者間存在著物料流；q表示第i+1個子任務(wù)中的第q個服務(wù)資源；n代表共有n種生產(chǎn)分任務(wù)；mi代表第i項分任務(wù)對應(yīng)符合要求的資源有m種；t(ij)代表分任務(wù)Ni對應(yīng)制造資源Mj所需加工時間；t(ij,(i+1)q)代表分任務(wù)Ni中第j個資源和分任務(wù)Ni+1中第q個資源的連接時間；c(ij)代表分任務(wù)Ni對應(yīng)制造資源Mj所需加工成本；c(ij,(i+1)q)代表分任務(wù)Ni中第j個資源和分任務(wù)Mi+1中第q個資源的連接成本；qj(i)代表分任務(wù)Ni對應(yīng)資源Mj的制造質(zhì)量合格值；mj(i)代表分任務(wù)Ni對應(yīng)資源Mj的服務(wù)管理值；fj(i)代表分任務(wù)Ni對應(yīng)資源Mj的動態(tài)反饋值。Tmax、Cmax、Qmin、Mmin、Fmin分別為反映客戶底線要求的最后總時間、最大總成本、最差平均質(zhì)量、最差平均管理和最差平均反饋值。完成整個過程的最長時間要小于等于客戶允許的最后時間；所需的成本要小于等于客戶給定的最大成本；質(zhì)量均值必須大于等于客戶的最差質(zhì)量要求；管理均值必須大于等于客戶的最差管理要求；反饋度均值必須大于等于客戶的最差反饋要求。此外，w1、w2、w3、w4、w5分別表示時間、成本、質(zhì)量、管理及反饋的權(quán)重值，且w1+w2+w3+w4+w5=1，各權(quán)重值計算過程如下：

步驟1 通過對評價指標間重要性的定量比較，建立出判斷矩陣A，A中的元素為aij(i，j=1,2,3,4,5)，指標重要性量化如表2所示。

步驟2 利用公式xij=aij/(a1j+a2j+a3j+a4j+a5j)對矩陣A中的元素aij進行處理，其中xij(i，j=1,2,3,4,5)表示處理后的元素。

步驟3 根據(jù)公式wi=xij/5再對矩陣A進行歸一化處理，其中wi(i=1,2,3,4,5)表示計算得到的權(quán)重值。

表2 指標重要性量化

2 改進算法的優(yōu)化原理

布谷鳥算法是由Yang Xinshe和Deb Suash在2009年提出的一種新的啟發(fā)式算法，它根據(jù)自然界鳥類或果蠅飛行規(guī)律，模擬布谷鳥寄生育雛的策略，提出兩個核心算法組件：Levy飛行和Biased隨機游走。在Levy Flights隨機游走中，每一代種群里的每個個體Xi分別以當代最優(yōu)個體Xbest為導(dǎo)向，搜索新的個體Xi+1,飛行步長滿足Levy分布，更新公式為：

(7)

其中：α0為比例因子，通常取0.01；β為常數(shù)，通常取1.5；u、v為滿足正態(tài)分布的隨機數(shù)，另外：

(8)

其中：Γ表示伽馬方程。

在Biased隨機游走中一般設(shè)定發(fā)現(xiàn)概率Pa為0.25，當縮放因子r∈[0,1]小于Pa時，保留原解；當縮放因子r大于Pa時，則根據(jù)Biased游走公式重新生成相同數(shù)量的新解。具體更新公式如下：

Xi=Xi+r(Xj-Xk)

(9)

基本布谷鳥算法具體運算流程如圖1所示。

改進自適應(yīng)布谷鳥算法(SAACS)是在基本布谷鳥算法(CS)的基礎(chǔ)上通過自適應(yīng)調(diào)整部分參數(shù)，加入雙向搜索策略，并引入模擬退火算法的思想后得到的，具體流程如圖2所示，其具體改進有以下幾個方面：

其一，在Levy Flights隨機游走尋找新解過程中的步長越大，全局搜索得到的解多樣性增加，搜索速度加快，更容易靠近最優(yōu)解，但是搜索精度會相應(yīng)降低；而步長越小，更有利于局部搜索，搜索精度得到提高，但是搜索速度變緩。因此，應(yīng)該令比例因子α0和常數(shù)β隨著迭代次數(shù)以及適應(yīng)度質(zhì)量自適應(yīng)調(diào)整，使運算過程在迭代初期、適應(yīng)度值較差的情況下擴大搜索范圍，增強全局搜索的能力，增加解的多樣性，而在迭代后期縮小搜索范圍達到精確搜索的目的。具體調(diào)整如下：

其中：n表示種群大??；αmax表示比例因子最大值；αmin表示比例因子最小值；βmax表示β最大值；βmin表示β最小值；σ1、σ2分別代表正態(tài)分布的方差；u代表正態(tài)分布的均值；t表示當前迭代次數(shù)；T表示迭代總次數(shù)；fi表示適應(yīng)度值。

其二，在Biased隨機游走過程中，將縮放因子r的取值范圍由[0,1]調(diào)整為[-1,1]，令單項搜索轉(zhuǎn)換為雙向搜索，在一定程度上保持了群體的多樣性，引導(dǎo)搜索過程向最優(yōu)解逼近，增強局部搜索效率，加快搜索最優(yōu)解速度。

其三，將模擬退火思想引入改進算法中。經(jīng)過Biased隨機游走得到新解之后，計算新解的適應(yīng)度值，并在適應(yīng)度擇優(yōu)后保留較優(yōu)解，而到迭代后期步長變?yōu)楹苄〉那闆r下，計算陷入局部最優(yōu)的風(fēng)險較大，因此對于淘汰解可用min(1,e-Δf/T)≤rand[0,1]進行隨機保留，隨著迭代次數(shù)增加，溫度降低，接受淘汰解的概率逐漸變大，可以在每次迭代后增加種群的多樣性，避免陷入局部循環(huán)。

3 改進算法的實現(xiàn)

類似于資源調(diào)度等離散型問題，在運用改進自適應(yīng)布谷鳥算法時，應(yīng)該對各項任務(wù)相應(yīng)資源構(gòu)成的組合方案進行編碼，如：對資源N1M3、資源N2M1、資源N3M4、資源N4M2、資源N5M1、資源N6M2、資源N7M1、資源N8M3組成的方案編碼為(3,1,4,2,1,2,1,3)。改進后的自適應(yīng)布谷鳥算法(SAACS)應(yīng)用于求解云制造資源配置優(yōu)化的數(shù)學(xué)模型中。運算步驟如下所示：

步驟1 對各項分任務(wù)相應(yīng)資源構(gòu)成的組合方案進行編碼，設(shè)定退火溫度Q等一系列參數(shù)值。

步驟2 隨機初始生成n個鳥巢，即n個資源組合方案。

步驟3 將初始種群中生成的每個資源組合解全部解碼，檢驗各組合方案是否滿足式(6)中的約束條件，并根據(jù)處理后的參數(shù)計算出各自函數(shù)值，作為初始適應(yīng)度值。

步驟4 根據(jù)Levy飛行在初始種群基礎(chǔ)上生成新的解，其中參數(shù)β和步長α采用自適應(yīng)方式。

步驟5 根據(jù)被發(fā)現(xiàn)概率pa，運用雙向搜索策略搜索新解以替換舊解，并檢驗新種群中每個資源組合是否滿足式(6)中的約束條件。

步驟6 計算得到每種資源組合的適應(yīng)度值，在進行適應(yīng)度擇優(yōu)后得到較優(yōu)解，對于其他解則用min(1,e-Δf/T)≤rand進行隨機保留。

步驟7 判斷是否符合循環(huán)終止條件，如果不符合跳轉(zhuǎn)步驟4。

步驟8 若符合終止條件，則再次計算得到每種資源組合的適應(yīng)度值，選擇出適應(yīng)度最小的解，即可得到最優(yōu)資源組合以及最大函數(shù)值。

4 實驗分析

現(xiàn)以某公司需要的智能通信配電設(shè)備生產(chǎn)為問題的實際應(yīng)用場景，將可以互相替代并可以移動的活動生產(chǎn)工位封裝成制造云服務(wù)，在全部零部件生產(chǎn)中挑選部分核心零部件為代表進行試驗。仿真試驗環(huán)境為2.20 GHz Pc,2 G內(nèi)存，Windows7 64位操作系統(tǒng)，Matlab R2012b。

依據(jù)文獻[15]的算例模型，客戶將制造任務(wù)提交云制造服務(wù)平臺后，制造任務(wù)主要被分為配電柜生產(chǎn)和機柜生產(chǎn)兩項任務(wù)，其中配電柜包含門、頂?shù)装宓壬a(chǎn)分任務(wù)，而機柜包括隔板、內(nèi)立柱等生產(chǎn)分任務(wù)。具體加工任務(wù)分解如表3所示。

表3 加工任務(wù)分解

平臺接受任務(wù)后首先立即在資源庫中進行“資源匹配”，建立出符合生產(chǎn)需求的初選資源集，如表4所示。

表4 各資源的量化

接著根據(jù)客戶按實際需求列出指標重要性判斷矩陣A：

經(jīng)過計算并歸一化處理后，得到矩陣A中的各指標權(quán)重值如表5所示,這5個權(quán)重值分別對應(yīng)(6)式中的w1,w2,w3,w4,w5。

表5 式(6)中的各個權(quán)重值

實驗一 算法有效性驗證

根據(jù)表4中各資源去量綱、指標轉(zhuǎn)化后的參數(shù)，分別利用基本布谷鳥算法(CS)、自適應(yīng)布谷鳥算法(ACS)[13]以及改進自適應(yīng)布谷鳥算法(SAACS)對資源配置優(yōu)化精選模型進行求解。設(shè)定初始種群數(shù)為n=30，全局迭代次數(shù)iteration=200，發(fā)現(xiàn)鳥窩的概率pa=0.25，函數(shù)參數(shù)個數(shù)nd=8，比例因子最大值αmax為0.5，比例因子最小值αmin為0.05，βmax為1.8，βmin為0.8，σ1、σ2分別為0.3和0.005，初始溫度Q=500，退溫方式為：Qt+1=aQt，其中冷卻系數(shù)a取0.5，Qt為第t次迭代的溫度，Tmax=45.12,Cmax=3944,Qmin=6，Mmin=5，F(xiàn)min=5。經(jīng)過MATLAB運算后，適應(yīng)度值變化曲線如圖3所示。

從圖3可以看出大約30代以后種群適應(yīng)度值趨于穩(wěn)定。最終得到的最小適應(yīng)度值為0.1864，總目標函數(shù)最大值maxZ為5.3648，對應(yīng)最優(yōu)資源組合方案為：資源N1M3、資源N2M3、資源N3M4、資源N4M3、資源N5M1、資源N6M3、資源N7M2、資源N8M2，完成總?cè)蝿?wù)的總時間為34.44h，完成總?cè)蝿?wù)的總成本為2 821元。實驗充分證明：改進自適應(yīng)布谷鳥算法在求解云制造資源配置模型方面是可行有效的。

實驗二 算法準確度驗證

根據(jù)表4中各資源去量綱、指標轉(zhuǎn)化后的參數(shù)，在相同種群規(guī)模n=50、相同迭代次數(shù)iteration=200和相同問題規(guī)模nd=8的情況下，分別運用基本布谷鳥算法(CS)、自適應(yīng)布谷鳥算法(ACS)[13]及改進自適應(yīng)布谷鳥算法(SAACS)對精選數(shù)學(xué)模型進行100次求解實驗，對比探究新算法求解的準確度，結(jié)果如表6所示。

表6 3種算法的計算準確度與收斂所需迭代次數(shù)對比

從表6對比結(jié)果可以看出，SAACS求解準確率明顯高于另外兩種算法，并且在相同條件下，SAACS的迭代次數(shù)更少于其他算法。因此，改進自適應(yīng)布谷鳥算法在求解云制造資源配置模型的準確度方面更符合要求。

實驗三 算法效率驗證

根據(jù)表4中各資源去量綱、指標轉(zhuǎn)化后的參數(shù)，在不同種群規(guī)模、不同迭代次數(shù)和擴大問題規(guī)模的情況下運用改進自適應(yīng)布谷鳥算法對精選數(shù)學(xué)模型進行求解，探究新算法的求解效率，結(jié)果如表7所示。

表7 SAACS運算時間

表7中運行時間單位為“秒(s)”，各種情況下每項實驗做十次取平均值，問題規(guī)模nd擴大部分的參數(shù)依據(jù)N1Mj(j=1,2,3)和N2Mj(j=1,2,3,4)。從表7中可以體現(xiàn)出隨著種群規(guī)模、問題規(guī)模和迭代次數(shù)的單方面變化，SAACS運算時間基本也成線性變化，另外還進一步表明改進自適應(yīng)布谷鳥算法在求解各種規(guī)模問題上的可行性和高效性。

5 結(jié)語

本文以基本布谷鳥算法為基礎(chǔ)，通過自適應(yīng)調(diào)整步長、動態(tài)調(diào)整參數(shù)，應(yīng)用雙向搜索策略和模擬退火思想，提出了改進自適應(yīng)布谷鳥算法(SAACS)，并將該算法運用于求解云制造資源配置優(yōu)化模型中。經(jīng)過實驗證明，新算法不僅是有效、可行的，而且在求解效率和準確度方面都優(yōu)于同類算法。改進自適應(yīng)布谷鳥算法為云制造環(huán)境下最優(yōu)資源服務(wù)鏈的快速獲得提供了一種新的思路和方法。

[1] 胡艷娟,武理哲，張霖，等.云制造服務(wù)評價理論與方法研究綜述[J].計算機集成制造系統(tǒng)，2017，23(3):640-649.

[2]尹超,張云，鐘婷.面向新產(chǎn)品開發(fā)的云制造服務(wù)資源組合優(yōu)選模型[J].計算機集成制造系統(tǒng)，2012，18(7):1368-1378.

[3] Zhang L,Luo Y,Li BH,et al. Cloud manufacturing: a new manufacturing paradigm[J]. Enterprise Information Systems，2014,8(2): 167-187

[4]張元龍,屠建飛,謝文東.基于模糊層次分析法的云制造資源評價[J].機械制造，2015，53(6):49-52.

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

[6] 蘇凱凱，徐文勝，李建勇.云制造環(huán)境下基于雙層規(guī)劃的資源優(yōu)化配制方法[J].計算機集成制造系統(tǒng)，2015，21(7):1941-1952.

[7]武善玉,張平,覮李方.云制造系統(tǒng)中基于粒子群優(yōu)化的多任務(wù)調(diào)度[J].華南理工大學(xué)學(xué)報，2015，1(43):105-110.

[8]蘭少峰,劉升.布谷鳥搜索算法研究綜述[J].計算機工程與設(shè)計，2015，(4):1063-1067.

[9]李志平,王 勇,張呈志.云模型的布谷鳥搜索算法[J].計算機應(yīng)用研究,2016.(1):93-97.

[10]林要華，王維.基于逐維策略的布谷鳥搜索增強算法[J].計算機工程與科學(xué)，2017，39(1):165-172.

[11]周歡，李煜.具有動態(tài)慣性權(quán)重的布谷鳥搜索算法[J].智能系統(tǒng)學(xué)報，2015(4):645-651.

[12]李娜，賀興時.基于粒子群算法的布谷鳥搜索算法[J].紡織高?；A(chǔ)科學(xué)學(xué)報，2014(3):374-379.

[13]彭建新,詹志輝,陳宗淦，等.自適應(yīng)步長和發(fā)現(xiàn)概率的布谷鳥搜索算法[J].濟南大學(xué)學(xué)報：自然科學(xué)版，2016，30(5):328-333.

[14] GaiGe Wang,S Tab.AH Gandow,et al. Chaotic cuckoo search[J]. Soft Comput，2016,20(9):3349-3362.

[15]王時龍,宋文艷，康玲，等.云制造環(huán)境下的制造資源優(yōu)化配置研究[J].計算機集成制造系統(tǒng)，2012，18(7)1:396-1405.