基于改進(jìn)遺傳算法的機(jī)器人裝配線平衡研究

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

關(guān)鍵詞：機(jī)器人裝配線平衡；雙目標(biāo)優(yōu)化；非支配排序遺傳算法；能耗" " 中圖分類號：TG 95；TP 18" " " " 文獻(xiàn)標(biāo)志碼：A

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

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

1 問題闡述

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

1.1 假設(shè)

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

1.2 數(shù)學(xué)模型

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

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

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

在裝配線平衡過程中，周期越短，生產(chǎn)效率越高，能耗越底，越節(jié)能、環(huán)保。目標(biāo)函數(shù)計算過程如公式（3）、公式（4）所示。

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

式中： c為循環(huán)時間；minc為最小周期； tih為機(jī)器人h處理任務(wù)i的時間。

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

式中：為任意任務(wù)i；pre（j）為在優(yōu)先網(wǎng)絡(luò)中設(shè)置j的中間前置任務(wù)；i、j為不同的任務(wù)編號。

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

式中：h為任意機(jī)器人h。

2 非支配遺傳算法

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

在實(shí)際的裝配過程中，序相關(guān)約束的工序經(jīng)常出現(xiàn)，當(dāng)裝配線平衡時必須加以考慮。這類工序需要在同一個工作站內(nèi)按順序連續(xù)完成。工序之間的約束關(guān)系如圖2所示。

2.1 編碼

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

2.2 選擇

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

2.3 交叉

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

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

2.4 變異

變異操作能夠有效避免遺傳算法陷入局部最優(yōu)解，并防止算法過早收斂。變異操作步驟如下。1）對給定的任務(wù)序列A隨機(jī)選擇1個任務(wù)C進(jìn)行變異操作，變異過程受到任務(wù)前置矩陣TP的約束。 2）找到C的前置任務(wù)和后置任務(wù)，確定可變異任務(wù)范圍D。3）如果找到了D，那么從中隨機(jī)選擇1個任務(wù)F進(jìn)行變異，并根據(jù)F的位置Q將任務(wù)F插入A中。構(gòu)建變異后的序列S，將F插入原序列中適當(dāng)?shù)奈恢茫⒎祷刈儺惡蟮男蛄小?/p>

2.5 多目標(biāo)問題的Pareto支配法

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

多目標(biāo)優(yōu)化問題計算過程如公式（11）所示。

式中：f（x）為目標(biāo)函數(shù)；x為決策變量；k為優(yōu)化目標(biāo)的數(shù)量；X為可行解集合。

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

2.6 算法流程

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

3 試驗(yàn)設(shè)計與結(jié)果分析

3.1 參數(shù)設(shè)置

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

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

3.2 數(shù)值計算

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

4 結(jié)論

本文提出了一種改進(jìn)的遺傳算法，解決機(jī)器人裝配線平衡問題。本文建立雙目標(biāo)優(yōu)化模型，在算法中引入精英策略，采用擁擠距離計算方法，提高了優(yōu)化的準(zhǔn)確性和穩(wěn)定性。試驗(yàn)結(jié)果顯示，與傳統(tǒng)算法相比，該算法在不同規(guī)模的裝配線中均能夠縮短節(jié)拍時間，降低能耗，優(yōu)化效率較高，實(shí)用性較強(qiáng)。未來的研究可以進(jìn)一步擴(kuò)展算法的適用范圍，提高其在實(shí)際生產(chǎn)環(huán)境中的應(yīng)用性。

參考文獻(xiàn)

[1]周濟(jì).智能制造是“中國制造2025”主攻方向[J].企業(yè)觀察家，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]周炳海，吳瓊.基于多目標(biāo)的機(jī)器人裝配線平衡算法[J].吉林大學(xué)學(xué)報（工學(xué)版），2021，51（2）：720-727.

[4]劉夢園，胡蓉，錢斌.混合EDA求解綠色機(jī)器人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—），男，福建省三明市人，博士研究生，講師，研究方向?yàn)殡x散系統(tǒng)調(diào)度建模與算法。

電子郵箱：gaozhongshun@fjut.edu。

通信作者：周杰（1998—），男，河南省周口市人，碩士研究生，研究方向?yàn)闄C(jī)器人裝配線平衡。

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