混合鯨魚優(yōu)化算法求解柔性作業(yè)車間調(diào)度問題①

李寶帥,葉春明

(上海理工大學(xué) 管理學(xué)院,上海 200093)

隨著生產(chǎn)技術(shù)的發(fā)展與制造業(yè)內(nèi)在需求的變化,制造業(yè)正在向著智能制造的方式轉(zhuǎn)變,作為產(chǎn)品生產(chǎn)制造中重要一環(huán),車間調(diào)度問題得到了極大關(guān)注.柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem,FJSP)作為經(jīng)典作業(yè)車間調(diào)度問題(job-shop scheduling problem,JSP)的延伸被認(rèn)為是NP-難問題,相較于JSP 具有更高靈活性與求解難度.如今智能制造是制造業(yè)主要發(fā)展方向,制造系統(tǒng)的高效運(yùn)行是智能制造主要要求之一.FJSP 具有工序排序與機(jī)器選擇兩個(gè)子問題,其求解更具復(fù)雜性,同時(shí)也更貼近實(shí)際車間生產(chǎn)制造情況,為尋求高效求解方法,對(duì)于FJSP 的求解方法具有廣泛的研究.目前對(duì)FJSP 的求解方法主要集中于元啟發(fā)式算法.張超勇等[1]對(duì)遺傳算法進(jìn)行改進(jìn),改變了染色體的表示方式,結(jié)合多種策略生產(chǎn)高質(zhì)量初始種群等多種操作,在基準(zhǔn)問題上進(jìn)行驗(yàn)證;Li 等[2]將禁忌搜索算法策略嵌入到遺傳算法中,綜合利用二者的尋優(yōu)能力,為更好平衡算法的勘探與開發(fā),通過與其他算法進(jìn)行對(duì)比實(shí)驗(yàn),改進(jìn)的混合算法具有顯著改進(jìn);仲于江等[3]利用改進(jìn)的粒子群算法對(duì)多目標(biāo)FJSP 進(jìn)行研究,利用小生境技術(shù)更新解集避免算法陷入局部最優(yōu),并改進(jìn)最優(yōu)解的選擇方式,在算例與車間仿真實(shí)驗(yàn)中驗(yàn)證改進(jìn)算法可行性.

隨著計(jì)算機(jī)科學(xué)技術(shù)發(fā)展,新式元啟發(fā)式算法不斷涌現(xiàn),如灰狼優(yōu)化算法[4],人工蜂群算法[5]等,學(xué)者利用新興的元啟發(fā)式算法對(duì)FJSP 進(jìn)行進(jìn)一步研究,Lu 等[6]設(shè)計(jì)了一種改進(jìn)的多目標(biāo)混合灰狼優(yōu)化算法,在算法中嵌入遺傳算子增強(qiáng)全局搜索能力,在多目標(biāo)動(dòng)態(tài)調(diào)度模型中與其他經(jīng)典算法進(jìn)行比較,體現(xiàn)改進(jìn)算法的優(yōu)越性;Karthikeyan 等[7]針對(duì)有限資源約束下的多目標(biāo)FJSP,考慮3 個(gè)最小化目標(biāo),結(jié)合鄰域結(jié)構(gòu)的局部搜索方法,提出一種混合螢火蟲算法并將其離散化應(yīng)用于多目標(biāo)FJSP;姜天華[8]采用兩段式編碼方式將改進(jìn)的灰狼優(yōu)化算法應(yīng)用于FJSP,引入變鄰域搜索方法與遺傳算法中交叉和變異算子的方式提高算法勘探能力在基準(zhǔn)與隨機(jī)算例中與其他算法進(jìn)行對(duì)比,數(shù)據(jù)證明改進(jìn)算法;王玉芬等[9]針對(duì)FJSP,對(duì)人工蜂群算法進(jìn)行改進(jìn),在搜索階段利用IPOX 與多點(diǎn)交叉方法避免產(chǎn)生非法解,通過增加偵察蜂的數(shù)量保持全局搜索能力,且用貪婪策略保留較優(yōu)解,在算例上驗(yàn)證改進(jìn)算法的有效性與收斂性;Li 等[10]針對(duì)FJSP,提出了一種基于禁忌搜索的混合人工蜂群算法來求解,并使用聚類分組輪盤賭的方式來初始化種群,同時(shí)為提高種群質(zhì)量,在計(jì)算過程中引入交叉算子,在基準(zhǔn)算例上與其他算法進(jìn)行比較并證明了算法有效性;劉雪紅等[11]對(duì)候鳥算法做出改進(jìn),使用精英分批策略提高算法性能,使其應(yīng)用于FJSP,解決最小完工時(shí)間與最小批次數(shù)目的多目標(biāo)FJSP.綜上,學(xué)者基于元啟發(fā)式算法解決FJSP 進(jìn)行了廣泛研究.

