[發明專利]一種基于聚類小生境遺傳算法的車間生產作業排程方法

有效

• 申請號: 202010314303.6
• 申請日: 2020-04-21
• 公開（公告）號: CN111208796B
• 公開（公告）日: 2020-08-04
• 發明（設計）人: 季海鵬;劉晶;孫敬哲;袁夕霞;徐培
• 申請（專利權）人: 天津開發區精諾瀚海數據科技有限公司
• 主分類號: G05B19/418
• 分類號: G05B19/418
• 代理公司: 石家莊知住優創知識產權代理事務所(普通合伙) 13131
• 代理人: 林艷艷

1.一種基于聚類小生境遺傳算法的車間生產作業排程方法，其特征在于，包括下述步驟：

S1：建立生產成本、加工時間和設備消耗成本的多目標函數，提出生產過程中的生產工藝順序、訂單數量、設備有效時間多約束條件，建立車間生產作業排程優化數學模型；

S2：針對多目標的特點提出一種基于粒子群權值優化方法對多目標函數進行加權處理，將多目標模型轉化為單目標函數的問題；其步驟如下：

1-1)已知有3個目標函數，利用粒子群算法分別求出各子目標函數最小值的最優解，記做X_i，i＝1，2，3；

1-2)將各目標函數得到的最優解代入不同的目標函數，獲取相應的目標函數值f_i(X_j)，即f_i(X_j)表示第j個目標函數的最優解代入第i個目標函數的函數值，X_j表示第j個目標函數的最優值；

1-3)計算在不同最優解X_i時各目標函數的差值

θ_i^j＝f_i(X_j)-f_i(X_i)

其中，表示第j個目標函數的最優解X_j代入到第i個目標函數得到的函數值與第i個目標函數的最小值之間的差值；

1-4)按照公式計算第i個目標函數的平均差值；

其中，u_i表示第i個目標函數的平均差值，j表示第j個目標函數，m表示共有m個目標函數，表示取不同最優解X_i時各目標函數的差值，由于所以按照m-1計算平均差值；

1-5)按照公式計算權重系數λ_i

其中，m表示m個目標函數，u_i表示第i個目標函數的平均差值，u_j表示第j個目標函數的平均差值，λ_i表示權值；

1-6)為了均衡有效解的范圍，將上述加權系數按大小進行排序，按照差值大的目標函數乘以較小的加權系數，差值小的目標函數乘以較大的加權系數，重新構造目標函數；

S3：初始化種群，隨機生成M個個體，并計算每個個體的適應度值，對每個個體的適應度進行計算按降序排列，并記憶前N個個體；

S4：根據基于密度值改進的K-means均值聚類算法把種群分為K個聚類并確定聚類中心，進而確定小生境遺傳算法的參數小生境半徑；具體步驟如下：

2-1)以每個樣本點為初始聚類中心，以r1為半徑劃定一個球形特征空間，統計落在該球形區域的點的數量作為該點的密度；

2-2)將密度最大的樣本數據設置為第1個初始聚類中心；

2-3)選擇1個整數r2r1，統計第1個初始聚類中心點的r2半徑范圍之外的數據中，選取密度次大的樣本數據作為第2個初始聚類中心；

2-4)按照2-3)的方法，依次得到剩余的初始聚類中心，若M＝K，則算法結束；S5：進行選擇操作，在每個聚類中隨機選取個體進行自適應交叉和變異；通過引入Sigmoid函數，使得交叉概率和變異概率呈現出S型，自適應的交叉和變異算子，具體為：

其中，P_c(x)為第x代的交叉概率，P_c為交叉概率的初始化參數，GEN為總的進化代數；

其中，P_m(x)為第x代的變異概率，P_m為變異概率的初始化參數，GEN為總的進化代數；

S6：小生境淘汰操作，將S3得到的M個個體記憶的N個個體合并起來，得到了一個含有M+N個個體的新群體，確定新群體中的個體屬于哪個聚類，在每一個聚類中計算每兩個個體A_i和A_j的適應度大小，并對其中適應度較低的個體加罰函數；

S7：計算新的適應度并記憶前N個個體；

S8：若滿足終止條件，則輸出算法結果，算法完成，若不滿足終止條件，則將種群及種群代數計數器更新。