張聞強(qiáng)，邢 征，楊衛(wèi)東1，

（1.糧食信息處理與控制教育部重點(diǎn)實(shí)驗(yàn)室（河南工業(yè)大學(xué)），鄭州 450001；2.河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，鄭州 450001）

0 引言

現(xiàn)代化制造業(yè)所涉及的供應(yīng)及制造流程正日益數(shù)據(jù)化、智慧化，快速、有效、個(gè)性化的生產(chǎn)模式開始成為主流。在此趨勢(shì)下，制造企業(yè)生產(chǎn)車間的靈活性面臨著嚴(yán)峻的挑戰(zhàn)［1］。如何合理地調(diào)度車間生產(chǎn)任務(wù)，使加工時(shí)間和加工成本最小化，是制約現(xiàn)代化制造企業(yè)發(fā)展的重要因素。其中，車間調(diào)度是指作業(yè)車間在生產(chǎn)能力和生產(chǎn)資源有限的前提下，依據(jù)被加工工件的工藝規(guī)程以及相關(guān)的約束條件，規(guī)劃出多個(gè)工件各工序間最優(yōu)的加工順序組合方案，來使生產(chǎn)系統(tǒng)的綜合性能達(dá)到最佳。在車間調(diào)度優(yōu)化問題的研究中，多目標(biāo)柔性作業(yè)車間調(diào)度問題（Multi-Objective Flexible Job-shop Scheduling Problem，MOFJSP）是最困難也最接近實(shí)際生產(chǎn)環(huán)境的車間調(diào)度優(yōu)化問題［2］。

現(xiàn)有的調(diào)度優(yōu)化算法一般分為兩類：精確算法和啟發(fā)式算法［3］。精確算法雖然具有較高的收斂速率，但算法的靈活性較差，且求解過程相對(duì)繁瑣，需要使用優(yōu)化問題的梯度信息。對(duì)于柔性作業(yè)車間調(diào)度問題（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）這 類 典 型 的NP-Hard（Nondeterministic Polynomial Hard）問題［4］，最合適的優(yōu)化技術(shù)是啟發(fā)式算法。關(guān)于這些啟發(fā)式方法的研究屬于進(jìn)化算法（Evolutionary Algorithm，EA）領(lǐng)域［5-6］。EA是一類成熟的具有高魯棒性和廣泛適用性的全局優(yōu)化方法，能夠不受問題性質(zhì)的限制，有效地處理傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜問題。而且由于這些算法對(duì)種群中的大量潛在的解決方案進(jìn)行操作，因此可以更有效和高效地探索大型和崎嶇的搜索空間。

對(duì)于一個(gè)EA，如果希望保證算法可以較快地找到符合期望的近似最優(yōu)解，那么就必須保證算法在探索和開發(fā)之間達(dá)到合理的平衡。然而，基于無免費(fèi)午餐定理［7］，沒有任何單一的搜索方法可以保證完美地解決所有可能的問題，特別是多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem，MOP）。由于MOP的復(fù)雜性，固定的單一策略在解決這類復(fù)雜問題時(shí)可能會(huì)遇到一些困難。因此，合理地兼顧收斂與分布，是打破單一進(jìn)化策略解決MOP固有局限性的好方法［8］。同時(shí)，根據(jù)每個(gè)算法的特點(diǎn)混合不同的進(jìn)化算法，可以發(fā)揮各種算法的優(yōu)勢(shì)從而得到更好的算法改進(jìn)［9］。

近年來，關(guān)于求解MOFJSP的研究相當(dāng)?shù)鼗钴S，已有許多有效的算法被應(yīng)用于解決該問題。李俊青等［10］提出了一種基于Pareto檔案集的混合禁忌搜索（Tabu Search，TS）算法。其中，混合TS算法將Pareto非支配排序算子應(yīng)用于鄰域解集，并包含一種加速Pareto集更新算法。同時(shí)，為了減小搜索空間，為算法設(shè)計(jì)了特殊的插入鄰域和交換鄰域算子。文獻(xiàn)［11］針對(duì)三個(gè)目標(biāo)的MOFJSP開發(fā)了一種混合蛙跳算法。所提的混合蛙跳算法使用了一種改良的種群初始化方法，采用自適應(yīng)策略來為種群中的個(gè)體分配非支配解，并在算法中嵌入了幾種局部搜索方法用以拓展算法在后期的搜索能力。孟冠軍等［12］將TS算法與改進(jìn)的人工蜂群（Artificial Bee Colony，ABC）算法混合來解決MOFJSP。其中主要的改進(jìn)之處在于，在ABC算法的不同階段采用不同的搜索機(jī)制，有效提升了獲得最優(yōu)解的概率。張麗［13］提出了一種混合多目標(biāo)優(yōu)化算法。改進(jìn)算法將NSGA-Ⅱ（Non-dominated Sorting Genetic AlgorithmⅡ）算法與粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法相融合，并對(duì)參數(shù)進(jìn)行有效優(yōu)化，防止算法陷入局部最優(yōu)；同時(shí)修改了精英選擇策略，考慮刪除個(gè)體后對(duì)鄰域個(gè)體擁擠密度的影響，將原本被刪除的較優(yōu)個(gè)體予以保留，以提高種群整體的質(zhì)量。張立果等［14］針對(duì)大多數(shù)算法解決MOFJSP所存在無法在單一目標(biāo)進(jìn)行深度搜索的問題，提出了一種求解多目標(biāo)問題的雙層遺傳算法。改進(jìn)算法舍去了遺傳算法中的選擇算子，并采用了一種新的交叉策略，以犧牲部分收斂速率的代價(jià)充分地提高了種群的多樣性。

