用于多目標雙層優化的嵌套遺傳算法——以混裝線規劃為例*

張 煒，王麗娟，彭精立

（廈門城市職業學院智能制造學院，福建 廈門 361008）

0 引言

工程實踐中的許多重要決策問題往往需要在不同的約束條件下同時處理多個相互沖突的目標。即多目標優化問題（Multi-objective Optimization Problem，MOP）[1-2]。MOP 的目標涉及相同或不同的一組決策變量，這些變量是相互約束的。由于每個目標的工程意義和尺寸不同，導致解決MOP存在一定的難度。

MOP 的目的是在優化目標之間進行權衡。傳統的解決方案是將其轉化為一個單一的目標問題。常見的方法有加權和法[3]、目標規劃法[4]、e約束法等[5]。例如，張波等[6]提出了多規則融合算法，有效地表征了裝配工藝和有限資源等剛性約束。通過航空發動機脈動式裝配過程實例驗證，證明了所提算法在隨機擾動、反復迭代和群體計算等方面的優勢。易建洋等[7]建立混裝線平衡和物料配送聯合優化數學模型。提出遺傳算法在仿真軟件里的應用仿真，并通過實例驗證方法研究的有效性。針對訂單分配與排序時存在的分配方案不合理、交期久等問題，以最小化最大完成時間和拖期時間為目標函數的訂單分配和排序兩級目標優化模型，利用基于參考點的快速非支配遺傳算法優化求解得到優化方案[8]。針對MOP，沒有單一的解決方案可以使所有目標同時達到最優。各類優化方法將不可避免地削弱一些目標。

因此，本文首先分析了多個目標之間的層次關系。將多目標轉化為多個單目標函數進行分層優化，使得優化過程更符合實際情況。

MOP 可以通過雙層編程來解決。雙層規劃廣泛應用于工程設計[9]、經濟管理和資源分配[10-12]。例如，Calvete和Gale[13]研究了上下兩級線性分式的雙層規劃問題，并給出了相應的遺傳算法。針對多條異構混裝線之間加工能力、作業時間不等效的特征，提出面向柔性定制的并行不等效生產計劃模型。提出一種結合Pareto 前沿解的改進遺傳算法，采用小生境技術保證種群多樣性[14]。Charnes 和Cooper[15]將多目標優化問題轉化為兩個線性規劃問題。通過求解兩個線性問題得到了相應分式規劃的最優解。不同的算法與雙層規劃方法相結合促進了多目標優化問題的不斷發展。本文以某混裝線規劃為例說明了雙層規劃的工程應用。針對該模型提出了一種嵌套遺傳算法。

1 混裝線平衡和排序

假設M系列產品需要在一個生產計劃周期T內生產。每個型號的總產品需求為DM，m∈{1,2,…,m,…,M}。每個產品的每個任務的優先級關系是預定義的。在一定的優化條件下，需要確定所有產品的生產順序。如果不同產品的總需求的最大公約數是g；最小生產周期單位為dm，可以表示為向量（d1，d2，…，dm，…，dM）。在計劃周期時間內，只訂購具有最小生產周期單元的產品，并重復g個過程。該規劃包含兩個問題：平衡和排序。

大多數關于混裝線平衡的研究都是基于綜合作業優先圖，它將多個產品的負載平衡轉化為單個產品的裝配線平衡問題[16-17]。例如，吳永明等[18]針對產品需求多樣化、工藝及設備動態變化，裝配線平衡方案需不斷調整，提出裝配線演進平衡方法，通過改進粒子群優化算法進行優化，所提算法增加粒子的多樣性和搜索能力，加快算法的搜索速度。以一個生產實例驗證了該方法的有效性和可行性。

對于混裝線排序問題，傳統的策略是使用遺傳算法[19]、蟻群算法[20]等。例如，江新利等[21]研究具備有限緩沖特征的兩階段排序問題，考慮生產系統的發泡設備約束，分別對預裝線與發泡線模具排序進行研究，使二者盡量匹配，減少在制品庫存數量。

混裝線平衡是混裝線排序的基礎，排序的結果用于評估平衡的好壞。姜東等[22]針對混流裝配線平衡排序優化問題，提出了一種多目標模擬退火算法。提出的模擬退火算法在初始化中將啟發式任務分配規則融入平衡問題，根據產品投產需求隨機生成產品序列；通過測試標準問題實驗，對所提出的算法進行參數校驗。

2 多目標雙層優化模型

平衡與排序的優化設計問題本質上是一個雙層規劃問題[23]。基于雙層規劃模型的理論框架，可以建立問題的決策機制。

2.1 上層優化問題

