基于改進遺傳算法的可重構制造系統快速配置*

洪胡平,張為民,謝樹聯

(同濟大學機械與能源工程學院,上海 201800)

0 引言

如今制造企業面臨著市場需求的快速波動與個性化發展趨勢,需要通過生產定制化產品來滿足消費者的不同需求。在這種情況下,高水平的定制是制造企業的關鍵競爭力。為此,制造企業必須擁有快速響應市場變化的新型制造系統?？芍貥嬛圃煜到y(reconfigurable manufacturing system,RMS) 由于其可重構性[1],能夠通過快速改變其配置,為每個需求期提供精確的功能和能力,是應對這一問題的有效解決方案。

RMS的流水線配置可以分為兩類:單零件流水線(single-product flow-line,SPFL)配置以及多零件流水線配置[2]。針對RMS的流水線配置優化問題,國內外學者都進行了一定的研究。BORTOLINI等[3]提出了一種具有替代零件布線和多個需求期的RMS配置優化模型,以平衡系統組建成本為目標,使用遺傳算法進行求解。徐修立等[4]針對大規模定制生產模式,建立了設備配置優化的0-1混合整數規劃模型,并設計采用了遺傳模擬退火算法求解。SMEDBERG等[5]針對多零件流水線的RMS配置,設計了一種知識驅動優化的方法,以加速RMS應用中的收斂。牟健慧等[6]針對分布式置換流水車間問題,以最小化調整加工時間為目標,建立流水車間逆調度數學模型,提出了一種混合遺傳優化算法進行求解。BATTAIA等[7]開發了一個混合整數編程模型,用于配置由可重構機床組成的流水線,以最小化設備成本。周鵬鵬等[8]針對柔性作業車間調度問題,以最大完工時間最小為目標,設計了一種混合遺傳算法進行求解。杜百崗等[9]構建了一個流水車間柔性分批調度模型,該模型以最小完工時間和最小加工成本為目標,并采用第二代多目標遺傳算法進行求解。陽光燦等[10]針對最小化最大完工時間目標的柔性作業車間調度問題,提出了一種改進編碼方式的遺傳算法。

在關于大規模定制背景下RMS的流水線配置問題的現有研究中,大多數工作僅考慮基于單一成本/時間的配置尋優,而同時考慮多個優化目標的研究較少,且所采用的算法也以單一尋優算法為主。

針對上述問題,本文以RMS中的SPFL配置為研究對象,基于3個優化目標:設備負載均衡度、產品生產時間以及產品生產成本,來建立系統制造資源配置模型,并構建了一種多目標遺傳-鄰域搜索(non-dominated sorting genetic algorithm-neighborhood search,NSGA-NS)混合算法對其優化求解。NSGA-NS算法中,針對遺傳算法局部搜索能力較差以及易受初始種群優劣影響等問題,受鄰域概念啟發,對每一次交叉變異后的個體進一步進行鄰域搜索,以充分發揮不同算法各自的優勢,獲得更好的求解效果。最后通過與歸檔式多目標模擬退火算法(archived multi-objective simulated annealing,AMOSA)[11]、第三代多目標遺傳算法(non-dominated sorting genetic algorithm-Ⅲ,NSGA-Ⅲ)、多目標粒子群優化算法(multiple objective particle swarm optimization,MOPSO)以及一種在MOPSO基礎上改進的多目標退火式粒子群算法(multiple objective annealing particle swarm optimization,MOAPSO)進行比較,驗證其效果。

1 問題描述

對于一個確定的產品,可以將其劃分為一系列加工特征的集合,產品的每一個加工特征由一道工序完成,一道工序僅使用一種工藝類型、設備與刀具,全部工序對應的工藝類型、設備與刀具的集合是該問題的一個配置解。工序所采用的工藝、設備以及刀具存在多種選擇,一個產品所對應的配置解空間十分龐大。本文所關注的問題是針對新的產品,從配置解空間中選擇適當的配置資源,以用于制造系統的搭建或重構,并完成新產品的生產。

基于以上描述,主要以機加工行業為參考,進行如下假設:

(1)產品的加工特征劃分可能存在不同的方案,即可行操作順序[12]?？山Y合可選設備的加工能力范圍、專家知識等制定,這些方案是已知的且本文僅對其中一種操作順序進行配置優化;

