基于改進量子進化算法的作業(yè)車間調(diào)度研究

張建明

（浙江理工大學(xué)理學(xué)院，310018杭州）

基于改進量子進化算法的作業(yè)車間調(diào)度研究

張建明

（浙江理工大學(xué)理學(xué)院，310018杭州）

針對作業(yè)車間調(diào)度問題，以最大完工時間最小化為優(yōu)化目標，提出了跳躍基因量子進化算法（JGQEA）。該算法在量子進化算法的基礎(chǔ)上引入跳躍基因算子，同時采用動態(tài)調(diào)整量子旋轉(zhuǎn)角策略以提高算法的搜索能力。通過仿真實驗驗證了算法的有效性，結(jié)果表明JGQEA優(yōu)于QEA等幾種進化算法。

作業(yè)車間調(diào)度；轉(zhuǎn)換機制；量子進化；旋轉(zhuǎn)角；跳躍算子

0 引 言

量子算法是以量子力學(xué)原理為基礎(chǔ)，它最本質(zhì)的特點是利用量子態(tài)的相干性和疊加性，以及量子比特之間的糾纏性，與經(jīng)典算法最本質(zhì)的區(qū)別在于量子并行性。因此，量子計算比經(jīng)典計算在速度上會有指數(shù)級的提高。但基于量子力學(xué)原理的量子計算機還處于研制的初級階段，因此，將量子計算與傳統(tǒng)智能計算相結(jié)合的量子智能計算就運用而生。

1996年Narayanan和Moore提出了量子遺傳算法（quantum genetic algorithm，QGA），并應(yīng)用于解決TSP問題［1］，開創(chuàng)了量子智能計算研究的新方向。2000年，由Han等［2］將量子位和量子門的概念引入進化算法，并用組合優(yōu)化問題驗證了算法的有效性。2002年，Han等［3］在量子遺傳算法的基礎(chǔ)上，引入種群遷移機制，提出了量子衍生遺傳算法（quantum inspired genetic algorithm，QIGA）。目前對QGA的改進方式主要包括算法結(jié)構(gòu)、進化方式以及編碼方法等，比如中國科技大學(xué)楊俊安等［4］提出了一種多宇宙并行量子遺傳算法，屬于算法結(jié)構(gòu)的改進；西南交通大學(xué)的張葛祥等［5］提出的采用量子比特相位比較法更新量子門和自適應(yīng)調(diào)整搜索網(wǎng)格策略，與西南交通大學(xué)的陳輝等［6］提出的混沌更新旋轉(zhuǎn)門轉(zhuǎn)角的量子遺傳算法，都屬于進化策略方面的改進；在編碼方法上的改進有：清華大學(xué)王凌等［7］給出的基于二進制編碼的混合量子遺傳算法和基于實數(shù)編碼的混合量子遺傳算法，李士勇等［8-9］在求解連續(xù)優(yōu)化問題時提出的基于實數(shù)編碼和目標函數(shù)梯度信息的雙鏈量子遺傳算法，以及基于量子位Bloch球面的量子進化算法［10］等。最近，在利用QGA對生產(chǎn)調(diào)度問題的研究中，Gu等［11-12］引入了量子交叉、變異等操作，獲得了不錯的優(yōu)化效果。以上各種量子智能算法都是傳統(tǒng)智能算法與量子算法相結(jié)合的產(chǎn)物。而跳躍基因算子在遺傳算法中的成功實踐，使我們有理由相信，提供了基因在種群內(nèi)的水平傳遞的跳躍基因，有可能在量子算法中有利于種群多樣性的保持，從而提高算法的優(yōu)化性能。因此，本文針對作業(yè)車間調(diào)度問題，以最大完工時間最小為優(yōu)化目標，在量子遺傳算法中引入跳躍基因算子，提出跳躍基因量子遺傳算法，以提高算法的優(yōu)化性能。

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

Job-shop調(diào)度問題包括典型Job-shop調(diào)度和帶并行機的Job-shop調(diào)度。Job-shop調(diào)度問題是先進制造與自動化及其他調(diào)度技術(shù)相關(guān)研究領(lǐng)域中的經(jīng)典熱點問題。

