摘 要：云制造環(huán)境下，云平臺(tái)以制造服務(wù)組合的形式為個(gè)性化需求提供按需服務(wù)，可顯著提升訂單響應(yīng)速度與提高資源利用率。采用哈里斯鷹算法構(gòu)建制造服務(wù)組合，針對(duì)制造服務(wù)間物流轉(zhuǎn)運(yùn)問題，建立獨(dú)特的編碼與解碼機(jī)制。為解決該算法存在早熟收斂問題，引入Logistic一維混沌系統(tǒng)，設(shè)計(jì)非線性逃逸能量更新機(jī)制和3種鄰域搜索策略。通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)后的哈里斯鷹算法在解決云制造服務(wù)組合優(yōu)化問題時(shí)具有顯著優(yōu)越性。

關(guān)鍵詞：云制造；服務(wù)組合；哈里斯鷹算法；任務(wù)調(diào)度

中圖分類號(hào)：TH164文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1671-5276（2024）03-0127-05

Research on Cloud Manufacturing Service Composition Method Based on

Improved Harris Hawks Optimization Algorithm

Abstract：In cloud manufacturing environment， the cloud platform provides on-demand services for personalized needs in the form of manufacturing service composition， which can significantly improve order response speed and resource utilization. This paper uses Harris Hawks optimization algorithm to construct manufacturing service composition， and establishes a unique coding and decoding mechanism for the logistics transfer between manufacturing services. In order to solve the premature convergence problem of the algorithm， the Logistic one-dimensional chaotic system is introduced， the nonlinear escape energy updating mechanism and three types of neighborhood search strategies are designed. Experiments verify the significant advantages of the improved Harris Hawk algorithm in solving the cloud manufacturing service portfolio optimization problem.

Keywords：cloud manufacturing; service composition; Harris Hawks optimization algorithm; task scheduling

0 引言

制造業(yè)技術(shù)的不斷突破推動(dòng)了智能制造領(lǐng)域的蓬勃發(fā)展。為解決產(chǎn)能過剩并提高分布式制造資源的利用率，制造服務(wù)優(yōu)化配置問題受到了密切關(guān)注。

目前針對(duì)制造服務(wù)優(yōu)化配置問題已經(jīng)有很多研究成果。DAO等［1］針對(duì)多企業(yè)的協(xié)同生產(chǎn)問題進(jìn)行深入研究，提出一種獨(dú)特的遺傳算法，使得求解效率大幅提高。AKBARIPOUR等［2］針對(duì)分布式制造資源之間的物流問題對(duì)服務(wù)質(zhì)量的影響進(jìn)行充分研究，提出一種混合整數(shù)規(guī)劃模型。WANG等［3］在制造服務(wù)異常的情況下提出了一種新的編碼形式，可以對(duì)制造服務(wù)的異常情況進(jìn)行動(dòng)態(tài)重構(gòu)。ZHANG等［4］提出了制造社區(qū)的概念與一種基于多目標(biāo)優(yōu)化的制造服務(wù)選擇和組合方法。LIANG等［5］提出一種基于深度強(qiáng)化學(xué)習(xí)算法的QoS-aware云制造服務(wù)組合優(yōu)化方法，規(guī)避了元啟發(fā)式算法參數(shù)設(shè)置復(fù)雜的問題。王平等［6］提出一種基于雙層規(guī)劃模型的資源服務(wù)組合方法并采用云遺傳算法對(duì)模型進(jìn)行求解。

目前大多數(shù)的優(yōu)化配置模型對(duì)多個(gè)任務(wù)與多個(gè)子任務(wù)進(jìn)行求解的較少。為此，本文提出一種基于改進(jìn)哈里斯鷹算法，提高了全局的搜索能力，以最小化加工成本為目標(biāo)，解決了分布式制造服務(wù)優(yōu)化配置的問題。

1 制造服務(wù)優(yōu)化配置問題分析

在云制造環(huán)境中，接受訂單的主體企業(yè)會(huì)將一部分訂單需求分配給合適的制造商，以減輕自己的生產(chǎn)壓力。因此需要在滿足制造任務(wù)要求的情況下，選取合適的制造商和合適的物流線路，使得所有任務(wù)的完工總成本最小，具體的問題研究模型如圖1所示。

為了能夠更加直觀地描述這一模型，現(xiàn)對(duì)該模型進(jìn)行如下假設(shè)：

