基于量子蟻群算法的智能制造調度問題研究

吳昌錢,黃 銳,羅志偉

(1.閩南科技學院計算機信息學院,福建 泉州 366200)(2.北京理工大學計算機學院,北京 100081)(3.廈門大學機電學院,福建 廈門 361000)

隨著我國科技的迅速發展,帶動了高端制造業市場,相關設施裝備的需求量也逐漸擴大. 先進的大型機械設備由各個重要的構件組成,這些構件的制造工藝復雜且加工精度非常高,因此,構件的制造過程是高端制造業的關鍵之處.

精密復雜構件的生產模式特點是典型的生產品種多,每種品種加工數量較少,交貨周期長,成本高. 而且,精密復雜構件的制造工藝較為復雜,且加工的精度較高,加工工序不同,并且工件間無約束,但同一工件的工序有順序[1]. 由此可見,制造車間調度問題(Aviation Manufacturing Job Shop Scheduling Problem,AMJSP)的特點與作業車間調度問題(Job Shop Scheduling Problem,JSP)的特點近似相等,因此,本文將AMJSP考慮為JSP. JSP對高端制造業的發展和進步的作用至關重要,如今的科技已較為發達,從而車間調度問題也逐漸復雜化,而傳統模式車間調度方案已經無法高效解決JSP問題,因此相應的各種求解車間調度問題的智能算法應運而生,例如遺傳算法(Genetic Algorithm,GA)、粒子群算法(Particle Swarm Optimization,PSO)等.

崔琪等[2]為了求解混合流水車間調度問題,提出了利用變鄰域搜索的方式來改進GA,該方案可有效求解車間調度問題,但其收斂速度較慢. 劉洪銘等[3]提出了一種改進PSO算法的方案,該算法基于自適應權重,提高了粒子利用率,加入了混沌以平衡全局與局部,但其容易丟失種群多樣性. 劉勝輝等[4]提出了一種雙禁忌表禁忌搜索算法,該算法避免了在搜索中容易出現循環的情況,提高了尋優能力. 黃海松等[5]提出了一種改進模擬退火算法以求解雙目標柔性JSP,該算法融合搜索與編碼方法提高了運行速度,避免了傳統的模擬退火算法陷入早熟,提高了算法的全局尋優能力. 施文章等[6]提出一種退火下布谷鳥算法求解JSP問題方案,該方案改善了種群的多樣性. 上述智能算法各有各的特點,以不同程度的效率解決JSP問題,但是隨著車間調度問題的復雜化加上算法的某些局限性,還需進一步對算法進行優化.

綜上所述,本文根據復雜構件制造車間的特點,結合量子計算和蟻群算法提出一種基于量子蟻群算法的智能制造車間調度問題方案,該方案保留了量子計算的高效性,提高了蟻群全局尋優能力,避免了螞蟻易陷局部最優解問題.

1 車間調度問題描述及數學模型

1.1 智能制造作業車間調度問題描述

在智能制造作業車間調度問題AMJSP當中,根據每個工件和每臺機器的信息特點,研究如何安排n個工件在m臺機器上的加工的順序,使得最大完工時間最小. 其加工過程中的基本假設和約束條件為:

(1)加工時,不考慮員工、機器、用電等意外因素;

(2)計算加工時間,不加入材料運輸、工件設備安裝拆卸等時間;

(3)工件的設計工藝都是提前確定好的,都是零時刻到達;

(4)工件工序按照工序順序加工且過程不中斷,對應的機器都是提前確定好的;

(5)一個機器同時只對一個工件的一道工序且該工序只能由該機器完成.

1.2 數學模型

基于上述問題描述和約束條件,建立JSP的數學模型,并構造相應的矩陣. 從上述描述可知,一般概括有n個工件,m臺機器,每個工件最多有m道工序,則對JSP問題的參數的集合分別有:

(1)n個工件的工序集合為J=(J1,J2,…,Jn)T,其中Ji=(ji1,ji2,…,jik,…,jnm)T,i∈[1,n],k∈[1,m],jik表示第i個工件的第k道工序.相應地,工件的工序排列矩陣J:

(1)

