改進(jìn)麻雀搜索算法求解DFJSP 問(wèn)題

王 燦，葉春明

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

隨著經(jīng)濟(jì)全球化和制造企業(yè)的規(guī)?；植际街圃斐蔀橐环N常見(jiàn)的生產(chǎn)模式。分布式柔性作業(yè)車(chē)間調(diào)度問(wèn)題（Distributed flexible job shop scheduling problem，DFJSP）是一個(gè)具有重要研究意義的基礎(chǔ)性問(wèn)題，傳統(tǒng)的單一工廠集中性生產(chǎn)逐漸被淘汰，多個(gè)柔性作業(yè)車(chē)間相互協(xié)同生產(chǎn)調(diào)度成為研究的重點(diǎn)。

目前，有關(guān)DFJSP研究較少，何怡［1］針對(duì)DFJSP 提出一種改進(jìn)蟻群算法，通過(guò)兩階段參數(shù)自適應(yīng)動(dòng)態(tài)調(diào)整，并利用旅行商問(wèn)題驗(yàn)證了算法的有效性，將其應(yīng)用于DFJSP 的求解。吳銳等人［2］針對(duì)DFJSP 特點(diǎn)，設(shè)計(jì)了三維向量編碼，并提出一種改進(jìn)人工蜂群算法求解。吳秀麗等人［3］提出一種改進(jìn)差分進(jìn)化算法求解DFJS 的雙目標(biāo)優(yōu)化模型，對(duì)總成本和提前或延期懲罰同時(shí)進(jìn)行了優(yōu)化。王彪［4］提出引入自適應(yīng)移動(dòng)因子的改進(jìn)混合蛙跳算法對(duì)分布式柔性生產(chǎn)調(diào)度進(jìn)行優(yōu)化。馬慶吉［5］提出一種新的編碼方式和基于啟發(fā)式規(guī)則的解碼方式，設(shè)計(jì)了相應(yīng)的優(yōu)化策略，并改進(jìn)灰狼算法求解DFJSP。孟磊磊等人［6］提出一種引入變鄰域搜索算法、針對(duì)關(guān)鍵工廠全解空間禁忌搜索的混合蛙跳算法。陳文洲等人［7］設(shè)計(jì)一種基于帕雷托優(yōu)化方法的人工蜂群算法對(duì)低碳DFJS 雙目標(biāo)優(yōu)化模型進(jìn)行求解。Giovanni 等人［8］提出一種改進(jìn)遺傳算法求解DFJSP。Lu 等人［9］認(rèn)為DFJSP 本質(zhì)是三維解空間探索問(wèn)題，涉及制造單元分配、機(jī)器選擇和工序排序三個(gè)調(diào)度決策，并通過(guò)改進(jìn)遺傳算法求解該問(wèn)題。

麻雀搜索算法（sparrow search algorithm，SSA）是2020 年由薛建凱［10］根據(jù)麻雀種群的覓食行為和反捕食行為提出的一種新型群體智能優(yōu)化算法，與其他算法相比，其搜索精度、收斂速度和穩(wěn)定性等方面極具競(jìng)爭(zhēng)力，已被應(yīng)用于多個(gè)領(lǐng)域，目前已然應(yīng)用于解決車(chē)間調(diào)度問(wèn)題。劉麗娜等人［11］提出一種量子計(jì)算、正余弦搜索和警戒者數(shù)量遞減策略改進(jìn)的麻雀搜索算法，并引入多鄰域搜索和高斯擾動(dòng)策略來(lái)求解作業(yè)車(chē)間調(diào)度問(wèn)題。因此，本文提出一種改進(jìn)麻雀搜索算法（improved sparrow search algorithm，ISSA），并驗(yàn)證其在求解分布式柔性作業(yè)車(chē)間調(diào)度問(wèn)題中的有效性。

1 分布式柔性作業(yè)車(chē)間調(diào)度問(wèn)題

1.1 符號(hào)定義

為方便理解，對(duì)本文出現(xiàn)的相關(guān)符號(hào)進(jìn)行定義，具體含義見(jiàn)表1。

