用于多目標(biāo)雙層優(yōu)化的嵌套遺傳算法——以混裝線規(guī)劃為例*

張 煒，王麗娟，彭精立

（廈門城市職業(yè)學(xué)院智能制造學(xué)院，福建 廈門 361008）

0 引言

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

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

因此，本文首先分析了多個目標(biāo)之間的層次關(guān)系。將多目標(biāo)轉(zhuǎn)化為多個單目標(biāo)函數(shù)進(jìn)行分層優(yōu)化，使得優(yōu)化過程更符合實際情況。

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

1 混裝線平衡和排序

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

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

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

混裝線平衡是混裝線排序的基礎(chǔ)，排序的結(jié)果用于評估平衡的好壞。姜東等[22]針對混流裝配線平衡排序優(yōu)化問題，提出了一種多目標(biāo)模擬退火算法。提出的模擬退火算法在初始化中將啟發(fā)式任務(wù)分配規(guī)則融入平衡問題，根據(jù)產(chǎn)品投產(chǎn)需求隨機生成產(chǎn)品序列；通過測試標(biāo)準(zhǔn)問題實驗，對所提出的算法進(jìn)行參數(shù)校驗。

2 多目標(biāo)雙層優(yōu)化模型

平衡與排序的優(yōu)化設(shè)計問題本質(zhì)上是一個雙層規(guī)劃問題[23]?；陔p層規(guī)劃模型的理論框架，可以建立問題的決策機制。

2.1 上層優(yōu)化問題

模型的上層需要對產(chǎn)品族的任務(wù)分配做出決策，即在滿足作業(yè)優(yōu)先順序的前提下，將產(chǎn)品族任務(wù)分配給工作站。評估的基本標(biāo)準(zhǔn)是工作站內(nèi)部工作負(fù)載平衡、工作站之間工作負(fù)載平衡和動態(tài)平衡的綜合利益。

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

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

2.2 下層優(yōu)化問題

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

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

上層目標(biāo)函數(shù)考慮了混裝線的平衡和排序問題。本文以工作站內(nèi)部工作負(fù)載平衡、工作站間工作負(fù)載平衡和動態(tài)平衡之間的最小乘積為上層目標(biāo)函數(shù)，如式（4）所示。

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

2.3 雙層優(yōu)化

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

3 嵌套遺傳算法

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

3.1 平衡遺傳算子設(shè)計

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

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

圖1 編碼和解碼

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

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

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

圖2 交叉和變異

3.2 排序遺傳算子設(shè)計

排序遺傳算子設(shè)計如下。

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

圖3 排序的編碼

（2）在種群初始化過程中，隨機產(chǎn)生了一個具有個體數(shù)量P的排序種群。目標(biāo)函數(shù)是適應(yīng)度函數(shù)J3。本文仍然使用輪盤賭來選擇和留住最優(yōu)秀的個體。

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

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

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

3.3 用于雙層規(guī)劃的嵌套遺傳算法

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

圖5 嵌套遺傳算法流程

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

步驟2：確定種群是否滿足上層約束條件，如果是，則將參數(shù)代入下層；如果沒有，則將適應(yīng)度設(shè)置為零，轉(zhuǎn)移到步驟3。

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

步驟4：驗證基礎(chǔ)種群的可行性，如果可行，進(jìn)行適應(yīng)性評估；如果不可行，請將適應(yīng)度設(shè)置為0。

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

步驟6：將下層的最優(yōu)個體和最優(yōu)值J3轉(zhuǎn)移到上層，評估適合度值。

步驟7：確定種群是否達(dá)到了最大迭代次數(shù)，如果達(dá)到，則記錄最優(yōu)解和最優(yōu)值；如果沒有，則重復(fù)步驟3，直到達(dá)到最大迭代次數(shù)。

4 應(yīng)用分析

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

表1 產(chǎn)品族工序作業(yè)時間

圖6 裝配作業(yè)優(yōu)先圖

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

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

表2 各算法優(yōu)化結(jié)果對比

5 結(jié)束語

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

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