使用PSO來解決MOFJSP的研究也有很多。Huang等［15］將PSO與變鄰域搜索算法相結(jié)合來解決MOFJSP。該算法的種群初始化方法為先由分配規(guī)則和調(diào)度規(guī)則產(chǎn)生優(yōu)良個(gè)體，然后由所設(shè)計(jì)的基于最早完成機(jī)（Earliest Completion Machine，ECM）機(jī)制的交叉和變異算子來進(jìn)行擾動(dòng)以產(chǎn)生新的個(gè)體。變鄰域搜索主要應(yīng)用于優(yōu)化全局歷史最優(yōu)解的分布，以增強(qiáng)算法的本地搜索能力。Kamble等［16］將粒子群算法與模擬退火（Simulated Annealing，SA）混合提出了混合算法（PSO-SA）。該算法創(chuàng)新地利用Pareto前沿和擁擠距離來確定粒子的適應(yīng)度，并使用PSO來實(shí)現(xiàn)良好的全局搜索能力。在實(shí)現(xiàn)高效收斂的同時(shí)，結(jié)合SA算子來進(jìn)行局部搜索，以賦予算法避免陷入局部最優(yōu)的能力。文獻(xiàn)［17］中描述了一種混合粒子群優(yōu)化算法，采用基于作業(yè)工序和機(jī)器分配的粒子表示方法，在離散域中直接更新粒子。該算法中混合使用了鮑德溫學(xué)習(xí)機(jī)制和SA來平衡全局搜索和局部搜索，并使用Pareto優(yōu)勢(shì)度來更新外部存檔中的歷史最優(yōu)個(gè)體。王云等［18］將密集距離排序方法融入PSO中，同時(shí)使用精英保留策略保存進(jìn)化過程中的優(yōu)勢(shì)個(gè)體，基于個(gè)體密集距離降序排列進(jìn)行外部種群的縮減和全局最優(yōu)值的更新，并引入變異機(jī)制以增強(qiáng)種群的多樣性和算法的全局搜索能力。仲于江等［19］嘗試?yán)肞SO算法獲得存儲(chǔ)非劣解的外部存檔，再基于小生境技術(shù)計(jì)算粒子的刪除概率對(duì)其進(jìn)行更新，并在最終解集的處理上提出了一種總體價(jià)值估計(jì)選取方法，以便于從最終解集中確定符合需求的折中解。毛天曄［20］改進(jìn)了PSO的進(jìn)化方式，通過使用三種不同的途徑移動(dòng)算子來保證工序序列向量和機(jī)器分配向量間的協(xié)同進(jìn)化，并提出一種動(dòng)態(tài)判斷種群停滯的機(jī)制，將PSO算法和TS算法有效結(jié)合；此外，改進(jìn)算法還使用了基于關(guān)鍵路徑的禁忌鄰域結(jié)構(gòu)，這收縮了鄰域空間的大小，提高了鄰域搜索的效率。尉雅晨［21］提出了獨(dú)立自適應(yīng)參數(shù)調(diào)整的PSO算法。改進(jìn)算法使用了慣性權(quán)重及學(xué)習(xí)因子的獨(dú)立調(diào)整策略，以動(dòng)態(tài)優(yōu)化算法參數(shù)；同時(shí)，改進(jìn)算法中以粒子的適應(yīng)度值和進(jìn)化能力作為指標(biāo)對(duì)種群進(jìn)行采樣劃分，并根據(jù)子種群的特性分別采用粒子重構(gòu)策略和差分變異策略兩種不同的操作更新粒子。

雖然目前關(guān)于解決MOFJSP已有了較多的研究，但多數(shù)研究僅針對(duì)算法進(jìn)行改進(jìn)，較少有研究者考慮針對(duì)問題特點(diǎn)改進(jìn)算法的相關(guān)策略；因此本文提出了基于多區(qū)域采樣策略的混合粒子群優(yōu)化算法（Hybrid Particle Swarm Optimization algorithm with Multi-Region Sampling strategy，HPSO-MRS）。HPSO-MRS的主要特點(diǎn)是：在問題層面上，針對(duì)FJSP設(shè)計(jì)了相應(yīng)的帶插空機(jī)制的解碼策略和基于鄰域差異的交叉算子，增強(qiáng)算法的問題搜索能力；在算法層面上，為了增強(qiáng)多目標(biāo)PSO中趨近Pareto前沿面多個(gè)區(qū)域的強(qiáng)收斂能力，設(shè)計(jì)了多區(qū)域采樣（Multi-Region Sampling，MRS）策略，有針對(duì)性地調(diào)整粒子在多個(gè)方向上的收斂能力，并帶來一定程度上均勻分布能力的提升。同時(shí)，由于HPSO-MRS的算法框架中并未設(shè)定特殊的個(gè)體擁擠距離計(jì)算和維持機(jī)制，一定程度上降低了計(jì)算時(shí)間，并依靠多方向強(qiáng)收斂帶來一定的分布性能維持能力。