1）每個(gè)制造任務(wù)的不同制造子任務(wù)在不同制造商可以并行加工，不同制造任務(wù)的總裝任務(wù)也可以在主體企業(yè)并行完成。

2）不同的制造商與制造商之間，制造商與主體企業(yè)之間只有一次運(yùn)輸。

3）貨物運(yùn)輸時(shí)運(yùn)載能力為無窮大，同時(shí)貨物都可以在一次運(yùn)輸?shù)倪^程中完成。

基于以上假設(shè)，本文建立以最小化成本為目標(biāo)函數(shù)的模型，目標(biāo)函數(shù)如下所示。

F=CM+CT（1）

式中：CM表示不同制造商的制造成本；CT表示在整個(gè)生產(chǎn)過程中由于物流而產(chǎn)生的成本。

式（1）表示所有任務(wù)的制造成本包括制造商和主體企業(yè)的制造成本兩部分；式（2）表示制造商的制造成本包括所有制造商的制造任務(wù)成本總和；式（3）表示物流成本包括制造商之間的物流成本（式（4））和運(yùn)輸?shù)街黧w企業(yè)之間的物流成本（式（5））兩部分。式中符號(hào)的描述如表1所示。

2 制造服務(wù)優(yōu)化配置問題模型求解

2.1 編碼與解碼

本文主要考慮3個(gè)問題：多個(gè)制造任務(wù)、制造商的選擇和物流方式的選擇，因此種群編碼也與這3部分有關(guān)，如圖2所示。

圖2中制造任務(wù)由制造任務(wù)數(shù)目與制造任務(wù)子任務(wù)的數(shù)目有關(guān)。深色序列的上半部分表示制造子任務(wù)序列，深色序列的下半部分表示制造子任務(wù)的制造商。物流運(yùn)輸選擇包括物流節(jié)點(diǎn)序列和物流節(jié)點(diǎn)決策變量兩個(gè)部分。物流部分的上方表示物流節(jié)點(diǎn)序列，其具體的節(jié)點(diǎn)序列與制造子任務(wù)序列有關(guān)，主要滿足以下規(guī)則：

1）運(yùn)輸節(jié)點(diǎn)序列中有意義數(shù)目與第一部分的不重復(fù)制造商節(jié)點(diǎn)數(shù)有關(guān)；

2）運(yùn)輸節(jié)點(diǎn)序列的順序與第一部分制造商節(jié)點(diǎn)的序列順序相同。

轉(zhuǎn)化后得到的物流部分編碼如圖3所示，無色部分無意義。深色上方序列表示運(yùn)輸節(jié)點(diǎn)序列，深色下方序列表示對(duì)應(yīng)節(jié)點(diǎn)的決策變量。

決策變量的解析主要滿足以下規(guī)則：

①具有相同的決策變量的運(yùn)輸節(jié)點(diǎn)在同一次運(yùn)輸過程中；

②不同的運(yùn)輸節(jié)點(diǎn)在同一個(gè)運(yùn)輸過程中，則物流路線總是從左側(cè)向右側(cè)運(yùn)輸；

③所有運(yùn)輸線路的終點(diǎn)都是主體企業(yè)；

④如果沒有相同的決策變量，則該制造商完成任務(wù)后直接運(yùn)輸?shù)街黧w企業(yè)。

根據(jù)以上規(guī)則，可以得出5條物流線路，其中4條分別是3號(hào)、5號(hào)、10號(hào)、6號(hào)直接運(yùn)輸?shù)街黧w企業(yè)；第5條物流線路是4號(hào)，首先運(yùn)輸?shù)?號(hào)然后再運(yùn)輸?shù)街黧w企業(yè)。

2.2 種群初始化

為了使算法的初始解具有更強(qiáng)的全局搜索能力，引入一維logistic混沌系統(tǒng)，如式（6）所示。

x（i+1）=μ×x（i）×（1－x（i））（6）

初始化流程如下（圖4）。

1）生成小數(shù)序列：隨機(jī)生成范圍為（0，1）的28個(gè)混沌個(gè)體與種群的28個(gè)維度相對(duì)應(yīng)，完成第一步初始化。

2）整數(shù)化：取得的28個(gè)混沌個(gè)體，擴(kuò)大10倍，并向上取整得到整數(shù)序列。

