基于量子狀態(tài)轉(zhuǎn)移算法的作業(yè)車間調(diào)度問(wèn)題

吳貝貝 李 喆

1(新疆大學(xué)電氣工程學(xué)院 新疆 烏魯木齊 830047) 2(新疆大學(xué)網(wǎng)絡(luò)與信息技術(shù)中心 新疆 烏魯木齊 830046)

Tolerance mechanism

0 引 言

作業(yè)車間調(diào)度問(wèn)題(Job-shop Scheduling Problem,JSP)是一類組合最優(yōu)化問(wèn)題，其實(shí)質(zhì)就是要解決如何合理地安排工件的加工順序，將有限的人力物力資源分配給不同的工作任務(wù)，使預(yù)定的目標(biāo)最優(yōu)化的問(wèn)題。研究該問(wèn)題，對(duì)于在現(xiàn)有的資源條件下提高工作效率和經(jīng)濟(jì)效益有十分重要的作用。目前國(guó)內(nèi)外學(xué)者已經(jīng)用多種智能優(yōu)化算法對(duì)JSP問(wèn)題進(jìn)行了研究。劉洪銘等[1]提出一種改進(jìn)粒子群算法，將自適應(yīng)權(quán)重及混沌策略相融合，有效地提升了粒子的利用率，提高了算法的全局和局部搜索能力。孫在省等[2]針對(duì)特定的可重入JSP問(wèn)題，提出一種基于塊結(jié)構(gòu)性質(zhì)的花粉算法用于最小化總加權(quán)延誤時(shí)間，該算法能夠在可行解空間區(qū)域內(nèi)進(jìn)行全局搜索，從而發(fā)現(xiàn)較優(yōu)解所在的區(qū)域。張垚等[3]提出了一種新型遺傳鄰域萬(wàn)有引力算法，并以此定義了一種新的交叉策略，可有效解決某類大規(guī)模JSP問(wèn)題。Dao等[4]提出了一種基于并行式的蝙蝠算法，采用隨機(jī)鍵編碼方式，以最大完工時(shí)間為優(yōu)化目標(biāo)求解JSP問(wèn)題，實(shí)驗(yàn)表明該方案可有效提升算法的收斂性及平穩(wěn)性能。上述優(yōu)化算法可有效彌補(bǔ)傳統(tǒng)算法所存在的不足，并且為求解JSP問(wèn)題擴(kuò)展了新的方向。

Zhou等[5]于2012年提出狀態(tài)轉(zhuǎn)移算法(State transition algorithm,STA)，這是一種新型的隨機(jī)性全局優(yōu)化方法，因其結(jié)構(gòu)簡(jiǎn)單、參數(shù)少、尋優(yōu)效率高，得到廣泛的應(yīng)用。王聰?shù)萚6]提出了結(jié)合正交學(xué)習(xí)機(jī)制和原對(duì)偶學(xué)習(xí)策略的狀態(tài)轉(zhuǎn)移算法[7]用于分?jǐn)?shù)階多渦卷混沌系統(tǒng)的辨識(shí)。陽(yáng)春華等[8]提出了一種離散狀態(tài)轉(zhuǎn)移算法用于求解旅行商問(wèn)題。王正元等[9]提出了一種基于狀態(tài)轉(zhuǎn)移算法的組合優(yōu)化方案，該策略融合了近似方法、下界算法、降維方法及精確求解的方法。董天雪等[10]在一次狀態(tài)轉(zhuǎn)移的基礎(chǔ)上提出了二次狀態(tài)轉(zhuǎn)移的概念，豐富了解的多樣性，使算法跳出局部最優(yōu)。