表1 符號(hào)定義Tab.1 Symbols definition

1.2 問(wèn)題描述

DFJSP 包含工序排序、工廠選擇、機(jī)器選擇三個(gè)子問(wèn)題［12］，實(shí)質(zhì)是一個(gè)典型的組合優(yōu)化問(wèn)題［1］，可將其描述為：將n個(gè)工件在f家工廠加工，每家工廠有mr臺(tái)機(jī)器，一個(gè)工件的所有工序只能在一家工廠加工，每道工序的可選擇加工機(jī)器以及加工時(shí)間已知。DFJSP 滿足以下假設(shè)：

（1）所有機(jī)器從0 時(shí)刻開(kāi)始可用。

（2）各工件加工的優(yōu)先級(jí)相同，同一工件各道工序有先后約束。

（3）每道工序在同一時(shí)刻只能被一臺(tái)機(jī)器加工。

（4）所有工件在0 時(shí)刻可以被加工且不考慮工件的運(yùn)輸時(shí)間。

（5）機(jī)器加工過(guò)程中沒(méi)有故障。

調(diào)度的目的是安排每家工廠的每臺(tái)機(jī)器上工件的加工順序，為每一個(gè)工件選擇合適的工廠，為每一道工序選擇適當(dāng)?shù)臋C(jī)器，使完工時(shí)間達(dá)到最小。

1.3 模型建立

本文以最小化全局最大完工時(shí)間Cmax為目標(biāo)進(jìn)行優(yōu)化。具體數(shù)學(xué)模型如下［13］：

其中，式（1）為目標(biāo)函數(shù)，表示全局最大完工時(shí)間的最小化；式（2）表示每個(gè)工件只能被分到一家工廠；式（3）表示每個(gè)工件的所有工序須在一家工廠完成加工；式（4）表示各工件的工序加工有先后約束；式（5）表示各工序只能選擇在一家工廠的一臺(tái)機(jī)器上加工；式（6）表示一臺(tái)機(jī)器在任意時(shí)間節(jié)點(diǎn)只能對(duì)一道工序進(jìn)行加工；式（7）表示每道工序直到加工完成不會(huì)被中斷。

2 改進(jìn)麻雀搜索算法求解DFJSP

2.1 SSA 概述

麻雀搜索算法模擬了麻雀群體的覓食和反捕食行為，在搜索精度、收斂速度和穩(wěn)定性等方面有較強(qiáng)的競(jìng)爭(zhēng)力。麻雀?jìng)€(gè)體分為發(fā)現(xiàn)者、加入者和偵察者，發(fā)現(xiàn)者負(fù)責(zé)搜尋并為麻雀種群提供食物豐富的區(qū)域和方向，加入者跟隨發(fā)現(xiàn)者以獲得食物。此外，種群中存在一定比例的個(gè)體負(fù)責(zé)偵查預(yù)警，如發(fā)現(xiàn)危險(xiǎn)則發(fā)出報(bào)警信號(hào)并在種群中移動(dòng)，當(dāng)預(yù)警值大于安全值時(shí)，發(fā)現(xiàn)者需帶領(lǐng)加入者移動(dòng)到其他安全的區(qū)域?qū)ふ沂澄?。研究?duì)此擬做闡釋分述如下。

（1）發(fā)現(xiàn)者。每次迭代過(guò)程中，發(fā)現(xiàn)者位置更新如下：

其中，t表示當(dāng)前迭代次數(shù)，j ＝1，2，…，d；itermax表示最大迭代次數(shù)；Xi，j表示第i個(gè)麻雀在第j維中的位置信息；α∈（0，1］ 表示一個(gè)隨機(jī)數(shù)；R2（R2∈［0，1］）表示預(yù)警值；ST（ST∈［0.5，1］）表示安全值；Q是服從正態(tài)分布的隨機(jī)數(shù)；L表示一個(gè)1× d的矩陣且元素全部為1。

（2）加入者。加入者位置更新如下：