鯨魚優(yōu)化算法(whale optimization algorithm,WOA)[12]是一種基于種群的元啟發(fā)式算法,已應(yīng)用于模型預(yù)測(cè)[13],參數(shù)優(yōu)化等方面[14],WOA 具有獨(dú)特的搜索機(jī)制,其應(yīng)用參數(shù)少,算法整體穩(wěn)定性高,尋優(yōu)能力較強(qiáng)[15],元啟發(fā)式算法在解決車間調(diào)度問題方面具有一定優(yōu)勢(shì),WOA 作為元啟發(fā)式算法的一種,同樣應(yīng)用于在車間調(diào)度應(yīng)用的方面,閆旭等[16]首先將WOA 應(yīng)用于車間調(diào)度問題,利用量子計(jì)算方式改進(jìn)的WOA求解JSP;張斯琪等[17]提出一種改進(jìn)的WOA 優(yōu)化單目標(biāo)的FJSP.為進(jìn)一步豐富FJSP 的求解算法,對(duì)FJSP求解進(jìn)行深入研究,本文首先利用非線性收斂因子與正余弦算法對(duì)WOA 進(jìn)行改進(jìn),提出一種混合正余弦鯨魚優(yōu)化算法(sine cosine whale optimization algorithm,SCWOA),并應(yīng)用SCWOA 求解以最小化最大完工時(shí)間的FJSP.

1 問題描述

FJSP 是經(jīng)典JSP 的擴(kuò)展,其問題可以描述為:假設(shè)在車間內(nèi)n個(gè)工件(J1,J2,···,Jn)需在m臺(tái)機(jī)器(M1,M2,···,Mm)上進(jìn)行加工,每個(gè)工件Ji包含一個(gè)以上工序,工序按預(yù)定順序進(jìn)行加工.使用Oij表示工件Ji的第j道工序,Mij表示可加工工序的機(jī)器集合,工序可在具備處理能力的機(jī)器上進(jìn)行加工.工序Oij在不同機(jī)器上的加工時(shí)間不同.FJSP 的調(diào)度目標(biāo)是為Oij選擇機(jī)器進(jìn)行加工,同時(shí)對(duì)機(jī)器上各個(gè)待加工工件工序進(jìn)行排列以確定加工時(shí)間,平衡各性能指標(biāo)以達(dá)到最好方案.

FJSP 的目標(biāo)是在一定的約束條件下對(duì)工件和機(jī)器按時(shí)間進(jìn)行分配并安排加工次序,使得加工性能指標(biāo)達(dá)到最優(yōu).

本文評(píng)價(jià)目標(biāo)是最大完工時(shí)間最小,目標(biāo)函數(shù)可表示為:

式中,Cj為工件最后完成時(shí)間,n為工件數(shù).

2 基本算法描述

2.1 鯨魚優(yōu)化算法