模型的上層需要對產品族的任務分配做出決策，即在滿足作業優先順序的前提下，將產品族任務分配給工作站。評估的基本標準是工作站內部工作負載平衡、工作站之間工作負載平衡和動態平衡的綜合利益。

混裝線平衡。在混裝線中，不同產品的類似任務可能具有不同的操作時間。產品的每個任務也可以有不同的操作時間。因此，當這些任務中的一些被分配給工作站時，工作站的工作負載時間可能達到給定的循環時間。因此，需要考慮每個工作站上不同產品的工作負載的平衡，以及不同工作站之間的工作負載平衡。所提出的工作站內部工作負載平衡和工作站之間工作負載平衡的目標分別用式（1）和式（2）表示。

式中：J1為工作站內部工作負載平衡；J2為工作站之間工作負載平衡；M為產品族混裝線上生產的產品種類；m為產品族混裝線上生產的第m種產品；i為產品族的第i個任務；S為產品族混裝線的站點數量；j、k分別為產品族混裝線上的第j、k個站點；Tmj、Tmk為第m種產品分配到j、k工作站的總工作時間；qm為第種產品需求百分比；tim為第m產品第i個任務的作業時間；Qim為加權系數；為分配到j站內的所有任務的加權平均作業時間。

2.2 下層優化問題

混裝線排序。由于不同產品的類似任務的操作時間并不總是相同的，當這些任務分配到一個工作站時，不同的排產順序會導致不同的等待時間。假設混裝線上的工作站的工作時間是z工作站中最大的，則其他工作站必須等待工作站完成工作，然后才能整體移動。因此，在每個工作站中，每個工作站的工作時間與該狀態下工作站的最大工作時間之間的平衡是需要考慮的目標函數。目標函數設置如式（3）所示。

式中：J3為每個工作站的工作時間與該狀態下工作站的最大工作時間之間的平衡；tzk為z狀態下k工作站分配到的任務的作業時間；maxtzk為z狀態下的所有工作站分配到的任務的作業時間的最大值；d為產品族各產品需求最小比例集之和。

上層目標函數考慮了混裝線的平衡和排序問題。本文以工作站內部工作負載平衡、工作站間工作負載平衡和動態平衡之間的最小乘積為上層目標函數，如式（4）所示。

模型的下層是混裝線的投產排序決策。排序決定了每個工作站的負荷水平和材料需求的進度，這些都與成本有關。目標函數可以用式（3）來表示。

2.3 雙層優化

基于以上對上下層目標需求的分析，可以建立混裝線平衡和排序的兩級優化模型：

3 嵌套遺傳算法

問題的變量可以分為兩部分：平衡決策變量和排序決策變量。每組平衡決策變量對應于一組最優排序決策變量。兩組變量處于不同的層級。如果使用經典的遺傳算法來求解，收斂速度會很慢，并且可能很難收斂到全局最優解。為了克服經典遺傳算法的缺點，加快收斂速度，將染色體分為兩段，分層次進行嵌套搜索。

3.1 平衡遺傳算子設計

平衡遺傳算子的設計主要包含以下4步。

（1）為了解決每個工作站中每個產品的任務分配，即求解變量Xijm以實現混裝線平衡，本文采用了基于操作序列的表達式，并使用浮點編碼方法。對于給定的產品m，任務i被分配給工作站j。所有任務形成一個任務序列，完成任務序列的工作站數量就是解決的問題代碼，如圖1所示。

圖1 編碼和解碼

（2）初始化種群，即生成一系列符合條件的個體。由于混裝線上同時生產m種不同的產品，因此需要將每種產品的所有操作任務分別分配到所有工作站。

（3）在選擇操作中，使用最優保存策略和輪盤賭。最優保存策略將幾個具有高度適應性的個體直接復制到下一代，而其他個體則使用輪盤選擇。在輪盤賭方法中，每個個體進入下一代的概率等于其適應度值與該個體在整個種群中的適應度值之和的比率。本文使用目標函數F（Y，X）的倒數作為適應度函數。

（4）交叉和變異如圖2 所示。采用兩點交叉法，從選擇操作產生的個體中選擇兩條染色體（如圖2（a）所示），并在染色體上任意確定兩個交叉點。兩條染色體在交叉處被分成3 部分。父代1 染色體的中間染色體（3，6，2）按父代2 染色體（2，6，3）的順序排列，形成新的子代1。類似地，父代2染色體的中間基因（7，4，6）按照父代1 染色體（4，6，7）的順序排列，形成新的子代2。為了避免過早收斂和陷入局部最優，在滿足優先級約束關系的前提下，采用了交叉變異方法。從種群中任意選擇個體的任何染色體（任務）進行變異，在交換之后，它不會違反任務之間的關系（圖2（b））。

圖2 交叉和變異