(2)一道工序所需刀具的數量與加工時長相關,向上取整;刀具的安裝時間、磨損更換時間、安裝或磨損更換的單位時間成本均為常量,與設備無關;

(3)若相鄰工序所選設備相同,仍用不同的圖例表示,但計算優化目標時視為共用設備;

(4)不考慮設備和物料運輸系統的故障與維護問題;所有設備在制造系統運行過程中均開機,不考慮物料運輸系統的待機成本;

(5)物料運輸成本與運輸距離成正比,運輸距離由設備正常工作所需最小空間決定,最小空間對設備而言為定值;

(6)物料運輸系統的運輸能力足夠,不會導致生產節拍緩滯,生產節拍的快慢只與加工特征、工藝、設備和刀具有關;

制造系統配置在滿足新產品的生產需求的同時,還應盡可能提高生產效率、降低產品的生產成本和避免轉換時的時間浪費。設備負載均衡度直接關系到整個制造系統的生產效率,如果機床設備的負載均衡度較高,就會出現某些設備空閑,而另外一些設備過度負荷的情況,進而導致生產效率低下,資源利用率不充分。因此本文對最優配置的評價除了考慮產品生產時間與生產成本外,還需考慮到設備的負載均衡度。

2 模型構建

2.1 三元組合集

表1表示的是三元組合集的示例。一個三元組合包括一道工序所選擇的工藝類型、設備類型以及刀具類型,這道工序的執行可以由該三元組合唯一確定。例如,第二列顯示,特征J2的操作工藝P1由包含刀具T2的設備M2來執行。為每一個特征選擇一個可行的三元組合,便構成三元組合集,即配置優化問題的一個配置解。

表1 三元組合集示例

2.2 優化目標計算

2.2.1設備負載均衡度

通過對SPFL進行分析,可計算出設備m的負載率Wm,式(1)表示設備負載率[13]的計算方式,其中,TMm表示設備m的所有加工工時,NP表示待加工產品數量,TJi表示i號三元組合對應的加工時間,THm表示設備m的所有準備工時,包括切換刀具的時間以及刀具磨損后更換刀頭所需的時間;T表示總加工時間,由式(6)給出。

SPFL的負載均衡度W體系生產線設備負載率的平衡程度,用數學模型表示為:

(1)

(2)

(3)

(4)

(5)

式中:TT表示安裝一次刀具所需時間,TT′表示刀具磨損后更換刀頭所需要的時間,kj表示加工j特征需要的刀具易耗件數量,由式(5)給出;TSt表示t型刀具的磨損更換加工時長。

(6)

2.2.2 產品生產時間

在生產出第一件產品后,之后的產品將按照一定的生產節拍TA產出。由于制造系統可能存在設備共用的情況,因此本文中生產節拍TA可按照在不同型號設備上的生產流程中的瓶頸時間來確定。

T=TP+(NP-1)·TA

(7)

式中:TP表示單件產品的生產時間,MSm表示m型設備所需的最小運行空間,TV表示物料運輸的平均運輸速度。

(8)

(9)

2.2.3 產品生產成本

產品的總生產成本C主要由工序加工成本、設備待機成本、刀具磨損更換成本、物料運輸成本、原材料成本等組成。其中,CJi表示i號三元組合的加工成本,CTt表示t型刀具的價格,CWm表示m型設備的單位待機時間成本,CD表示單位運輸距離的物料運輸成本,CP表示單件產品的原材料成本。

(10)

本模型的優化目標函數為:

(11)

3 模型求解方法

RMS的制造資源配置問題屬于典型的NP-Hard問題,考慮通過啟發式算法來解決。

對于多目標優化問題,目標之間往往量綱不同、互相沖突,難以像單目標優化問題一樣直接比較目標值來確定兩個解之間的優劣。因此通過帕累托非支配排序算法來進行最優解的選擇,解空間中所有非劣解的集合即帕累托前沿解集。

3.1 編碼與解碼

待加工產品所需的加工工序數量n=len(J),通過一個n維向量來表示解,如表2所示。位置分量Xi表示工序i所選的三元組合。其值為0～1之間的實數,即工序i所選的三元組合在可選三元組合集中的位置。

