基于改進灰熵并行優化量子狀態轉移算法求解MOJSP問題

吳貝貝 李喆

摘? 要： 為了解決多目標作業車間調度問題（MOJSP），提出一種改進灰熵并行關聯度的量子狀態轉移算法（QSTA）。構建以最大完工時間、最大拖期時間及總流程時間皆最短的多目標作業車間調度問題模型，利用灰熵權值計算適應度值來引導算法的進化，并將該方法應用于含容忍策略的QSTA中解決MOJSP問題。仿真結果表明，改進灰熵并行關聯度引導QSTA求解MOJSP問題的可行性和有效性，其解優于其他三種智能優化算法，是解決作業車間生產調度問題的一種高效方法。

關鍵詞： MOJSP; 量子狀態轉移; MOJSP建模; 灰色關聯分析; 容忍機制; 仿真分析

中圖分類號： TN911.2?34; TP301.06? ? ? ? ? ? 文獻標識碼： A? ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）10?0069?07

Quantum state transfer algorithm based on improved grey entropy parallel optimization for solving MOJSP

WU Beibei1， LI Zhe2

（1. College of Electrical Engineering， Xinjiang University， Urumqi 830047， China;

2. Center of Network and Information Technology， Xinjiang University， Urumqi 830046， China）

Abstract： A quantum state transition algorithm （QSTA） with improved gray entropy parallel correlation degree is proposed? to solve the MOJSP （multi?objective job?shop scheduling problem）. A MOJSP model is established with the maximum completion time， the maximum delay time and the total process time are the shortest， and the gray entropy weight is used to calculate the fitness value to guide the evolution of the algorithm. This method is applied into the QSTA with tolerance policy to solve the MOJSP. The simulation results show that the improved grey entropy parallel correlation degree guides QSTA is feasible and effective in solving the MOJSP， and its solution is better than that of other three intelligent optimization algorithms， which is an efficient method to solve the MOJSP.

Keywords： MOJSP; quantum state transition algorithm; MOJSP modeling; grey correlation analysis; tolerance mechanism; simulation analysis

0? 引? 言

作業車間調度問題（Job?shop Scheduling Problem，JSP）是一種典型的組合優化問題，屬于NP難題[1]。其研究以求解單目標為主，但在實際生產制造過程中，生產者往往要求生產能夠滿足多個目標而非單一目標。因此，MOJSP更符合生產制造的實際情形，具有非常重要的現實意義。又因其各目標間存在復雜的制約關系，較難達到各目標皆最優，所以也成為一個研究的難點。

在優化MOJSP問題時，適應度值分配（Fitness Assignment）是一個關鍵問題。對單目標問題而言，解的適應度函數和目標函數是一致的，并且可以方便地進行比較和排序。但是當優化多目標問題時，由于多個目標之間存在沖突，僅通過簡單的排序很難評估其解的質量，所以必須全面考慮多個目標。有學者為解決Patero前端的取舍及最優解集采用灰關聯分析法[2?3]，然而，僅采用該方法會導致局部關聯點存在傾向問題。李禾澍等人為求解多目標水文站網優化問題構建了一種基于信息熵的模型，對站網信息量進行定量分析并結合多目標優化方法，可有效地對站網進行優化[4]。鄭斯斯等人為確定設備選型結果，采用將信息熵值法的效用值和多屬性決策相結合的方法，對裝卸設備進行綜合排序[5]。然而，僅采用信息熵卻不能有效利用各目標之間相關聯的信息。狀態轉移算法（State Transition Algorithm，STA）是由周曉君等人于2012年提出的一種新型的隨機性全局優化方法，因其結構簡單、參數少、尋優效率高，得到廣泛的應用[6]。陽春華等人為求解旅行商問題提出了離散狀態轉移算法[7];王聰等人提出一種原對偶狀態轉移算法用于分數階多渦卷混沌系統的辨識[8]。然而，單純的采用STA得到的工序缺乏多樣性，因此引入量子旋轉門操作以豐富工序的多樣性。

本文針對多目標作業車間調度優化問題，構建以最大完工時間、最大拖期時間和總流程時間皆最短為優化目標的MOJSP數學模型。利用信息熵理論與灰色關聯度分析并行地處理各目標函數，解決了僅采用單一分析策略存在的弊端問題，并利用改進灰熵并行關聯度值評判解的優劣。在此基礎上提出一種量子狀態轉移算法（Quantum State Transition Algorithm，QSTA），該算法以改進灰熵并行關聯度作為適應度值求解MOJSP問題，通過仿真實例驗證了所提方法的可行性和有效性。

1? 作業車間調度模型的構建

1.1? 問題描述

JSP問題的一般描述如下：在給定每個工件使用機器的序列、每個工件每道工序的加工時間和每個工件的加工工藝的情況下，設計一種合理的工件加工工序，可使n個待加工的工件在m臺設備上進行加工，且滿足某些性能指標最優化。

