[發明專利]一種基于候鳥優化算法的多目標混流雙邊裝配線平衡方法

在審

• 申請號: 201711493844.4
• 申請日: 2017-12-31
• 公開（公告）號: CN108038339A
• 公開（公告）日: 2018-05-15
• 發明（設計）人: 梅慧文;張超勇;林文文;任彩樂;孟磊磊;任亞平;林海;許飛;冀道立;易文凱
• 申請（專利權）人: 武漢企鵝能源數據有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06N3/00
• 代理公司: 武漢藍寶石專利代理事務所(特殊普通合伙) 42242
• 代理人: 吳陽

1.一種多目標混流雙邊裝配線平衡方法，其特征在于，包括以下步驟：

步驟1，根據混流雙邊裝配線平衡問題特點，建立以裝配線最小化工位數、最小化負載均衡和最小化單位成品總成本為目標的數學模型；

步驟2，利用NEH啟發式初始化和隨機初始化相結合的方法對所述數學模型進行初始化，生成多組初始解，并采用快速非支配排序算法對這些解進行排序，得到多個邊界集，根據候鳥優化算法的特點，選取第一個邊界集中聚集距離最大的個體成為種群的領飛鳥，根據聚集距離的大小依次選取各個邊界集中的兩個個體作為種群的跟飛鳥；同時設置最大巡回次數G以及初始化巡回次數g＝1；

步驟3，分別根據預設的選擇策略選擇鄰域結構以產生領飛鳥和跟飛鳥的多個鄰域解，并進行非支配排序，查找可支配領飛鳥或跟飛鳥的個體并替換所述領飛鳥或跟飛鳥，實現所述領飛鳥和跟飛鳥的進化；

步驟4，更新非支配解集，并針對非支配解集中的每一個非支配解采用多目標迭代貪婪算法進行局部搜索；

步驟5，若巡回次數g小于最大巡回次數G，則g＝g+1，并跳轉至步驟3，否則設置g＝1，并在當前非支配解集中選擇一個個體替換領飛鳥；

步驟6，判斷是否滿足算法終止準則，若未滿足，則跳轉至步驟3，否則，算法終止，輸出非支配解集，所述非支配解集即為混流雙邊裝配線平衡問題的最優解。

2.根據權利要求1所述一種多目標混流雙邊裝配線平衡方法，其特征在于，步驟2中所述的利用NEH初始化和隨機初始化方法對所述數學模型進行初始化，生成多組初始解，包括：

首先，利用NEH啟發式初始化方法，以最小化組合目標為目標產生一個初始解，然后以最小化單位成品總成本為目標產生一個初始解，再隨機產生一組初始解，即采用隨機生成的方式產生任務序列進行編碼，調整任務序列后進行解碼。

3.根據權利要求2所述所述一種多目標混流雙邊裝配線平衡方法，其特征在于，所述NEH啟發式初始化方法步驟如下：

步驟201，基于優先級的編碼方式，根據分級位置權得到各任務的初始優先權值，然后按照優先權值的大小降序排列得到任務序列SEQ(SEQ＝{task1，task2，…taskn})；

步驟202，設置i＝1；

步驟203，將第i個任務taski移出，移出后的任務序列為SEQ′，并將taski插入到SEQ′的每一個位置得到新的任務序列，進行解碼，如果比當前解更優則進行替換；i＝i+1；

步驟204，如果i≤n，則重復步驟3，否則算法終止，輸出任務序列。

4.根據權利要求3所述所述一種多目標混流雙邊裝配線平衡方法，其特征在于，所述步驟203包括：解碼時，需要考慮任務的節拍時間約束、優先關系約束和操作方位約束。

5.根據權利要求4所述所述一種多目標混流雙邊裝配線平衡方法，其特征在于，所述步驟203具體包括：所述操作方位包括左方位L、右方位R和任意方位E；對于操作方位為E的任務，如果左右工位的開始時間相同則隨機選擇一個工位，否則，分配到較早開始的工位；在選擇操作工位時，如果左右工位不屬于同一個成對工位，在滿足節拍時間的前提下，優先選擇成對工位序號小的工位。

6.根據權利要求1所述一種多目標混流雙邊裝配線平衡方法，其特征在于，所述步驟3包括：

針對領飛鳥：針對交換、向前插入、向后插入和逆序四種鄰域結構，通過隨機數R選擇任一種鄰域結構，產生領飛鳥的k個鄰域解，對這些鄰域解進行非支配排序，得到第一個邊界集中聚焦距離最大的個體，然后將該個體與領飛鳥進行比較，如果該個體支配領飛鳥，則用該個體替換領飛鳥，否則，領飛鳥不變；將領飛鳥的x個未用到的較優鄰域解傳給下一個個體；

針對跟飛鳥：針對交換、向前插入、向后插入和逆序四種鄰域結構，通過隨機數R選擇任一種鄰域結構，產生跟飛鳥的k-x個鄰域解，并與前面一個個體傳來的x個鄰域解合并成一個集合，進行支配排序，同樣找到第一個邊界集中聚焦距離最大的個體，如果該個體支配跟飛鳥，則進行替換。