表2 解向量示例

圖1所表示的是前兩個分量的解碼過程,由一個解向量到一個配置的解碼主要基于工序可選三元組合集。工序可選三元組合集在尋優之前生成,其主要基于車間現有的設備和刀具,可隨設備和刀具的增減同步更新。由位置分量Xi,可以通過等概率輪盤賭算法唯一確定第i道工序選用的三元組合,得到對應的一個配置。

圖1 解向量到配置的解碼

3.2 多目標遺傳-鄰域搜索算法

遺傳算法參考的是生物界的自然選擇規律,不同個體之間通過染色體交叉以及變異產生新的個體,并以一定的生存規則對所有個體進行選擇,這里的生存規則即為算法中的目標函數。NSGA-Ⅲ與其他多目標遺傳算法的區別在于最后一個帕累托前沿的選擇機制,其使用基于參考點的選擇,相較于擁擠度而言,在3個以上優化目標的情況下仍然能夠很好地保持種群的多樣性。

遺傳算法具有隨機搜索能力,利用適當的交叉變異操作能夠有效避免局部最優乃至獲得全局最優。但正是由于其全局隨機性,導致其收斂速度較慢。而鄰域搜索算法具有快速的局部最優搜索能力,因此考慮結合鄰域搜索對遺傳算法進行改進,提高搜索效率,以實現制造資源的快速配置?；贜SGA-Ⅲ對每一次交叉變異后的個體進行鄰域搜索,鄰域搜索算法與模擬退火中使用的一致,依賴于特征可選三元組合集。隨機選取當前解中一個特征的三元組合,在該特征的特征可選三元組合集中,隨機選取一個除當前組合以外的組合,替換該三元組合,以此作為當前解的鄰域解。在本文中,命名為NSGA-NS算法,算法流程如圖2所示。

圖2 NSGA-NS流程

4 配置案例

4.1 配置案例描述

本節通過一個案例對前述問題與算法模型進行探討。目前有一批待生產的液壓閥閥塊,需要從供應商能夠提供的且滿足制造商需求的設備、刀具中選擇合適的配置搭建制造系統以完成生產。

液壓閥閥塊的加工特征已通過交鑰匙工程平臺中的特征提取功能模塊獲取,采用傳統機加工工藝,可以得到可行的加工特征劃分方案,如圖3所示。

圖3 液壓閥閥塊加工特征

可供選擇的設備、刀具的型號數量分別為30、50。設備和刀具供應量是充足的。除案例涉及的各項數據及配置計算結果[14]外,各項全局參數的取值如表3所示。

表3 全局參數取值

4.2 配置結果比較

為驗證本文所構建的NSGA-NS的效果,開發了AMOSA、NSGA-Ⅲ、MOPSO、MOAPSO四種算法用于比較。其中,AMOSA的算法流程與文獻[11]中所述一致。MOAPSO是基于MOPSO改進的一種優化算法。

MOPSO的一個突出特點是收斂速度快的同時容易陷入局部最優解,而模擬退火算法由于其基于溫度系統的劣解保留策略,能夠在一定程度上跳出局部最優。因此考慮在粒子群優化算法中引入溫度條件,根據溫度來調整速度更新的慣性權重,同時在個體最優解的更新中以一定概率接受劣解,所形成的算法即為MOAPSO。

為便于比較,將不同算法相同性質的參數設為一致:對每一次計算,保證初始種群/粒子群一致,鄰域解/子代數量均為100,總體最大迭代次數均為300,歷史最優種群/解集持續未變化的最大迭代次數均為50。各算法參數設置如表4所示。

表4 算法參數設置

4.2.1 配置結果的評估指標

除運算時長CT外,本文通過兩個指標來對不同算法得到的帕累托前沿解的尋優性、收斂性和多樣性進行評估,以比較多目標優化算法的質量。超體積HV[15-16]涵蓋了各算法的尋優性、收斂性與多樣性特征,能夠較為全面的評價目標算法的優劣。DPO表示各算法最后一代前沿解未被其他算法的前沿解支配的比例,直觀地顯示了各算法的解之間的支配性,體現算法尋得的前沿解的質量。

(12)

(13)