3.2 排序遺傳算子設計

排序遺傳算子設計如下。

（1）在最小生產周期單元中，生產序列的編碼采用浮點編碼方式，如圖3所示。

圖3 排序的編碼

（2）在種群初始化過程中，隨機產生了一個具有個體數量P的排序種群。目標函數是適應度函數J3。本文仍然使用輪盤賭來選擇和留住最優秀的個體。

（3）至于交叉，使用基于切割點隨機交叉的方法從隨機生成的排序群體中隨機選擇兩個父代個體。選擇一個染色體位置作為這兩個個體的切割點，并將它們切割成前一部分和后一部分，如圖4（a）所示。從父代2 中逐個搜索滿足父代1 后端序列的染色體，并將其作為子代1 的后端。父代2 的剩余染色體被保留為子代1的早期染色體。

圖4 排序群體的交叉和變異

關于突變，本文使用反轉突變方法（圖4（b）），在父代染色體上隨機產生兩個突變點，并反轉中間部分的基因序列，以獲得新一代染色體。

3.3 用于雙層規劃的嵌套遺傳算法

針對上述雙層優化解的直接求解方法，提出了一種嵌套遺傳算法用以生成X和Y。該算法分為上層和下層，分別設計用于平衡和排序。具體流程如圖5所示。

圖5 嵌套遺傳算法流程

步驟1：初始化種群，并根據上層變量大小隨機生成種群個數N。

步驟2：確定種群是否滿足上層約束條件，如果是，則將參數代入下層；如果沒有，則將適應度設置為零，轉移到步驟3。

步驟3：確定是否達到最大迭代次數，如果達到，記錄最佳值，然后進入步驟4；如果沒有，則進入排序、選擇、交叉和突變的過程，然后轉入步驟2；將上層可行個體引入下層，并初始化下層群體Y（X）。

步驟4：驗證基礎種群的可行性，如果可行，進行適應性評估；如果不可行，請將適應度設置為0。

步驟5：確定較低層次的種群是否達到最大迭代次數，如果達到，則記錄最低個體和最優值；如果沒有，則返回步驟4并重復，直到達到最大迭代次數。

步驟6：將下層的最優個體和最優值J3轉移到上層，評估適合度值。

步驟7：確定種群是否達到了最大迭代次數，如果達到，則記錄最優解和最優值；如果沒有，則重復步驟3，直到達到最大迭代次數。

4 應用分析

以某客車焊接車間混焊接生產線生產的一系列A、B、C型客車為研究對象，客車產品族的綜合作業優先圖如圖6所示。在生產計劃周期內，3種產品的計劃產量分別為DA=8、DB=12、DC=8。因此，在最小生產周期內，每種產品的需求分別為dA=DA/4=2，dB=DA/4=3，dC=DA/4=2。每個產品的任務時間如表1所示。

表1 產品族工序作業時間

圖6 裝配作業優先圖

為了證明嵌套遺傳算法的有效性，選擇了傳統的遺傳算法和粒子群算法來解決上述問題。傳統的遺傳算法使用順序優化方法來解決這個問題。首先，求解平衡的最優值。其次，在平衡的基礎上，求解排序的最優值。另外，使用粒子群算法的“歸一化”方法同時求解了J1J2J3。與嵌套遺傳算法不同，在求解過程中沒有交互過程，即平衡方案只對應于一個排序情況。

各種方法的混裝線規劃優化結果如表2 所示。從表中可以看出，除了目標函數J2之外，本文所提方法在每個指標上都優于其他算法。盡管順序優化的求解方法在求解平衡時獲得了更好的結果。然而，在排序問題的優化過程中，由于解域的限制，只能得到次優解。對于“歸一化”的并行解決方案，即同時解決平衡和排序問題，這將導致優化結果的隨機性。一般來說，嵌套遺傳算法那的整體優化效果可以比其他3 種方法獲得更好的結果。

表2 各算法優化結果對比

5 結束語

工程多目標優化問題屬于NP難題，很難找到全局最優解。針對一般的多目標決策問題，本文分析總結了兩級決策方法和歸一化方法求解過程存在的缺陷，提出了一種嵌套遺傳算法。將該方法和算法應用于混裝線的平衡和排序。通過分別對裝配任務和產品進行編碼，使用嵌套遺傳算法對平衡和排序進行優化。

以一個混合模型焊裝生產線的平衡和排序問題為例，將所提算法和傳統歸一化方法、順序優化方法進行對比，對比的結果表明，該算法可以獲得令人滿意的結果。多目標優化仍然是一個NP難題。如何找到一個更客觀、更現實的優化目標，如何對其進行更合理的評估，并提出更有效的算法，還有待進一步探索。