基于改進遺傳算法的機器人裝配線平衡研究

摘 要：針對機器人裝配線平衡問題，本文構建以最小化節拍時間和能耗為目標的數學模型，并提出了一種基于改進遺傳算法的優化方法。首先，建立數學模型來描述機器人裝配線平衡問題。其次，優化算法引入Pareto前沿排序、精英策略和擁擠距離計算等方法來提升算法的綜合性能。最后，試驗結果表明，本文算法在不同規模的實例問題中的優化效果均較好，與傳統算法相比，本文算法效率更高，能耗更低。本文算法為提高裝配線的生產效率和節能效果提供了新的解決方案。

關鍵詞：機器人裝配線平衡；雙目標優化；非支配排序遺傳算法；能耗" " 中圖分類號：TG 95；TP 18" " " " 文獻標志碼：A

在汽車制造和電子工業領域中，裝配線應用廣泛，隨著智能制造和人工智能的迅速發展以及《中國制造2025》[1]戰略的實施，工業機器人逐漸替代人工，執行繁重、重復和危險的裝配任務。因此機器人裝配線平衡問題（Robotic Assembly Line Balancing Problem，RALBP）受到了廣泛關注。

RALBP是在生產調度過程中一類經典的非確定性多項式（NP-hard）組合優化問題，對制造企業經濟效益有重要影響[2]。周炳海[3]提出了一種改進的基于分解的多目標進化算法來實現機器人裝配線工作站數量最小化和總能耗最小化2個目標。本文提出基于能耗和節拍時間的RALBP雙目標優化問題。節拍時間是衡量生產效率的重要指標，其優化能夠提升裝配線的整體產出能力，能耗降低是綠色制造與可持續發展戰略的核心要求之一。在優化過程中，這2個目標通常會相互制約，構成了一個復雜的雙目標優化問題。為了有效解決這個問題，本文提出了一種基于帕累托（Pareto）的改進遺傳算法，其目的是找到能耗與節拍時間之間的最佳平衡點，為制造企業高效、節能生產提供有力支持。

1 問題闡述

在機器人裝配線中，每個工作站需要分配合適的機器人執行不同的裝配任務，給定一條裝配線L，包括若干個工位S={S1，S2，...，Sn}、任務N={N1，N2，...，Nm}和機器人H={H1，H2，...，Hr}，將任務N分配至工位S，并在每個工位Si指派合適的機器人Hi，使整體裝配效率最大化。11個裝配線任務、4個工作站以及不同類型的4種機器人的分配示意如圖1所示。

1.1 假設

為了描述機器人裝配線平衡問題，進行如下假設[4]。1）裝配線只生產一種單一產品。2）工序與工序間的優先關系是已知的。3）各裝配任務不可再分，并且滿足優先關系。4）每項任務的時間和能耗由執行該任務的機器人決定，并且該機器人的執行時間和能耗是固定的。5）在最短時間內完成任務的機器人為最佳選擇。6）任務和機器人分配不受限制。7）工作站的數量等于機器人類型的數量。8）物料搬運、裝卸時間、設置以及換刀時間可以忽略不計，或包含在任務時間內。

1.2 數學模型

在機器人裝配線平衡過程中，1個任務只能分配到1個工作站中，每個工作站中只有1個機器人，如公式（1）、公式（2）所示。

式中：xis為決策變量，判斷任務i是否分配到工作站s。

式中：ysh為決策變量，判斷機器人h是否分配至工作站s。

在裝配線平衡過程中，周期越短，生產效率越高，能耗越底，越節能、環保。目標函數計算過程如公式（3）、公式（4）所示。

式中：E為能耗；minE為最小能耗；s為工作站；Nw為工作站總數；Na為任務總數；i為任務編號；eih為機器人h處理任務i的能量消耗。

式中： c為循環時間；minc為最小周期； tih為機器人h處理任務i的時間。

約束條件如公式（5）～公式（10）所示，公式（5）定義了任務之間的優先關系，其保證對有先后順序關系的一對任務來說，先行任務不會被分配到比其后繼任務更晚的工作站。公式（6）保證每個任務必須分配給1個工作站，公式（7）保證每個工作站配備1個機器人。公式（8）保證每個機器人只能被分配到1個工作站。

式中：為任意任務i；pre（j）為在優先網絡中設置j的中間前置任務；i、j為不同的任務編號。

式中：s為任意工作站s。

式中：h為任意機器人h。

2 非支配遺傳算法