1 FJSP描述

FJSP的主要特點(diǎn)是，要在某個(gè)作業(yè)車間中加工一批工件，每個(gè)工件由一組工序集合構(gòu)成，這些工序遵循順序約束，即第一個(gè)工序未完成時(shí)第二個(gè)工序無法開始；同時(shí)，每個(gè)工序?qū)?yīng)一組具備加工能力的機(jī)器集合，機(jī)器具備不可搶占性和不可中斷性。正因此特點(diǎn)，F(xiàn)JSP在求解時(shí)不僅要考慮確定作業(yè)路徑，還需要確定每個(gè)工序?qū)?yīng)的處理機(jī)器，其中涉及了大量的約束關(guān)系，因此該問題實(shí)際的求解過程相對(duì)復(fù)雜，在求解該問題的過程中很容易陷入局部最優(yōu)。

為了清晰地描述所考慮的問題，使用以下的符號(hào)。

1）索引：

i，h為工件索引；i，h=1，2，…，n；

j為機(jī)器索引；j=1，2，…，m；

k，g為工件的工序順序索引，k，g=1，2，…，ni；

v為機(jī)器上的工序順序索引，v=1，2，…，mj。

2）參數(shù)：

n為工件總數(shù)；

m為機(jī)器總數(shù)；

ni為工件i的工序總數(shù)；

mj為機(jī)器j上處理的工序總數(shù)；

A（i，k）為工件i第k個(gè)工序的可用機(jī)器集合；

oik為工件i的第k個(gè)工序；

pikj為工件i的第k個(gè)工序在機(jī)器j上的加工時(shí)間；

wjv為機(jī)器j上第v個(gè)被加工的工序；

qvj為機(jī)器j上第v個(gè)被加工工序的加工時(shí)間。

3）決策變量：

cik=工序oik的完成時(shí)間；

tjv=wjv的完成時(shí)間

其中，參數(shù)mj、wjv和qvj是過渡參數(shù)。參數(shù)wjv與oik描述的均為某個(gè)工序，但oik可以在問題集中被找到，wjv則只能從具體解碼出的調(diào)度時(shí)間表當(dāng)中得知。同樣地，參數(shù)mj和qvj也是一樣的情況。根據(jù)符號(hào)，考慮的FJSP可以表述為：

目標(biāo)函數(shù)（最小化）：

約束條件：

式（1）～（2）是最小化最大完工時(shí)間（Makespan，Cmax）和總機(jī)器延遲時(shí)間（Total Machine Delay Time，Td）的目標(biāo)函數(shù)。在式（2）中，如果存在某個(gè)解決方案在機(jī)器j上只分配了一個(gè)工序，那么Td=tj1-q1j-0。如果機(jī)器j上沒有分配工序，則Td=0。解空間由8條約束集來描述。在式（3）中，規(guī)定同一個(gè)作業(yè)中工序的先后順序，oi(k-1)加工完成前oik無法啟動(dòng)。式（4）說明在處理某個(gè)工序時(shí)，應(yīng)從工序的可用機(jī)器集合A（i，k）中選擇且僅能選擇一臺(tái)機(jī)器用于加工oik。對(duì)于同時(shí)分配在同一臺(tái)機(jī)器j上兩個(gè)工序oik與ohg，如果oik在ohg之前到達(dá)，那么ohg的啟動(dòng)時(shí)間應(yīng)大于等于oik的完成時(shí)間，如式（5）所述。當(dāng)然，在式（6）中，如果ohg在oik之前到達(dá)，那么oik的啟動(dòng)時(shí)間同樣應(yīng)大于等于ohg的完成時(shí)間。同理，式（7）規(guī)定，在同一臺(tái)機(jī)器j上分配的所有工序都應(yīng)滿足像式（5）和式（6）中的規(guī)則。式（8）中給出了機(jī)器選擇決策變量的取值范圍，式（9）～（10）規(guī)定了任意工序的完成時(shí)間均大于等于0。

2 基于多區(qū)域采樣混合粒子群優(yōu)化算法

2.1 HPSO-MRS

HPSO-MRS的總體結(jié)構(gòu)如圖1所示。其中初始化粒子群將在2.2節(jié)中描述；計(jì)算適應(yīng)度值為分別計(jì)算粒子群中個(gè)體的式（1）與式（2）的數(shù)值；更新外部存檔采用先將當(dāng)前非支配解加入全局歷史最優(yōu)粒子（Gbest）集合與每個(gè)粒子的個(gè)體歷史最優(yōu)粒子（Pbest）集合，再從集合中去除所有被支配解的方法；多區(qū)域采樣策略將在2.3節(jié)中展開；更新粒子位置的方法將在2.4節(jié)中描述。更為詳細(xì)的過程在算法1中給出。

圖1 HPSO-MRS總體結(jié)構(gòu)Fig.1 Overall structure of HPSO-MRS

算法1 HPSO-MRS。

輸入：問題數(shù)據(jù)，參數(shù)；

輸出：全局搜索到的最優(yōu)解集（Gbest集合）。

1）初始化粒子群（大小為N）；

2）while最大評(píng)價(jià)次數(shù)do

3）根據(jù)式（1）與式（2）計(jì)算每個(gè)粒子的適應(yīng)度值；

