基于改進(jìn)灰熵并行優(yōu)化量子狀態(tài)轉(zhuǎn)移算法求解MOJSP問題

吳貝貝 李喆

摘? 要： 為了解決多目標(biāo)作業(yè)車間調(diào)度問題（MOJSP），提出一種改進(jìn)灰熵并行關(guān)聯(lián)度的量子狀態(tài)轉(zhuǎn)移算法（QSTA）。構(gòu)建以最大完工時(shí)間、最大拖期時(shí)間及總流程時(shí)間皆最短的多目標(biāo)作業(yè)車間調(diào)度問題模型，利用灰熵權(quán)值計(jì)算適應(yīng)度值來引導(dǎo)算法的進(jìn)化，并將該方法應(yīng)用于含容忍策略的QSTA中解決MOJSP問題。仿真結(jié)果表明，改進(jìn)灰熵并行關(guān)聯(lián)度引導(dǎo)QSTA求解MOJSP問題的可行性和有效性，其解優(yōu)于其他三種智能優(yōu)化算法，是解決作業(yè)車間生產(chǎn)調(diào)度問題的一種高效方法。

關(guān)鍵詞： MOJSP; 量子狀態(tài)轉(zhuǎn)移; MOJSP建模; 灰色關(guān)聯(lián)分析; 容忍機(jī)制; 仿真分析

中圖分類號(hào)： TN911.2?34; TP301.06? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)： 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? 引? 言

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

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

本文針對(duì)多目標(biāo)作業(yè)車間調(diào)度優(yōu)化問題，構(gòu)建以最大完工時(shí)間、最大拖期時(shí)間和總流程時(shí)間皆最短為優(yōu)化目標(biāo)的MOJSP數(shù)學(xué)模型。利用信息熵理論與灰色關(guān)聯(lián)度分析并行地處理各目標(biāo)函數(shù)，解決了僅采用單一分析策略存在的弊端問題，并利用改進(jìn)灰熵并行關(guān)聯(lián)度值評(píng)判解的優(yōu)劣。在此基礎(chǔ)上提出一種量子狀態(tài)轉(zhuǎn)移算法（Quantum State Transition Algorithm，QSTA），該算法以改進(jìn)灰熵并行關(guān)聯(lián)度作為適應(yīng)度值求解MOJSP問題，通過仿真實(shí)例驗(yàn)證了所提方法的可行性和有效性。

1? 作業(yè)車間調(diào)度模型的構(gòu)建

1.1? 問題描述

JSP問題的一般描述如下：在給定每個(gè)工件使用機(jī)器的序列、每個(gè)工件每道工序的加工時(shí)間和每個(gè)工件的加工工藝的情況下，設(shè)計(jì)一種合理的工件加工工序，可使n個(gè)待加工的工件在m臺(tái)設(shè)備上進(jìn)行加工，且滿足某些性能指標(biāo)最優(yōu)化。

1.2? 構(gòu)建多目標(biāo)作業(yè)車間調(diào)度模型

實(shí)際生產(chǎn)中，JSP問題具有多目標(biāo)性。本文綜合考慮工件加工的最大完工時(shí)間、最大拖期時(shí)間及總流程時(shí)間這三個(gè)目標(biāo)，各目標(biāo)的數(shù)學(xué)描述如下：

1） 最大完工時(shí)間

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

式中，[Ci，k]表示工件i在第k臺(tái)設(shè)備上的加工完成時(shí)間，即工件i的完工時(shí)間。

2） 最大拖期時(shí)間

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

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

3） 總流程時(shí)間

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

針對(duì)本文選擇的三個(gè)子目標(biāo)，多目標(biāo)優(yōu)化問題的模型可描述為：

