改進鯨魚優化算法及其在混流U型裝配線平衡問題的應用

2023-10-09 01:55:28張凌波周劍揚

科學技術與工程 2023年26期

關鍵詞：優化

張凌波, 周劍揚

(華東理工大學信息科學與工程學院, 上海 200237)

鯨魚優化算法(whale optimization algorithm,WOA)具有收斂速度快,性能穩定等優勢,自從提出以來廣泛應用于故障診斷[1]、參數調優[2]、水資源配置[3]和模型優化[4]。但同其他的智能優化算法一樣,存在收斂精度較低,易于陷入局部最優等問題,已有許多學者對其進行了研究和改進。黃元春等[5]提出一種偽反向學習和高斯-柯西混合變異策略的改進鯨魚算法,改善了算法的收斂速度和精度;吳坤等[6]將灰狼優化算法中的等級制度和微分進化算法中的貪婪策略引入鯨魚優化算法,提升了算法的全局搜索能力;Jiang等[7]將差分算法和鯨魚優化算法結合,并引入云自適應慣性權重,有效平衡全局和局部搜索。上述改進雖然改善了WOA的性能,但是在尋優精度和算法穩定性方面還存在不足,仍有改進空間。

裝配線是由一些物料搬運設備連接起來連續生產線,由多個工位組成,每個工位完成整個裝配過程的幾個環節。由于任務分配的不合理,裝配線各工位的負載并不均衡,就會出現“瓶頸工序”,造成資源的浪費和生產效率低下。裝配是生產過程的重要環節之一,據調查,裝配占用總生產時間的50%和總生產成本的20%。

裝配線平衡問題(assembly line balancing problem,ALBP)是指根據裝配線的已知信息,合理地將各工序分配至各個工作站,優化裝配線某些指標的一系列復雜問題。常見的裝配線平衡問題主要可以分為3類,即第1類裝配線平衡問題(ALBP-Ⅰ)、第2類裝配線平衡問題(ALBP-Ⅱ)、E類裝配線平衡問題[8](ALBP-E)。ALBP-Ⅰ是已知裝配線的節拍時間,最小化裝配線的工作站數量;ALBP-Ⅱ是已知裝配線的工作站數量,最小化裝配線的節拍時間;ALBP-E是最小化工作站數量和節拍時間,提高裝配線效率。裝配線根據類型,可以分為直型線、U型線和并行線;根據生產產品的類型,又可分為單模、多模和混模。隨著市場變化和精益生產的發展,越來越多的企業采用靈活性更好的混流U型線代替傳統的單模直型線,這使得混流U型線的平衡問題(mixed model U-shaped assembly line balancing problem,MMUALBP)成為近幾年的研究重點;彭運芳等[9]針對第2類混流U型裝配線的平衡問題,構建了其混合整數規劃模型,并提出了一種改進的遺傳算法,采用3種工序分配方法,并通過實驗驗證了算法的有效性;劉佳楠等[10]針對直型線和U型線的混流裝配線平衡問題,提出多目標的平衡方法,并采用改進的遺傳算法進行優化;原丕業等[11]的研究兼顧工作站的平均和瞬時負荷,建立了混流U型裝配線的多目標數學模型,并設計了一種自適應遺傳算法求解;Aufy等[12]針對混流直型和U型線的裝配線平衡問題,設計了一種工人-任務分配的啟發式模型,并通過實例驗證其模型的有效性;Zhang等[13]以最小化混流U型裝配線的能源消耗和生產效率為目標建立了多目標模型,并設計了一種改進的多目標蜻蜓優化算法求解;Zheng等[14]基于任務選擇因子的編碼方式,提出一種混合交叉熵算法,用于解決混流U型線的平衡問題。如何合理地分配工序和更精準的求解,是混流U型裝配線目前需要解決的問題。

針對鯨魚優化算法在實際應用中存在尋優能力不足、求解效果不穩定和易于陷入局部最優等問題,現提出一種改進的鯨魚優化算法(improve whale optimization algorithm,IWOA),并將其應用到求解混流U型裝配線平衡問題。在WOA的基礎上,現引入均勻設計方法進行初始種群的生成,提高初始種群的質量;融合NEWUOA算法,增強鯨魚優化算法的局部搜索能力;提出一種新的越界處理方法,降低算法陷入局部最優的可能;引入非線性收斂因子和自適應權重,平衡算法的局部和全局搜索,增加算法的搜索精細度。通過7個基準測試函數,驗證IWOA在尋優效果和求解穩定性方面的優越性。針對混流U型裝配線平衡問題,以裝配線節拍時間為優化目標,設計帶閾值的工序分配方法。最后通過21個混流裝配線標準算例,進一步驗證本文提出的IWOA的有效性。

