基于自我學(xué)習(xí)遺傳算法的云制造資源優(yōu)選*

宋士琳，趙 柱，薛 鵬，馬沁怡，周茂軍

(大連工業(yè)大學(xué)機(jī)械工程與自動(dòng)化學(xué)院，遼寧 大連 116034)

0 引言

近年來(lái)，制造業(yè)逐漸由傳統(tǒng)的線下交易模式轉(zhuǎn)向線上交易模式，在信息技術(shù)和物流業(yè)的發(fā)展推動(dòng)下，制造業(yè)傾向于開(kāi)始外包其制造活動(dòng)[1-2]。在此背景下，云制造(Cloud Manufacturing ,CMfg)作為新型網(wǎng)絡(luò)化制造模式和集成技術(shù)正逐漸興起，成為先進(jìn)制造的重要發(fā)展方向[3-4]。CMfg環(huán)境下，如何提高制造服務(wù)效率與縮短制造服務(wù)時(shí)間一直是云制造亟需解決的問(wèn)題[5]。通常借助各種智能算法來(lái)實(shí)現(xiàn)此類問(wèn)題的解決與優(yōu)化：文獻(xiàn)[6]基于一種用作局部搜索的近似動(dòng)態(tài)規(guī)劃的遺傳算法來(lái)解決動(dòng)態(tài)泊位分配問(wèn)題；文獻(xiàn)[7]提出了一種新型的鯨魚(yú)優(yōu)化算法來(lái)解決云制造資源配置問(wèn)題；文獻(xiàn)[8]提出一種改進(jìn)的帶有精英策略的快速非支配排序遺傳算法解決服務(wù)組合問(wèn)題；文獻(xiàn)[9]提出了一種高效的動(dòng)態(tài)蟻群遺傳混合算法，引入最優(yōu)融合評(píng)價(jià)策略和迭代閾值加以改進(jìn)。但上述文獻(xiàn)中的單一智能算法在解決局部搜索問(wèn)題上存在易陷入局部最優(yōu)解且容易出現(xiàn)早熟的缺點(diǎn)，影響算法本身的搜索效率[10]，求解過(guò)程適應(yīng)性不強(qiáng)，迭代求解過(guò)程的圖像過(guò)于單調(diào)且極易陷入局部最優(yōu)解，存在最優(yōu)個(gè)體在迭代過(guò)程中淘汰的缺點(diǎn)。針對(duì)解決此類問(wèn)題的特殊性，考慮到自我學(xué)習(xí)算法在解決全局優(yōu)化問(wèn)題上的特有優(yōu)勢(shì)，提出了基于Sarsa算法(一種自我學(xué)習(xí)算法)與遺傳算法(Genetic Algorithm,GA)動(dòng)態(tài)結(jié)合的算法對(duì)云制造資源優(yōu)選方案進(jìn)行動(dòng)態(tài)優(yōu)化的方法，通過(guò)建立以滿足資源提供者相關(guān)效益與資源需求者任務(wù)需求為目標(biāo)的數(shù)學(xué)模型，優(yōu)化出云制造資源的優(yōu)選方案，實(shí)現(xiàn)對(duì)總體完成時(shí)間的縮短以及云平臺(tái)總體制造效率的提高。

1 制造資源優(yōu)選數(shù)學(xué)建模

1.1 問(wèn)題描述

建立結(jié)合實(shí)際制造需要以尋求最優(yōu)配置的數(shù)學(xué)模型并通過(guò)建模求解與實(shí)例驗(yàn)證，并作如下假設(shè)：

(1)資源需求者的需求可分解為多個(gè)子任務(wù)。

(2)一個(gè)子任務(wù)的制造資源只能由一個(gè)資源提供者提供，每個(gè)資源提供者可同時(shí)處理多個(gè)子任務(wù)。

設(shè)n個(gè)資源需求者(Cus)的若干子任務(wù)(Tas)有l(wèi)個(gè)資源提供者(Sup)提供制造資源，相關(guān)參數(shù)及描述見(jiàn)表1。

表1 相關(guān)參數(shù)符號(hào)及描述

1.2 目標(biāo)函數(shù)

(1)時(shí)間成本目標(biāo)函數(shù)

制造服務(wù)的時(shí)間類別包括制造時(shí)間和運(yùn)輸時(shí)間，則時(shí)間函數(shù)[11]表示為：

(1)

式中,n為資源需求者數(shù)量，l為資源提供者數(shù)量，m為單個(gè)資源需求者的子任務(wù)數(shù)量，其中匹配資源提供者具有唯一性：