其中，Xp表示當(dāng)前發(fā)現(xiàn)者占據(jù)的最優(yōu)位置；Xworst表示當(dāng)前全局最差的位置；A表示一個(gè)1×d的矩陣，元素隨機(jī)取值為1或-1，且A＋＝ AT(AAT)-1。

（3）偵查者。偵查者位置更新如下：

其中，Xbest是當(dāng)前全局最優(yōu)位置；β是服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)；K∈[-1，1]，fi表示當(dāng)前麻雀?jìng)€(gè)體適應(yīng)度值；fg表示當(dāng)前種群中最佳適應(yīng)度值；fw表示當(dāng)前種群中最差適應(yīng)度值；ε為極小的常數(shù)。

2.2 編碼與解碼

本文選用基于工序序列的編碼，編碼僅包含一條工序序列，序列長(zhǎng)度等于所有工件的工序數(shù)之和，用來(lái)確定工序排序。

麻雀搜索算法用于處理連續(xù)型問(wèn)題，無(wú)法直接應(yīng)用于車(chē)間調(diào)度等離散型問(wèn)題，因此需要選擇合適的編碼方式。n個(gè)工件共D道工序，個(gè)體位置向量為X ＝［x1，x2，…，xd，…，xD］，各元素可在［-δ，δ］ 中任意取值，并按一定順序存儲(chǔ)。假設(shè)有3 個(gè)工件、共8 道工序，各元素在［-2，2］ 中任意取值，個(gè)體位置向量如圖1 所示。

圖1 個(gè)體位置向量Fig. 1 Individual position vector

采用文獻(xiàn)［14］中的轉(zhuǎn)換方法實(shí)現(xiàn)連續(xù)個(gè)體位置向量向離散車(chē)間調(diào)度之間的轉(zhuǎn)化。轉(zhuǎn)換結(jié)果如圖2 所示，可得工序序列為O31→O11→O21→O32→O22→O12→O13→O33。

圖2 調(diào)度方案Fig. 2 Scheduling scheme

與一般車(chē)間調(diào)度問(wèn)題相比，DFJSP 需考慮工廠選擇，本文工廠選擇采用文獻(xiàn)［15］的方法，包含3個(gè)步驟：

（1）選擇每個(gè)工件的第一道工序，并維持這些工序的序列，推導(dǎo)得出一個(gè)工件序列，如從O31→O11→O21→O32→O22→O12→O13→O33之中選出O31→O11→O21，進(jìn)而推出工件序列J3→J1→J2。

（2）計(jì)算各工件在各工廠的平均加工時(shí)間，將工件-工廠-機(jī)器表縮減得到工件-工廠表。

（3）按照工件序列，根據(jù)當(dāng)前最大完工時(shí)間最小化規(guī)則將工件分配給特定工廠。

2.3 種群初始化

SSA 算法隨機(jī)初始化產(chǎn)生種群個(gè)體的方式，會(huì)導(dǎo)致生成種群分布不均勻，種群多樣性減少，影響算法尋優(yōu)效率。為保證求解速度和質(zhì)量，本文初始化種群的生成策略為隨機(jī)生成與反向?qū)W習(xí)相混合，50%個(gè)體采用隨機(jī)生成方式，50%個(gè)體采用反向?qū)W習(xí)生成方式。利用反向?qū)W習(xí)策略［16］生成種群的主要思想：首先隨機(jī)生成初始種群，再根據(jù)初始種群生成其反向種群，從中選擇較優(yōu)的種群作為下一代種群。操作步驟為：

（1）隨機(jī)初始化n個(gè)麻雀?jìng)€(gè)體的位置X ＝［x1，x2，…，xd，…，xD］ 作為初始種群P1，其中各元素可在［-δ，δ］ 中任意取值。

（2）生成初始種群P1中每個(gè)麻雀?jìng)€(gè)體的反向個(gè)體，構(gòu)成反向種群P2，其中反向個(gè)體位置X' ＝其中。

（3）將種群P1、P2合并，根據(jù)適應(yīng)度值對(duì)2n個(gè)麻雀?jìng)€(gè)體升序排序，最終選取適應(yīng)度值前n個(gè)麻雀?jìng)€(gè)體為初始種群。