(2)n個工件加工使用的機器集合為M=(M1,M2,…,Mn)T,其中Mi=(mi1,mi2,…,mik,…,mnm),i∈[1,n],k∈[1,m],mik表示為第i個工件的第k道工序所加工的機器.相應地,工序所需機器的加工機器矩陣MJ為:

(2)

(3)n個工件的各個工序加工時間的集合為:T=(T1,T2,…,Tn)T,其中Ti=(ti1,ti2,…,tik,…,tnm),i∈[1,n],k∈[1,m],tik表示第i個工件的第k道工序加工所需要的時間.相應地,工序的加工時間矩陣TJ為:

(3)

綜上所述,在智能制造車間調度問題中,給定工件的工序矩陣和相應的生產時間矩陣,求出最短生產時間的目標函數公式定義為:

min[max(Tx)].

(4)

根據上述的約束條件和矩陣,可得出相應的約束公式為:

Cij-Kij-tij=0,

(5)

式中,1≤i≤n,1≤j≤m.式(5)對應的約束條件是工件工序對應的機器是確定的,按照工序順序加工且過程不中斷.Cij是指工件的完工時間.

Kij+tij≤Ki(j+1),

(6)

式中,1≤i≤n,1≤j≤m.式(6)對應的約束條件是加工的工序按著一定的順序開始進行.

Kijq+tij≤Kweq,

(7)

式中,1≤i≤n,1≤j≤m.式(7)對應的約束條件是一個機器同時只能進行一個工件的一道工序且該工序只能由該機器完成.Kweq是指加工w工件的第e道工序在機器q上的進行生產的開始時間.

2 量子蟻群算法的優化機理

量子蟻群算法(Quantum Ant Colony Algorithm,QACA)是由量子計算和蟻群算法結合而成的,以量子計算[7-9]為基礎,可以提高蟻群全局尋優能力,避免螞蟻易陷局部最優解問題.

2.1 量子計算

在QACA中,量子比特對信息素進行編碼,它是一個二維復向量空間中由標準正交基{|0〉,|1〉}所組成的向量單位,其狀態可表示為|ψ〉=|α〉+|β〉,其中α和β滿足|α|2+|β|2=1,表示|0〉和|1〉的概率幅.通過利用量子旋轉門來改變相位可以實現對量子比特的狀態改變,其表示式為(8):

(8)

2.2 量子蟻群算法基本思想

根據文獻[10-12]提出的基于蟻群的啟發式進化算法,可得螞蟻k轉移相鄰節點的概率為式(9):

(9)

圖1 量子蟻群算法流程圖

信息素強度更新方程為:

τij(new)=(1-ρ)τij(old)+Δτij(k),

(10)

(11)

式中,τij(new)表示螞蟻移動的下一個節點;ρ為信息素的揮發性,0≤ρ<1;τij(old)表示螞蟻所在當前的節點;Q為常數.

綜上所述,量子蟻群算法流程為:

步驟1:螞蟻利用轉移概率移動節點;

步驟2:計算各個螞蟻目標函數最優值;

朗讀能夠訓練普通話的發音技巧。學生在一定的量的朗讀訓練之后可以達到吐字清晰，語音響亮，瑯瑯上口，悅耳動聽；能通過語音傳達出文章所表達的感情。

步驟3:利用量子旋轉門、信息素強度方程式更新;

步驟4:若當前滿足迭代次數,則輸出最優解,否則返回步驟1.

3 基于量子蟻群算法的制造車間調度問題求解

將量子蟻群算法(Quantum Ant Colony Algorithm,QACA)應用到求解制造車間調度問題當中,根據工件的工序的加工時間矩陣TJ,可構造一個有向圖,如圖2所示.在圖2中,螞蟻從左邊的開始處開始向ti1移動,下一個移動節點為tij(new),其可移動節點集合表示為:

圖2 基于量子螞蟻的AMJSP有向圖

tij(new)={tpq||i≠p}.

(12)

螞蟻橫向移動時,只能向相鄰的右節點進行移動,向其他節點移動時,移動到的節點不約束.直至螞蟻移動到結束.其中,螞蟻移動過的節點不可能重復移動.

其算法實現步驟如下.