3）物流編碼處理：在整數(shù)序列中，前18位是制造商選擇部分，后10位是物流部分。將制造商選擇部分在不改變順序的情況下，除去重復(fù)的制造商，得到運(yùn)輸節(jié)點(diǎn)序列。

2.3 種群更新策略

本文提出MHHO（Multi-HHO）算法，在HHO算法的基礎(chǔ)上通過改進(jìn)逃逸能量更新策略和增加鄰域搜索策略兩種方式，增加算法的全局搜索能力，改進(jìn)后的HHO算法（MHHO）流程如圖5所示。

搜索階段如式（7）和式（8）所示，在開始階段，HHO算法會(huì)根據(jù)初始種群，在可行解空間內(nèi)進(jìn)行搜索。

式中：x（t）和x（t+1）分別表示本次迭代和下一次迭代過程中哈里斯鷹的位置向量；xm（t）表示本次迭代中哈里斯鷹種群的平均位置；xrand（t）是獵物的位置；r1、r2、r3、r4和q是區(qū)間（0，1）中的隨機(jī)數(shù)；UB、LB分別表示變量的上限和下限；xrand是當(dāng)前種群中隨機(jī)選擇的哈里斯鷹的位置；N表示種群數(shù)量。

由圖5可以看出，開發(fā)階段較為復(fù)雜，HHO算法會(huì)根據(jù)獵物的捕捉概率r和獵物的逃逸能量E兩部分確定哈里斯鷹的迭代點(diǎn)位。逃逸能量的更新如式（9）所示。

E=2×（1－t/T）×E0（9）

式中：E表示獵物的逃逸能量；E0表示區(qū)間（-1，1）的隨機(jī)數(shù)；t表示當(dāng)前的迭代次數(shù)；T表示算法預(yù)設(shè)的最大迭代次數(shù)。當(dāng)|E|≥0.5時(shí)表示有較多的逃逸能量。r≥0.5表示在本次捕獵中，獵物最終被追捕?；谶@兩個(gè)參數(shù)，在這個(gè)階段包括4種迭代策略。

1）軟圍攻：當(dāng)|E|≥0.5和r≥0.5時(shí)，如式（10）所示。

X（t+1）=Xrabbit（t）－X（t）－E|JXrabbit（t）－X（t）| （10）

式中J=2（1-r5）表示獵物嘗試逃離時(shí)的能量強(qiáng)度，其中r5（0，1）是一個(gè)隨機(jī)數(shù)。

2）硬圍攻：當(dāng)|E|＜0.5和r≥0.5時(shí)，如式（11）所示。

X（t+1）=Xrabbit－EXrabbit（t）－X（t）（11）

3）漸進(jìn)式軟圍攻： |E|≥0.5和r＜0.5，如式（12）所示。

式中：D表示種群的維度；S表示一個(gè)隨機(jī)個(gè)體；LF的Levy飛行函數(shù)；表示更優(yōu)。

4）漸進(jìn)式硬圍攻：當(dāng)|E|＜0.5和r＜0.5時(shí)，如式（13）所示。

5）逃逸能量更新策略

文中通過使用一種非線性逃逸能量更新策略，其逃逸能量更新如式（14）所示，曲線如圖6所示。

由圖6可以看出，改進(jìn)的逃逸能量曲線中在120次迭代左右依然有一定的概率進(jìn)入搜索階段，能夠在全局的范圍內(nèi)搜索更優(yōu)的可行解，大大提高了算法的全局搜索能力。

6）鄰域搜索策略

鄰域搜索通過不同種群個(gè)體進(jìn)行交叉、置換等操作，尋找該個(gè)體附近的優(yōu)秀編碼。在本算法中主要包括3種鄰域搜索策略：

策略1，隨機(jī)選擇1個(gè)個(gè)體，隨機(jī)選擇某個(gè)位置，將該位置的編碼重新生成；

策略2，隨機(jī)選擇2個(gè)個(gè)體，隨機(jī)選擇2個(gè)位置，將2個(gè)位置之間的編碼交換；

策略3，隨機(jī)選擇2個(gè)個(gè)體，隨機(jī)選擇位置，將指定位置的編碼進(jìn)行交換。

3 仿真驗(yàn)證與分析

3.1 算法設(shè)計(jì)