生產(chǎn)系統(tǒng)有n個工件需要在m臺機器上加工，調(diào)度的任務(wù)是把工序分配給機器上某個時間段，調(diào)度的目標就是確定每個機器上工件的加工順序和每個工件的開始加工時間，使得完成所有工件所需的時間Makespan最?。庸ぶ芷诨蚱渌笜诉_到最優(yōu)）。典型Job-shop調(diào)度問題的數(shù)學(xué)模型描述為［13］：

滿足約束條件：

其中Ω是一足夠大的正數(shù)，cik與tik分別表示第i個工件在第k臺機器上的加工時間；aijk與xijk為：

2 基于作業(yè)車間調(diào)度問題的量子進化算法

本節(jié)在量子遺傳算法的基礎(chǔ)上，引入跳躍基因算子，以提高優(yōu)良個體性能在種群進化過程中的有效傳遞；在量子個體更新的過程中，引進新的量子角的選擇模式，以保持種群在進化過程中的多樣性，防止早熟收斂。

2.1 編碼機制

在量子進化算法中，一個量子比特位可以表示為

其中α，β為復(fù)數(shù)，且滿足歸一化條件｜α｜2+｜β｜2=1。一個具有l(wèi)位的量子個體就表示為：

2.2 解碼機制

對于車間調(diào)度問題，我們的目的是在滿足工藝約束等條件下，合理安排各個工件在每臺機器上的加工次序，使得最大完工時間等性能指標達到最優(yōu)。而量子個體是通過概率幅對解的一種線性疊加態(tài)，因此，要通過解碼機制，把線性疊加態(tài)的解解碼為十進制的解。筆者在文獻［10］中解碼方法的基礎(chǔ)上，提出以下解碼方案。

第四步，將D（t）中的數(shù)按從小到大排序，最小的m個數(shù)表示第一個工件，接下來的m個數(shù)表示第二個工件，依次類推。在此過程中保持每個數(shù)在D（t）中的相對位置不變。因此，可以得到n個工件序號每個都重復(fù)m次的一個排列S（t）。S（t）中的第k次出現(xiàn)的數(shù)i將表示第i個工件的第k道工序。如果在D（t）中出現(xiàn)相等的數(shù)字，則位置序號較小的數(shù)代表工序號較小的工件。

解碼流程圖如圖1所示。

圖1 編碼及解碼過程

以3個工件2臺機器的3×2JSSP調(diào)度問題為例：則Q（t）為12位量子比特位的染色體，對Q（t）進行觀測，若得到的12位二進制串X（t）=｛0，1，1，1，0，1，0，1，0，0，1，1｝，則D（t）=（1，2，1，1，0，2），因此，位置1與位置5表示工件1；位置3與位置4表示工件2；位置2與位置6表示工件3。因此，S（t）=（1，3，2，2，1，3），則位置1中的1表示第一個工件的第一道工序，位置5中的1表示第一個工件的第二道工序；位置3中的2表示第二個工件的第一道工序，依次類推。所以，任何一個量子個體都可以解碼為一個可行調(diào)度，該方法的優(yōu)點是解碼方法簡單，同時不會產(chǎn)生非法解。

2.3 量子旋轉(zhuǎn)角