非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithms，NSGA）是SRINIVAS和DEB[5]1994年提出的一種基于Pareto最優概念的遺傳算法。在多目標優化領域，NSGA直接體現了Goldberg的理念。NSGA基于基本遺傳算法對選擇和再生成過程進行了優化，其將個體按支配與非支配關系進行分層，再進行選擇，在多目標優化中取得明顯效果。

在實際的裝配過程中，序相關約束的工序經常出現，當裝配線平衡時必須加以考慮。這類工序需要在同一個工作站內按順序連續完成。工序之間的約束關系如圖2所示。

2.1 編碼

在RALBP中，編碼操作的作用是生成多個滿足裝配優先關系的可行解，每個解對應不同的作業處理順序。 2個染色體的編碼示例如圖3所示。本文采用由3個部分組成的實數編碼方式，分別表示工序序列、機器人和工作站。

2.2 選擇

為了防止遺傳退化并保留優秀基因，選擇操作采用二元錦標賽方法。從隨機排列的種群索引中選擇2個個體，基于其適應度值和擁擠距離來決定優劣。比較適應度值，如果P的值更小（假設較小的適應度值表示更好的個體），那么選擇P；如果P的值更大，那么選擇q；如果適應度值相同，那么比較擁擠距離，選擇具有較大擁擠度的個體。如果兩者的擁擠度相同，那么隨機挑選其中一個，重復這個過程，直到新的種群規模被填滿。這種方法模擬了在自然界中優秀個體更有可能繁衍后代的現象。

2.3 交叉

在基因交叉操作中，優良基因的交叉組合通常會提高產生優秀個體的概率。隨機選擇交叉點并進行基因交換，假設有2條染色體，每條染色體包括11個基因，作為待交叉的父代個體，分別記作父代個體R1、R2，交叉后生成的子代個體為S1。在交叉過程中，隨機選擇R1染色體上的2個交叉點a1和a2，從R1中提取區間[a1 ，a2]的基因完整遺傳給子代S1。從S2中刪除與該區間基因重復的部分，并將剩余基因按原有順序依次填補到子代缺失的基因位上，生成新的子代個體。采用這種方式，S1在基因組合方面既繼承了父代基因的優勢，又利用交叉操作生成了新的基因序列，有可能產生更具競爭力的后代，染色體交叉過程如圖4所示。

交叉操作具有隨機性，生成的子代個體可能會發生基因沖突，特別是某些基因可能不再滿足原有的作業優先關系。因此，在交叉操作完成后，須對新染色體進行基因沖突檢測，以識別并修正不符合優先關系的基因，保證最終子代個體滿足相關約束條件，進一步提高遺傳算法的效率，使效果更好。

2.4 變異

變異操作能夠有效避免遺傳算法陷入局部最優解，并防止算法過早收斂。變異操作步驟如下。1）對給定的任務序列A隨機選擇1個任務C進行變異操作，變異過程受到任務前置矩陣TP的約束。 2）找到C的前置任務和后置任務，確定可變異任務范圍D。3）如果找到了D，那么從中隨機選擇1個任務F進行變異，并根據F的位置Q將任務F插入A中。構建變異后的序列S，將F插入原序列中適當的位置，并返回變異后的序列。

2.5 多目標問題的Pareto支配法

RALBP是一個研究節拍時間和能耗的多目標優化問題，其目標是在滿足約束條件的前提下，使多個目標同時達到最佳狀態。對多目標優化問題來說，最優解不是單一的，而是由多個帕累托最優解（即非劣最優解）組成的一組解集。

多目標優化問題計算過程如公式（11）所示。

式中：f（x）為目標函數；x為決策變量；k為優化目標的數量；X為可行解集合。

設存在2個解x1和x2，如果x1和x2滿足公式（12），那么解x1能支配x2，即x1lt;x2，如公式（12）所示。

2.6 算法流程

算法流程如圖5所示。流程從初始化種群開始，通過選擇、交叉和變異等遺傳操作生成子代，根據快速非支配排序，采用精英策略來合并父代和子代。流程不斷迭代，更新種群，直到滿足最大代數條件，最終輸出最優解。

3 試驗設計與結果分析

3.1 參數設置