2.4 萊維飛行優(yōu)化發(fā)現(xiàn)者位置

麻雀在覓食狀態(tài)下的運(yùn)動(dòng)路線是萊維飛行軌跡，特點(diǎn)是大范圍的探索，折線方式的急劇轉(zhuǎn)向，目標(biāo)是獲得更多食物機(jī)會(huì)。在SSA 算法中，由于發(fā)現(xiàn)者在搜索過(guò)程中的帶頭作用，加入者位置更新易受發(fā)現(xiàn)者影響，使得麻雀種群容易出現(xiàn)聚集，陷入局部最優(yōu)，因此發(fā)現(xiàn)者的位置更新必須有一定的隨機(jī)性。為避免SSA 容易早熟而陷入局部最優(yōu)，提高全局尋優(yōu)能力，在發(fā)現(xiàn)者位置更新公式中引入萊維飛行［17］。利用Levy 飛行來(lái)增加發(fā)現(xiàn)者搜索方向的多元性，以增強(qiáng)算法的全局搜索能力，避免陷入局部最優(yōu)。

Levy 飛行的隨機(jī)步長(zhǎng)s的計(jì)算公式為：

當(dāng)R2＜ST時(shí)，發(fā)現(xiàn)者個(gè)體位置的每一維都在縮小，因此將發(fā)現(xiàn)者位置更新公式改進(jìn)為：

其中，“ ⊕”表示點(diǎn)乘，Levy（λ）表示步長(zhǎng)服從Levy 分布的隨機(jī)搜索向量s（μ，v）。

2.5 學(xué)習(xí)更新策略優(yōu)化加入者位置

加入者在有效控制全局探索和局部開(kāi)發(fā)的平衡中發(fā)揮重要作用，但發(fā)現(xiàn)最優(yōu)解后，加入者迅速向最優(yōu)解靠攏，容易陷入局部最優(yōu)，因此，對(duì)加入者的位置引入學(xué)習(xí)更新策略，使加入者不僅向最優(yōu)麻雀?jìng)€(gè)體學(xué)習(xí)，也進(jìn)行自我學(xué)習(xí)和隨機(jī)個(gè)體學(xué)習(xí)。

（1）自我學(xué)習(xí)。在加入者位置中引入自適應(yīng)慣性權(quán)重因子ω來(lái)提升加入者對(duì)自身的學(xué)習(xí)，權(quán)重因子ω計(jì)算公式如下：

迭代前期，權(quán)重因子ω值較大，可提高全局搜索能力，迭代后期ω值自適應(yīng)減小，有利于進(jìn)行局部搜索，并提高收斂速度。

（2）最優(yōu)個(gè)體學(xué)習(xí)。借鑒螢火蟲(chóng)算法［18］中的吸引度規(guī)則，螢火蟲(chóng)種群中發(fā)光弱的會(huì)被發(fā)光強(qiáng)的吸引并向其移動(dòng)，且吸引度僅僅與發(fā)光強(qiáng)度、距離相關(guān)，距離越大，吸引度越小。吸引度β計(jì)算方式如下：

其中，β0表示最大吸引度，即r ＝0 時(shí)的吸引度；γ表示光吸收系數(shù)，在［0.1，10］ 中任意取值；r表示2 只螢火蟲(chóng)之間的距離；β0＝1。

（3）隨機(jī)個(gè)體學(xué)習(xí)。向隨機(jī)個(gè)體學(xué)習(xí)有助于提升種群多樣性，但隨機(jī)個(gè)體影響因子過(guò)大不利于算法收斂，因此，隨機(jī)個(gè)體學(xué)習(xí)因子S定義為：

其中，fk為隨機(jī)個(gè)體k的適應(yīng)度值。

加入者位置更新公式改進(jìn)為：

其中，Xk，j表示隨機(jī)個(gè)體k的位置。

2.6 正態(tài)云模型優(yōu)化偵查者位置