在QEA中，利用量子門進行量子個體的更新，而量子旋轉(zhuǎn)門是被廣泛采用的更新手段。在此過程中，量子旋轉(zhuǎn)角的選擇將起到至關(guān)重要的作用。對于旋轉(zhuǎn)角，不僅要確定旋轉(zhuǎn)角的大小還要確定旋轉(zhuǎn)角的方向。旋轉(zhuǎn)角θ和旋轉(zhuǎn)方向可以通過表1得到，其中ri為當(dāng)前量子個體第i個量子比特位所觀測到的二進制編碼（0或1）；bi為當(dāng)前最優(yōu)個體的第i位量子比特位所觀測到的二進制編碼；Δθi為旋轉(zhuǎn)角的大小，控制算法收斂的速度；s（αi，βi）為旋轉(zhuǎn)角的方向，保證算法的收斂；f（x）為適應(yīng)度函數(shù)。比如，當(dāng)ri=0，bi=1，f（r）＞f（b）時，為使當(dāng)前解收斂到一個具有更高適應(yīng)度的量子個體，應(yīng)增大當(dāng)前解取得0概率，即要使得｜αi｜2變大，此時，如果（αi，βi）在第一、三象限，θ應(yīng)順時針方向旋轉(zhuǎn)；如果（αi，βi）在第二、四象限，θ應(yīng)逆時針方向旋轉(zhuǎn)，以增大｜αi｜2的值。因此，旋轉(zhuǎn)角大小的選擇對算法的收斂性能具有巨大的影響。在大部分量子進化算法或混合量子進化算法中，量子旋轉(zhuǎn)角的大小總是通過查表給出，量子旋轉(zhuǎn)角的大小往往是固定的。大小的選擇通常也是根據(jù)具體問題由經(jīng)驗給出，與目標函數(shù)的本身沒有太大的關(guān)系。盡管量子進化算法中個體的表示方式?jīng)Q定了量子種群比經(jīng)典的進化算具有更強的多樣性，但量子個體進化過程中αi逐漸向0或1收斂而使種群失去多樣性。為了保持種群的多樣性，使得進化更具有目的性，本文采用動態(tài)調(diào)整旋轉(zhuǎn)角策略。在進化初期由于為了使每個解都有被搜索到的可能，旋轉(zhuǎn)角θ應(yīng)小一些，以提高種群的探索能力；在進化中期種群會逐漸失去多樣性，因此應(yīng)增大旋轉(zhuǎn)角θ；在進化后期為了提高種群的開發(fā)能力，增加種群的局部搜索能力，應(yīng)再次減小旋轉(zhuǎn)角θ。因此，筆者采用第一代到（T為最大進化代數(shù)）代內(nèi)旋轉(zhuǎn)角線性增加；在代之后旋轉(zhuǎn)角線性減少。即：

表1 量子旋轉(zhuǎn)角

2.4 跳躍基因算子

目前，跳躍基因算子主要有兩種形式：剪切粘貼置換與復(fù)制粘貼置換［14］。這兩種置換又分為在同一染色體內(nèi)的置換與染色體之間的置換。同一染色體內(nèi)的剪切粘貼置換就是在染色體內(nèi)隨機產(chǎn)生一個剪切點和隨機長度的跳躍基因，再隨機產(chǎn)生一個新的粘貼點，將跳躍基因粘貼到新的粘貼點上，如圖2（a）。染色體間的剪切粘貼置換是在兩個不同的染色體上都隨機產(chǎn)生一個剪切點和隨機長度的跳躍基因，同時在每個染色體上隨機產(chǎn)生一個新的粘貼點，然后將兩個跳躍基因片段交叉粘貼到新的粘貼點處。染色體內(nèi)的復(fù)制粘貼置換就是在染色體內(nèi)隨機產(chǎn)生一個復(fù)制點和隨機長度的跳躍基因，再隨機產(chǎn)生一個新的粘貼點，將跳躍基因復(fù)制到新的粘貼點上，如圖2（b）。在染色體間的復(fù)制粘貼置換是在兩個不同的染色體上都隨機產(chǎn)生一個復(fù)制點和隨機長度的跳躍基因，同時在每個染色體上隨機產(chǎn)生一個新的粘貼點，然后將兩個跳躍基因片段交叉復(fù)制到新的粘貼點處。本文采用在同一染色體內(nèi)的剪切粘貼置換，并把這種引入跳躍基因算子的量子遺傳算法稱為跳躍基因量子進化算法（jumping genes quantum evolutionary algorithm，JGQEA）。

圖2 同一染色體內(nèi)的置換

針對JSSP的JGEQA偽代碼為：

3 仿真結(jié)果與分析