WOA 的設(shè)計(jì)源于鯨魚群的捕食行為.在鯨魚群體中,其捕食行為常常伴隨著個(gè)體之間的合作,鯨魚群捕食行為中最特別之處是氣泡網(wǎng)捕食行為,即鯨魚群在發(fā)現(xiàn)獵物之后,會(huì)以螺旋路徑逐漸包圍獵物,將獵物活動(dòng)范圍逐漸縮小,最終捕食獵物[12].WOA 從鯨魚群獨(dú)特的捕食行為中進(jìn)行研究,通過仿效鯨魚群捕食的方式,從搜索、包圍、捕食獵物3 個(gè)方面建立數(shù)學(xué)模型,模擬算法尋優(yōu)過程.

2.1.1 包圍獵物階段

WOA 模仿鯨魚群協(xié)同捕食方式,會(huì)有多個(gè)鯨魚個(gè)體對(duì)獵物進(jìn)行包圍捕獵,算法在開始時(shí)設(shè)置一組隨機(jī)解并計(jì)算解的適應(yīng)度,同時(shí)將適應(yīng)度最高的解視作目標(biāo),其余鯨魚個(gè)體會(huì)向目標(biāo)靠攏接近,其位置更新方式可以表示為:

式中,X*為獵物位置,t為迭代次數(shù),A,C為系數(shù),其計(jì)算方式為:

其中,a隨迭代次數(shù)增加從2 線性下降為0,r∈[-1,1]的隨機(jī)數(shù).

2.1.2 氣泡網(wǎng)捕食

鯨魚群在進(jìn)行捕食時(shí)會(huì)沿著圓形或“9”形的路徑捕食獵物,為模仿這種捕食方式,WOA 設(shè)置兩種方法進(jìn)行模仿,第1 種為個(gè)體收縮環(huán)繞機(jī)制,這一機(jī)制通過a的線性降低來實(shí)現(xiàn),由式(4)可知,A的值也會(huì)隨a的減小而減小,當(dāng)a的值在[-1,1]時(shí),鯨魚個(gè)體會(huì)對(duì)目標(biāo)獵物進(jìn)行收縮環(huán)繞行為.第2 種為鯨魚個(gè)體螺旋形位置更新,WOA 首先計(jì)算鯨魚個(gè)體與捕獵目標(biāo)之間距離,然后在二者之間建立一個(gè)螺旋方程,模擬鯨魚個(gè)體的螺旋形運(yùn)動(dòng)方式[17],公式為:

式中,D′為鯨魚個(gè)體與獵物之間的距離,b為定義螺旋形狀的常數(shù),l為[-1,1]之間的隨機(jī)數(shù).WOA 通過這兩種機(jī)制模擬整個(gè)鯨魚群捕食路徑,為模擬同時(shí)發(fā)生的兩種行為,設(shè)置WOA 分別以50%的幾率進(jìn)行收縮環(huán)繞機(jī)制或螺旋更新機(jī)制,公式如下:

其中,p為[0,1]之間的隨機(jī)數(shù).

2.1.3 尋找獵物階段

為進(jìn)一步尋找獵物,WOA 利用A的變化來進(jìn)行探索,即|A|＜1時(shí)算法會(huì)進(jìn)行精確搜索,鯨魚個(gè)體會(huì)向當(dāng)前最優(yōu)個(gè)體進(jìn)行移動(dòng),與開發(fā)階段不同,當(dāng)A的隨機(jī)值大于1 或小于-1 時(shí),鯨魚個(gè)體會(huì)遠(yuǎn)離當(dāng)前獵物并且根據(jù)一個(gè)隨機(jī)鯨魚個(gè)體來更新自己的位置,位置更新公式如下:

其中,Xrand為隨機(jī)選取的鯨魚個(gè)體的位置.