4）將所有非支配粒子放入Gbest集合；

5）去除Gbest集合中的所有被支配解；

6）for每個(gè)粒子do

7） 將粒子放入該個(gè)體對(duì)應(yīng)的Pbest集合；

8） 從該P(yáng)best集合中移除所有被支配解；

9）end for

//多區(qū)域采樣策略（MRS）

10）粒子群中的所有粒子根據(jù)式（1）的數(shù)值排序并根據(jù)Fit1的子種群規(guī)模選取粒子；

11）所有粒子根據(jù)PDDR-FF函數(shù)數(shù)值排序并根據(jù)PDDR的子種群規(guī)模選取粒子；

12）所有粒子根據(jù)式（2）的數(shù)值排序并根據(jù)Fit2的子種群規(guī)模選取粒子；

13）for子種群Fit1中的每個(gè)粒子do

14）采用二元競賽選擇法，根據(jù)適應(yīng)度函數(shù)（1）的值對(duì)Pbest和Gbest進(jìn)行選擇，并更新粒子位置；

15）end for

16）for子種群PDDR中的每個(gè)粒子do

17）采用二元競賽選擇法隨機(jī)Pbest和Gbest進(jìn)行選擇，并更新粒子位置；

18）end for

19）for子種群Fit2中的每個(gè)粒子do

20）采用二元競賽選擇法，根據(jù)適應(yīng)度函數(shù)（2）的值對(duì)Pbest和Gbest進(jìn)行選擇，并更新粒子位置；

21）end for

22）所有子種群合并成重組粒子群（大小為N）；

23）end while

24）returnGbest集合；

2.2 編解碼與粒子初始化

本文采用兩段編碼，分別是工序分配（Operation Assignment，OA）決策變量和機(jī)器選擇（Machine Selection，MS）決策變量。表1中給出一個(gè)4×4的FJSP示例。

表1 FJSP示例Tab.1 FJSP instance

根據(jù)示例與編碼規(guī)則可有如下編碼，如圖2中的OA與MS序列所示。OA序列分別是每個(gè)作業(yè)中工序的排序，作業(yè)中有幾個(gè)工序，作業(yè)序號(hào)就重復(fù)出現(xiàn)幾次，首次出現(xiàn)的相同作業(yè)序號(hào)代表該作業(yè)的第一個(gè)工序，第二次出現(xiàn)即代表該作業(yè)的第二個(gè)工序。OA序列的數(shù)值順序敏感，任意交換兩個(gè)位置的數(shù)值可能會(huì)影響其他位置數(shù)值的釋義。初始化粒子時(shí)，通過擾亂一條合法的OA序列中等位基因的排序來產(chǎn)生新的序列。MS序列分別是從J1到J4的每個(gè)工序的機(jī)器選擇決策變量，變量數(shù)值為該工序?qū)?yīng)所有可加工機(jī)器列表的下標(biāo)。另外，MS序列的數(shù)值不具備順序關(guān)系。初始化粒子時(shí)，MS序列中的每一位數(shù)字從該工序?qū)?yīng)的可加工機(jī)器列表的下標(biāo)中隨機(jī)產(chǎn)生。

圖2 編解碼示例Fig.2 Encodingand decoding instance

解碼時(shí)，先讀取一位OA，根據(jù)該序號(hào)對(duì)應(yīng)的作業(yè)序號(hào)以及該序號(hào)是第幾次出現(xiàn)確定這位基因?qū)?yīng)的是哪個(gè)工序。再由MS序列對(duì)應(yīng)這個(gè)工序的決策變量決定這個(gè)工序所在的處理機(jī)器。釋義結(jié)果如圖3所示。在生成時(shí)間表時(shí)，如果使用常規(guī)解碼策略解碼，如OA的第一位為1，MS的第1位為1，則o11要在機(jī)器M1上加工，處理時(shí)間為1；OA第二位為2，MS的第4位為1，則o21要在機(jī)器M2上加工，處理時(shí)間為4。以該規(guī)則解碼的甘特圖如圖3上半部所示，在該方案中，最大完工時(shí)間為14，總機(jī)器延遲時(shí)間為22。

圖3 帶插空機(jī)制的解碼方法Fig.3 Decoding method with interpolation mechanism

由于FJSP需要針對(duì)每個(gè)工件的單個(gè)工序來確定具體的作業(yè)路徑，故而調(diào)度的結(jié)果中可能包含部分局部左移。因此針對(duì)這種問題，在解碼方法中添加了插空機(jī)制。帶插空機(jī)制的解碼策略在遵循OA序列決定的工序順序的同時(shí)，如果某個(gè)工序已被調(diào)度需要加入時(shí)間表，則判斷調(diào)度時(shí)間表當(dāng)中對(duì)應(yīng)機(jī)器的所有空閑時(shí)間段。如果某個(gè)空閑時(shí)間段滿足這個(gè)工序開始加工的所有約束，并且滿足加工的處理時(shí)間長度，則在這段空閑時(shí)間段中放置工序，否則將該工序按照約束關(guān)系添加至該機(jī)器加工隊(duì)列的隊(duì)尾。針對(duì)同一段編碼，帶插空機(jī)制的解碼策略調(diào)度產(chǎn)生的甘特圖如圖3下半部所示。由于機(jī)器M4的空閑時(shí)間段（1-4）滿足o12開始加工的所有約束，所以o12工序可以被提前到o22工序之前完成。同樣地，工序o13、o31、o32均可以被提前處理。在帶插空機(jī)制的解碼策略解碼出的甘特圖中，最大完工時(shí)間為11，總機(jī)器延遲時(shí)間為14。