步驟1:初始化,設置各個參數值,其中,螞蟻數與機器數m相同,最大迭代次數DDmax,信息素τij(0)=1,螞蟻量子信息素編碼所有αij和βij初始值都設置為2-1/2.設置基于量子螞蟻的AMJSP有向圖,共n×m個節點.

步驟2:在開始處放入n個螞蟻,最終螞蟻向結束節點移動.節點移動的概率為式(9).

步驟3:設置每個螞蟻所走的節點數組Ak[n×m],即第k個螞蟻所走的節點放入數組中.根據式(9)和式(12)設置可選節點數組Kk[n×m],即第k個螞蟻還未走過的路徑節點的集合.

步驟4:如果螞蟻走完所有節點,則計算出該螞蟻的目標函數值即最短完工時間,記錄當前最低值,否則,執行步驟2.

步驟5:根據式(8)改變量子信息、式(10)和式(11)改變軌跡信息素強度.

步驟6:若當前滿足迭代次數DDmax,則輸出最優解,否則執行步驟2.

4 實驗結果與分析

關于JSP求解若干典型問題,國內外學者專家設計了不同參數,以便測試比較各自的優化性能[13],如表1所示.

表1 不同參數的JSP調度案例

在眾多案例中,關于JSP運用最多的是LA類和FT類,因此,本文選擇該兩類數據案例對基于量子蟻群算法的求解制造車間調度問題進行性能測試. 為了更好的評估,實驗平臺為Windows 10,CPU i7,8G內存,Matlab R2018b仿真軟件,其他實驗仿真環境相關參數如表2所示.

表2 實驗參數

首先對FT06案例進行調度尋優,將所提方案對其進行求解得到的最優解,如圖3所示. 可以看出,基于量子蟻群算法的FT06尋優效率比較快,在執行4次后就可得到最優解,在執行5次的時候就可得到平均解,從此可見,量子蟻群算法在制造車間調度的收斂性能上有優勢,最優解為55.

圖3 基于QACA-AMJSP的FT06尋優解過程

將QACA-AMJSP與GA方案[14-15]、PSO算法方案[16-18]在FT06案例上進行對比,如圖4所示. 可以看出,GA方案的收斂速度較慢且低于PSO方案的收斂速度,而QACA-AMJSP方案的算法收斂速度最快. QACA-AMJSP方案在執行4次時,達到了最優解55. GA在執行6次的時候,達到了最優解58,PSO方案在執行次數到7次時,最優解也達到了55,但總體而言,與GA和PSO方案相比,QACA-AMJSP方案的全局尋優能力較強,收斂速度較快.

圖4 與其他方案的FT06最優解對比圖

然后對LA36案例進行調度尋優,將所提方案對其進行求解得到的最優解,如圖5所示. 可以看出,基于量子蟻群算法的LA36尋優效率比較快,在執行23次后就可得到最優解,在執行24次的時候就可得到平均解,由此可見,量子蟻群算法在制造車間調度的收斂性能上有優勢,最優解為1 268.

圖5 基于QACA-AMJSP的LA36尋優解過程

將QACA-AMJSP與GA方案、PSO方案在LA36案例上進行對比,如圖6所示. 可以看出,GA方案的收斂速度較慢,遠低于PSO方案的收斂速度,而QACA-AMJSP方案的算法收斂速度最快. GA在執行24次的時候,達到了最優解1 574,QACA-AMJSP方案在執行23次時最優解達到了1 268,PSO方案在執行次數到24次時,最優解也達到了1268,但總體而言,與GA和PSO方案相比,QACA-AMJSP方案的全局尋優能力較強,收斂速度較快.

圖6 與其他方案的LA36最優解對比圖

5 結論

提出量子計算與模擬自然界蟻群行為的蟻群算法相結合求解智能制造車間調度問題. 根據智能制造車間的特點,構建了相應的車間調度數學模型. 然后利用量子蟻群算法求解AMJSP,提高了蟻群全局尋優能力,避免了螞蟻易陷局部最優解問題. 實驗結果表明,相比GA和PSO,量子蟻群算法對解決智能制造車間調度問題具有較高的搜索效率和較快的收斂速度. 但是未來智能制造車間會逐漸復雜化,復雜構件的加工精度會越來越細,還需要人工全程參與,因此,下一步研究將人員因素考慮到智能制造車間調度問題中進行求解.