WOA 從一組隨機(jī)解開始.在每次迭代中,鯨魚個(gè)體會(huì)根據(jù)隨機(jī)選擇的鯨魚個(gè)體位置或當(dāng)前最優(yōu)個(gè)體位置更新自身的位置,當(dāng)|A|＞1時(shí),鯨魚群進(jìn)行隨機(jī)搜索,|A|＜1時(shí),每個(gè)鯨魚個(gè)體會(huì)依據(jù)獵物位置更新本身所處位置,以此來進(jìn)行勘探與開發(fā);同時(shí)根據(jù)p的隨機(jī)取值,選擇對(duì)數(shù)螺旋方式或收縮環(huán)繞方式靠近捕獲獵物,WOA 會(huì)在達(dá)到最大迭代次數(shù)時(shí)結(jié)束.元啟發(fā)式算法作為求解FJSP 的有效手段,其中WOA 作為眾多元啟發(fā)式算法的一種,本身具備較強(qiáng)的搜索能力,在函數(shù)求解方面的穩(wěn)定性與求解精度強(qiáng)于大部分元啟發(fā)式算法,但同時(shí)也具有元啟發(fā)式算法共有的易陷入局部最優(yōu)等的缺點(diǎn)[18].因此本文在引入非線性收斂因子與正余弦算法策略對(duì)WOA 進(jìn)行改進(jìn),并應(yīng)用于FJSP 的求解.

2.2 正余弦算法

正余弦算法(sine cosine algorithm,SCA)由Mirjalili 在2016年提出[19],SCA 算法的主要思想是在算法尋優(yōu)過程中綜合使用正弦函數(shù)與余弦函數(shù)來進(jìn)行勘探與開發(fā),通過正余弦函數(shù)的周期性變化實(shí)現(xiàn)勘探與開發(fā).SCA 算法首先隨機(jī)創(chuàng)建一組初始解,然后根據(jù)正余弦函數(shù)進(jìn)行迭代更新位置,尋找最優(yōu)解,其位置更新公式可以表示為:

其中,Xt是在第t次迭代時(shí)個(gè)體的位置,pt表示在第t次迭代時(shí)適應(yīng)度最高的個(gè)體所處位置,SCA 控制參數(shù)包括r1、r2、r3、r4,其中r1的表示公式如下:

其中,k為常數(shù),t為當(dāng)前迭代次數(shù),T為最大迭代次數(shù);r2∈[0,2π],r3∈[0,2π],r4∈[0,1],均為隨機(jī)數(shù).在SCA算法中,r1確定個(gè)體下一次更新的運(yùn)動(dòng)方向;r2確定個(gè)體的移動(dòng)距離;r3是當(dāng)前最優(yōu)個(gè)體位置的一個(gè)權(quán)重,若r3＞1表示增大當(dāng)前最優(yōu)個(gè)體位置對(duì)其他個(gè)體改變的影響,若r3＜1表示減弱當(dāng)前最優(yōu)個(gè)體位置對(duì)其他個(gè)體改變的影響;r4代表隨機(jī)選擇正余弦函數(shù).在4 個(gè)參數(shù)中,r1的取值對(duì)SCA 全局探索與局部開發(fā)之間的平衡影響較大,r1＞1時(shí),函數(shù)r1sin(r2)與r1cos(r2)的值會(huì)大于1 或小于-1,此時(shí)個(gè)體會(huì)遠(yuǎn)離當(dāng)前的最優(yōu)個(gè)體,算法會(huì)探索更加廣闊的求解區(qū)域,保證算法全局探索能力;當(dāng)r1≤1時(shí),函數(shù)r1sin(r2)與r1cos(r2)的值會(huì)處于-1 到1 之間,此時(shí)個(gè)體會(huì)逐漸向當(dāng)前最優(yōu)個(gè)體移動(dòng),算法會(huì)對(duì)區(qū)域內(nèi)進(jìn)行進(jìn)一步精確搜索,保證算法進(jìn)行良好的局部開發(fā).SCA 在正弦余弦函數(shù)中利用自適應(yīng)參數(shù)平滑實(shí)現(xiàn)從全局探索到局部開發(fā),能夠?qū)⑷痔剿骱途植块_發(fā)有效結(jié)合起來.

