基于改進量子進化算法的作業車間調度研究

張建明

（浙江理工大學理學院，310018杭州）

基于改進量子進化算法的作業車間調度研究

張建明

（浙江理工大學理學院，310018杭州）

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

作業車間調度；轉換機制；量子進化；旋轉角；跳躍算子

0 引 言

量子算法是以量子力學原理為基礎，它最本質的特點是利用量子態的相干性和疊加性，以及量子比特之間的糾纏性，與經典算法最本質的區別在于量子并行性。因此，量子計算比經典計算在速度上會有指數級的提高。但基于量子力學原理的量子計算機還處于研制的初級階段，因此，將量子計算與傳統智能計算相結合的量子智能計算就運用而生。

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

1 作業車間調度問題的描述及數學模型

Job-shop調度問題包括典型Job-shop調度和帶并行機的Job-shop調度。Job-shop調度問題是先進制造與自動化及其他調度技術相關研究領域中的經典熱點問題。

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

滿足約束條件：

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

2 基于作業車間調度問題的量子進化算法

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

2.1 編碼機制

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

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

2.2 解碼機制

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

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

解碼流程圖如圖1所示。

圖1 編碼及解碼過程

以3個工件2臺機器的3×2JSSP調度問題為例：則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表示第二個工件的第一道工序，依次類推。所以，任何一個量子個體都可以解碼為一個可行調度，該方法的優點是解碼方法簡單，同時不會產生非法解。

2.3 量子旋轉角

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

表1 量子旋轉角

2.4 跳躍基因算子

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

圖2 同一染色體內的置換

針對JSSP的JGEQA偽代碼為：

3 仿真結果與分析

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

表2 最優結果比較

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

圖4 對La06不同算法的比較

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

4 結 論

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

［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］楊俊安，莊鎮泉，史 亮.多宇宙并行量子遺傳算法［J］.電子學報，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］李士勇，李盼池.基于實數編碼和目標函數梯度的量子遺傳算法［J］.哈爾濱工業大學學報，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］張建明.基于改進量子進化算法的生產調度問題研究［D］.上海：華東理工大學，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

（責任編輯：康 鋒）

1673-3851（2014）03-0310-06

2013-12-30

國家自然科學基金（10871181）

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