1.2? 構建多目標作業車間調度模型

實際生產中，JSP問題具有多目標性。本文綜合考慮工件加工的最大完工時間、最大拖期時間及總流程時間這三個目標，各目標的數學描述如下：

1） 最大完工時間

[f1=Cmax=max{Ci，k|i∈1，2，…，n;k∈1，2，…，m}] （1）

式中，[Ci，k]表示工件i在第k臺設備上的加工完成時間，即工件i的完工時間。

2） 最大拖期時間

[f2=Tmax=max{（0，Li）|i∈1，2，…，n}]? ? ?（2）

式中，[Li=Ci，k-due（i）]，due（i）為工件i的交貨期。式（2）表示工件i的最大拖期時間為工件i的完工時間減去交貨期再與零之間取較大者。

3） 總流程時間

[f3=Smax=i=1nCi，k]? ? ? ? ? ? （3）

針對本文選擇的三個子目標，多目標優化問題的模型可描述為：

[Y=（min f1，min f2，min f3）]? ? ? ? （4）

[Cjk-tik+M（1-aihk）≥Cih]? ? ? ? （5）

[Cjk-Cik+M（1-xihk）≥tjk]? ? ? ? （6）

[Cik≥0]? ? ? ? ? ? ? ? ? ?（7）

[aihk，xijk=0，1]? ? ? ? ? ? ? （8）

[i，j=1，2，…，n;h，k=1，2，…，m]? ? ? ? （9）

式（4）為多目標函數;式（5）表示工序的前后約束關系;式（6）表示工序的非阻塞約束關系;式（7）表示工件的完工時間大于零;式（8）表示工序、機器約束;式（9）表示各下標變量的取值范圍。式中：[tik]和[Cjk]表示工件i在設備k上的加工時間及完工時間;M是一個極大的正數;[aihk=1]表示機器h比機器k優先加工工件i;[xijk=1]表示工件i比工件j優先在設備k上加工;反之，二者皆為0。

2? 基于改進灰熵并行優化QSTA求解問題

2.1? 量子狀態轉移算法

根據量子疊加及量子躍遷理論的特點，通過變換量子旋轉門來生成新的編碼。根據薛定諤方程，量子旋轉門必須為酉正矩陣，量子旋轉門的構造直接影響算法性能。量子旋轉門構造如下：

[cos θi-sin θisin θicos θi]? ? ? ? ? ?（10）

則量子位[αiβi]的量子旋轉門更新過程為：

[αiβi=cos θi-sin θisin θicos θiαiβi]? ? ? （11）

式中：[θi]為量子旋轉門的旋轉角;[αiβi]為更新后的概率幅。

采用狀態轉移算法作為旋轉角搜索策略，同時結合量子旋轉門操作提升算法的全局搜索能力。使用狀態轉移算法中產生候選旋轉角的統一框架可以描述為：

[θk+1=Akθk+Bkukyk+1=f（θk+1）]? ? ? ? （12）

式中：[θk，θk+1∈Rn]分別表示旋轉角的當前狀態與更新后的狀態，當前狀態對應優化問題的一個解，經過一次算子變換產生的[θk+1]將構成一個候選解集;[Ak，Bk∈Rn×n]為狀態轉移矩陣;[uk∈Rn]是關于歷史狀態和狀態[θk]的一個函數表達式;[f（θk+1）]表示狀態更新后的目標函數值。

為了使QSTA求解優化問題時量子旋轉角狀態轉移過程具有可控性，依據傳統狀態轉移算法設計了4種量子旋轉角狀態更新算子。

1） 量子旋轉算子

[θk+1=θk+α1nθk2Rrθk]? ? ? ?（13）

式中：α是一個正的常數，稱為旋轉因子;[Rr∈Rn×n]是一個服從[-1，1]均勻分布的隨機矩陣;[?2]是一個向量的二范數;利用旋轉算子可以使產生的候選解落在半徑為α的超球體內。

2） 量子平移算子

[θk+1=θk+βRtθk-θk-1θk-θk-12]? ? ?（14）

式中：β是一個正的常數，稱為平移因子;[Rt∈R]是一個服從[0，1]均勻分布的隨機變量;平移搜索是一種線搜索，它以[θk]為起點并沿著其指定的方向進行搜索，搜索的最大長度為β。

3） 量子伸縮算子

[θk+1=θk+γReθk]? ? ? ? ? （15）

式中：γ是一個正的常數，稱為伸縮因子;[Re∈Rn×n]是一個服從高斯分布的隨機矩陣。該算子主要用作整個空間內的全局搜索。

4） 量子坐標變換算子

[θk+1=θk+δRaθk]? ? ? ? ? （16）

式中：δ是一個正的常數，稱為坐標因子;[Ra∈Rn×n]是一個服從高斯分布的隨機對角稀疏矩陣，且矩陣中只有一個隨機位置上的元素不為零。坐標算子有利于增強單維搜索能力。