文中設(shè)計(jì)的制造服務(wù)優(yōu)化配置仿真實(shí)驗(yàn)包括3種情況：制造規(guī)模為3×10、4×10、5×10，表示制造任務(wù)數(shù)目分別為3、4、5個(gè)，制造商的數(shù)目為10個(gè)。其中制造任務(wù)1—5的生產(chǎn)周期分別為27 d、26 d、25 d、26 d和28 d。

3.2 仿真結(jié)果分析

為了驗(yàn)證文中MHHO算法的優(yōu)越性，將相同的問題與HHO、PSO（particle swarm optimization）、NSGA-Ⅱ（non-dominated sorting genetic algorithm-II）4種算法在上述仿真環(huán)境中進(jìn)行比較。仿真實(shí)驗(yàn)利用MATLAB2021a進(jìn)行程序編寫，運(yùn)行環(huán)境為Win10系統(tǒng)，2.6GHz，16G內(nèi)存。每個(gè)算法的種群規(guī)模為100，迭代次數(shù)選定為200次。收斂曲線對(duì)比如圖7—圖9所示。

從圖7—圖9中可以看出，MHHO算法具有最低的最小化成本，在不陷入局部收斂的情況下，具有最快的收斂速度。同時(shí)，由于引入Logistic一維混沌系統(tǒng)，MHHO算法在初始具有最低的適應(yīng)度。MHHO算法的中期乃至后期都具有一定的搜索能力，并沒有出現(xiàn)局部收斂的問題。

將上述算法重復(fù)運(yùn)行30次，最優(yōu)解、平均解、平均收斂次數(shù)和平均求解時(shí)間等結(jié)果如表2所示。不同制造規(guī)模下MHHO算法都可以獲得更高質(zhì)量的最優(yōu)解和平均解。在平均收斂次數(shù)方面，MHHO算法稍劣于HHO和PSO，但是有效避免了陷入局部最優(yōu)的問題。相較于NSGA-Ⅱ，MHHO算法的平均收斂次數(shù)更低，最優(yōu)解與平均解的質(zhì)量更高。MHHO算法的平均求解時(shí)間最長。但隨著制造任務(wù)數(shù)量的增多，平均求解時(shí)間與其他算法的差距越來越小。

4 結(jié)語

針對(duì)分布式制造服務(wù)優(yōu)化配置問題，文中從制造任務(wù)數(shù)目、制造商選擇和物流方案三方面進(jìn)行研究，建立優(yōu)化目標(biāo)模型，設(shè)計(jì)獨(dú)特的編碼與解碼方式。針對(duì)HHO算法全局搜索能力差的問題，從種群初始化、逃逸能量更新和鄰域搜索3個(gè)角度進(jìn)行改進(jìn)。最后，通過不同規(guī)模制造任務(wù)的案例，驗(yàn)證了MHHO算法在求解質(zhì)量、收斂速度方面的有效性和優(yōu)越性。同時(shí)隨著制造規(guī)模的增加，MHHO算法將具有更強(qiáng)的優(yōu)勢(shì)。

參考文獻(xiàn)：

［1］ DAO S D，ABHARY K，MARIAN R. An innovative GA for optimisation of integrated manufacturing-transportation scheduling in VCIM systems［J］. Operational Research，2020，20（3）：1289-1320.

［2］ AKBARIPOUR H，HOUSHMAND M. Service composition and optimal selection in cloud manufacturing：Landscape analysis and optimization by a hybrid imperialist competitive and local search algorithm［J］. Neural Computing and Applications，2020，32（15）：10873-10894.

［3］ WANG Y， WANGS， KANG L， et al. An effective dynamic service composition reconfiguration approach when service exceptions occur in real-life cloud manufacturing［J］. Robotics and Computer-Integrated Manufacturing，2021，71：102143.

［4］ ZHANG Y，TANG D B，ZHU H H，et al. A flexible configuration method of distributed manufacturing resources in the context of social manufacturing［J］. Computers in Industry，2021，132：103511.

［5］ LIANG H， WEN X， LIU Y， et al. Logistics-involved QoS-aware service composition in cloud manufacturing with deep reinforcement learning［J］. Robotics and Computer-Integrated Manufacturing，2021，67：101991.

［6］ 王平，肖涵，潘燕華. 基于雙層規(guī)劃的云制造資源服務(wù)組合［J］. 計(jì)算機(jī)集成制造系統(tǒng)，2022，28（1）：51-58.