1 標準的鯨魚優化算法

WOA是Mirjalili等[15]通過對座頭鯨特有的氣泡網狩獵方式進行研究和模擬,建立數學模型,而后提出的一種智能優化算法。該算法包括包圍獵物、氣泡網攻擊和搜索獵物3個階段。

1.1 包圍獵物

WOA通過假定當前的最優個體所處的位置即為獵物或者最接近獵物的位置,以此吸引其他個體向著最優個體移動,完成對獵物的包圍,其過程可以描述為

D1=|CX*(t)-X(t)|

(1)

X(t+1)=X*(t)-AD1

(2)

式中:D1為中間變量;t為當前的迭代次數;X*為最佳鯨魚個體的位置;X為當前鯨魚個體的位置;A和C為系數,定義為

A=2ar-a

(3)

C=2r

(4)

式中:r為[0,1]的隨機數;隨著迭代次數的增加,收斂因子a線性地從2減至0。

1.2 氣泡網攻擊

鯨魚個體根據自身和獵物之間的距離,通過一種對數螺旋方程更新位置,其過程可以描述為

X(t+1)=D2eblcos(2πl)+X*(t)

(5)

式(5)中:D2=|X*(t)-X(t)|為當前鯨魚個體和獵物之間的距離;e為自然常數;b為螺旋對數方程常數;l為[-1,1]的隨機數。

為了更好地模擬座頭鯨的這種獨特捕食行為,WOA設置了一個概率閾值,用于在包圍和螺旋更新兩種行為之間進行選擇,通常情況下,兩種行為的概率都為50%,其數學模型為

(6)

式(6)中:p1為[0,1]的隨機數。

1.3 搜索獵物

WOA會根據系數A的值來決定是靠近最優個體進行包圍獵物或螺旋更新,還是遠離最優個體進行隨機搜索。當|A|>1時,WOA將隨機選擇參考個體Xrand,執行全局搜索,而不再是以最優個體為參考。過程可以描述為

D3=|CXrand(t)-X(t)|

(7)

X(t+1)=Xrand(t)-AD3

(8)

2 改進的鯨魚優化算法

WOA具有實現簡單、可調參數少和收斂速度快等優點,廣泛應用于工程問題優化,但在實際應用中發現,WOA存在尋優精度不足、易于陷入局部最優等缺點。針對上述問題,在WOA的種群初始化、局部搜索、越界修正和收斂因子方面提出了幾點改進措施,具體如下。

2.1 基于均勻設計的種群初始化策略

一般的智能優化算法使用隨機方式進行初始種群的生成,這樣的初始種群只具有一定的隨機性,而不能保證有較好均勻性。均勻試驗設計,簡稱均勻設計,是由Fang等[16]提出的一種試驗設計方法,用于將試驗點均勻的散布在試驗區域內,盡可能地減少試驗次數。以往采用均勻設計的智能優化算法[17-18]大多使用好格子點法進行均勻設計表的生成,但是好格子點法要求試驗次數n和因子個數s滿足式(9)的限制:

(9)

式(9)中:φ(?)為歐拉函數。

這要求優化算法的種群數量要足夠大,但對于群智能優化算法,過大的種群數量意味著算法運行時間的增多。切割法[19]的思想是從一個較大的均勻設計中切割出一個符合條件的偏差最小的均勻設計作為近似均勻設計。相較于好格子點法,切割法只要求較大的均勻設計的試驗次數p或p+1為素數,可用于算法求解高維復雜問題時初始種群的生成。IWOA采用基于切割法的均勻設計種群初始化方法,并使用方冪好格子法作為切割法的初始設計,混合偏差作為均勻性度量,混合偏差的公式為

(10)

式中:zij為第i個點的第j維坐標。

2.2 基于NEWUOA的局部搜索算子

NEWUOA是一種無導數優化方法[20],用于求解求導困難、無約束的黑箱問題。NEWUOA是一種基于信賴域的確定性優化算法,采用二次逼近的方式,不需要計算目標優化函數的導數。因此,NEWUOA和智能優化算法具有很好的契合度。NEWUOA的流程可以描述如下。

步驟1選擇初始插值點xi,計算F(xi)中的最優值,設定最優值對應的xi為xopt。構建初始的二次模型Qinit,設定參數ρ=ρbeg,Δ=ρbeg。