為了驗證JGQEA對JSSP的有效性，選取Muth與Thompson提出的經(jīng)典的基準問題mt06、mt10及mt20［15-16］和由Applegate與Cook提出的經(jīng)典的基準問題la01、la02、la03、la04、la05、la06、la21、la24、la33、la36及l(fā)a38，與MA、GA、SGA、PSO及 QEA的優(yōu)化效果進行比較。表2中JGQEA的測試參數(shù)為：種群規(guī)模為300，跳躍概率為0.1，最大代數(shù)為300。利用Matlab編程，測試環(huán)境為：Intel（R）Core 2 Duo 2.93GHz CPU，2G內(nèi)存。表中OPT表示最優(yōu)解，MA表示基因算法（memetic algorithm）［17］，GA表示遺傳算法（genetic algorithm）［18］，SGA表示Nakan與Yamada提出的遺傳算法［19］，PSO表示離子群算法（particle swarm optimization）［20-21］，QEA表示普通量子進化算法。從表2可知，盡管JGQEA不是所有問題中都得到最優(yōu)解，但所得到的最優(yōu)解好于GA、SGA、PSO、QEA等方法獲得的最優(yōu)解，在mt10、mt20、La38中所獲的最優(yōu)解較MA算法獲得的最優(yōu)解差。由此可以說明，JGQEA有較好的優(yōu)化性能。在QEA與JGQEA的比較中可以發(fā)現(xiàn)，引入跳躍基因算子的JGQEA的優(yōu)化性能比QEA都有所提高，這進一步說明跳躍基因算子可以改善算法的優(yōu)化性能。為了比較不同的跳躍概率對算法收斂速度的影響，筆者以La06為例，選擇不同的跳躍概論來比較它們的收斂速度，如圖3所示。

表2 最優(yōu)結(jié)果比較

圖3 不同跳躍概率下收斂速度比較（La06）

圖4 對La06不同算法的比較

圖3中，我們?nèi)=0.03，C=0.01；種群規(guī)模為300，最大代數(shù)100，運行次數(shù)為10次；跳躍概率分別取0、0.05、0.1、0.15；豎軸表示運行10次完工時間的平均值，橫軸表示運行代數(shù)。從圖中可以看出，當(dāng)選擇一個恰當(dāng)?shù)奶S概率時，算法的收斂速度會得到有效的改善，特別是在跳躍概率分別取0.05、0.1、0.15時，其收斂速度都優(yōu)于跳躍概率為零的情況。在圖4中，以La06為模擬對象，將JGQGA與POS、QGA、GA的優(yōu)化性能做了比較，結(jié)果顯示JGQGA比這幾種算法在優(yōu)化質(zhì)量上都有所提高。其中JGQGA中相關(guān)參數(shù)為：種群規(guī)模300，最大代數(shù)150，A=0.03，C=0.01，跳躍概率為0.1。

4 結(jié) 論

本文提出了JGQEA用于解決JSSP問題。在JGQEA中采用動態(tài)調(diào)整量子旋轉(zhuǎn)角的策略，同時引入跳躍基因，以改善量子種群的多樣性，提高JGQEA的優(yōu)化性能。對多個JSSP的基準問題以最大完工時間為優(yōu)化目標進行優(yōu)化調(diào)度，JGQEA所獲地的最優(yōu)值優(yōu)于GA、SGA、PSO及QEA所獲得的最優(yōu)值，但是不及 MA所獲得的最優(yōu)值。這一方面說明，JGQEA具有良好的優(yōu)化性能，另一方面也說明JGQEA的優(yōu)化性能還有進一步改進和提高的要求。在優(yōu)化目標方面，本文僅對最大完工時間作為優(yōu)化目標對JGQEA的優(yōu)化性能進行檢驗。實際的調(diào)度目標往往包括利潤最大、庫存最小、提前拖期懲罰最小等等的多目標調(diào)度，因此，如何將JGQEA用于JSSP的多目標調(diào)度具有非常重要的研究價值，這也是我們以后要重點研究的內(nèi)容。

［1］Narayanan A，Moore M.Quantum inspired genetic algorithm［C］//IEEE International Conference on Evolutionary Computation.Iscataway，1996：61-66.

［2］Han K H，Kim J H.Genetic quantum algorithm and its application to combinatorial optimiza-tion problem［C］// IEEE International Conference on Evolutionary Computation.Lajolla，2000：1354-1360.

［3］Han K H，Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial timization［J］.IEEE Transactions on Evolutionary Computation，2002，6（6）：580-593.

［4］楊俊安，莊鎮(zhèn)泉，史 亮.多宇宙并行量子遺傳算法［J］.電子學(xué)報，2004，32（6）：923-928.