3 混合正余弦鯨魚優(yōu)化算法

3.1 編碼解碼

基于FJSP 的特性,設(shè)置基于機(jī)器分配與工序排序的兩段式向量進(jìn)行編碼,分別對(duì)應(yīng)FJSP 的兩個(gè)子問題,對(duì)于一個(gè)鯨魚個(gè)體向量X=(x1,x2,···,xn),將其分為長度相等兩段,滿足n=2l,l為FJSP 總工序數(shù),第一段向量用于表示機(jī)器分配,第二段向量表示工序排序,并設(shè)置個(gè)體位置取值范圍為[-ε,ε],ε為FJSP 總工件數(shù).假設(shè)存在一個(gè)3 個(gè)工件,每工件含2 道工序的調(diào)度問題,則可表示為兩段向量,每段向量長度為6,個(gè)體位置向量總長為12,個(gè)體位置元素的取值介于[-3,3]之間,如圖1所示是一段個(gè)體位置向量.

圖1 個(gè)體位置向量

3.1.1 編碼

首先對(duì)第一段機(jī)器分配向量進(jìn)行編碼,參考文獻(xiàn)[20]的編碼方法,通過式(13)將鯨魚個(gè)體位置向量映射到當(dāng)前可選機(jī)器集合的機(jī)器序號(hào),從而完成個(gè)體位置轉(zhuǎn)換機(jī)器分配的過程.

其中,x(j)為鯨魚個(gè)體向量,s(j)為可選機(jī)器集合,u(j)為機(jī)器集合中的序號(hào).如圖2 為第一段機(jī)器分配向量的轉(zhuǎn)換過程.

圖2 機(jī)器分配向量轉(zhuǎn)換

工序O11選擇可選機(jī)器集合中的序號(hào)2 機(jī)器即M3,工序O12選擇可選機(jī)器集合中序號(hào)1 機(jī)器即M1.

工序排序向量的編碼采用文獻(xiàn)[21]的最大位置值規(guī)則(largest position value,LPV)來實(shí)現(xiàn),首先按照位置元素值的大小進(jìn)行降序排列,之后依照這一排列順序?qū)崿F(xiàn)工序順序的排列,最后確定工序順序.如圖3所示為第2 段向量的轉(zhuǎn)換過程.

圖3 工序排序向量轉(zhuǎn)換

3.1.2 解碼

解碼也包括機(jī)器分配與工序排序兩部分,機(jī)器分配向量向個(gè)體位置向量的轉(zhuǎn)換是公式的逆轉(zhuǎn)換,即:

若發(fā)生特殊情況,在可選集合中僅存在唯一一臺(tái)機(jī)器,即當(dāng)s(j)為1 時(shí),此時(shí)x(j)取值為[-ε,ε]之間的隨機(jī)數(shù).

工序排序向量的解碼同樣依據(jù)LPV 規(guī)則,工序排序向量π(j)的轉(zhuǎn)換根據(jù)式(15)實(shí)現(xiàn).

3.2 非線性收斂因子

任何群智能優(yōu)化算法在尋優(yōu)的過程中都存在全局探索與局部開發(fā)兩個(gè)階段,恰當(dāng)平衡兩個(gè)階段,可使算法在初期尋優(yōu)中探索更大范圍,同時(shí)提升其后期對(duì)于局部范圍的搜索精度,提升算法求解的整體準(zhǔn)確性.WOA 的勘探與開發(fā)平衡主要由 |A|確定,又由式(4)可知 |A|是由收斂因子a的變化決定,收斂因子a的值較大時(shí),|A|＞1,算法會(huì)處于全局探索階段,反之|A|＜1,算法會(huì)處于局部開發(fā)階段.針對(duì)SCA,其勘探與開發(fā)兩階段之間平衡主要取決于參數(shù)r1.