步驟2計算‖d‖≤Δ條件下Q(xopt+d)的近似最小值,其中d為信賴域子問題的近似解。如果‖d‖<Δ,則將參數CRVMIN的值設置為二次模型Q的最小曲率值。

步驟3如果‖d‖>ρ/2,則計算F(xopt+d),設定參數RATIO為[F(xopt)-F(xopt+d)]/[Q(xopt)-Q(xopt+d)],并在參數Δ≥ρ條件下調整ρ的值。將參數MOVE設置為0或者下次迭代過程中要舍去的插值點的索引。如果‖d‖<ρ/2,則跳至步驟11。

步驟4如果MOVE>0,則更新二次模型Q,將xMOVE替換為xopt+d。如果F(xopt+d)

步驟5如果RATIO≥0.1,則跳轉至步驟2。

步驟6將xMOVE設置為當前迭代中使得距離參數DIST=‖xMOVE-xopt‖最大的插值點。

步驟7如果DIST≥2Δ,跳至步驟10。

步驟8如果參數d、Δ、RATIO滿足‖d‖≤ρ,Δ≤ρ,RATIO≤0,轉至步驟9;反之,轉至步驟2。

步驟9如果ρ=ρend,轉至步驟13;反之,轉至步驟10。

步驟10將參數ρ在滿足約束ρ≥ρend下縮小10倍,并將Δ設置為max{ρold/2,ρnew},跳至步驟2。

步驟11使用參數CRVMIN測試‖d‖的最近3個值和F-Q是否足夠小,如果是,則轉至步驟9,反之跳至步驟12。

步驟12設置參數ρ為原來的1/10且不低于其下界值,RATIO=-1,轉至步驟6。

步驟13如果||d||<ρ/2,則計算F(xopt+d)后,算法終止;否則,直接終止算法。

NEWUOA具有優越的局部搜索能力,初始點的選取影響著優化結果,而WOA的種群更新依賴于引導個體,優秀的引導個體可以更好地引導種群的搜索方向。通過融合NEWUOA,由WOA提供全局最優個體作為NEWUOA的初始點,同時WOA借助NEWUOA進行更好的局部搜索,優化引導個體,從而提高自身的尋優能力。在算法初始運行時,對種群中最優個體執行一次NEWUOA,如果種群最優值發生變化,則繼續對種群最優個體執行NEWUOA,反之,則停止執行NEWUOA,直到累計30次迭代,種群最優值都沒有發生變化,則繼續啟用NEWUOA,重復上述過程。

2.3 基于環形區間和隨機波動越界修正策略

大部分智能優化算法在處理越界問題上一般會舍棄越界個體或直接將越界個體修正至邊界,這樣可能會導致該個體頻繁越界,致使算法陷入局部最優。采用一種基于環形區間和隨機波動的越界修正策略,公式為

(11)

式(11)中:mod(n1,n2)為修正的按模運算,假設n1=pnn2+re,pn為正整數,re為余數,當re>0時, mod(n1,n2)=re;當re=0時,mod(n1,n2)=n2;p2和rand(0,1)為[0,1]的隨機數;lb和ub分別為算法搜索區域的下界和上界;Xi(t)為個體第i維的坐標。

2.4 非線性收斂因子和自適應權重系數

A是控制WOA進行全局搜索和局部搜索的關鍵參數,其變化受到a的影響。根據文獻[5]中的研究,a不同變化趨勢對算法的全局搜索和局部搜索存在一定程度的影響。為均衡算法的全局和局部搜索,引入的非線性收斂因子a的計算公式為

(12)

式(12)中:Max_iter為最大迭代次數。

經式(12)改進后,a在算法迭代過程中的變化趨勢為先緩后急,增加了算法全局搜索所占用的迭代次數比例,增強了算法的全局搜索能力。此外,為進一步增加算法的搜索精細度,設計了一種自適用權重ω,隨著迭代進程的推進,ω可以使得種群在最優個體附近進行更加精細的搜索,其計算公式為

(13)

X(t+1)=ωX*(t)-AD1

(14)

X(t+1)=D2eblcos(2πl)+ωX*(t)

(15)

2.5 IWOA步驟

本文提出的IWOA偽代碼如下。

注:T為迭代次數;Tmax為最大迭代次數。

圖1給出了IWOA更加直觀的流程圖。

2.6 算法復雜度分析

3 仿真實驗結果與分析

