[發明專利]基于序優化與在線核極限學習機的分層迭代優化調度方法

有效

• 申請號: 201210543781.X
• 申請日: 2012-12-17
• 公開（公告）號: CN103105775A
• 公開（公告）日: 2013-05-15
• 發明（設計）人: 劉民;郝井華;郭路;吳澄;王凌;張亞斌;劉濤
• 申請（專利權）人: 清華大學
• 主分類號: G05B13/02
• 分類號: G05B13/02
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 樓艮基

1.基于序優化與在線核極限學習機的分層迭代優化調度方法，其特征在于，所述方法是在計算機上依次按以下步驟實現的：步驟1：初始化調度算法相關參數

采集調度所需的相關初始化信息，包括每個lot的片數、品種、工藝流程信息，每個操作的菜單、可加工機器名稱、所屬的加工機器組名稱信息，每個機器的釋放時間、所屬的機器組、對每種菜單的加工時間信息，這些信息寫入算法數據庫中，在調度算法啟動時，作為初始化信息加載到算法中；

確定差分進化優化算法相關參數：選定種群規模N＝20，差分縮放因子F＝0.3，最大進化代數G_max＝5，雜交率CR＝0.8，變異比率λ＝0.3；迭代次數設為2次；

步驟2：差分進化算法初始解生成；

優化過程中，對于菜單層主要采用菜單多屬性權值優化，優化的菜單屬性主要包括該菜單中所含的操作平均剩余加工時間、平均到達時間、平均后續操作數量、平均緊急程度四個屬性；對于操作層主要優化操作的優先權序列，于是，對于每個機器組而言，采用的編碼方式為：i表示該機器組編號i＝1，2，…，g，g為機器組的數量；r_i表示機器組i可加工菜單的最大數量；{w_i，1，w_i，2，w_i，3，w_i，4}為四個調度屬性的權值，權值初始化時在[01]范圍內隨機取值；表示第j個菜單對應所有操作生成的優先權序列，其中d_i表示菜單j所包含的操作的總數量，表示機器組i的菜單j中的第k個操作，k＝1，2，…，dj；操作優先權序列采用隨機方式產生；

所有機器組的組合，構成一條初始解個體；

步驟3：采用差分進化算法獲得第一次迭代前較優解

步驟3.1：解碼

對步驟2中生成的初始解，通過離散事件仿真的方式獲得對每個調度解個體的適應度評價；

仿真過程中，主要包含菜單選擇和菜單內操作選擇兩種決策過程：

當機器空閑時，首先對緩沖區內所有的操作按照菜單進行分組，計算每種菜單內所有操作的平均剩余加工時間、平均到達時間、平均后續操作數量、平均緊急程度四個屬性，根據編碼過程中給定的調度屬性加權矢量{w_i，1，w_i，2，w_i，3，w_i，4}計算菜單的優先權值，選取權值高的菜單進行加工；

菜單選定后，對菜單內每個操作按照解個體中給定的操作優先權從高到低的方式進行選擇，直至選出的操作總片數最接近機器加工片數的最大值；此時，被選中的所有操作組成一個batch，將該batch中的所有操作都同時上機進行加工；

加工完成后，仿真推進至下一次菜單選擇和菜單內操作選擇過程，直至所有操作都加工完成，仿真結束；

步驟3.2：變異交叉過程

差分進化算法變異交叉過程描述如下：

步驟3.2.1：隨機選擇三個個體，

步驟3.2.2：操作層操作優先權序列變異方法：

1)選擇需變異的操作優先權子序列

假定機器組M_l對應操作的數量為D_l，需進行變異的操作數量為表示向下取整；隨機生成一整數r₄，0≤r₄≤D_l-D_λ，從中機器組M_l對應的操作優先權序列中，從位置r₄選取長度為D_λ的操作子序列，記為該子序列對應的位置矢量記為這里位置矢量指的是從0開始標記的位置編號，則：

Pr1r4={r4,r4+1,···,r4+Dλ-1}]]>

將上式記作：

Pr1r4={r4,r4+1,···,r4+Dλ-1}={Pr1,0r4,Pr1,1r4,···,Pr1,Dλ-1r4}]]>

不失一般性，記為第r₄+k(0≤k≤D_λ-1)個操作在中對應的操作優先權序列的位置編號，則對選取的長度為D_λ的操作子序列中的每一個元素，在中查找對應位置的元素后，得到的位置矢量為：

Pr2r4={Pr2,0r4,Pr2,1r4,···,Pr2,Dλ-1r4}]]>

Pr3r4={Pr3,0r4,Pr3,1r4,···,Pr3,Dλ-1r4}]]>

Pr1r4={Pr1,0r4,Pr1,1r4,···,Pr1,Dλ-1r4}]]>

這里中由所對應的操作、中位置所對應的操作以及中位置所對應的操作相同；

2)執行變異操作

令F為差分縮放因子(F＜1)，按下式計算變異后中每個元素所對應的位置矢量