然而無論是WOA 收斂因子a還是SCA 參數(shù)r1都根據(jù)迭代次數(shù)由2 線性遞減至0,為適應(yīng)WOA與SCA 的優(yōu)化過程,因此本文提出一種非線性收斂因子調(diào)整策略,對(duì)WOA 的收斂因子a進(jìn)行改進(jìn),其改進(jìn)公式如下:

其中,t為當(dāng)前迭代次數(shù),T為最大迭代次數(shù),λ ,μ都為常數(shù).此種改進(jìn)使得的值可以隨著迭代過程進(jìn)行非線性變化,適應(yīng)WOA 與SCA 的非線性優(yōu)化過程.

如圖4所示為WOA 收斂因子與非線性收斂引子在迭代過程中的變化對(duì)比.非線性收斂因子相比標(biāo)準(zhǔn)WOA 的收斂因子,的值在其優(yōu)化過程前期取值較大且遞減速度較慢,保證 |A|的取值較大,進(jìn)而使得算法前期全局搜索范圍較大,適用于全局搜索,在后期取值較小且遞減速度加快,|A|的取值較小,算法在更小范圍內(nèi)進(jìn)行搜索,保證算法局部搜索精確性,提高算法搜索精度,同時(shí)可提高算法收斂速度.

圖4 收斂因子迭代對(duì)比

3.3 正余弦算法策略

SCA 利用正余弦函數(shù)的周期性變化實(shí)現(xiàn)尋優(yōu)過程,這種位置更新方式使得算法勘探時(shí)會(huì)探索更大區(qū)域,局部開發(fā)時(shí)會(huì)在更小范圍內(nèi)進(jìn)行精確搜索,綜合利用SCA 的位置更新方式,將其應(yīng)用于WOA 的位置更新與螺旋更新中,對(duì)WOA 進(jìn)行改進(jìn),提高WOA 的整體尋優(yōu)水平.標(biāo)準(zhǔn)SCA 參數(shù)r1作為平衡探索與開發(fā)的重要參數(shù),其迭代變化也與WOA 中收斂因子類似,呈線性變化,這種線性變化無法充分發(fā)揮算法在探索、開發(fā)能力[22].因此同樣考慮對(duì)SCA 參數(shù)r1引入非線性收斂因子策略,對(duì)r1改進(jìn)如式(17)所示,增強(qiáng)SCA 的全局探索能力與局部搜索能力.

3.3.1 改進(jìn)鯨魚個(gè)體位置更新方式

WOA 全局探索能力依靠式(9)來實(shí)現(xiàn),即通過隨機(jī)選擇鯨魚個(gè)體來確保算法的全局探索,這種隨機(jī)產(chǎn)生鯨魚個(gè)體的方法只有同時(shí)滿足p＜0.5 且|A|＞1 時(shí),算法才會(huì)采用式(9)進(jìn)入全局探索階段,過多的條件限制使得WOA 全局探索能力略顯不足,因此將SCA 與WOA 進(jìn)行混合,利用SCA 的尋優(yōu)方式,結(jié)合SCA 較強(qiáng)的全局探索能力,首先對(duì)WOA 的全局探索方式進(jìn)行改進(jìn).利用控制參數(shù)為指數(shù)函數(shù)遞減的SCA 較原算法具有更高的計(jì)算精度,同時(shí)提高了算法的求解效率,因此結(jié)合非線性收斂因子策略,同時(shí)把式(11)引入WOA,對(duì)式(10)進(jìn)行改進(jìn)如下:

基于同樣考慮,把SCA 策略引入WOA 的局部開發(fā)過程中,提升算法的局部開發(fā)能力,對(duì)式(3)進(jìn)行改進(jìn)如下:

3.3.2 改進(jìn)鯨魚個(gè)體螺旋更新方式

