基于多區(qū)域采樣策略的混合粒子群優(yōu)化求解多目標柔性作業(yè)車間調(diào)度問題

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

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

0 引言

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

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

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

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

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

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

1 FJSP描述

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

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

1）索引：

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

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

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

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

2）參數(shù)：

n為工件總數(shù)；

m為機器總數(shù)；

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

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

A（i，k）為工件i第k個工序的可用機器集合；

oik為工件i的第k個工序；

pikj為工件i的第k個工序在機器j上的加工時間；

wjv為機器j上第v個被加工的工序；

qvj為機器j上第v個被加工工序的加工時間。

3）決策變量：

cik=工序oik的完成時間；

tjv=wjv的完成時間

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

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

約束條件：

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

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

2.1 HPSO-MRS

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

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

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

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

6）for每個粒子do

7） 將粒子放入該個體對應的Pbest集合；

8） 從該Pbest集合中移除所有被支配解；

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中的每個粒子do

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

15）end for

16）for子種群PDDR中的每個粒子do

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

18）end for

19）for子種群Fit2中的每個粒子do

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

21）end for

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

23）end while

24）returnGbest集合；

2.2 編解碼與粒子初始化

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

表1 FJSP示例Tab.1 FJSP instance

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 粒子更新方式

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

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

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

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

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

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

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

表2 獲取的鄰域動作Tab.2 Acquired neighborhood actions

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

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

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

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

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

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

3 實驗與結(jié)果分析

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

3.1 評價指標

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

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

IGD是通過計算Pareto前沿到解集的距離得出的。當解集接近Pareto前沿時，較小的IGD指標值要求解集中個體的分布類似于Pareto前沿。越小的IGD指標值意味著更好的收斂性能和分布性能。

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

因此，本次實驗中主要使用指標HV和IGD來評估算法的收斂性能，使用指標Spacing來評估算法的分布性能。

3.2 實驗結(jié)果

本次實驗在10個Benchmark問題上進行測試，數(shù)據(jù)集是部分柔度FJSP，分別為Mk01～Mk10［24］。數(shù)據(jù)集的工件數(shù)量、機器數(shù)量以及工序?qū)钠骄鶛C器數(shù)如表3所示。

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

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

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

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

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

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

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

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

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

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

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

表8 不同算法的平均運行時間 單位：msTab.8 Average running times of different algorithms unit：ms

4 結(jié)語

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