mat(sup,cus,tas)=1,0

(2)

式(2)表示若資源提供者sup與資源需求者cus的子任務(wù)tas相匹配，則mat(sup,cus,tas)=1，反之mat(sup,cus,tas)=0。

t(sup,cus,tas,1)=mt(sup,cus,tas)

(3)

t(sup,cus,tas,2)=tt(sup,cus,tas)

(4)

(2)資源提供者效率轉(zhuǎn)化函數(shù)

資源提供者效益轉(zhuǎn)化函數(shù)[12]表示為:

BR=

(5)

(3)整體目標(biāo)函數(shù)

為實(shí)現(xiàn)可接受條件下的多目標(biāo)要求，賦予各目標(biāo)不同的權(quán)值從而達(dá)到資源方案的非劣性平衡。此函數(shù)可表示為：

(6)

式中，ω1、ω2分別為時(shí)間函數(shù)和效益函數(shù)的權(quán)值,j=1,2,3...l。

1.3 約束條件

各子任務(wù)時(shí)間之和不超過(guò)該任務(wù)最大時(shí)間：

(7)

2 模型求解

2.1 染色體編碼

采用整數(shù)編碼，每個(gè)染色體表示待選任務(wù)的全部制造順序。染色體長(zhǎng)度為2 m。定義前半段為所有資源需求者編號(hào)，數(shù)量即表示子任務(wù)的數(shù)量；后半段表示前半段資源需求者的子任務(wù)對(duì)應(yīng)的資源提供者編號(hào)。

以某條染色體為例，見(jiàn)表2。

表2 染色體編碼

表2中列數(shù)表示該條染色體包含基因數(shù)，共18列，每一列表示一個(gè)基因。該條染色體個(gè)體表示4個(gè)資源需求者分別包含2,2,2,3個(gè)子任務(wù)在3個(gè)資源提供者進(jìn)行生產(chǎn)制造。

2.2 種群初始化

隨機(jī)生成N個(gè)初始染色體個(gè)體，這N個(gè)個(gè)體組成一個(gè)種群，以這N個(gè)個(gè)體構(gòu)成的種群作為初始種群，逐代進(jìn)化，設(shè)置t=0，最大進(jìn)化代數(shù)為gen。

2.3 適應(yīng)度值

適應(yīng)度函數(shù)值是評(píng)價(jià)個(gè)體優(yōu)劣的指標(biāo)[12]：

(8)

式中，常數(shù)c為保守估計(jì)值，視目標(biāo)函數(shù)而定，P表示整體目標(biāo)函數(shù)值。

2.4 選擇操作

采用輪盤(pán)賭的方式對(duì)個(gè)體進(jìn)行選擇。每個(gè)個(gè)體的適應(yīng)度值與整個(gè)種群中個(gè)體適應(yīng)度值和的比例決定進(jìn)入下一代的概率[13]：

x(i)=Fit(i)/∑Fit(t)

(9)

2.5 基于Sarsa算法自我學(xué)習(xí)的交叉和變異操作

設(shè)交叉率與變異率分別為Pc和Pm，Pc與Pm過(guò)大或過(guò)小都會(huì)對(duì)破壞種群，不利于解的收斂和最優(yōu)解的生成;本文設(shè)計(jì)了一種能夠根據(jù)迭代進(jìn)程進(jìn)行自我學(xué)習(xí)的動(dòng)態(tài)參數(shù)生成方法，實(shí)現(xiàn)智能調(diào)整遺傳算法的關(guān)鍵參數(shù)，自我學(xué)習(xí)的模型框架如圖1所示，在時(shí)間步長(zhǎng)t時(shí)，代理獲取當(dāng)前狀態(tài)st并在at采取行動(dòng)。然后，在第t+1時(shí)刻，轉(zhuǎn)入狀態(tài)st+1,代理從環(huán)境中得到獎(jiǎng)勵(lì)rt，代理更新動(dòng)作選擇并采取合適的動(dòng)作。

圖1 自我學(xué)習(xí)框架

圖中t是當(dāng)前步,S集包含所有狀態(tài)。Sarsa算法的目標(biāo)是估計(jì)一個(gè)最優(yōu)策略的Q值。該模型根據(jù)環(huán)境和狀態(tài)行為的反饋信息進(jìn)行更新，用以表征行為選擇的合理性。Q值保存在Q值表中，用于記錄學(xué)習(xí)經(jīng)歷。初始Q值表(式10)是一個(gè)零值矩陣，其行數(shù)等于狀態(tài)的數(shù)量，列數(shù)等于動(dòng)作的數(shù)量。Q值的計(jì)算需要考慮已有的狀態(tài)、行動(dòng)、獎(jiǎng)勵(lì)等經(jīng)驗(yàn), 式(11)為Q值更新算法。