為了驗證IWOA的性能,選擇7個基準測試函數,如表1所示,與幾種工程上常用的智能優化算法以及其他的改進鯨魚算法比較,包括遺傳算法(genetic algorithm, GA)、WOA、PWOA[5]、GWOA[6]、BWOA[21]、NWOA[22]和RWOA[23]。測試函數中,F1～F3為多模態函數,F4為固定維度的多模態函數,F5～F7為單模態函數。測試指標包括最優值、最差值、均值、標準差、和平均運行時間。測試軟件為MATLAB2021b,測試環境為11th Gen Intel(R) Core(TM) i7-11800H @ 2.30 GHz,16 GB RAM。

表1 基準測試函數

參與測試的算法參數設置如下:遺傳算法[24]的精英保留個數設置為2,交叉率0.7,變異率0.1;WOA和IWOA中參數b都遵循WOA,文獻[15]設置為1,其余改進鯨魚優化算法的參數設置均參考其原文獻。所有算法的種群大小設置為30,迭代次數上限為500次,算法終止條件為|f(x)-fmin|≤10-5或達到最大迭代次數。為避免隨機性,對每種算法獨立運行1 000次。測試結果如表2所示。

表2 算法測試結果

由表2可知,在尋優精度方面,相較于其他算法,IWOA在測試函數F1～F2和F4～F7上求得的結果最優,僅在F3上略差于其他算法,這得益于IWOA采用NEWUOA算法作為其局部搜索算子的一部分,增強了算法的搜索能力,并通過引入了自適應參數,增加算法的搜索精細度;在算法求解穩定性方面,IWOA在7個測試函數中的最差值指標均是最小的,此外,在F1～F2和F4～F7中的均值和標準差指標也是最小的,即更接近最優值的均值和更小的標準差,僅在F3中的均值和標準差指標略差于PWOA,這表明在所有參與測試的算法中,IWOA在求解穩定性方面具有一定的優越性。

在平均運行時間方面,IWOA在F1、F3、F4和F6上取得了最短的平均運行時間,而在其余3個測試函數中要差于其他算法。圖2給出了所有算法在迭代500次的過程中最優值的均值隨迭代次數的變化曲線。由圖2可知,IWOA在F2、F5和F7中的收斂曲線所表現出的特性為在迭代前期快速收斂,在中后期略慢于PWOA和GWOA,但最終仍可收斂至最優值;在F1、F4和F6中,IWOA在收斂精度方面表現出顯著優勢,并且可以在較小的迭代次數內快速收斂至最優值或其附近,收斂曲線位于所有算法的下方;在F3中,IWOA同樣在前期有著最快的收斂速度,但其收斂精度要低于PWOA。

圖2 收斂曲線

綜合上述結果,相較于其他算法,IWOA具有更高求解精度和更好的求解穩定性,雖然所提出的改進措施對運行時間存在一定的負面影響,但仍可在前期加快算法的收斂。

4 基于改進鯨魚優化算法的混流U型裝配線平衡優化

4.1 問題描述

第2類混流U型裝配線平衡問題就是已知工作站的數量,在混合模型和U型裝配線的情況下,最小化裝配線的節拍時間。相較于一般的單模直線型裝配線平衡問題,混流U型裝配線平衡問題的復雜性更高,主要體現在:①單模的裝配線只生產單一品種的產品,其各個工序的裝配時間相對固定,而混流的裝配線生產多種工藝相似,品種不同的產品,不同產品相同工序的裝配時間存在差異;②直線型裝配線的工序分配只能按照工序的順序,例如從前往后或從后往前進行,而U型線的工序分配更為靈活,可以同時從裝配線的前后進行工序的分配。為了降低混流裝配線平衡問題的復雜度,一般采取的方式是根據各產品主生產計劃(master production schedule,MPS),構建綜合工序優先級圖[25],將“混流”轉換為“單模”問題,如圖3所示,模型A、B、C的MPS為1∶1∶1。本文所建立的數學模型基于以下假設:①每中產品的工序所需的裝配時間是固定值,不受其他因素的影響;②所有模型的優先級圖都可以構成綜合優先級圖;③不同產品的相同工序須分配到同一個工作站;④所有產品的工序優先級相同。

圈中數字表示工序序號;圈上數字表示工序時間

4.2 數學模型

針對第2類混流U型裝配線的平衡問題,優化目標定義為最小化節拍時間Ct,如式(16)所示。

minCt

(16)

模型同時需要滿足相關約束:

(17)

(18)

(19)

(20)

(21)

(22)