為進(jìn)一步提高SSA 跳出局部最優(yōu)的能力，且提升算法的收斂速度和求解精度，在偵查者位置更新公式中引入云模型［19］。云模型是處理定性概念和定量描述間的不確定轉(zhuǎn)換模型，反映了隨機(jī)性和模糊性［20］。云的數(shù)字特征為期望（Ex）、熵（En）和超熵。期望是能夠代表定性概念量化的最典型樣本，熵反映了云滴的離散程度和取值范圍，超熵反映了云滴的凝聚程度。正態(tài)云滴生成過(guò)程可定義如下：

其中，Nd表示期望生成的云滴數(shù)目。

將當(dāng)前全局最優(yōu)位置作為正態(tài)云模型的期望Ex，偵查者位置更新公式改進(jìn)為：

其中，P表示麻雀種群中偵查者的位置；En表示偵查者距離麻雀最優(yōu)個(gè)體的范圍；He表示偵查者位置的分散程度。在迭代前期，En值較大，能夠提高全局搜索能力，在迭代后期自適應(yīng)減小，有利于進(jìn)行局部搜索，提高收斂速度。因此，En，He計(jì)算方式如下：

其中，DISPmax表示偵查者距離全局最優(yōu)位置的最大距離，φ、δ為正整數(shù)。

2.7 交叉和變異算子

交叉和變異兩個(gè)操作相互配合、相互競(jìng)爭(zhēng)，能夠均衡算法的全局搜索和局部搜索能力。考慮到算法的運(yùn)行時(shí)間，本文對(duì)每次迭代發(fā)現(xiàn)者中任2 個(gè)麻雀?jìng)€(gè)體進(jìn)行交叉操作，因個(gè)體位置為連續(xù)型向量，故本文設(shè)計(jì)了一種交叉策略。對(duì)每次迭代發(fā)現(xiàn)者中任一個(gè)麻雀?jìng)€(gè)體進(jìn)行變異操作，變異算子采用SIM 算子。

交叉策略如圖3 所示。首先，在父代中隨機(jī)選擇幾個(gè)位置可不連續(xù)的基因，2 條染色體選擇位置相同；然后，將父代1 中所選基因復(fù)制到相同位置的子代1 中，并將父代2 中所選基因復(fù)制到相同位置的子代2 中；接著，將父代1 中的剩余基因復(fù)制到子代2 的同一位置，并將父代2 中的剩余基因復(fù)制到子代1 的同一位置。

圖3 交叉示意圖Fig. 3 Schematic diagram of crossing

變異算子采用SIM 算子，即反轉(zhuǎn)突變，如圖4 所示。在麻雀?jìng)€(gè)體中選擇一個(gè)隨機(jī)的基因序列，將該序列中的基因順序顛倒。

圖4 變異示意圖Fig. 4 Schematic diagram of mutation

2.8 改進(jìn)麻雀搜索算法步驟

至此，本文改進(jìn)麻雀搜索算法流程如圖5 所示。

圖5 ISSA 算法流程Fig. 5 Algorithm process of ISSA

3 仿真實(shí)驗(yàn)與分析

3.1 算例生成

本文使用Fisher 等人［21］設(shè)計(jì)的3 個(gè)典型問(wèn)題mt06、mt10 和mt20 以及15 個(gè)Lawrence［22］基準(zhǔn)測(cè)試?yán)觢a01～la15，并假設(shè)所有工廠完全相同，分別考慮2 家、3 家工廠的情況。

3.2 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證ISSA 算法求解分布式柔性作業(yè)車(chē)間調(diào)度的有效性，與SSA 算法、PSO 算法對(duì)比進(jìn)行研究分析。

本文算法運(yùn)行環(huán)境為：Windows10 64 位操作系統(tǒng)，Intel（R）Core（TM）i5-1135G7 ＠ 2.40 GHz 2.42 GHz處理器，16.0 GB 內(nèi)存，Matlab R2017a 開(kāi)發(fā)軟件。

為避免測(cè)試結(jié)果的隨機(jī)性，更加準(zhǔn)確地對(duì)ISSA、SSA、PSO 算法就DFJSP 進(jìn)行比較，設(shè)置每個(gè)算法最大迭代次數(shù)為500 次，種群規(guī)模為100，針對(duì)每個(gè)算例，每種算法獨(dú)立運(yùn)行20 次，取運(yùn)行結(jié)果的最小值和平均值，2 家工廠、3 家工廠實(shí)驗(yàn)結(jié)果分別見(jiàn)表2、表3。