[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）為多目標(biāo)函數(shù);式（5）表示工序的前后約束關(guān)系;式（6）表示工序的非阻塞約束關(guān)系;式（7）表示工件的完工時(shí)間大于零;式（8）表示工序、機(jī)器約束;式（9）表示各下標(biāo)變量的取值范圍。式中：[tik]和[Cjk]表示工件i在設(shè)備k上的加工時(shí)間及完工時(shí)間;M是一個(gè)極大的正數(shù);[aihk=1]表示機(jī)器h比機(jī)器k優(yōu)先加工工件i;[xijk=1]表示工件i比工件j優(yōu)先在設(shè)備k上加工;反之，二者皆為0。

2? 基于改進(jìn)灰熵并行優(yōu)化QSTA求解問題

2.1? 量子狀態(tài)轉(zhuǎn)移算法

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

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

則量子位[αiβi]的量子旋轉(zhuǎn)門更新過程為：

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

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

采用狀態(tài)轉(zhuǎn)移算法作為旋轉(zhuǎn)角搜索策略，同時(shí)結(jié)合量子旋轉(zhuǎn)門操作提升算法的全局搜索能力。使用狀態(tài)轉(zhuǎn)移算法中產(chǎn)生候選旋轉(zhuǎn)角的統(tǒng)一框架可以描述為：

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

式中：[θk，θk+1∈Rn]分別表示旋轉(zhuǎn)角的當(dāng)前狀態(tài)與更新后的狀態(tài)，當(dāng)前狀態(tài)對(duì)應(yīng)優(yōu)化問題的一個(gè)解，經(jīng)過一次算子變換產(chǎn)生的[θk+1]將構(gòu)成一個(gè)候選解集;[Ak，Bk∈Rn×n]為狀態(tài)轉(zhuǎn)移矩陣;[uk∈Rn]是關(guān)于歷史狀態(tài)和狀態(tài)[θk]的一個(gè)函數(shù)表達(dá)式;[f（θk+1）]表示狀態(tài)更新后的目標(biāo)函數(shù)值。

為了使QSTA求解優(yōu)化問題時(shí)量子旋轉(zhuǎn)角狀態(tài)轉(zhuǎn)移過程具有可控性，依據(jù)傳統(tǒng)狀態(tài)轉(zhuǎn)移算法設(shè)計(jì)了4種量子旋轉(zhuǎn)角狀態(tài)更新算子。

1） 量子旋轉(zhuǎn)算子

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

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

2） 量子平移算子

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

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

3） 量子伸縮算子

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

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

4） 量子坐標(biāo)變換算子

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

式中：δ是一個(gè)正的常數(shù)，稱為坐標(biāo)因子;[Ra∈Rn×n]是一個(gè)服從高斯分布的隨機(jī)對(duì)角稀疏矩陣，且矩陣中只有一個(gè)隨機(jī)位置上的元素不為零。坐標(biāo)算子有利于增強(qiáng)單維搜索能力。

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

2.2? 容忍非局部最優(yōu)解機(jī)制

量子狀態(tài)轉(zhuǎn)移算法每次迭代過程只考慮當(dāng)前最優(yōu)解，在此基礎(chǔ)上進(jìn)行狀態(tài)轉(zhuǎn)移，然而應(yīng)用量子狀態(tài)轉(zhuǎn)移算法處理JSP問題時(shí)容易陷入局部最優(yōu)。因此本文提出一種對(duì)非局部最優(yōu)解的容忍機(jī)制，如表1所示，其能夠有效避免加工序列處于局部最優(yōu)狀態(tài)無法收斂的情況。

本文考慮單次序列的局部變化，可能不會(huì)使新序列獲得更好的適應(yīng)度值，但對(duì)同一序列的連續(xù)局部變化形成的新序列也有可能導(dǎo)致更好的結(jié)果。所以本文設(shè)置非局部最優(yōu)狀態(tài)下的容忍次數(shù)，允許非局部最優(yōu)解獲得連續(xù)的狀態(tài)變化，以此增加解的多樣性，同時(shí)可有效地避免某一加工序列陷入局部最優(yōu)。

2.3? 適應(yīng)度值分配策略

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

2.3.1? 灰熵關(guān)聯(lián)度適應(yīng)度值分配策略

在多目標(biāo)優(yōu)化算法中存在多種適應(yīng)度值分配策略，例如基于Pareto優(yōu)先級(jí)關(guān)系排序的適應(yīng)度值分配策略、基于隨機(jī)權(quán)重求和的適應(yīng)度值分配策略及基于選擇性權(quán)重的適應(yīng)度值分配策略等。熵是一種測量微觀分布均勻性的方法，它代表了熱力學(xué)系統(tǒng)的混沌狀態(tài)和生態(tài)學(xué)中物種的多樣性。本文借助熵值權(quán)重的思想，提出基于灰熵關(guān)聯(lián)的適應(yīng)度值分配策略，具體步驟如下。

步驟1：使用量子狀態(tài)轉(zhuǎn)移算法分別優(yōu)化子目標(biāo)，得到各子目標(biāo)函數(shù)的最優(yōu)解，構(gòu)成參考序列[Y0={f1（0），f2（0），…，fM（0）}]，M為目標(biāo)個(gè)數(shù)。此外，對(duì)于可行解[xi]，逐個(gè)對(duì)子目標(biāo)函數(shù)值[fm（i）]進(jìn)行計(jì)算，構(gòu)成比較序列[Yi={f0（i），f1（i），…，fM（i）}]，m=1，2，[…]，M;i=1，2，[…]，N。

步驟2：對(duì)理想解和可行解的各目標(biāo)函數(shù)值無量綱化處理。

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

步驟3：計(jì)算灰關(guān)聯(lián)系數(shù)。

[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）]為分辨系數(shù)，一般取0.5。

步驟4：求可行解各子目標(biāo)的比重、信息熵及熵值權(quán)重。

[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：求可行解的灰熵關(guān)聯(lián)度。

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

熵并行分析法是一種將動(dòng)態(tài)灰過程變化趨勢(shì)的整體性分析和信息熵相結(jié)合的方法，是一種全局性方法。把可行解的灰熵關(guān)聯(lián)度作為多目標(biāo)解的適應(yīng)度值，能夠客觀地表示可行解與理想解之間的相近程度。通常，灰熵并行關(guān)聯(lián)度的值越大，可行解就越逼近理想解。

2.3.2? 改進(jìn)灰熵關(guān)聯(lián)度適應(yīng)度分配策略

經(jīng)試驗(yàn)驗(yàn)證分析，以灰熵并行關(guān)聯(lián)度作為最終的優(yōu)化目標(biāo)引導(dǎo)智能算法進(jìn)化，當(dāng)比較序列與參考序列之間的差值相等時(shí)，r=1，則該適應(yīng)度不能引導(dǎo)智能算法進(jìn)化。

以算例FT06為例，使用灰熵關(guān)聯(lián)度作為適應(yīng)度值，同時(shí)優(yōu)化最大完工時(shí)間和總流程時(shí)間。各目標(biāo)優(yōu)化的最優(yōu)解所對(duì)應(yīng)的目標(biāo)函數(shù)值可構(gòu)成參考序列：[Y0={55，228}]，由優(yōu)化算法搜索得到的可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值構(gòu)成比較序列：[Yi={fCmax（i），fSmax（i）}，][i=1，2，…，N]。以灰熵關(guān)聯(lián)度引導(dǎo)QSTA進(jìn)化可以得到如圖1、圖2所示的結(jié)果。

從圖中可以看出，以灰熵并行關(guān)聯(lián)度作為適應(yīng)度值存在2個(gè)問題：

1） 單目標(biāo)收斂過程與灰熵關(guān)聯(lián)度收斂過程不一致。

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

以灰熵關(guān)聯(lián)度作為適應(yīng)度函數(shù)會(huì)存在上述問題，因此需要重新構(gòu)造適應(yīng)度函數(shù)。本文同時(shí)考慮灰熵關(guān)聯(lián)度和序列絕對(duì)差，從而得到改進(jìn)灰熵關(guān)聯(lián)度適應(yīng)度函數(shù)，且從式（23）中可以看出該值越接近0說明比較序列與參考序列的符合程度越高。