由式(6)可知,在WOA 中個(gè)體會(huì)一直以對(duì)數(shù)螺旋的軌跡方式進(jìn)行位置更新,這種螺旋更新位置的方式雖然可以加快整體收斂速度,但是會(huì)導(dǎo)致群體內(nèi)個(gè)體以較快速度聚合在一起,進(jìn)而導(dǎo)致整個(gè)種群喪失多樣性,最終增大陷入局部最優(yōu)的幾率.因此,為增強(qiáng)整個(gè)種群多樣性與跳出局部最優(yōu)能力,同樣利用SCA 策略對(duì)螺旋更新方式實(shí)行改進(jìn)如下:

其中,r3為[0,1]之間的隨機(jī)數(shù),通過利用正弦螺旋更新運(yùn)動(dòng)與余弦螺旋更新運(yùn)動(dòng)的隨機(jī)發(fā)生,避免種群多樣性的快速丟失,使其從全局勘探平滑地過渡到局部開發(fā),最終迭代收斂到最優(yōu)解.

3.3.3 混合鯨魚優(yōu)化算法流程與實(shí)施

混合正余弦鯨魚優(yōu)化算法綜合非線性收斂因子與SCA 策略改進(jìn)方式,提高算法全局勘探能力與局部開發(fā)能力,SCWOA 的框架如下:

(1)定義目標(biāo)函數(shù),設(shè)置算法參數(shù),包括種群規(guī)模N,最大迭代次數(shù)T,設(shè)置t=1;

(2)進(jìn)入主循環(huán),根據(jù)適應(yīng)度記錄最優(yōu)個(gè)體位置,定義并更新非線性收斂引子參數(shù)設(shè)置依據(jù)式(16),式(17);

(3)定義并更新參數(shù)A,C,l,θ,r3,r4的值,A的數(shù)值依據(jù)式(4)所定,C為[0,2]內(nèi)隨機(jī)值,l,θ,r4為[0,1]內(nèi)隨機(jī)值,r3為[0,2π]內(nèi)隨機(jī)值;

(4)判斷p＜0.5,若|A|≥0.5,采用式(18)更新個(gè)體位置;若|A|＜0.5,采用式(19)更新個(gè)體位置;

(5)判斷p≥0.5,采用式(20)更新個(gè)體位置;

(6)判斷t=T,若滿足進(jìn)行步驟(7),否則返回步驟(2);

(7)輸出最優(yōu)個(gè)體位置與目標(biāo)函數(shù)最優(yōu)解.

圖5 為SCWOA 流程圖.

圖5 SCWOA 運(yùn)行流程

4 實(shí)驗(yàn)分析

本文選取文獻(xiàn)[23]中BRdata 包含的10 個(gè)FJSP 標(biāo)準(zhǔn)調(diào)度實(shí)例(MK01-MK10),與文獻(xiàn)[24]中5 個(gè)標(biāo)準(zhǔn)調(diào)度實(shí)例(kacem01-kacem05)對(duì)SCWOA 實(shí)行實(shí)例驗(yàn)證,SCWOA 由Python 3.7 實(shí)現(xiàn),在Windows 10,Intel(R)Core(TM)i5-9300 CPU,2.4 GHz 主頻,16 GB 內(nèi)存的系統(tǒng)上運(yùn)行.算法參數(shù)設(shè)置種群為160,最大迭代次數(shù)為300.

首先對(duì)基本W(wǎng)OA 與SCWOA 進(jìn)行實(shí)驗(yàn)對(duì)比,以驗(yàn)證非線性收斂因子與正余弦策略改進(jìn)措施的有效性.為避免隨機(jī)性,算法共運(yùn)行10 次,Time 表示算法的平均運(yùn)行時(shí)間,Best 代表10 次運(yùn)行結(jié)果中最優(yōu)結(jié)果,Avg代表10 次實(shí)驗(yàn)的平均優(yōu)化結(jié)果.借鑒文獻(xiàn)[17]的對(duì)比方法加入提升率,其計(jì)算公式為(SCWOABest-WOABest)/SCWOABest,其用來表示SCWOA 相較于原算法的提升水平.其實(shí)驗(yàn)對(duì)比結(jié)果如表1所示.

