[發明專利]一種基于免疫遺傳算法求解第一類裝配線平衡問題的方法

在審

• 申請號: 201810803005.6
• 申請日: 2018-07-20
• 公開（公告）號: CN109146136A
• 公開（公告）日: 2019-01-04
• 發明（設計）人: 張含葉;梁偉杰
• 申請（專利權）人: 九江學院
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12;G06Q50/04
• 代理公司: 南昌新天下專利商標代理有限公司 36115
• 代理人: 謝德珍

1.一種基于免疫遺傳算法求解第一類裝配線平衡問題的方法，其特征在于，該方法包括以下步驟：

1）函數ψ(?)的定義：

A*， 滿足：

(1) 如果 則交換矩陣A中 和 的位置；

(2) 如果 則矩陣A中 和 位置保持不變；

其中，

n 代表裝配任務的總數目；矩陣A中的任意列均代表n的一個全排列；

2） 約束條件包括：

一個裝配作業元素只能分配到一個工作站中

其中，k表示裝配工作站的序號，M表示裝配工作站的總數，i表示裝配作業元素的序號；

裝配優先約束關系約束

其中，j表示裝配作業元素的序號；

裝配節拍約束（即，任一工作站的裝配時間不得大于裝配節拍）

其中，N表示裝配作業元素的集合，t_i表示第i個作業元素的裝配時間，C表示裝配節拍；

變量的取值范圍

3）目標函數：

其中，f₁表示最小化工作站數，f₂表示最小化平滑指數，w₁和w₂均表示權重系數；

所述最小化工作站數為

其中， m表示裝配工作站的序號；

所述最小化平滑指數為

其中， ST_k表示第k個裝配工作站的裝配時間；

因此，目標函數的計算公式為：

]]>	（1）

4）免疫遺傳算法：

步驟一:設定參數

(1) PS：種群規模；

(2)P_c：交叉概率；

(3) P_m：變異概率；

(4) P_i：免疫接種概率；

(5) ：相似度閾值， ；

步驟二: 初始化：

隨機生成PS個初始個體，把這PS個初始個體記為矩陣A，且對其進行操作，使滿足A*；

步驟三: 更新種群：

(1)交叉操作：

令，其中 表示大于或等于x的最小正整數；如果M₁為奇數，則M₁←M₁-1；

首先，從第t代種群A^(t)中隨機選取M₁個個體構建矩陣；接著，從 中隨機選取兩個個體執行交叉操作，原理如圖1所示，經過交叉操作后的矩陣記為；最后，對 執行 操作，并令 ；

(2) 變異操作 ：

令 ；首先，從第t代種群A^(t)中隨機選取M₂個個體構建矩陣；接著，對 中的所有個體進行變異操作，原理如圖2所示，經過變異操作后的的矩陣記為；最后，對執行 操作，并令 ；

(3) 免疫接種操作：

令，P_g代表記憶庫中的接種疫苗；首先，從第t代種群A^(t)中隨機選取M₃個個體構建矩陣；接著，對中的所有個體和P_g進行交叉操作，原理如圖1所示，經過交叉操作后的的矩陣記為；最后，對執行操作，并令 ；

(4) 抗體生存期望選擇：

令 ，中所有個個體的生存期望根據公式進行計算，并對結果進行升序排列，選擇前PS個個體構成下一代種群A^(t+1)；

其中，

其中，表示抗體u和抗體v在第j位基因上的基因值相等，即抗體u和抗體v具有等位基因j；

表示抗體u和抗體v具有等位基因的總個數；

步驟四: 更新記憶庫：

矩陣A^(t+1)中所有M個個體的目標函數根據公式(1)進行計算，并把具有最小目標函數的個體記為；如果 ，則 ；否則，；

步驟五: 終止條件驗證：

一般而言，算法只要滿足下面三個條件中的任意一個，則終止迭代；

（1）最優個體的適應度達到給定的閾值；

（2）最優個體的適應度和群體的適應度不再上升；

（3）迭代次數達到預設的代數；

其中，選擇條件（2）作為算法的停止條件，即在算法的迭代過程中，一旦最優個體的適應度和群體適應度不再上升，則停止迭代，進入步驟六；否則，轉入步驟三；

步驟六: 結果輸出：

輸出最佳裝配線平衡結果。