(10)

Q(st,at)←(1-α)Q(st,at)+α((rt+1+γQ(st+1,at+1))

(11)

式中，Q(st,at)表示在當(dāng)前狀態(tài)st執(zhí)行行為at后的Q值;α表示學(xué)習(xí)率，設(shè)為0.75;rt+1表示在狀態(tài)st執(zhí)行行為at后的獎(jiǎng)勵(lì)價(jià)值，初始獎(jiǎng)勵(lì)r= 1;γ表示折算率，設(shè)為0.2；Q(st+1,at+1)表示在狀態(tài)st+1下通過(guò)ε-貪婪決策選擇的行為at+1的期望Q值。

主要步驟[14]：

步驟1:初始化Q值表；

步驟2:獲得當(dāng)前狀態(tài)st，s←st；

步驟3:根據(jù)Q值表選擇動(dòng)作a并執(zhí)行；

步驟4:獲得強(qiáng)化獎(jiǎng)勵(lì)r，并獲得新的狀態(tài)st+1；

步驟5:如果滿足GA的停止條件，則終止進(jìn)程，否

則轉(zhuǎn)到步驟6；

步驟6:根據(jù)式(11)更新Q值；

步驟7:更新?tīng)顟B(tài):s←st+1，轉(zhuǎn)到步驟2。

圖2 學(xué)習(xí)模塊

2.5.1 狀態(tài)與行為設(shè)置

狀態(tài)的構(gòu)建需要考慮種群適應(yīng)度的變化，包括：種群平均適應(yīng)度、種群多樣性、最佳個(gè)體適應(yīng)度。式(12)表示用第一代種群的平均適應(yīng)度標(biāo)準(zhǔn)化后的種群平均適應(yīng)度；式(13)表示第一代種群多樣性歸一化后的種群多樣性；式(14)表示用第一代的最佳適應(yīng)度進(jìn)行歸一化后得到種群最佳適應(yīng)度[15]；式(15)表示種群狀態(tài)值：

(12)

(13)

(14)

S*=w1f*+w2d*+w3m*

(15)

2.5.2 獎(jiǎng)勵(lì)方法

通過(guò)最優(yōu)個(gè)體適應(yīng)度與種群平均適應(yīng)度轉(zhuǎn)換計(jì)算得出獎(jiǎng)勵(lì)值。式(16)表示Pc獎(jiǎng)勵(lì)，式(17)表示Pm獎(jiǎng)勵(lì)。如果第t代的最優(yōu)個(gè)體優(yōu)于第(t-1)代，代理就會(huì)得到當(dāng)前Pc有效的獎(jiǎng)勵(lì)。如果第t代的平均適應(yīng)度優(yōu)于第t-1代，代理會(huì)得到當(dāng)前Pm有效的獎(jiǎng)勵(lì)。

(16)

(17)

2.5.3 行為選擇策略

在探索和開(kāi)發(fā)之間進(jìn)行行為選擇。ε-貪婪是一種行為選擇策略,式(18)表示在獲取到狀態(tài)s后對(duì)行為a的決策[16]：

(18)

式中，ε為貪婪率，取ε= 0.9，β是0到1之間的一個(gè)隨機(jī)值。當(dāng)ε≥β，使期望Q值最大化的動(dòng)作a被選擇，這也被稱為貪婪策略。當(dāng)ε<β時(shí)，進(jìn)行探究，選擇一個(gè)隨機(jī)動(dòng)作a。

2.5.4 交叉與變異操作

基于Sarsa算法改進(jìn)的遺傳算法(以下簡(jiǎn)稱Sa-GA)中，每一次的迭代都需要獲取自我學(xué)習(xí)代理中的Pc和Pm值，進(jìn)行交叉與變異。

在被選中的變異個(gè)體中，首先確定變異位置P1、P2，然后把相應(yīng)位置的子任務(wù)或制造資源提供者進(jìn)行對(duì)換，即實(shí)現(xiàn)個(gè)體的變異。

當(dāng)滿足最大迭代次數(shù)時(shí)，運(yùn)算終止，輸出結(jié)果，得出最終的優(yōu)化結(jié)果，總體流程圖如圖3所示。