表1 WOA 與SCWOA 實(shí)驗(yàn)對(duì)比結(jié)果

從表1 對(duì)比結(jié)果可知,SCWOA 相較WOA 在最優(yōu)尋優(yōu)結(jié)果與平均尋優(yōu)結(jié)果方面都獲得了一定的提升,在8 個(gè)實(shí)例中優(yōu)化結(jié)果得到了提升,并且最大提升效果達(dá)到了0.1,證明SCWOA 的改進(jìn)措施有效.值得注意的是SCWOA 的時(shí)間復(fù)雜度也較WOA 有一定程度的提高.如圖6所示為SCWOA 在MK04 上的調(diào)度甘特圖,MK04 有8 個(gè)加工機(jī)器與15 個(gè)待加工工件,求解結(jié)果Cmax 為67,雖未達(dá)到最優(yōu)調(diào)度結(jié)果,但調(diào)度結(jié)果仍優(yōu)于大部分優(yōu)化算法.

圖6 MK04 調(diào)度甘特圖

同時(shí)將SCWOA 與其他元啟發(fā)式算法進(jìn)行實(shí)驗(yàn)對(duì)比,對(duì)比算法包括基本遺傳算法、文獻(xiàn)[2]中的混合遺傳算法、文獻(xiàn)[8]的混合灰狼優(yōu)化算法、文獻(xiàn)[24]與文獻(xiàn)[25],最優(yōu)結(jié)果以粗體表示,對(duì)比結(jié)果如表2 與表3所示.

表2 SCWOA 與其他算法在Kacem 實(shí)驗(yàn)對(duì)比結(jié)果

表2 對(duì)比結(jié)果表明文獻(xiàn)[24]在缺失2 個(gè)算例情況下獲得最優(yōu)解有1 次,文獻(xiàn)[8]獲得最優(yōu)解有4 次,文獻(xiàn)[25] 獲得最優(yōu)解有3 次,SCWOA 獲得最優(yōu)解有4 次.SCWOA 表現(xiàn)較好.表3 對(duì)比結(jié)果表明GA 獲得最優(yōu)解有1 次,文獻(xiàn)[23]獲得最優(yōu)解1 次,文獻(xiàn)[2]獲得最優(yōu)解有4 次,文獻(xiàn)[8]獲得最優(yōu)解5 次,SCWOA獲得最優(yōu)解次數(shù)最多,并且SCWOA 的尋優(yōu)能力在問題規(guī)模較大時(shí)相較于其他算法表現(xiàn)也較好,以上結(jié)果綜合表明SCWOA 應(yīng)用于FJSP 的有效性.

表3 SCWOA 與其他算法在BRdata 實(shí)驗(yàn)對(duì)比結(jié)果

5 結(jié)束語

本文以FJSP 的最大完工時(shí)間為優(yōu)化目標(biāo),對(duì)WOA進(jìn)行設(shè)計(jì)改進(jìn),提出了一種混合正余弦鯨魚優(yōu)化算法.首先以兩段式編碼使鯨魚優(yōu)化算法離散化,使其可應(yīng)用于FJSP;加入非線性收斂因子策略;并加入SCA 的優(yōu)化策略,改進(jìn)鯨魚優(yōu)化算法的位置變動(dòng)方式,提高全局勘探與局部開發(fā)能力.通過與其他算法在BRdata 算例上的實(shí)驗(yàn)對(duì)比,實(shí)驗(yàn)對(duì)比結(jié)果證明了算法設(shè)計(jì)的有效性.下一步工作可將鯨魚優(yōu)化算法應(yīng)用于更加復(fù)雜的車間調(diào)度問題,如多目標(biāo)FJSP,進(jìn)一步豐富算法的應(yīng)用范圍,并且可將綠色調(diào)度目標(biāo)作為算法優(yōu)化目標(biāo),響應(yīng)國家碳中和、碳達(dá)峰政策.