式中:Q表示所評估的算法得到的非支配解的集合,δ為勒貝格測度,vi為Q中的第i個帕累托解與參考點間構成的超體積,參考WHILE等[17]提出的方法計算;|PS(Q)|表示Q中未被任意其他算法獲得的解支配的解的數量。計算超體積的參考點取所有算法得到的帕累托解在各優化目標上的極值。在計算之前,對所有帕累托解進行規范化處理。

4.2.2 配置結果分析

算法程序采用Python3編寫,程序運行環境為Windows 11,處理器為AMD Ryzen 75800H8-Core Processor 3.2 GHz,進行4次計算。各優化算法結果指標如表5和圖4所示。

表5 不同算法比較

結合各算法運算時長以及超體積參數,觀察與分析如下:

(1)就各算法的前沿解質量而言,從各算法最后一代前沿解未被其他算法的前沿解支配的比例可以看出,NSGA-Ⅲ與NSGA-NS的前沿解質量相對于其他3種算法有巨大優勢。其中NSGA-NS相較于NSGA-Ⅲ有一定提升,MOAPSO相較MOPSO有微小的領先。

(2)就各算法計算速度而言,在保證各算法每次迭代生成的領域解/種群數量一致的前提下,NSGA-NS的速度最快,相較NSGA-Ⅲ速度提升接近一倍;其次是AMOSA、MOPSO與MOAPSO的計算速度相較于其他算法有大幅降低,MOAPSO略快于MOPSO。主要原因在于本文中開發的算法均未進行并行計算,粒子群算法的多粒子并行搜索下對計算速度的提升是巨大的。

(3)通過超體積對算法收斂性進行觀察,在收斂性方面,各算法均表現較好;在收斂迭代次數方面,MOAPSO表現最好,在40～50代內達到收斂,相較MOPSO有一定提升;NSGA-NS收斂迭代次數相較NSGA-Ⅲ有明顯提升;AMOSA收斂迭代次數相對較差,在迭代末期仍保持緩慢上升趨勢。

(4)通過超體積對算法尋優性能進行觀察,NSGA-NS與NSGA-Ⅲ相較于其他3種算法有明顯優勢,其帕累托前沿明顯比AMOSA、MOPSO和MOAPSO更靠近全局最優前沿。MOPSO在尋優性能方面與AMOSA類似,MOAPSO相較MOPSO有較大提升。

通過以上配置結果可知,NSGA-NS與NSGA-Ⅲ在前沿解質量上相對其他算法有顯著優勢,相較于NSGA-Ⅲ,NSGA-NS在大幅縮短運行時長的情況下,收斂速度略有提升,同時尋優性能沒有劣勢;MOAPSO相較MOPSO,在略微縮短運行時長的情況下,顯著提高了算法的尋優性能,兩種混合相對于原算法均取得了比較好的效果。比較MOAPSO與NSGA-NS兩種算法,NSGA-NS在收斂速度略微低于MOAPSO的情況下,尋優性能顯著強于MOAPSO。

5 結束語

本文針對RMS的SPFL快速配置問題,開展了配置模型構建與求解方法的研究。成果總結如下:

(1)建立了一套用于可重構系統快速配置的模型,綜合考慮了產品加工特征、工藝、設備和刀具等多個配置因素,以設備負載均衡度、產品生產成本和產品生產時間作為優化目標,并應用于一個液壓閥閥塊加工案例。

(2)開發了混合啟發式算法以求解上述模型:結合鄰域搜索對NSGA-Ⅲ進行改進, 對交叉變異后的個體進一步進行鄰域搜索,構建了NSGA-NS算法。

(3)對上述5種優化算法進行比較,結果表明,NSGA-NS和NSGA-Ⅲ在前沿解質量上顯著優于其他算法。在計算速度方面NSGA-NS最優,其次是AMOSA與NSGA-Ⅲ;MOPSO與MOAPSO的計算速度相較其他3種算法表現較差。MOAPSO在收斂迭代次數方面最優,但結合計算時間來看,收斂速度并不理想?？傮w而言,NSGA-NS解決了NSGA-Ⅲ收斂速度慢的問題,使得NSGA-NS既能夠保持NSGA-Ⅲ的全局尋優性能,又能夠顯著提高其運行效率,在5種算法中表現最佳。