圖3 基于Sarsa改進(jìn)的GA算法運(yùn)算流程圖

3 案例驗(yàn)證與分析

3.1 案例描述

對(duì)本文的基于Sa-GA的制造資源優(yōu)選方法進(jìn)行驗(yàn)證。模擬某時(shí)段某云制造平臺(tái)運(yùn)營(yíng)狀況:10家資源提供者與6名資源需求者的需求申請(qǐng)，將每個(gè)需求分解為11個(gè)子任務(wù)，匹配關(guān)系與時(shí)間成本如表3所示。

表3 任務(wù)可選方案

表中可提供服務(wù)的制造商數(shù)量為1～2個(gè)，括號(hào)中為對(duì)應(yīng)的制造時(shí)間，若無(wú)相對(duì)應(yīng)任務(wù)，則時(shí)間為0。

3.2 算法驗(yàn)證分析

以表3數(shù)據(jù)為輸入的問(wèn)題模型對(duì)時(shí)間目標(biāo)函數(shù)進(jìn)行有效驗(yàn)證。相關(guān)參數(shù)設(shè)置如表4所示。

表4 相關(guān)參數(shù)設(shè)置

取各制造資源提供者的效益轉(zhuǎn)化率br(sup=i，i=1,…,10)分別為：96%，95%，93%，92.5%，96%，98%，95%，96.5%，97%，94%，代入式(4)得到資源提供者效益值，見(jiàn)表5。

表5 資源提供者效益值

優(yōu)化步驟如下：

步驟1：初始化表4中遺傳相關(guān)參數(shù)。初始化表3相關(guān)數(shù)據(jù)與自我學(xué)習(xí)狀態(tài)設(shè)置和行為設(shè)置；

步驟2：據(jù)式(5)，計(jì)算個(gè)體適應(yīng)度值并對(duì)個(gè)體根據(jù)適應(yīng)度值進(jìn)行排序，選出優(yōu)秀個(gè)體；

步驟3：據(jù)式(9)進(jìn)行選擇，采用前半段基因的單點(diǎn)交叉并按每次迭代經(jīng)Sa-GA生成的交叉率Pc與變異率Pm隨機(jī)選擇進(jìn)行交叉與變異操作；

步驟4：將新個(gè)體重新插入種群，進(jìn)行循環(huán)；

步驟5：達(dá)到最大迭代次數(shù)時(shí)停止，返回最優(yōu)值。

最后得出解的收斂曲線，見(jiàn)圖4，Sa-GA對(duì)云制造資源優(yōu)選的解的收斂在迭代前半段達(dá)到相對(duì)穩(wěn)定趨勢(shì)后仍然能繼續(xù)找到相對(duì)更優(yōu)解，對(duì)比GA對(duì)資源優(yōu)選解的收斂在前半段趨于固定值后沒(méi)有繼續(xù)更新，其已陷入局部最優(yōu)解或已淘汰最優(yōu)個(gè)體，說(shuō)明Sa-GA對(duì)尋優(yōu)過(guò)程有較有效的優(yōu)化。Sa-GA云制造資源優(yōu)選方案如圖6所示,對(duì)比GA(圖5)，最短完成時(shí)間分別在80～85天之間與90～95天之間，完成時(shí)間大幅減少，說(shuō)明Sa-GA對(duì)目標(biāo)函數(shù)的尋優(yōu)程度有顯著的提升。

圖4 Sa-GA與GA進(jìn)化收斂曲線對(duì)比

圖5 GA資源優(yōu)選方案

圖6 Sa-GA資源優(yōu)選方案

4 總結(jié)

針對(duì)云制造環(huán)境下多制造任務(wù)并行情況下的資源優(yōu)選，本文提出了一種資源優(yōu)選方法，該方法以制造資源的時(shí)間成本與使用效益為優(yōu)化目標(biāo)，應(yīng)用基于Sarsa算法改進(jìn)的遺傳算法經(jīng)自我學(xué)習(xí)實(shí)現(xiàn)相關(guān)參數(shù)動(dòng)態(tài)化優(yōu)化，避免了因單一算法過(guò)早收斂或陷入局部最優(yōu)而影響整體的優(yōu)化配置方案，通過(guò)實(shí)驗(yàn)驗(yàn)證該模型優(yōu)化方法明顯提高了云制造環(huán)境下資源提供者的生產(chǎn)效率，有效縮短了訂單完成時(shí)間。