式中:M為模型數量;dm為模型m的需求;D為模型總需求;K為工作站數量;N為工序數量;tjm為模型m的工序j所需裝配時間;Tj為工序j的加權時間;P為工序優先級集合;xjk和yjk為決策變量,分別為分配順序從前向后和從后向前時,工序j是否分配給工作站k,是則為1,反之為0。

式(17)為裝配線上生產產品的總需求;式(18)為綜合優先級圖中各工序根據MPS計算得出加權裝配時間;式(19)表示每一道工序都被分配至一個工作站;式(20)表示每個工作站的總裝配時間不得超過節拍時間;式(21)和式(22)表示向后和向前的工序分配需要滿足工序的優先級約束。

4.3 編碼與解碼

采用優先級權重的編碼方式,初始對每道工序賦予[0,1]的隨機數,作為該工序的優先級權重,以Jackson問題為例,其編碼如圖4所示。

圖4 Jackson優先級權重編碼

解碼就是將種群個體的編碼信息解釋成工序分配信息,為更好地進行工序分配,本文提出一種帶閾值的工序分配方法。根據影子約束關系[26],如圖5所示,從前后兩個方向進行分配,具體步驟如下。

圖5 影子約束關系圖

步驟2根據P,同時向前向后搜索無約束的工序,將無緊前工序的工序(P列和為0)放入P1中,無緊后工序的工序(P行和為0)放入P2中。

步驟3分別P1和P2中選擇優先級權重最大的工序a和b并比較其權重大小,如果a的權重大于等于b,轉至步驟4,否則轉至步驟5。

步驟6如果k=K-1,將剩余工序分配至工作站K,輸出分配結果,結束工序分配程序,否則k=k+1,轉至步驟2。

圖6給出了解碼的流程圖。

4.4 算例測試結果與分析

為了驗證IWOA在求解裝配線平衡問題上的性能,采用網站(https://assembly-line-balancing.de/)[27]中的混流數據集作為測試算例,具體數據信息如表3所示,選擇與第3節中相同的算法作為對比算法。測試指標為節拍時間和對應的平衡率,平衡率RB的計算公式為

表3 混流裝配線測試算例

(23)

4.4.1 參數設置

針對Thom、Kim、Arcus三組問題,設定算法的迭代次數為500。為避免隨機性,對每種算法獨立運行10次,取最優值作為最終結果,并對表中結果的最優值進行加粗處理,其余參數設置和測試環境與第3節中保持一致。

4.4.2 結果和分析

表4給出了8種算法的對比結果。根據表4可知,在簡單問題Thom1～Thom3上,所有算法均可以求得最佳的生產節拍;在6個中等規模的問題Kim1～Kim6中,IWOA在所有的算例中都能夠求得更小的節拍時間;在12個大規模的問題Arcus1～Arcus12中,IWOA在11個算例中求得了最小的節拍時間,這說明IWOA具有更好的尋優能力。Arcus9～Arcus12因為存在單個工序裝配時間超過工作站平均裝配時間的情況,所以無法達到100%的平衡率。

圖7給出了所有算法在部分用例中的收斂曲線圖。在簡單算例Thom1中,所有算法都可以在前幾次迭代快速收斂至最優值,而在中等算例Kim1和大規模算例Arcus3,IWOA雖然在前期的收斂速度要落后于其他算法,但仍可收斂至更優的值。上述的實驗結果驗證了IWOA的有效性,能夠在復雜問題上求得更好的解。

圖7 部分算例的收斂曲線

5 結論

以最小節拍時間作為優化目標,建立了第2類混流U型裝配線平衡問題的模型,并提出了一種改進的鯨魚優化算法IWOA進行模型的求解。算法采用均勻設計作為初始種群的生成策略,提高初始種群的均勻性;采用NEWUOA算法作為IWOA的局部搜索算子,強化算法的局部搜索性能;在處理越界點時采用一種基于環形區間和隨機波動的修正策略,降低算法陷入局部最優的可能;最后引入了非線性收斂因子和自適應權重系數,平衡算法的全局和局部搜索,增強算法的搜索精細度。針對第2類混流U型裝配線平衡問題,IWOA的采用優先級權重的編碼方式,并采用一種帶閾值的解碼方案,盡可能地得到更好的工序分配方案。通過7個基準函數測試和21個裝配線標準算例測試表明IWOA在一般問題上的求解精度和穩定性高于對比算法,同時在復雜問題的優化效果也要優于對比算法,驗證了算法改進的有效性,為工程中解決混流U型裝配線的平衡問題提供了可行的解決方案。