基于混合算法的云制造資源配置研究

李貽婷

基于混合算法的云制造資源配置研究

李貽婷

（南京信息工程大學(xué)，江蘇 南京 210044）

針對云環(huán)境下制造資源優(yōu)化配置模型求解問題，提出一種在花朵授粉算法基礎(chǔ)上引入遺傳算法和模擬退火算法的混合算法。首先，在花朵授粉算法的基礎(chǔ)上引入遺傳算法，用于前期種群初始化；然后，在迭代過程中加入模擬退火算法，避免陷入局部最優(yōu)；最后，使用該混合算法求解實際問題，驗證該算法處理資源配置問題的有效性和準確性。

云制造；資源配置；花朵授粉算法；遺傳算法；模擬退火算法

0 引言

云制造資源配置是在云環(huán)境下實現(xiàn)資源合理高效地配置[1-2]。資源配置可以解決制造資源與制造能力不均衡帶來的資源閑置、資源短缺、制造能力不足、制造能力過剩等問題。建立資源模型是實現(xiàn)資源合理配置的重要環(huán)節(jié)。文獻[3]構(gòu)建雙層規(guī)劃數(shù)學(xué)模型，并采用改進的多目標遺傳算法對模型求解，實現(xiàn)云制造資源優(yōu)化配置；文獻[4]利用遺傳算法和蟻群算法相結(jié)合的混合算法解決云制造資源調(diào)度；文獻[5]結(jié)合遺傳算法和分層序列法的優(yōu)勢，提出一種遺傳分層序列多目標決策方法；文獻[6]使用改進的布谷鳥算法解決資源配置問題，利用自適應(yīng)性調(diào)整部分參數(shù)和Levy飛行步長，采用模擬退火思想防止陷入局部最優(yōu)；文獻[7]使用改進的鯨魚優(yōu)化算法，引入編碼解碼方式和慣性權(quán)重對資源模型進行求解。以上文獻中的算法大都存在易早熟、局部搜索能力弱、過分依賴參數(shù)設(shè)置等問題。本文根據(jù)文獻[8-10]，提出一種在花朵授粉算法基礎(chǔ)上引入遺傳算法和模擬退火算法的混合算法，并應(yīng)用于求解資源模型，為云環(huán)境下制造資源合理配置提供一種新的解決方案。

1 問題描述

云平臺接受不同產(chǎn)品的訂單并將其匯總統(tǒng)計，通過資源配置將制造資源分配給合適的服務(wù)商，為用戶提供便捷高效的服務(wù)[11]。云制造模式的評價體系主要由時間、成本、質(zhì)量和服務(wù)組成[12]。資源配置也圍繞這4個指標進行。

如現(xiàn)有訂單需求加工一套設(shè)備，客戶將設(shè)備制造需求上傳到云平臺，云平臺進行信息加工處理后，對制造這套設(shè)備的各個資源配置進行建模。假設(shè)制造這套設(shè)備可以分解為項分任務(wù)，那么任務(wù)集合為

GeneralTask = {Task|= 1, 2, ... ,}

其中，Task為總?cè)蝿?wù)中第項分任務(wù)。

每項分任務(wù)都有多個候選資源，假設(shè)Task有m個候選資源，可表示為

TaskResources= {Resources|= 1, 2, ... ,m}

其中，Resources為第項分任務(wù)對應(yīng)的第個制造資源。

2 建立資源配置模型

根據(jù)客戶提出的任務(wù)需求，以時間、成本、質(zhì)量和服務(wù)這4個指標模型作為求解優(yōu)化目標。

完成任務(wù)的總時間為

完成任務(wù)的總成本為

加工產(chǎn)品總質(zhì)量為

加工產(chǎn)品總服務(wù)反饋為

式中：

由于4個指標之間的量綱不同，將它們都化為成本型指標即求解最小化目標函數(shù)，則總目標函數(shù)為

約束條件：

約束條件公式(6)～(10)即任務(wù)要求不超過最大任務(wù)加工時間和加工成本，不低于最小任務(wù)加工質(zhì)量和服務(wù)反饋。各個權(quán)重和為1。

3 求解資源配置模型

3.1 編碼

花朵授粉算法由英國劍橋?qū)W者YANG提出，基本思想來源于對自然界花朵自花授粉、異花授粉的模擬，前者對應(yīng)局部搜索，后者對應(yīng)全局搜索。在花朵授粉算法中，花粉位置對應(yīng)資源序號，采取實數(shù)編碼方式，個體位置元素在[0,1]之間選取，假設(shè)有8項分任務(wù)，則編碼方案如表1所示。