通過對(duì)比兩種解碼方法的甘特圖和兩個(gè)目標(biāo)函數(shù)值可知，針對(duì)完全相同的粒子編碼序列，帶插空機(jī)制的解碼方法可以得到更好的調(diào)度方案。在第3章的實(shí)驗(yàn)部分，為了得到合理的對(duì)比結(jié)果，所有的算法均采用改進(jìn)的解碼策略。

2.3 多區(qū)域采樣策略

由于本文所考慮的MOFJSP同時(shí)最小化兩個(gè)優(yōu)化目標(biāo)，因此在問題求解過程中會(huì)存在許多非支配解，故而在考慮算法最終結(jié)果收斂性的同時(shí)，也需要注重分布性能。

本文使用基于Pareto支配和被支配關(guān)系的適應(yīng)度函數(shù)（Pareto Dominance and Dominated Relationship Fitness Function，PDDR-FF）來篩選種群中的非支配個(gè)體［22］。PDDRFF函數(shù)的計(jì)算過程如式（11）所述：

其中：q（k）是粒子群中支配粒子k的粒子個(gè)數(shù)，p（k）是粒子k支配粒子群中其他粒子的個(gè)數(shù)，pSize是粒子群中粒子的個(gè)數(shù)。較小的eval（k）說明粒子k在當(dāng)前粒子群中擁有較好的收斂性，據(jù)此可以區(qū)分出種群中較為靠近Pareto的個(gè)體粒子。同時(shí)，矢量評(píng)估遺傳算法（Vector Evaluated Genetic Algorithm，VEGA）在解決多目標(biāo)優(yōu)化問題時(shí)，選擇將個(gè)體分別在不同的單個(gè)目標(biāo)上進(jìn)行優(yōu)化，因此VEGA具備著優(yōu)良的分布性能。

MRS策略綜合了上述函數(shù)和算法的優(yōu)點(diǎn)，將粒子群中的粒子根據(jù)自身所在的優(yōu)勢(shì)區(qū)域加以區(qū)分，并指導(dǎo)這些粒子在自己的優(yōu)勢(shì)方向上繼續(xù)移動(dòng)。如圖4所示，在PSO中，通過添加特定的選擇策略分別選擇出靠近Pareto中心和兩個(gè)邊緣區(qū)域的粒子，讓靠近Pareto中心區(qū)域的粒子繼續(xù)向中心區(qū)域移動(dòng)，靠近Pareto的兩個(gè)邊緣區(qū)域的粒子繼續(xù)向兩個(gè)邊緣區(qū)域移動(dòng)，從而在確保算法的收斂性能的同時(shí)保證分布性能。讓粒子向特定方向的移動(dòng)，是通過粒子在更新位置時(shí)，為粒子選擇在這些方向上較好的Pbest和Gbest來實(shí)現(xiàn)的，如圖5所示。

圖4 粒子劃分示意圖Fig.4 Schematic diagram of particle partition

圖5 子種群粒子更新示意圖Fig.5 Schematic diagram of subpopulation particleupdate

適應(yīng)度函數(shù)f1與f2指的是本文所解決的MOFJSP中最小化的兩個(gè)目標(biāo)函數(shù)。劃分子種群時(shí)，根據(jù)VEGA的思想，靠近Pareto上邊緣區(qū)域的粒子在適應(yīng)度函數(shù)f1（式（1））上會(huì)具有較小的數(shù)值，因此可以根據(jù)適應(yīng)度函數(shù)值f1的數(shù)值大小來選擇靠近Pareto上邊緣區(qū)域的子種群（Fit1）中的粒子。同樣地，靠近Pareto下邊緣區(qū)域的粒子會(huì)具有較小的適應(yīng)度值f2（式（2）），根據(jù)適應(yīng)度值f2的數(shù)值大小來選擇該方向上子種群（Fit2）中的粒子。根據(jù)PDDR-FF的思想，如果當(dāng)前種群中某個(gè)粒子被支配的數(shù)量越少、支配其他粒子的數(shù)量越多，PDDRFF數(shù)值就越小，相對(duì)整個(gè)粒子群而言也就越靠近Pareto中心區(qū)域。因此靠近Pareto中心區(qū)域的子種群（PDDR）中的粒子根據(jù)PDDR-FF指標(biāo)的數(shù)值大小來選擇。此外，分別劃分三個(gè)子種群的操作流程均是將粒子群中的所有粒子按照不同的數(shù)值依據(jù)進(jìn)行排序，并根據(jù)預(yù)設(shè)的子種群大小從排序的結(jié)果中依序取得。