在算法中需要確定3個重要的參數，分別為種群大小、交叉概率和變異概率，因素水平見表1。采用正交試驗法考察各個參數的影響。根據大量試驗確定因子水平，因此，采用正交表L9（34）。針對TONGE中的規模問題，即70個問題進行試驗，每個參數進行10次測試，試驗方案以及試驗結果見表2，設置9個試驗方案，分別得到因素主次和優方案。以機器人裝配線的周期時間最短為主要目標，試驗指標為單指標。由表2可知，極差越大，其在試驗范圍內的數值變化會導致試驗指標的波動越大，極差最大的因素對應的水平對試驗結果的影響最明顯，即主要因素。因此，各因素從主到次的順序為變異概率、種群大小和交叉概率。經過直觀分析得到的方案C2A2B2并不屬于在正交表中已經進行的9個試驗方案，需要進一步與正交表中結果最好的6號試驗進行對比試驗，TONGE迭代過程如圖6、圖7所示，圖6中的最短周期為356 s，圖7中的最短周期為328 s。由圖6、圖7可知，隨著迭代代數增加，目標值逐漸趨于穩定，說明算法逐漸收斂，因此C2A2B2是最好的優方案。

在Windows 10操作系統下，利用MATLAB進行編程與仿真。本文研究多目標優化問題，在運行算法后得到最小循環時間和最小能耗，與粒子群算法進行對比試驗。算法迭代次數Generations=50，種群大小Solution_num=400，交叉概率ProC=0.7，變異概率ProM=0.02，交叉參數DisC=20，變異參數DisM=20。實例問題的參數設置采用 GAO等[6]的數據集生成的RALBP算例，按照任務的數量規模進行分組試驗。

3.2 數值計算

針對每個算例，筆者使用不同的隨機種子分別對上述2種算法進行10次獨立試驗，試驗結果見表3。將循環時間和能耗進行對比可知，本文提出的NSGA-Ⅱ算法在各方面均優于粒子群算法。隨著問題規模增加，NSGA-Ⅱ在能耗方面的優越性更加明顯。NSGA-Ⅱ引入了精英策略，擴大了搜索空間，因此優化效果更好。具體來說，父代種群與其子代種群結合，利用競爭生成下一代種群，可以保留優質個體，避免其在進化過程中丟失，提升優化結果的精確度。此外，NSGA-Ⅱ對種群個體進行分層存放，保證最佳個體不會丟失，加速提升種群水平。該算法還引入擁擠度和擁擠度比較算子，解決了NSGA算法需要人工設定共享參數的問題。擁擠度是個體間的比較標準，能夠將準Pareto解集中的個體均勻地擴展至整個Pareto域，進一步保證了種群的多樣性。因此，NSGA-Ⅱ能夠解決不同規模的RALBP-2多目標問題。算例HAHN的迭代過程如圖8所示，觀察圖中的曲線，可知隨著迭代次數增加，能量逐步收斂，在經過50代以后，最短循環時間和最小能耗的平均值趨于平緩。

4 結論

本文提出了一種改進的遺傳算法，解決機器人裝配線平衡問題。本文建立雙目標優化模型，在算法中引入精英策略，采用擁擠距離計算方法，提高了優化的準確性和穩定性。試驗結果顯示，與傳統算法相比，該算法在不同規模的裝配線中均能夠縮短節拍時間，降低能耗，優化效率較高，實用性較強。未來的研究可以進一步擴展算法的適用范圍，提高其在實際生產環境中的應用性。

參考文獻

[1]周濟.智能制造是“中國制造2025”主攻方向[J].企業觀察家，2019（11）：54-55.

[2]CHUTIMA P.A comprehensive review of robotic assembly line balancing problem[J].Journal of intelligent manufacturing，2022，33（1）：1-34.

[3]周炳海，吳瓊.基于多目標的機器人裝配線平衡算法[J].吉林大學學報（工學版），2021，51（2）：720-727.

[4]劉夢園，胡蓉，錢斌.混合EDA求解綠色機器人U型裝配線平衡問題[J].控制工程，2023，30（2）：307-315.

[5]SRINIVAS N，DEB K.Muiltiobjective optimization using"nondominated sorting in genetic algorithms[J].Evolutionary computation，1994，2（3）：221-248.

[6]GAO J，SUN L，WANG L，et al.An efficient approach for type II robotic assembly line balancing problems[J].Computers amp; industrial engineering，2009，56（3）：1065-1080.

第一作者：高忠順（1988—），男，福建省三明市人，博士研究生，講師，研究方向為離散系統調度建模與算法。

電子郵箱：gaozhongshun@fjut.edu。

通信作者：周杰（1998—），男，河南省周口市人，碩士研究生，研究方向為機器人裝配線平衡。

電子郵箱：2097523720@qq.com。基金項目：福建省教育廳科技項目“考慮Purge的集束型設備群的調度建模與優化算法研究”（項目編號：JAT190420）。