［5］Zhang G，Gu Y，Hu L，et al.A novel quantum genetic algorithm and its application to digital filter design［J］.Intelligent Transportation Systems，2003，2：1600-1605.

［6］Chen H，Zhang J H，Zhang C.Chaos updating rotated gates quantum-inspired genetic algorithm proceedings of the international conference on communications［J］. Cuircuits and Systems，2004，2：1108-1112.

［7］Wang L，Tang F，Wu H.Hybrid genetic algorithm based on quantum computing for numerical optimization and parameter estimation［J］.Appl Math Comput，2005，171：1141-1156.

［8］Li P，Li S.Quantum-inspired evolutionary algorithm for continuous spaces optimization［J］.Chinese Journal of Electronics，2008，17（1）：80-84.

［9］李士勇，李盼池.基于實數(shù)編碼和目標函數(shù)梯度的量子遺傳算法［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2006，38（8）：1216-1218，1223.

［10］Li P，Li S.Quantum-inspired evolutionary algorithm for continuous spaces optimization based on Bloch coordinates of qubits［J］.Neurocomputing，2008，72：581-591.

［11］Gu J，Gu X，Gu M.A novel parallel quantum genetic algorithm for stochastic job shop scheduling［J］.J Math Anal Appl，2009，355（1）：63-81.

［12］Gu J，Gu M，Cao C，et al.A novel competitive co-evolutionary quantum genetic algorithm for stochastic jobshop scheduling problem［J］.Comput Oper Res，2010，37（5）：927-937.

［13］張建明.基于改進量子進化算法的生產(chǎn)調(diào)度問題研究［D］.上海：華東理工大學(xué)，2013.

［14］Ripon K S N，Sam K，Man K F.A real coding jumping gene genetic algorithm（RJGGA）for multi-objective optimization［J］.Inf Sci，2007，177（2）：632-654.

［15］Muth J F，Thompson G L.Industrial Scheduling［M］. EngleWood Cliffs：Prentice-Hall，1963.

［16］Ripon K S N，Chi H T，Sam K.Multi-objective evolutionary job-shop scheduling using jumping genes genetic algorithm［C］//2006 International Joint Conference on Neural Networks.Vancouver，2006：3100-3107.

［17］Gao L，Zhang G，Zhang L，et al.An efficient memetic algorithm for solving the job shop scheduling problem［J］.Comput Indust Engin，2011，60：699-705.

［18］Ombuki B M，Ventresca M.Local search genetic algorithms for job shop scheduling problem［J］.Applied Intelligence，2004，21：99-109.

［19］Nakano R，Yamada T.Conventional genetic algorithm for job-shop problems［C］//Proceedings of the 4th International Conference on Genetic Algorithms（ICGA'91）.San Diego，1991：474-479.

［20］Kennedy J，Eberhart R C.Particle swarm optimization［C］//IEEE International Conference on Neural Networks，Perth，1995：1942-1948.

［21］Tasgetiren M F，Sevkli M，Liang Y C.A particle swarm optimization and differential evolution algorithms for job shop scheduling problem［J］.Inter J Oper Res，2006，3（2）：120-135.

A Novel Quantum Evolutionary Algorithm for Job-shop Scheduling

ZHANG Jian-ming
（School of Sciences，Zhejiang Sci-Tech University，Hangzhou 310018，China）

For job-shop scheduling，this paper proposes jumping gene quantum evolutionary algorithm（JGQEA）with the optimization objective of minimizing the makespan.This algorithm introduces jumping gene operator based on quantum evolutionary algorithm，and applies dynamic adjusting quantum rotation angle strategy to improve search capability of the algorithm.The effectiveness of the algorithm is verified by simulation experiment，and results show that JGQEA is superior to QEA and several other evolutionary algorithm.

job-shop scheduling；converting mechanism；quantum evolution；rotation angle；jumping operator

TP18

A

（責(zé)任編輯：康 鋒）

1673-3851（2014）03-0310-06

2013-12-30

國家自然科學(xué)基金（10871181）

張建明（1972-），男，陜西延川人，博士、副教授，主要從事微分方程分支問題及智能計算方面的研究。