表1 編碼方案

用輪盤賭解碼的方式將個體位置元素轉(zhuǎn)換成資源序號。如任務(wù)1有4個地區(qū)可以選取資源，默認這4個地區(qū)的適應(yīng)度相等。具體而言，當個體位置元素落入（0，1/4）區(qū)間時表示選擇第一個地區(qū)資源；當個體位置元素落入（1/4，2/4）區(qū)間時表示選擇第二個地區(qū)資源，以此類推直到所有任務(wù)選取完資源。表1中個體位置元素所對應(yīng)的資源序號是（1，2，1，2，2，3，1，1）。

3.2 混合算法

混合算法是在花朵授粉算法的基礎(chǔ)上，通過引入遺傳算法和模擬退火算法進行改進?；ǘ涫诜鬯惴ú捎眠z傳算法初始化種群，將得到的較優(yōu)解代替花朵授粉算法隨機產(chǎn)生的初始解，使花朵授粉算法后續(xù)迭代更容易找到最優(yōu)解。同時，引入模擬退火算法，避免算法陷入局部最優(yōu)?；旌纤惴ㄓ?個步驟。

1）初始化種群和各參數(shù)。使用遺傳算法對初始種群進行優(yōu)化，并輸出最后一次迭代種群。

2）將導(dǎo)入花朵授粉算法，并用代替花朵授粉算法中的初始解。

3）比較適應(yīng)度值大小，選出最優(yōu)解和最優(yōu)值。

4）根據(jù)轉(zhuǎn)換概率的大小選擇自花授粉還是異花授粉，如果轉(zhuǎn)換概率> rand，則進行異花授粉，即全局授粉，按公式(11)更新。

電容器的擊穿故障很容易發(fā)現(xiàn)，但是當并聯(lián)多個元件時，很難確定具體的故障分量。電容器的開路故障可以通過將相同類型和容量的電容器與檢測到的電容器并聯(lián)以觀察電路功能是否恢復(fù)來確定。電容和電參數(shù)變化的檢測比較麻煩。一般可按下列方法進行。首先，電容器的一根引線應(yīng)該從電路板上移除，以避免周圍部件的影響。其次，根據(jù)電容器的不同情況，采用不同的方法進行檢查：

式中：

式中：

如果轉(zhuǎn)換概率< rand，則進行自花授粉，即局部授粉，按公式(13)更新。

式中：

5）計算并比較適應(yīng)度值大小擇優(yōu)，根據(jù)接受概率公式(14)保留隨機解。

6）判斷是否滿足結(jié)束條件，若不滿足跳到步驟4）；若滿足，退出程序并輸出最優(yōu)解和最優(yōu)值。

混合算法流程圖如圖1所示。

圖1 混合算法流程圖

4 實例分析

根據(jù)參考文獻[13]，某型號齒輪加工可分解為8項任務(wù)，每項任務(wù)都需要對應(yīng)的加工設(shè)備。通過云平臺搜索所有符合該任務(wù)的加工設(shè)備資源，并以時間少、成本低和高質(zhì)量為目標配置資源方案。加工設(shè)備資源分布表如表2所示。設(shè)定最終交付地為E，區(qū)域之間的運輸時間和費用關(guān)系如表3所示。

表2 加工設(shè)備資源分布表

表3 時間成本表

使用層次分析法得到時間、成本、質(zhì)量、服務(wù)的權(quán)重系數(shù)分別為1= 0.171 5，2= 0.230 4，3= 0.506 2，4= 0.091 9。把表1、表2的數(shù)據(jù)代入公式(1)～(4)，可分別得到max= 16 550、max= 3 890、min= 42、min= 45。

采用傳統(tǒng)遺傳算法、花朵授粉算法、混合算法分別求解目標函數(shù)。

傳統(tǒng)遺傳算法（GA）：染色體長度為8，種群規(guī)模為30，交叉概率= 0.5，= 0.2，迭代次數(shù)為200。

花朵授粉算法（FPA）：位置緯度為8，種群規(guī)模為30，轉(zhuǎn)換概率為0.8，迭代次數(shù)為200。

混合算法（AFPA）：位置緯度為8，種群規(guī)模為30，轉(zhuǎn)換概率為0.8，迭代次數(shù)為200，交叉概率= 0.5，= 0.2，退火方式Q+1=αQ，初始溫度= 500，其中冷卻系數(shù)取0.5。

