基于自我學習遺傳算法的云制造資源優選*

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

(大連工業大學機械工程與自動化學院，遼寧 大連 116034)

0 引言

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

1 制造資源優選數學建模

1.1 問題描述

建立結合實際制造需要以尋求最優配置的數學模型并通過建模求解與實例驗證，并作如下假設：

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

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

設n個資源需求者(Cus)的若干子任務(Tas)有l個資源提供者(Sup)提供制造資源，相關參數及描述見表1。

表1 相關參數符號及描述

1.2 目標函數

(1)時間成本目標函數

制造服務的時間類別包括制造時間和運輸時間，則時間函數[11]表示為：

(1)

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

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

(2)

式(2)表示若資源提供者sup與資源需求者cus的子任務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)資源提供者效率轉化函數

資源提供者效益轉化函數[12]表示為:

BR=

(5)

(3)整體目標函數

為實現可接受條件下的多目標要求，賦予各目標不同的權值從而達到資源方案的非劣性平衡。此函數可表示為：

(6)

式中，ω1、ω2分別為時間函數和效益函數的權值,j=1,2,3...l。

1.3 約束條件

各子任務時間之和不超過該任務最大時間：

(7)

2 模型求解

2.1 染色體編碼

采用整數編碼，每個染色體表示待選任務的全部制造順序。染色體長度為2 m。定義前半段為所有資源需求者編號，數量即表示子任務的數量；后半段表示前半段資源需求者的子任務對應的資源提供者編號。

以某條染色體為例，見表2。

表2 染色體編碼

表2中列數表示該條染色體包含基因數，共18列，每一列表示一個基因。該條染色體個體表示4個資源需求者分別包含2,2,2,3個子任務在3個資源提供者進行生產制造。

2.2 種群初始化

隨機生成N個初始染色體個體，這N個個體組成一個種群，以這N個個體構成的種群作為初始種群，逐代進化，設置t=0，最大進化代數為gen。

2.3 適應度值

適應度函數值是評價個體優劣的指標[12]：

(8)

式中，常數c為保守估計值，視目標函數而定，P表示整體目標函數值。

2.4 選擇操作

采用輪盤賭的方式對個體進行選擇。每個個體的適應度值與整個種群中個體適應度值和的比例決定進入下一代的概率[13]：

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

(9)

2.5 基于Sarsa算法自我學習的交叉和變異操作

設交叉率與變異率分別為Pc和Pm，Pc與Pm過大或過小都會對破壞種群，不利于解的收斂和最優解的生成;本文設計了一種能夠根據迭代進程進行自我學習的動態參數生成方法，實現智能調整遺傳算法的關鍵參數，自我學習的模型框架如圖1所示，在時間步長t時，代理獲取當前狀態st并在at采取行動。然后，在第t+1時刻，轉入狀態st+1,代理從環境中得到獎勵rt，代理更新動作選擇并采取合適的動作。

圖1 自我學習框架

圖中t是當前步,S集包含所有狀態。Sarsa算法的目標是估計一個最優策略的Q值。該模型根據環境和狀態行為的反饋信息進行更新，用以表征行為選擇的合理性。Q值保存在Q值表中，用于記錄學習經歷。初始Q值表(式10)是一個零值矩陣，其行數等于狀態的數量，列數等于動作的數量。Q值的計算需要考慮已有的狀態、行動、獎勵等經驗, 式(11)為Q值更新算法。

(10)

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

(11)

式中，Q(st,at)表示在當前狀態st執行行為at后的Q值;α表示學習率，設為0.75;rt+1表示在狀態st執行行為at后的獎勵價值，初始獎勵r= 1;γ表示折算率，設為0.2；Q(st+1,at+1)表示在狀態st+1下通過ε-貪婪決策選擇的行為at+1的期望Q值。

主要步驟[14]：

步驟1:初始化Q值表；

步驟2:獲得當前狀態st，s←st；

步驟3:根據Q值表選擇動作a并執行；

步驟4:獲得強化獎勵r，并獲得新的狀態st+1；

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

則轉到步驟6；

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

步驟7:更新狀態:s←st+1，轉到步驟2。

圖2 學習模塊

2.5.1 狀態與行為設置

狀態的構建需要考慮種群適應度的變化，包括：種群平均適應度、種群多樣性、最佳個體適應度。式(12)表示用第一代種群的平均適應度標準化后的種群平均適應度；式(13)表示第一代種群多樣性歸一化后的種群多樣性；式(14)表示用第一代的最佳適應度進行歸一化后得到種群最佳適應度[15]；式(15)表示種群狀態值：

(12)

(13)

(14)

S*=w1f*+w2d*+w3m*

(15)

2.5.2 獎勵方法

通過最優個體適應度與種群平均適應度轉換計算得出獎勵值。式(16)表示Pc獎勵，式(17)表示Pm獎勵。如果第t代的最優個體優于第(t-1)代，代理就會得到當前Pc有效的獎勵。如果第t代的平均適應度優于第t-1代，代理會得到當前Pm有效的獎勵。

(16)

(17)

2.5.3 行為選擇策略

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

(18)

式中，ε為貪婪率，取ε= 0.9，β是0到1之間的一個隨機值。當ε≥β，使期望Q值最大化的動作a被選擇，這也被稱為貪婪策略。當ε<β時，進行探究，選擇一個隨機動作a。

2.5.4 交叉與變異操作

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

在被選中的變異個體中，首先確定變異位置P1、P2，然后把相應位置的子任務或制造資源提供者進行對換，即實現個體的變異。

當滿足最大迭代次數時，運算終止，輸出結果，得出最終的優化結果，總體流程圖如圖3所示。

圖3 基于Sarsa改進的GA算法運算流程圖

3 案例驗證與分析

3.1 案例描述

對本文的基于Sa-GA的制造資源優選方法進行驗證。模擬某時段某云制造平臺運營狀況:10家資源提供者與6名資源需求者的需求申請，將每個需求分解為11個子任務，匹配關系與時間成本如表3所示。

表3 任務可選方案

表中可提供服務的制造商數量為1～2個，括號中為對應的制造時間，若無相對應任務，則時間為0。

3.2 算法驗證分析

以表3數據為輸入的問題模型對時間目標函數進行有效驗證。相關參數設置如表4所示。

表4 相關參數設置

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

表5 資源提供者效益值

優化步驟如下：

步驟1：初始化表4中遺傳相關參數。初始化表3相關數據與自我學習狀態設置和行為設置；

步驟2：據式(5)，計算個體適應度值并對個體根據適應度值進行排序，選出優秀個體；

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

步驟4：將新個體重新插入種群，進行循環；

步驟5：達到最大迭代次數時停止，返回最優值。

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

圖4 Sa-GA與GA進化收斂曲線對比

圖5 GA資源優選方案

圖6 Sa-GA資源優選方案

4 總結

針對云制造環境下多制造任務并行情況下的資源優選，本文提出了一種資源優選方法，該方法以制造資源的時間成本與使用效益為優化目標，應用基于Sarsa算法改進的遺傳算法經自我學習實現相關參數動態化優化，避免了因單一算法過早收斂或陷入局部最優而影響整體的優化配置方案，通過實驗驗證該模型優化方法明顯提高了云制造環境下資源提供者的生產效率，有效縮短了訂單完成時間。