選擇參考位置時(shí)，均采用二元競賽選擇法從參考位置集合中選取。對(duì)于Fit1中的粒子，選擇Gbest時(shí)根據(jù)規(guī)則，從全局的Gbest集合中隨機(jī)選擇兩個(gè)個(gè)體，將函數(shù)值f1更小的一個(gè)作為本次更新所參考的Gbest；選擇Pbest時(shí)，從被更新粒子個(gè)體的Pbest集合中隨機(jī)選擇兩個(gè)個(gè)體，將函數(shù)值f1更小的作為本次更新所參考的Pbest。Fit2中的粒子采用同樣的方法來選擇參考位置，但競賽勝出的規(guī)則改為適應(yīng)度值f2更小。對(duì)于PDDR中的粒子，由于全局的Gbest集合以及被更新粒子對(duì)應(yīng)的Pbest集合中存儲(chǔ)的都是非支配解，無法根據(jù)PDDR-FF函數(shù)加以區(qū)分，因此隨機(jī)選擇任意一個(gè)即可。

本文第3章中參與比較的HPSO不具備劃分子種群的操作，同時(shí)HPSO中對(duì)于參考位置的選擇均是隨機(jī)選擇。

2.4 粒子更新方式

由式（11）～（12）可知，在經(jīng)典PSO算法中，粒子的移動(dòng)主要受到自身慣性、Pbest以及Gbest三部分的指導(dǎo)，但加速度的表達(dá)使得經(jīng)典PSO在解決離散的組合優(yōu)化問題時(shí)變得困難。為了使PSO可以更好地處理MOFJSP，本文混合了遺傳算法的交叉和變異算子來更新粒子位置［23］。HPSO-MRS的粒子更新公式如式（14）所述。其中使用的F1為一種基于鄰域差異的交叉操作。F2是變異操作。

對(duì)應(yīng)經(jīng)典PSO的三部分指導(dǎo)，HPSO也由兩個(gè)交叉算子以及一個(gè)變異算子來更新粒子位置。操作的流程由如下三個(gè)部分構(gòu)成。

第二部分為等式（16），是該粒子的“社會(huì)”部分，代表粒子之間的協(xié)作。其中λit+1是中間粒子。

最后，第三部分為一個(gè)概率為ω的變異操作，如等式（17），代表粒子本身的突變，為搜索過程提供擾動(dòng)。

交叉算子即等式（14）～（16）中的函數(shù)F1。由于粒子編碼中的OA與MS序列結(jié)構(gòu)的不同，交叉算子對(duì)這兩部分的操作也不同，OA部分的交叉應(yīng)注重避免非法解的產(chǎn)生。

OA序列交叉前需要尋找與參考位置間的差異。具體的操作流程在圖6中給出。從當(dāng)前位置OA序列的第一個(gè)等位基因出發(fā)，對(duì)比參考位置的第一位等位基因，如果不同，則在當(dāng)前位置的OA序列中從第二位開始向后查找與參考位置內(nèi)容相同的等位基因。找到后，將當(dāng)前位置OA序列中的第一位等位基因與找到的等位基因進(jìn)行交換，并記錄這個(gè)交換所涉及的兩個(gè)下標(biāo)，如表2所示。另外，當(dāng)前位置的等位基因與參考位置的等位基因攜帶的信息相同時(shí)，則參考位置不需要執(zhí)行鄰域動(dòng)作。

圖6 OA部分鄰域差異獲取示意圖Fig.6 Schematic diagram of OA neighborhood difference acquisition

表2 獲取的鄰域動(dòng)作Tab.2 Acquired neighborhood actions

在該過程中所找到的所有鄰域動(dòng)作可以視為當(dāng)前位置到參考位置的總距離，按照一定的步長去執(zhí)行這些鄰域動(dòng)作則可以視作當(dāng)前位置向參考位置的移動(dòng)。假設(shè)本次交叉的步長參數(shù)c1=0.5，隨機(jī)數(shù)R1=0.8，則本次更新執(zhí)行的步長為2，故選擇的鄰域動(dòng)作即表2中的（1，3），（4，7），執(zhí)行交叉的過程及結(jié)果則如圖7所示。

圖7 OA部分交叉示意圖Fig.7 Schematic diagram of OA crossover operation

MS序列交叉時(shí)，從參考粒子的MS序列中隨機(jī)選擇一位等位基因，然后將當(dāng)前粒子的MS序列中相同位置的內(nèi)容更改為所選擇的等位基因。重復(fù)執(zhí)行這個(gè)操作，直到滿足本次交叉的最大操作次數(shù)。操作的次數(shù)由OA序列執(zhí)行鄰域動(dòng)作的步長確定。由于本次交叉的示例中使用的步長為2，故MS序列交叉的結(jié)果如圖8所示。

圖8 MS部分交叉操作示意圖Fig.8 Schematic diagram of MS crossover operation

變異算子即式（13）與式（16）中的函數(shù)F2。在決定是否進(jìn)行變異操作時(shí)，隨機(jī)產(chǎn)生一個(gè)［0，1］的任意實(shí)數(shù)，如果小于ω，則執(zhí)行變異，否則跳過該操作。該變異操作遵循隨機(jī)性原則，具體的操作如圖9所示。在當(dāng)前位置的OA序列中，隨機(jī)選擇兩個(gè)下標(biāo)，交換兩個(gè)下標(biāo)對(duì)應(yīng)位置中的內(nèi)容。在MS序列中，隨機(jī)挑選一位等位基因，將該位置的內(nèi)容根據(jù)其對(duì)應(yīng)操作的可用機(jī)器集合進(jìn)行重新隨機(jī)選擇。

圖9 OA及MS部分變異操作示意圖Fig.9 Schematic diagram of OA and MS mutation operation