3種算法適應(yīng)度曲線變化圖如圖2所示。

圖2 3種算法適應(yīng)度曲線變化圖

圖2中，由于混合算法前期采用遺傳算法進行初始化，因此收斂速度明顯高于花朵授粉算法；引入模擬退火算法，在后期步長較短的情況下，避免陷入局部最優(yōu)，快速找到最優(yōu)解；混合算法得到最優(yōu)配置的資源序號是（3,1,2,2,4,3,2,3），即立車3→自動車床1→搖臂鉆床2→銑齒機2→圓弧倒角機4→立磨3→研磨2→配對機3。

5 結(jié)語

本文使用混合算法求解云制造資源配置模型。通過實例求解，將混合算法與傳統(tǒng)遺傳算法、花朵授粉算法進行分析比較，驗證了混合算法的有效性。

[1] 蘇凱凱.云制造環(huán)境下的制造資源優(yōu)化配置方法研究[D]. 北京:北京交通大學(xué),2017.

[2] 侯紹波.云制造模式下制造資源優(yōu)化配置研究[D].天津:天津理工大學(xué),2017.

[3] 殷亮,周臨震,劉德仿,等.面向云制造資源的優(yōu)化配置方法研究[J].組合機床與自動化加工技術(shù),2018(12):155-160.

[4] 邰麗君,胡如夫,趙韓,等.面向云制造服務(wù)的制造資源多目標動態(tài)優(yōu)化調(diào)度[J].中國機械工程,2013,24(12):1616-1622.

[5] 汪勇,徐瓊,張凌,等.基于遺傳分層序列法的云制造資源優(yōu)化配置[J].統(tǒng)計與決策,2016(20):80-83.

[6] 楊喜娟,楊博,武福.基于改進自適應(yīng)布谷鳥算法的云制造資源配置優(yōu)化研究[J].制造技術(shù)與機床,2018(5):137-142.

[7] 吳書強,欒飛.基于改進型鯨魚算法的云制造資源配置研究[J].制造業(yè)自動化,2019,41(12):95-98,124.

[8] 竇學(xué).花朵授粉算法及其改進方法研究[D].阜新:遼寧工程技術(shù)大學(xué),2016.

[9] 肖輝輝,萬常選,段艷明.一種改進的新型元啟發(fā)式花朵授粉算法[J].計算機應(yīng)用研究,2016,33(1):126-131.

[10] 高新勤,荊彥臻,杜景霏.基于改進型遺傳算法的制造資源優(yōu)化配置方法研究[J].制造業(yè)自動化,2017,39(11):99-104.

[11] ZHANG Q, QI D Y. Service-oriented collaborative design platform for cloud manufacturing [J]. Journal of South China University of Technology (Natural Science Edition), 2011,39 (12):75-81.

[12] 王藝霖,胡艷娟,朱非凡,等.云制造資源優(yōu)化配置研究綜述[J].制造技術(shù)與機床,2017(11):36-42.

[13] 易建亮,陳志廣,肖儂,等.基于代理的并行文件系統(tǒng)元數(shù)據(jù)優(yōu)化與實現(xiàn)[J].計算機研究與發(fā)展,2018,55(2):438-446.

Research on Resource Allocation of Cloud Manufacturing Based on Hybrid Algorithm

LI Yiting

(Nanjing University of Information Technology, Nanjing 210000, China)

An improved flower pollination algorithm is proposed for the solution of the optimal allocation model of manufacturing resources in the cloud environment. On the basis of the basic flower pollination algorithm, other algorithms are introduced—the genetic algorithm is used in the initial population initialization part, and the simulated annealing algorithm is added in the iterative process to avoid falling into the local optimum. Finally, the algorithm is used to solve actual problems, and the effectiveness and accuracy of the algorithm in dealing with resource allocation problems are verified.

cloud manufacturing; resource allocation; flower pollination algorithm; genetic algorithm; simulated annealing algorithm

TH166；TP391

A

1674-2605(2022)02-0007-05

10.3969/j.issn.1674-2605.2022.02.007

李貽婷，女，1996年生，碩士研究生，主要研究方向：智能優(yōu)化算法的改進及應(yīng)用、資源配置。E-mail：2697090317@qq.com

李貽婷.基于混合算法的云制造資源配置研究[J].自動化與信息工程,2022,43(2):41-44,48.

LI Yiting. Research on resource allocation of cloud manufacturing based on hybrid algorithm[J]. Automation & Information Engineering, 2022,43(2):41-44,48.