量子計(jì)算作為突破當(dāng)前計(jì)算極限的重要技術(shù)，也成為各國(guó)專家學(xué)者密切關(guān)注的前沿學(xué)科之一[11]。量子計(jì)算是將量子理論及智能計(jì)算二者相融合，并應(yīng)用量子并行計(jì)算特性，能夠彌補(bǔ)傳統(tǒng)優(yōu)化算法中的不足，避免算法陷入局部最優(yōu)，提高算法的收斂速度。對(duì)此國(guó)內(nèi)外學(xué)者做了大量的研究工作。黃力明等[12]提出了一種新的量子旋轉(zhuǎn)門調(diào)整策略，確保當(dāng)前解無(wú)論處于何種狀態(tài)都能收斂到一個(gè)更優(yōu)的染色體，即最優(yōu)解染色體。解平等[13]為保證可行解向最優(yōu)解方向搜索，在量子旋轉(zhuǎn)門更新的基礎(chǔ)上同時(shí)引入局部更新操作。閆旭等[14]采用量子計(jì)算和量子優(yōu)化的思想提出了一種量子鯨魚優(yōu)化算法,可有效解決算法出現(xiàn)的收斂精度低、易早熟的問(wèn)題。高輝等[15]通過(guò)嘗試不同的初始旋轉(zhuǎn)角度來(lái)進(jìn)行算例的仿真實(shí)驗(yàn)，并探討分析了初始旋轉(zhuǎn)角對(duì)算法性能所產(chǎn)生的影響。Salido等[16]提出了一些分析公式來(lái)估計(jì)能效、魯棒性和最大完工時(shí)間這些參數(shù)之間的比率關(guān)系。

本文針對(duì)群智能優(yōu)化算法在求解作業(yè)車間調(diào)度問(wèn)題時(shí)過(guò)分依賴初值、局部搜索能力差、收斂速度慢等不足，提出了量子狀態(tài)轉(zhuǎn)移算法(Quantum state transition algorithm,QSTA)，將量子計(jì)算與優(yōu)化的思想引入狀態(tài)轉(zhuǎn)移算法構(gòu)成量子狀態(tài)轉(zhuǎn)移算法，以最大完工時(shí)間最小為目標(biāo)函數(shù)，來(lái)求解JSP問(wèn)題。

1 作業(yè)車間調(diào)度問(wèn)題的數(shù)學(xué)描述

1.1 問(wèn)題描述

JSP問(wèn)題一般被描述為：假定有n個(gè)工件，它們要經(jīng)過(guò)m臺(tái)機(jī)器加工，每個(gè)工件在特定的機(jī)器設(shè)備上進(jìn)行加工被稱為一道“工序”，每道工序的加工時(shí)間是事先確定的。每個(gè)工件的加工工藝過(guò)程是事先給定的，因此，一個(gè)工件可看作一列工序的組成部分。所以調(diào)度需處理的問(wèn)題就是要安排一種合理的工件加工順序及開始加工的時(shí)間，以滿足某種性能指標(biāo)的最優(yōu)。本文所求解的性能指標(biāo)為“最小化最大完工時(shí)間”，并且在求解該問(wèn)題時(shí)必須滿足以下約束條件：

(1) 機(jī)器不存在故障，工件從t=0時(shí)刻開始加工。

(2) 每臺(tái)機(jī)器在任一時(shí)刻最多加工一道工序。

(3) 作業(yè)的加工路線必須嚴(yán)格遵守，一旦開始加工不得中途停止，直至這道工序被加工完。

(4) 每個(gè)作業(yè)的加工工藝固定，不允許改變。

1.2 數(shù)學(xué)模型建立

求解JSP問(wèn)題的實(shí)質(zhì)是指在滿足上述約束條件的情況下，找到一組可行解(可行的加工工序)并令所要求的目標(biāo)函數(shù)達(dá)到最優(yōu)。實(shí)現(xiàn)最小化最大完工時(shí)間，可有效提高車間的生產(chǎn)效率，降低企業(yè)的生產(chǎn)成本，因此將最大完工時(shí)間最小化作為目標(biāo)函數(shù)進(jìn)行求解具有一定的現(xiàn)實(shí)意義。

由于本文求解的決策變量(機(jī)器數(shù)、工件數(shù))均為正整數(shù)，因此利用整數(shù)規(guī)劃模型對(duì)JSP問(wèn)題的數(shù)學(xué)模型進(jìn)行描述：