對以上4種算子計算出的旋轉角分別通過量子旋轉門更新量子位，通過量子坍縮操作對量子位進行觀測，生成二進制串通過相應的編碼方式將其映射到解空間中。

2.2? 容忍非局部最優解機制

量子狀態轉移算法每次迭代過程只考慮當前最優解，在此基礎上進行狀態轉移，然而應用量子狀態轉移算法處理JSP問題時容易陷入局部最優。因此本文提出一種對非局部最優解的容忍機制，如表1所示，其能夠有效避免加工序列處于局部最優狀態無法收斂的情況。

本文考慮單次序列的局部變化，可能不會使新序列獲得更好的適應度值，但對同一序列的連續局部變化形成的新序列也有可能導致更好的結果。所以本文設置非局部最優狀態下的容忍次數，允許非局部最優解獲得連續的狀態變化，以此增加解的多樣性，同時可有效地避免某一加工序列陷入局部最優。

2.3? 適應度值分配策略

優化多目標問題的描述如下：確定由可行域中的決策變量所組成的向量，其滿足所有約束并優化由多個目標函數組成的向量，但構成這些向量的多個目標通常彼此矛盾。所以，上述的“優化”是指找到一個或一組解向量以滿足目標向量中的全部目標函數。

2.3.1? 灰熵關聯度適應度值分配策略

在多目標優化算法中存在多種適應度值分配策略，例如基于Pareto優先級關系排序的適應度值分配策略、基于隨機權重求和的適應度值分配策略及基于選擇性權重的適應度值分配策略等。熵是一種測量微觀分布均勻性的方法，它代表了熱力學系統的混沌狀態和生態學中物種的多樣性。本文借助熵值權重的思想，提出基于灰熵關聯的適應度值分配策略，具體步驟如下。

步驟1：使用量子狀態轉移算法分別優化子目標，得到各子目標函數的最優解，構成參考序列[Y0={f1（0），f2（0），…，fM（0）}]，M為目標個數。此外，對于可行解[xi]，逐個對子目標函數值[fm（i）]進行計算，構成比較序列[Yi={f0（i），f1（i），…，fM（i）}]，m=1，2，[…]，M;i=1，2，[…]，N。

步驟2：對理想解和可行解的各目標函數值無量綱化處理。

[f′m（i）=max（Yi）-fm（i）max（Yi）-min（Yi）]? ? ? ?（17）

步驟3：計算灰關聯系數。

[r=miniminmf′m（i）-f′m（0）+ρmaximaxmf′m（i）-f′m（0）f′m（i）-f′m（0）+ρmaximaxmf′m（i）-f′m（0）] （18）

式中，[ρ?（0，1）]為分辨系數，一般取0.5。

步驟4：求可行解各子目標的比重、信息熵及熵值權重。

[Pm（i）=f′m（i）m=1Mf′m（i）]? ? ? ? （19）

[em（i）=-1ln Mi=1N（Pm（i）·ln Pm（i））]? （20）

[Wm（i）=1-em（i）m=1M（1-em（i））]? ? ? ? ?（21）

步驟5：求可行解的灰熵關聯度。

[R（Y0，Yi）=m=1MWm（i）·r（fm（0），fm（i））]? （22）

熵并行分析法是一種將動態灰過程變化趨勢的整體性分析和信息熵相結合的方法，是一種全局性方法。把可行解的灰熵關聯度作為多目標解的適應度值，能夠客觀地表示可行解與理想解之間的相近程度。通常，灰熵并行關聯度的值越大，可行解就越逼近理想解。

2.3.2? 改進灰熵關聯度適應度分配策略

經試驗驗證分析，以灰熵并行關聯度作為最終的優化目標引導智能算法進化，當比較序列與參考序列之間的差值相等時，r=1，則該適應度不能引導智能算法進化。

以算例FT06為例，使用灰熵關聯度作為適應度值，同時優化最大完工時間和總流程時間。各目標優化的最優解所對應的目標函數值可構成參考序列：[Y0={55，228}]，由優化算法搜索得到的可行解所對應的目標函數值構成比較序列：[Yi={fCmax（i），fSmax（i）}，][i=1，2，…，N]。以灰熵關聯度引導QSTA進化可以得到如圖1、圖2所示的結果。

從圖中可以看出，以灰熵并行關聯度作為適應度值存在2個問題：

1） 單目標收斂過程與灰熵關聯度收斂過程不一致。

2） 比較序列（59，232）與參考序列（55，228）之間的的差值相等，大小為4，這導致灰熵關聯度為1，即最大值，算法不再收斂。

以灰熵關聯度作為適應度函數會存在上述問題，因此需要重新構造適應度函數。本文同時考慮灰熵關聯度和序列絕對差，從而得到改進灰熵關聯度適應度函數，且從式（23）中可以看出該值越接近0說明比較序列與參考序列的符合程度越高。