3 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)在Windows10系統(tǒng)下進(jìn)行，CPU為Inter Core i5-4590CPU@3.30 GHz，內(nèi)存為8 GB，實(shí)驗(yàn)環(huán)境是IntelliJ IDEA2019.2版本。數(shù)據(jù)集采用Benchmark問題Mk01～Mk10。對(duì)比算法分別為不包含MRS策略的經(jīng)典多目標(biāo)HPSO、基于非支配排序的經(jīng)典多目標(biāo)遺傳算法NSGA-Ⅱ、基于適應(yīng)度分配策略的多目標(biāo)進(jìn)化算法（Strength Pareto Evolutionary Algorithm 2，SPEA2）以及基于分解的多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm based on Decomposition，MOEA/D）。所有對(duì)比算法與本文提出的改進(jìn)算法HPSO-MRS均使用了2.2節(jié)中的改進(jìn)解碼策略與2.4節(jié)中的交叉變異算子。此外，在所有數(shù)據(jù)集上，每個(gè)算法各運(yùn)行30次。

3.1 評(píng)價(jià)指標(biāo)

本次實(shí)驗(yàn)分別使用評(píng)價(jià)指標(biāo)HV（Hyper Volume）、IGD（Inverted Generational Distance）、Spacing來評(píng)估不同算法之間的解集質(zhì)量。其中：

HV是解集中的個(gè)體所支配的空間大小。較大的HV指標(biāo)值意味著更好的收斂性能。本實(shí)驗(yàn)中HV的參考點(diǎn)設(shè)定為在各目標(biāo)上尋找到的最差的適應(yīng)度值。

IGD是通過計(jì)算Pareto前沿到解集的距離得出的。當(dāng)解集接近Pareto前沿時(shí)，較小的IGD指標(biāo)值要求解集中個(gè)體的分布類似于Pareto前沿。越小的IGD指標(biāo)值意味著更好的收斂性能和分布性能。

Spacing根據(jù)解集中每個(gè)解決方案與其他解決方案之間的最短距離來得出。較小的Spacing指標(biāo)值意味著更好的分布性能。

因此，本次實(shí)驗(yàn)中主要使用指標(biāo)HV和IGD來評(píng)估算法的收斂性能，使用指標(biāo)Spacing來評(píng)估算法的分布性能。

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

本次實(shí)驗(yàn)在10個(gè)Benchmark問題上進(jìn)行測試，數(shù)據(jù)集是部分柔度FJSP，分別為Mk01～Mk10［24］。數(shù)據(jù)集的工件數(shù)量、機(jī)器數(shù)量以及工序?qū)?yīng)的平均機(jī)器數(shù)如表3所示。

表3 數(shù)據(jù)集規(guī)模及差異Tab.3 Dataset sizeand difference

算法參數(shù)的配置情況如表4所示。所有算法的最大評(píng)價(jià)次數(shù)均設(shè)置為10 000，種群大小均為100，變異率均設(shè)置為0.2，隨機(jī)步長范圍均為0～1的任意實(shí)數(shù)。遺傳算法的交叉率設(shè)置為0.8，步長設(shè)置為0.2。此外，HPSO-MRS與HPSO關(guān)于Pbest的步長設(shè)置為0.2，關(guān)于Gbest的步長設(shè)置為0.4。HPSO-MRS還需配置子種群大小，本次實(shí)驗(yàn)對(duì)于大小為100的種群將三個(gè)子種群的數(shù)量分別設(shè)置為30/40/30。

表4 不同算法的參數(shù)配置Tab.4 Parameter configuration of different algorithms

在算法效力方面，HV指標(biāo)均值以及顯著性分析結(jié)果在表5中展示，其中”+”“-”“*”分別意味著相對(duì)于HPSO-MRS，對(duì)比算法是顯著性好、顯著性差和結(jié)果相似（使用Wilcoxon’s rank sum test，0.05置信度下的結(jié)果，下同）。根據(jù)顯著性分析結(jié)果可以看出，在85%的對(duì)照組中，HPSO-MRS均要顯著優(yōu)于其他四個(gè)對(duì)比算法，且30次結(jié)果的HV均值方面也均優(yōu)于其他算法。因此，HPSO-MRS在多數(shù)情況下所搜索到的最終解集與參考點(diǎn)所構(gòu)成的支配空間最大，故而HPSO-MRS相較于其他四個(gè)對(duì)比算法可以更穩(wěn)定地獲得收斂性更好的最終解集。

表5 HV指標(biāo)均值及顯著性分析結(jié)果Tab.5 Average HV and significanceanalysis results

表6中列舉了30次運(yùn)行結(jié)果IGD指標(biāo)的各項(xiàng)分析結(jié)果?？梢钥闯?，除少數(shù)情況下無法確認(rèn)優(yōu)于其他對(duì)比算法的顯著性，77.5%的對(duì)照組中HPSO-MRS仍舊顯著優(yōu)于對(duì)比算法。據(jù)此，結(jié)合五個(gè)算法的IGD指標(biāo)均值，可以看出HPSO-MRS在多數(shù)情況下的最終解集最為靠近Pareto前沿、且分布情況更加接近于Pareto前沿面。

表6 IGD指標(biāo)均值及顯著性分析結(jié)果Tab.6 Average IGD and significanceanalysis results