優(yōu)化目標(biāo)如下：

(1)

約束條件如下：

Cjk-tik+M(1-aihk)≥Cih

(2)

Cjk-Cik+M(1-xihk)≥tjk

(3)

Cik≥0

(4)

aihk,xijk=0,1

(5)

i,j=1,2,…,nh,k=1,2,…,m

(6)

式中：tik和Cik表示第i個(gè)工件在第k臺(tái)機(jī)器上的加工時(shí)間以及完工時(shí)間；M是一個(gè)極大的正數(shù)；aihk=1表示機(jī)器h比機(jī)器k優(yōu)先加工工件i；xijk=1表示工件i比工件j優(yōu)先在機(jī)器k上加工；反之，二者皆為0。

式(1)為目標(biāo)函數(shù)，表示最大完工時(shí)間最?。粍t式(2)表示當(dāng)前工序與上道工序之間的約束關(guān)系；式(3)表示工序之間是非阻塞約束關(guān)系；式(4)表示各工件的完工時(shí)間必須大于零；式(5)表示工序、機(jī)器約束；式(6)表示各下標(biāo)變量的取值范圍。

2 算法描述

2.1 量子比特位編碼

量子計(jì)算[17](Quantum computation,QC)首次于1982年提出，現(xiàn)今已成為國(guó)內(nèi)外專家學(xué)者所密切關(guān)注的前沿問(wèn)題。進(jìn)行量子計(jì)算時(shí)運(yùn)用量子比特表示信息,采用|0〉與|1〉代替微觀粒子所存在的兩種基本狀態(tài),記號(hào)“|〉”稱為Dirac記號(hào),在量子力學(xué)中表示狀態(tài)。除了|0〉和|1〉之外,量子比特還可以是疊加態(tài),即這兩種狀態(tài)之間的中間狀態(tài)：|φ〉=α|0〉+β|1〉,參數(shù)α、β代表一對(duì)復(fù)數(shù),是指量子態(tài)的概率幅,即量子態(tài)|φ〉以|α2|的概率坍縮到|0〉或以|β2|的概率坍縮到|1〉,且滿足：

(7)

量子邏輯門是指對(duì)量子狀態(tài)采用邏輯變換所生成的量子裝置，它是量子計(jì)算可以實(shí)現(xiàn)的基礎(chǔ)。

2.2 解空間映射方法

解空間映射是將量子比特位編碼應(yīng)用于JSP的關(guān)鍵環(huán)節(jié)。編碼時(shí)一定要考慮狀態(tài)的可行性、有效性和對(duì)問(wèn)題解空間表征的完備性。在求解車間調(diào)度問(wèn)題時(shí)，可行解就是工件的排列順序，所以必須將量子位的概率幅轉(zhuǎn)變成工件的加工工序編碼。

在JSP問(wèn)題中，從一組可行解上進(jìn)行有限次位置變換生成的解仍然是可行的，本文采用基于移位解碼的編碼方式和基于實(shí)數(shù)的交換位編碼方式。這兩種編碼方式均是在一組可行解基礎(chǔ)上進(jìn)行有限次位置交換從而生成新的加工序列，這保證了狀態(tài)的可行性和有效性，同時(shí)兩種編碼方式對(duì)解空間表征的完備性具有互補(bǔ)作用，詳細(xì)論述如下。

1) 基于移位解碼的編碼方式是以父代工件的加工工序作為參考模板，根據(jù)某一個(gè)二進(jìn)制串進(jìn)行移位解碼從而得到子代工件工序的編碼轉(zhuǎn)換方式[18]。定義二進(jìn)制串中數(shù)值0取當(dāng)前父代序列的第一位值，數(shù)值1取當(dāng)前父代序列的第二位值，以此策略，順次從父代個(gè)體中取出其值組成子代個(gè)體，隨后將取出的值從父代中刪除，方便選取下一位值，其具體說(shuō)明如圖1所示。運(yùn)用此方法對(duì)序列進(jìn)行重新排序，有助于增加序列的多樣性，并提高算法全局搜索的能力。