上式中，mod表示取余；表示變異后的位置矢量；

3)交叉過程

記分別為位置矢量中的第k個位置，上述兩個位置對應的操作為一個操作對，交叉操作即為對上述兩個位置對應的操作按初始化給定的概率CR進行交換；即隨機生成一個取值在[0，1]內的數，將該數與CR值比較，如果該隨機數大于CR則交換，否則不交換；

步驟3.2.3：菜單層多調度屬性權值變異交叉方法：

1)變異過程

yij=wr1j+F(wr2j-wr3j)]]>

上式中，為個體的多屬性權值部分；為個體的多屬性權值部分；為個體的多屬性權值部分；表示變異后第j代第i個個體的調度屬性權值部分；

2)交叉過程

假定表示的第k個變量，表示第j代第i個個體的第k個變量，k＝1，2，3，4，交叉過程為：隨機生成一個取值在[0，1]內的數，將該數與CR值比較，如果該隨機數大于CR則否則

步驟3.2.4：變異交叉完成后，所得到的個體記為

步驟3.3：選擇

若完成變異和交叉后的個體適應度高于原有個體，則將新個體取代原有個體，作為第j+1代第i個個體即：

xij+1=xij,f(xij)≤f(vij)vji,f(xij)>f(vij)]]>

其中表示的目標函數值；表示的目標函數值；

步驟3.4：終止條件

重復步驟3.1～步驟3.3，直至滿足所設定的最大進化代數G_max＝5；

步驟4：菜單層基于序優化方法的快速優化

菜單層采用序優化方法進行優化，具體算法描述如下：

步驟4.1：隨機產生N₀＝20條個體，每個個體生成時，操作層的操作優先權序列為步驟3優化后得到的操作優先權，菜單層的多屬性權值產生方法與步驟2中菜單層多屬性權值產生方法相同；

記為其中x_i為一組權值矢量，由所有機器組對應的菜單層屬性加權矢量{w_i，1，w_i，2，w_i，3，w_i，4}組成；

通過仿真獲得這N₀個個體的目標函數值，記為Y=y1y2···yN0;]]>

步驟4.2：將步驟4.1生成的N₀對數據作為訓練數據，構造訓練集{X，Y}；

步驟4.3：隨機產生N_test＝1000個調度解個體構造集合Θ_r，每個個體的產生方法與步驟2中調度解個體的產生方法相同；

步驟4.4：采用核極限學習機，獲得N_test＝1000個調度解個體的目標函數值的估計值，計算公式如下：

Y^test=K(xtest,1,x1)K(xtest,1,x2)···K(xtest,1,xN0)K(xtest,2,x1)K(xtest,2,x2)···K(xtest,2,xN0)············K(xtest,Ntest,x1)K(xtest,Ntest,x2)···K(xtestNtest,xN0)Aπ-1y1Aπ-1y2···Aπ-1yN0]]>

其中Aπ-1=1v+K(x1,x1)K(x1,x2)···K(x1,xN0)K(x2,x1)1v+K(x2,x3)···K(x2,xN0)············K(xN0,X1)K(xN0,x2)···1v+K(xN0,xN0)-1]]>

K(*，#)＝exp(-γ||*-#||²)為預先給定的核函數，其中*和#代表核函數的兩個輸入變量，這里γ取值為γ＝2¹¹；目標函數值的估計值v為預先給定的折中系數，這里取值為v＝2¹³；x_test，i表示N_test＝1000個調度解個體中的第i個個體，i＝1，2，…，N_test；

步驟4.5：利用序優化公式計算需要仿真的個體數量，根據序優化方法，各參數取值為Z₀＝8.1998，k＝1，ρ＝1.9164，g＝35，r＝-2.0250，η＝10，e＝2.718281828459為自然對數；

步驟4.6：根據步驟4.4計算的N_test＝1000個調度解個體的目標函數值估計值，根據步驟4.5計算得到的s值，選定最優的s個調度解個體，對選定的s個解個體進行仿真，選出仿真得到的目標函數值最優的解作為最終優化結果；

此解即為采用序優化方法優化后的調度解；

步驟5：操作層基于差分進化算法的操作優先權優化

步驟5.1：差分進化算法初始解生成

隨機產生N₀＝20條個體，每個個體生成時，菜單層的多屬性權值固定為步驟4最優解中對應的權值，操作層的操作優先權序列隨機產生，產生方法與步驟2中操作層的操作優先權產生方法相同；

步驟5.2：解碼

具體過程與步驟3.1相同；

步驟5.3：變異

具體過程與步驟3.2.1～3.2.2同；

步驟5.4：選擇

具體過程與步驟3.3相同；

步驟5.5：操作層優化終止條件

重復步驟5.1～步驟5.4，直至滿足所設定的最大進化代數G_max＝5；

步驟6：迭代終止條件

重復步驟4～步驟5，直至滿足迭代終止條件，即最大迭代次數N_iter＝2。