Spacing的指標(biāo)數(shù)據(jù)分析情況在表7中給出。在指標(biāo)的顯著性分析結(jié)果中，HPSO-MRS不具備顯著優(yōu)于HPSO的能力，但10個(gè)數(shù)據(jù)集下的指標(biāo)均值多數(shù)優(yōu)于HPSO。此外，HPSOMRS共在35%的對(duì)照組中顯著優(yōu)于對(duì)比算法，且其他四個(gè)對(duì)比算法均不存在顯著優(yōu)于HPSO-MRS的情況。因此，HPSOMRS的分布性能相較HPSO已經(jīng)有所改善，且要優(yōu)于其他三個(gè)對(duì)比算法。

表7 Spacing指標(biāo)均值及顯著性分析結(jié)果Tab.7 Average Spacing and significanceanalysis results

通過以上指標(biāo)對(duì)算法的評(píng)估可以得出，在算法效力方面，由于MRS策略經(jīng)過劃分子種群與分別為不同子種群中的粒子選擇參與指導(dǎo)粒子移動(dòng)的參考粒子，從而增強(qiáng)了粒子趨近Pareto前沿面多個(gè)區(qū)域的強(qiáng)收斂能力，進(jìn)而使HPSO-MRS整體具備較好的收斂能力。同時(shí)由于針對(duì)性調(diào)整了粒子在多個(gè)方向上的收斂能力，因此也帶來一定程度的均勻分布能力的提升。

效率方面，表8中給出了每個(gè)算法的平均運(yùn)行時(shí)間（CPU Time），單位為ms。通過算法30次運(yùn)行的平均運(yùn)行時(shí)間可以看出，HPSO-MRS與HPSO在解決較小規(guī)模的數(shù)據(jù)集時(shí)具備良好的運(yùn)行效率，但隨著問題復(fù)雜程度的提高，兩個(gè)算法消耗的時(shí)間開始增加。特別是在Mk08～Mk10中，HPSO-MRS的運(yùn)行時(shí)間高于其余四個(gè)對(duì)比算法。這是由于HPSO-MRS與HPSO算法為每個(gè)粒子都保留了一個(gè)單獨(dú)的Pbest集合來保存搜索過程中粒子搜索到的所有非支配解，故而在解決非支配解較多的復(fù)雜問題時(shí)，個(gè)體的Pbest集合規(guī)模的不斷擴(kuò)大以及動(dòng)態(tài)維護(hù)外部存檔操作耗時(shí)的增加會(huì)使算法耗費(fèi)較多的運(yùn)行時(shí)間。同時(shí)，由于MRS策略的額外計(jì)算，HPSO-MRS總體的運(yùn)行時(shí)間會(huì)略微高于HPSO，但HPSO-MRS中并未設(shè)定特殊的個(gè)體擁擠距離計(jì)算和維持機(jī)制，所以改進(jìn)策略消耗的時(shí)間成本較低?；跓o免費(fèi)午餐定理，沒有任何一個(gè)方法可以在完美解決所有類型優(yōu)化問題的同時(shí)仍具備高效的運(yùn)行效率，因此在算法中添加改進(jìn)的優(yōu)化策略往往導(dǎo)致運(yùn)行時(shí)間成本的增加，本文提出的HPSO-MRS也是如此。綜合HPSO-MRS算法在各個(gè)數(shù)據(jù)集上的效力優(yōu)勢(shì)及運(yùn)行時(shí)間成本，可以確定HPSOMRS在算法時(shí)間方面的略微增加是可接受的。

表8 不同算法的平均運(yùn)行時(shí)間 單位：msTab.8 Average running times of different algorithms unit：ms

4 結(jié)語

本文針對(duì)多目標(biāo)柔性作業(yè)車間調(diào)度問題，提出了基于多區(qū)域采樣策略的混合粒子群優(yōu)化算法。該算法通過結(jié)合VEGA和PDDR-FF函數(shù)的優(yōu)點(diǎn)，將粒子群中的個(gè)體粒子按照與Pareto前沿的位置關(guān)系進(jìn)行劃分重組，并為這些子種群中的粒子選擇合適的參考粒子，以驅(qū)動(dòng)它們繼續(xù)在優(yōu)勢(shì)方向上移動(dòng)。與其他算法相比，HPSO-MRS的收斂性能得到了較好的改善，同時(shí)分布性能也有了一定的提升。但該策略需要?jiǎng)討B(tài)維護(hù)較多的外部存檔，在解決較為復(fù)雜的問題時(shí)，隨著數(shù)據(jù)集中非支配解數(shù)量的增加算法的運(yùn)行效率可能會(huì)受到限制。下一步可將子種群劃分的比例與搜索狀態(tài)特征進(jìn)行耦合，嘗試在不同代數(shù)下根據(jù)粒子群中粒子分布的狀態(tài)動(dòng)態(tài)調(diào)整劃分比例，以在保持收斂性能的前提下進(jìn)一步提升整體的分布性能。同時(shí)，考慮在算法所動(dòng)態(tài)維護(hù)的外部存檔大小與問題所具有的非支配解數(shù)量之間達(dá)到平衡，以求在解決復(fù)雜數(shù)據(jù)集時(shí)，該策略仍可以擁有較好的運(yùn)行效率。