圖1 移位解碼

2) 為了使加工序列發(fā)生微小變化，引起序列更新，本文提出一種基于實(shí)數(shù)的交換位編碼方式。通過(guò)交換加工序列中任意兩位置的值，從而產(chǎn)生新的加工序列。每一個(gè)序列有兩個(gè)量子串控制其交換位，將量子串轉(zhuǎn)換為二進(jìn)制數(shù)，再換算成十進(jìn)制編碼，進(jìn)而將加工序列中對(duì)應(yīng)位置的值進(jìn)行交換。

對(duì)于有N個(gè)工件M個(gè)機(jī)器的JSP問(wèn)題，采用兩個(gè)最小能表示N×M對(duì)應(yīng)的二進(jìn)制位數(shù)個(gè)量子位，一個(gè)量子串對(duì)應(yīng)加工序列中的一個(gè)待交換位置。例如6個(gè)工件6臺(tái)機(jī)器需要6個(gè)量子位來(lái)描述其工作序列中的位置，量子串被表示為：

(8)

對(duì)上述兩個(gè)量子位串進(jìn)行觀測(cè)，如圖2所示，若得到二進(jìn)制串[0 0 1 0 0 0]、[0 1 0 0 1 1]，則換算成十進(jìn)制為[8]、[19]，將序列中對(duì)應(yīng)位置的值交換。這種編碼方式可以對(duì)加工序列進(jìn)行微調(diào)，通過(guò)加工序列局部變化引起其序列的更新。

圖2 交換位解碼

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

根據(jù)量子的疊加特性及變遷理論，應(yīng)用量子旋轉(zhuǎn)門變換更新產(chǎn)生新的編碼。量子旋轉(zhuǎn)門構(gòu)造如下:

(9)

(10)

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

(11)

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

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

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

(12)

2) 量子平移算子:

(13)

式中：β是正常數(shù)，稱為平移因子；Rt∈R是一個(gè)服從[0,1]均勻分布的隨機(jī)變量。

3) 量子伸縮算子:

θk+1=θk+γReθk

(14)

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

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

θk+1=θk+δRaθk

(15)

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

對(duì)以上四種算子計(jì)算出的旋轉(zhuǎn)角分別通過(guò)量子旋轉(zhuǎn)門更新量子位，通過(guò)量子坍縮操作對(duì)量子位進(jìn)行觀測(cè)，生成二進(jìn)制串通過(guò)相應(yīng)的編碼方式將其映射到解空間中，可有效增加解的多樣性并避免非法解的產(chǎn)生。

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

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

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

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

2.5 QSTA算法流程

量子狀態(tài)轉(zhuǎn)移算法是在原有狀態(tài)轉(zhuǎn)移算法(STA)的基礎(chǔ)上引入量子旋轉(zhuǎn)門操作以豐富工序的多樣性。通過(guò)狀態(tài)轉(zhuǎn)移算法的不同操作更新旋轉(zhuǎn)門所需的旋轉(zhuǎn)角，進(jìn)行量子旋轉(zhuǎn)門操作。對(duì)量子位串觀測(cè)引起坍縮，生成二進(jìn)制狀態(tài)，通過(guò)此狀態(tài)獲得不同的加工序列，計(jì)算加工工序的總完工時(shí)間，進(jìn)而選出最短完工時(shí)間對(duì)應(yīng)的加工序列作為當(dāng)前最優(yōu)工序。

QSTA流程如圖4所示。

圖4 量子狀態(tài)轉(zhuǎn)移算法流程

QSTA的優(yōu)化步驟如下：

Step2生成二進(jìn)制移位編碼。隨機(jī)生成移位編碼的旋轉(zhuǎn)角，通過(guò)量子旋轉(zhuǎn)門對(duì)移位編碼的量子位串執(zhí)行量子旋轉(zhuǎn)門操作，對(duì)此量子位串進(jìn)行觀測(cè)，獲得二進(jìn)制移位編碼，使用此編碼對(duì)全局最優(yōu)加工序列進(jìn)行重新排序，然后進(jìn)行適應(yīng)度計(jì)算，保存最優(yōu)適應(yīng)度結(jié)果。

