[發明專利]一種基于NSGA-III算法的工序排序多目標優化方法

在審

• 申請號: 202111229219.5
• 申請日: 2021-10-21
• 公開（公告）號: CN113988396A
• 公開（公告）日: 2022-01-28
• 發明（設計）人: 袁偉;郭偉;王磊;李佳駿;鄭鑫昌
• 申請（專利權）人: 天津大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/04
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 程毓英

1.一種基于NSGA-III算法的工序排序多目標優化方法，包括下列步驟：

第一步，利用工序關系圖譜PRG表達工序間的優先關系并生成工序約束矩陣

工序排序需要滿足工序排序規則，根據零件的幾何特征和加工的技術要求，在滿足以上四類優先關系要求后生成工序關系圖譜PRG，PRG為有向無環圖，節點為工序編號，邊表示所連接兩節點代表的工序間的優先關系，對PRG內工藝節點的關系作出以下定義：

1)前驅關系：即工序i可以通過任一路徑到達工序j，則稱工序i為工序j的前驅工序；

2)后繼關系：與前驅關系相反，即工序i可以通過任一路徑到達工序j時，稱工序j為工序i的后繼工序；

3)并列關系：若工序i與工序j既不是前驅關系也非后繼關系，則稱工序i與工序j為并列工序；

基于三類關系作出PRG圖，

基于PRG圖生成對應的工序約束矩陣PCM_ij：

其中，PCM_ij表示工序P_i與工序P_j之間的優先關系，n為待加工零件的總工序數，PCM_ij根據約束關系取得，如下：

第二步，建立工序排序的多目標優化模型

工序排序優化以總機床成本、總刀具成本、總機床變更成本、總刀具更換成本和總碳排放量為優化目標建立目標函數，以工序約束矩陣PCM_ij構建約束關系進行優化求解，由此構建如下優化目標函數：

i總機床成本

其中，Mcost是總的機床成本，n為總工序數，MTID_i是工序i使用的機床代號，ω_m是機床MTID_i的成本系數；

ii總刀具成本

其中，Tcost是總的刀具成本，n為總工序數，TLID_i是工序i使用的刀具代號，ω_t是刀具TLID_i的成本系數；

iii總機床變更成本

其中，MCcost是總的機床變更成本，ω_mc是機床的變更成本系數，MTID_i，MTID_i+1分別是工序i和工序i+1使用的機床代號，γ₁是機床變更函數；

iv總刀具變更成本

其中，TCcost是總的刀具更換成本，ω_tc是刀具的變更成本系數，MTID_i，MTID_i+1分別是工序i和工序i+1使用的機床代號，Tl_i，Tl_i+1分別是工序i和工序i+1使用的刀具代號，γ₂是刀具變更函數；

v總碳排放量

其中，MPcost是總的碳排放量，MTID_i是工序i使用的機床代號，ω_co2是機床MTID_i的碳排放系數；

第三步，染色體編碼

為將優化涉及到的各元素進行有效的映射，采用適用于工序優化的染色編碼機制，編碼方式共由三段組成：其中第一段為工序序列編碼順序，采用排序編碼，其代表了各工序的排序順序；第二段為該工序所用的機床編號，采用整數編碼，取值范圍為備選機床的代號范圍；第三段為該工序所用刀具編號，采用整數編碼，取值范圍為備選刀具的代號范圍；

第四步，基于NSGA-III算法求解，方法如下：

步驟i設置算法參數，包括進化次數、變異率和交叉率等；根據染色體編碼方式和映射關系初始化參考點和種群N；

步驟ii對父代種群P_t，通過選擇、交叉、變異產生子種群Q_t；

步驟iii混合P_t和Q_t得到一個新種群R_t，其規模為2N；對R_t內所有個體進行解碼并計算其適應度，該適應度為優化模型中的各目標函數：Mcost、Tcost、MCcost、TCcost、MPcost；

步驟iv對R_t進行非支配排序并劃分為不同層級的非支配解集合(F₁,F₂,F₃,…,F_L,…,F_W)；

步驟v產生一個新解集S_t，從F₁開始，每次移動一個非支配解集到S_t，直到首次出現S_t的數量大于或等于N的數量，設F_L是首次滿足這一條件的解集，則

步驟vi從S_t中選擇解產生下一代父種群P_t+1：若S_t的數量等于N，則P_t+1＝S_t，否則，先將S_t中的集合(F₁,F₂,F₃,…F_L-1)放入P_t+1，然后再從F_L中根據基于參考點選擇機制選取其余解；

步驟vii若滿足終止條件，則輸出最終的解，否則重復步驟ii。