表2 2 家工廠測(cè)試結(jié)果Tab.2 2 FMU test results

由表2、表3 結(jié)果可知，在最小值方面，ISSA 優(yōu)于SSA，大部分優(yōu)于PSO；在平均值方面，ISSA 絕大部分優(yōu)于SSA 和PSO。綜上，ISSA 在多工廠大部分算例上均表現(xiàn)優(yōu)異，整體尋優(yōu)性能優(yōu)于SSA 和PSO。

為更好地對(duì)比3 種算法的收斂效果，選取具有代表性的實(shí)例mt10、la05、la10、la15，分別繪制了2家工廠、3 家工廠的研究中各算法的收斂曲線對(duì)比圖，如圖6、圖7 所示。

圖6 2 家工廠不同算法尋優(yōu)曲線對(duì)比Fig. 6 Comparison of optimization curves of different algorithms for two factories

圖7 3 家工廠不同算法尋優(yōu)曲線對(duì)比Fig. 7 Comparison of optimization curves of different algorithms for three factories

由圖6、圖7 中ISSA 與SSA、PSO 算法尋優(yōu)曲線對(duì)比可以看出，在求解2 家工廠、3 家工廠mt10、la05、la10、la15 測(cè)試問(wèn)題時(shí)，ISSA 尋優(yōu)曲線基本位于SSA、PSO 尋優(yōu)曲線左下方，且除2 家工廠la10、3家工廠mt10、la15 測(cè)試問(wèn)題外，其余測(cè)試問(wèn)題尋優(yōu)曲線ISSA 均在100 次迭代內(nèi)居于領(lǐng)先位置，說(shuō)明ISSA 在求解DFJSP 時(shí)的收斂精度和收斂速度優(yōu)于SSA 和PSO。此外，2 家工廠la10、3 家工廠mt10、la15 測(cè)試問(wèn)題在迭代進(jìn)行100 次后雖沒(méi)能持續(xù)保持領(lǐng)先，但I(xiàn)SSA 能夠在迭代后期跳出局部最優(yōu)，找到更優(yōu)解。綜上可知，利用萊維飛行、學(xué)習(xí)更新策略、正態(tài)云模型、交叉變異等對(duì)經(jīng)典麻雀搜索算法改進(jìn)后，ISSA 能夠有效平衡全局搜索和局部開(kāi)發(fā)，在求解DFJSP 過(guò)程中具有更高的收斂精度和更快的收斂速度。實(shí)驗(yàn)利用ISSA 對(duì)DFJSP 求解得到的最好調(diào)度結(jié)果的部分加工甘特圖如圖8 所示。

圖8 部分算例甘特圖Fig. 8 Partial examples Gantt chart

4 結(jié)束語(yǔ)

本文研究了具有較高復(fù)雜度和求解難度的DFJSP，針對(duì)其特性，建立了以最小化最大完工時(shí)間為優(yōu)化目標(biāo)的調(diào)度模型。為了有效求解該模型，結(jié)合反向?qū)W習(xí)策略、萊維飛行、學(xué)習(xí)更新策略、正態(tài)云模型及交叉變異算子，提出了一種改進(jìn)麻雀搜索算法（ISSA），有效避免了SSA 求解時(shí)易陷入局部最優(yōu)的缺點(diǎn)。通過(guò)仿真實(shí)驗(yàn)與其他算法進(jìn)行對(duì)比，分析驗(yàn)證了ISSA 的性能，表明所提算法能有效求解DFJSP，且具有一定的優(yōu)越性。目前，DFJSP 的相關(guān)研究還有所欠缺，在未來(lái)工作中，將進(jìn)一步改進(jìn)麻雀搜索算法或利用其他算法及其改進(jìn)算法來(lái)求解該問(wèn)題，并探索研究更加符合生產(chǎn)實(shí)際的多目標(biāo)DFJSP。