Step3對(duì)非最優(yōu)解的容忍操作。對(duì)Step 2中所產(chǎn)生的加工序列根據(jù)容忍次數(shù)連續(xù)調(diào)整加工序列的不同位置，并對(duì)其進(jìn)行適應(yīng)度值計(jì)算，保存最優(yōu)適應(yīng)度結(jié)果。

Step4采用量子狀態(tài)轉(zhuǎn)移算子生成位置交換編碼。采用量子旋轉(zhuǎn)、量子伸縮、量子坐標(biāo)變換操作對(duì)旋轉(zhuǎn)角進(jìn)行更新，通過(guò)量子旋轉(zhuǎn)門對(duì)交換位編碼的量子位串執(zhí)行量子旋轉(zhuǎn)門操作，對(duì)此量子位串對(duì)進(jìn)行觀測(cè)，獲得二進(jìn)制編碼，將其轉(zhuǎn)換成十進(jìn)制交換位編碼，使用此編碼對(duì)全局最優(yōu)加工序列中的兩個(gè)位置進(jìn)行交換，然后進(jìn)行適應(yīng)度計(jì)算，保存最優(yōu)適應(yīng)度結(jié)果。

Step5根據(jù)容忍次數(shù)連續(xù)調(diào)整Step 4中所產(chǎn)生的加工序列的不同位置，并對(duì)其進(jìn)行適應(yīng)度值計(jì)算，保存最優(yōu)適應(yīng)度結(jié)果。

Step6判斷是否滿足終止條件，若滿足則結(jié)束搜索，否則返回Step 2。

3 實(shí) 驗(yàn)

本實(shí)驗(yàn)選用MATLAB R2015b編程語(yǔ)言實(shí)現(xiàn)，運(yùn)行環(huán)境為:處理器1.60 GHz，處理器速度1 800 MHz，物理環(huán)境3 993 MB，Windows 10操作系統(tǒng)。為驗(yàn)證本文算法解決作業(yè)車間調(diào)度問(wèn)題的高效性，采用QSTA方法對(duì)作業(yè)車間調(diào)度標(biāo)準(zhǔn)測(cè)試問(wèn)題庫(kù)中的12個(gè)測(cè)試問(wèn)題進(jìn)行求解并與其他算法相比較。上述12種算例分別為文獻(xiàn)[19]提出的實(shí)例FT06、FT10、FT20和Lawrence等[20]提出的實(shí)例LA01、LA06、LA11、LA16、LA21、LA26、LA31、LA36、LA40。

3.1 STA、PSO和GA的仿真對(duì)比

狀態(tài)轉(zhuǎn)移算法的參數(shù)選擇：搜索規(guī)模SE=100，旋轉(zhuǎn)因子的最大值αmax=1，最小值為αmin=1e-4，旋轉(zhuǎn)因子α=1，平移因子β=1，伸縮因子γ=1，坐標(biāo)系數(shù)δ=1，迭代次數(shù)M=500。為了更準(zhǔn)確地與PSO和GA就JSP問(wèn)題進(jìn)行比較，將各個(gè)參數(shù)設(shè)置與STA保持一致，即種群規(guī)模NIND=100，最大迭代次數(shù)M=500。各個(gè)算法單獨(dú)運(yùn)行20次，所得到的結(jié)果如表1所示。

表1 三種算法(STA、GA、PSO)的比較

續(xù)表1

可以看出，在搜索規(guī)模、迭代次數(shù)和獨(dú)立運(yùn)行次數(shù)皆相同的情況下，STA、PSO和GA在FT06、LA01、LA06、LA11等問(wèn)題中均能收斂到當(dāng)前已知最優(yōu)解。在尋最優(yōu)解個(gè)數(shù)上STA算法要優(yōu)于PSO和GA。在計(jì)算大規(guī)模問(wèn)題算例時(shí)GA要優(yōu)于STA，從最優(yōu)解、平均值方面可以得出，STA優(yōu)于PSO，但部分劣于GA。

仿真結(jié)果表明，STA雖能有效解決JSP，但對(duì)比PSO及GA來(lái)說(shuō)并無(wú)明顯優(yōu)越性，因此還需對(duì)基本STA做進(jìn)一步的改進(jìn)，本文采用QSTA繼續(xù)對(duì)以上算例進(jìn)行求解。QSTA求解的部分甘特圖如圖5所示。

(a) FT06甘特圖(makespan=55/min)

(b) FT10甘特圖(makespan=960/min)

(c) LA01甘特圖(makespan=666/min)

(d) LA16甘特圖(makespan=945/min)圖5 部分調(diào)度問(wèn)題甘特圖

3.2 QSTA與STA的對(duì)比

利用量子狀態(tài)轉(zhuǎn)移算法繼續(xù)對(duì)上述問(wèn)題進(jìn)行求解，將算法的搜索規(guī)模設(shè)置為SE=100，最大迭代次數(shù)M=500，獨(dú)立運(yùn)行20次，量子旋轉(zhuǎn)角設(shè)置為rand×2×π。運(yùn)算結(jié)果如表2所示，尋優(yōu)成功率的計(jì)算方法為：最優(yōu)解個(gè)數(shù)/獨(dú)立運(yùn)行總次數(shù)。

通過(guò)QSTA與STA算法就求解作業(yè)車間調(diào)度問(wèn)題的比較結(jié)果可知，量子狀態(tài)轉(zhuǎn)移優(yōu)化算法在算法的尋優(yōu)成功率方面有很大的提升，在LA06、LA11問(wèn)題上的尋優(yōu)成功率的值均在100%,且在LA31中QSTA可以搜索到已知最優(yōu)解。結(jié)合圖6所示的尋優(yōu)曲線對(duì)比可知，采用QSTA可有效解決JSP問(wèn)題，QSTA搜索得到的最優(yōu)解及平均值皆明顯優(yōu)于STA，且收斂速度及收斂精度也明顯優(yōu)于STA、PSO和GA。綜上所述，QSTA可有效求解JSP問(wèn)題，與STA相比其收斂精度更高、收斂速度更快。因此，改進(jìn)后的量子狀態(tài)轉(zhuǎn)移算法可有效避免算法陷入早熟，增強(qiáng)算法的求解精度并提高算法的收斂速度。

表2 QSTA與STA算法的比較

(a) FT06收斂曲線

(b) FT10收斂曲線

(c) LA16收斂曲線

(d) LA31收斂曲線圖6 部分測(cè)試問(wèn)題尋優(yōu)曲線對(duì)比

4 結(jié) 語(yǔ)

本文針對(duì)傳統(tǒng)群智能算法求解JSP時(shí)存在的算法易早熟、后期收斂速度慢和全局搜索能力差的問(wèn)題，提出了量子狀態(tài)轉(zhuǎn)移算法來(lái)求解JSP問(wèn)題。首先，驗(yàn)證了STA在解決JSP時(shí)具有可行性，并發(fā)現(xiàn)了STA在解決JSP時(shí)存在缺陷；為提升STA搜索可行解的多樣性及收斂精度，采用移位解碼和交換位編碼兩種編碼方式，結(jié)合量子計(jì)算的優(yōu)點(diǎn)提出QSTA；在此基礎(chǔ)上又提出一種容忍非最優(yōu)解機(jī)制，對(duì)其進(jìn)行仿真實(shí)驗(yàn)。通過(guò)對(duì)比發(fā)現(xiàn)，QSTA在解決JSP時(shí)可有效彌補(bǔ)傳統(tǒng)算法的不足，具有迭代次數(shù)少、收斂速度快、全局搜索能力強(qiáng)等優(yōu)點(diǎn)。