肖蕾蕾，史二娜

(西安科技商貿(mào)職業(yè)學(xué)院，陜西 西安 210096)

0 引言

為了提高PSO算法中粒子的隨機(jī)性和PSO算法的全局搜索性能，sun 于2004 年提出了量子粒子群優(yōu)化算法(Quantum－ behaved Particle Swarm Optimization，QPSO)［1，2］，以DELTA 勢(shì)阱為基礎(chǔ)，從量子力學(xué)的角度出發(fā)，賦予粒子量子行為，使其在量子空間中搜索。在量子空間中，由于量子狀態(tài)的疊加、相干和糾纏特性，粒子可能出現(xiàn)在搜索空間的任何位置。而在PSO算法中，絕大多數(shù)粒子的搜索空間被限制在搜索空間的某個(gè)范圍內(nèi)，可能存在搜索“禁”區(qū)［1］，因而QPSO算法的全局搜索性能遠(yuǎn)遠(yuǎn)優(yōu)于PSO算法，并且QPSO的全局收斂性已經(jīng)得到了證明［3］。

1 量子粒子群算法

1.1 量子粒子群優(yōu)化算法數(shù)學(xué)描述

QPSO算法通過波函數(shù)ψ(x，t)來描述粒子的狀態(tài)，并通過求解薛定愕方程得到粒子在空間某一點(diǎn)出現(xiàn)的概率密度函數(shù)，再通過Monte Carlo 隨機(jī)模擬得到粒子的位置方程為:

式中:N—種群中粒子數(shù)目;D—粒子的維數(shù);u和φ—在［0，1］區(qū)間上均勻分布的隨機(jī)數(shù);Pid(t)—局部吸引點(diǎn);Cd(t)—種群中所有粒子的平均最好位置點(diǎn)。和標(biāo)準(zhǔn)PSO算法一樣，Pi和Pg為粒子i所經(jīng)歷的最好位置和種群中所有粒子所經(jīng)歷的最好位置;α(t)為收縮擴(kuò)張系數(shù)，是QPSO算法的唯一的控制參數(shù)。

1.2 基于量子粒子群算法的粒子編碼方式

編碼問題是設(shè)計(jì)算法的首要的關(guān)鍵問題。粒子編碼方式仍采用基于工序的編碼方法，對(duì)于n個(gè)工件m 臺(tái)機(jī)床的Job－shop 調(diào)度問題，分別用自然數(shù)1，2，…，n 表示每個(gè)不同的工件，由于每個(gè)工件有m 道工序，這樣就總共有n×m 道工序。采用基于工序的表達(dá)方法進(jìn)行編碼［4］，即用一個(gè)長(zhǎng)度為n×m的粒子代表一種排序方案，粒子中的每一個(gè)元素對(duì)應(yīng)的是工件標(biāo)號(hào)，然后根據(jù)工件標(biāo)號(hào)在序列中出現(xiàn)的順序確定該工件的工序。

1.3 基于量子粒子群算法目標(biāo)函數(shù)及適應(yīng)值的計(jì)算

結(jié)合各工件的工藝約束和各工序完成時(shí)間約束，仍將各個(gè)粒子的最大完成時(shí)間作為適應(yīng)度值，最大完成時(shí)間的具體計(jì)算過程如下［4，5］:

(1)將所有工件所對(duì)應(yīng)的第一道工序的開始加工時(shí)間初始化為零。

(2)為每臺(tái)機(jī)器設(shè)定一個(gè)加工鏈表，用于表示該機(jī)器上加工的工件及順序。

(3)執(zhí)行調(diào)度方案中的第一個(gè)加工操作，將該操作加入到所對(duì)應(yīng)的加工機(jī)器的加工鏈表中，記錄該工件第一道工序的開始加工時(shí)間和加工結(jié)束時(shí)間，并將該工件下一道工序的理論開始加工時(shí)間設(shè)置為該工件第一道工序的加工結(jié)束時(shí)間。

(4)順序執(zhí)行調(diào)度方案中的其他加工操作，將這些加工操作依次加入到該操作所對(duì)應(yīng)的加工機(jī)器的加工鏈表中。

(5)執(zhí)行完畢調(diào)度方案中的所有加工操作后，比較所有工件最后一道工序的加工結(jié)束時(shí)間，取最大值，即為當(dāng)前調(diào)度方案的最大完工時(shí)間。記錄所有機(jī)器的加工鏈表，即為當(dāng)前調(diào)度方案的實(shí)際調(diào)度結(jié)果。

1.4 量子粒子群算法參數(shù)的選擇

在QPSO算法中，除了群體大小、問題維數(shù)與迭代次數(shù)外的唯一控制參數(shù)為式(3－5)中的壓縮－擴(kuò)張因子α，它在算法中起到的作用是能夠調(diào)節(jié)算法的收斂過程。盡管算法只有一個(gè)控制參數(shù)，但是尚未對(duì)其進(jìn)行過系統(tǒng)的研究。在文獻(xiàn)［8］中，通過仿真結(jié)果得知QPSO算法的壓縮－擴(kuò)張因子必須滿足α ＜1.781 才能保證粒子的收斂，否則算法將肯定不能保證收斂。在這樣的前提條件下，如何選擇α的取值及取值方式已成為一個(gè)重要的研究課題。文獻(xiàn)［3］提出了α的三種控制策略:固定取值策略，線性減小取值策略及非線性減小取值策略。結(jié)合標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真結(jié)果得出:固定取值策略的魯棒性較差;采用控制參數(shù)線性減小的取值方式并且線性減小的取值范圍在［0.8，0.6］和［1.0，0.5］時(shí)能夠?qū)^大多數(shù)的函數(shù)取得較好的優(yōu)化結(jié)果;而非線性減小的取值策略也能夠取得一些較好的結(jié)果。

本文采用α 線性減小的取值方式，計(jì)算公式如下:

式中，α1＜α0，α0和α1分別是控制參數(shù)α的初始值和終止值。

1.5 量子粒子群算法位置的初始化

對(duì)于粒子的初始位置，本文將xid任意隨機(jī)數(shù)，即:

式中rand()是隨機(jī)產(chǎn)生的任意實(shí)數(shù)。

1.6 量子粒子群算法位置的更新

對(duì)于n個(gè)工件m 臺(tái)機(jī)床的Job－shop 調(diào)度問題，位置矢量應(yīng)該是一個(gè)n×m 維實(shí)向量，分別根據(jù)式(1)、(2)和式(3)進(jìn)行平均最好位置點(diǎn)Cd(t)、局部吸引點(diǎn)pid(t)和位置矢量的更新。在位置迭代過程中，‘±’是由(0，1)之間產(chǎn)生的隨機(jī)數(shù)決定的，當(dāng)產(chǎn)生的隨機(jī)數(shù)大于0.5 時(shí)取‘－’，其余取‘+’，并且表示粒子的二維向量的第一維向量保持不變，待粒子位置更新之后對(duì)粒子位置矢量進(jìn)行從小到大的排序，進(jìn)而生成待加工的工序序列，然后解碼生成調(diào)度方案。

1.7 量子粒子群算法流程

Step1:初始化α0、α1、tmax，并且設(shè)當(dāng)前進(jìn)化代數(shù)t=0。

Step2:設(shè)定種群數(shù)N，隨機(jī)初始化各粒子的位置矢量。

Step3:將各粒子位置矢量映射為工序序列，計(jì)算各個(gè)調(diào)度方案的最大完成時(shí)間，從而對(duì)各個(gè)調(diào)度方案的性能指標(biāo)進(jìn)行評(píng)價(jià)。

Step5:根據(jù)式(1)計(jì)算粒子的平均最優(yōu)位置C(t)。

Step6:判斷t是否等于tmax，如果t=tmax，則輸出Pg(t)，并由Pg(t)得到最優(yōu)調(diào)度方案;否則，執(zhí)行Step6。

Step7:對(duì)種群中所有粒子進(jìn)行如下操作［6，7］:

①按式(4)更新壓縮－擴(kuò)張因子α(t)，按式(2)更新粒子局部吸引點(diǎn)位置Pi(t)，然后按式(3)更新粒子位置Xi(t)，并將粒子位置矢量映射為新的工序序列。

②計(jì)算粒子的最大完成時(shí)間。

③若粒子的最大完成時(shí)間小于Pi(t)對(duì)應(yīng)的最大完成時(shí)間，則Pi(t)=Xi(t);若粒子的最大完成時(shí)間小于Pg(t)對(duì)應(yīng)的最大完成時(shí)間，Pg(t)=Xi(t)。

Step8:令t=t+1，轉(zhuǎn)Step6。

2 典型算例仿真結(jié)果

2.1 FT06 問題的尋優(yōu)結(jié)果

FT06(6×6)標(biāo)準(zhǔn)測(cè)試問題每個(gè)工件的加工路線與每道工序?qū)?yīng)的加工時(shí)間見表1。

表1 FT06(6×6)問題工件工序與工時(shí)

FT06算例的第一行數(shù)據(jù)表示工件1 先在機(jī)器3 上加工1s，然后在機(jī)器l 上加工3s，然后在機(jī)器2 上加工6s，依次類推，最后在機(jī)器5 上加工6s。

2.2 FT06 問題的仿真結(jié)果

取種群數(shù)目N=20，最大迭代次數(shù)tmax=100，分別采用PSO算法和QPSO算法連續(xù)運(yùn)行20 次所得到的結(jié)果如表2所示。

表2 基于PSO和QPSO算法的FT06 問題仿真結(jié)果

從表2 可以看出，采用PSO和QPSO算法找到的最優(yōu)調(diào)度的最大完工時(shí)間為55s。而FT06Job－shop 調(diào)度問題在參考文獻(xiàn)［4］中用基于位置矢量更新的粒子群算法調(diào)度后，最大完工時(shí)間為55s ，用基于遺傳算法的粒子群算法調(diào)度后，最大完工時(shí)間也為55s，說明PSO和QPSO算法在求解FT06Job－shop 調(diào)度問題上取得了較好的效果。

考慮到優(yōu)化算法的收斂效果也是評(píng)價(jià)該算法優(yōu)化性能的重要指標(biāo)，由于兩種算法在求解FT06Job－shop 調(diào)度問題時(shí)都取得了較好的效果，這里就給出了兩種算法求解FT06Job－shop 調(diào)度問題時(shí)的各代種群最優(yōu)調(diào)度結(jié)果的收斂效果圖。PSO和QPSO 每一代的最小值收斂效果如圖1所示，PSO和QPSO 每一代的平均值收斂效果如圖2所示。

圖1 PSO和QPSO 每一代的最小值收斂效果

圖2 PSO和QPSO 每一代的平均值收斂效果

由圖1和圖2 可以看出，對(duì)于FT06 車間調(diào)度問題，QPSO算法在求解FT06Job－shop 調(diào)度問題時(shí)的效果明顯好于PSO算法。

2.3 仿真結(jié)果分析

由于在經(jīng)典PSO算法中粒子的收斂是以軌道的形式實(shí)現(xiàn)的，并且由于粒子的速度總是有限的，因此在搜索過程中粒子的搜索空間是一個(gè)有限的區(qū)域，不能覆蓋整個(gè)可行空間。QPSO算法，量子系統(tǒng)的粒子在測(cè)量之前沒有既定的規(guī)程，而已一定的概率分布出現(xiàn)在任何位置，從而可以達(dá)到全局搜索。從動(dòng)力學(xué)的角度看，QPSO算法中粒子的收斂過程是以局部吸引點(diǎn)p為吸引子，隨著速度的減小不斷地接近p點(diǎn)，最后跌落到p 點(diǎn)［9，10］。因此在整個(gè)過程中，在p 點(diǎn)處實(shí)際上存在某種形式的吸引勢(shì)能場(chǎng)吸引著粒子。這正是整個(gè)粒子群能保持聚集性的原因。而且，QPSO算法的控制參數(shù)較PSO算法更少，因此QPSO算法相對(duì)于PSO算法而言，可以避免算法陷入局部極值從而具有更好的全局收斂性能。因此，在FT06算例仿真結(jié)果中，QPSO的尋優(yōu)能力均優(yōu)于PSO算法。

3 結(jié)論

本文通過典型車間調(diào)度問題算例驗(yàn)證了粒子群算法和量子粒子群算法解決車間調(diào)度問題的有效性及優(yōu)越性，通過車間調(diào)度問題FT06算例的仿真結(jié)果證明QPSO算法的尋優(yōu)能力優(yōu)于PSO算法。

［1］Sun J，F(xiàn)eng B，Xu W B.Particle Swarm Optimization with Particles Having Quantum Behavior［C］.Proceedings of IEEE Congress on Evolutionary Computation，2004:325－331.

［2］Sun J，Xu W，F(xiàn)eng B.A Global Search Strategy of Quantum－behaved Particle Swarm Optimization［C］.Proceedings of IEEE Conference on Cybernetics and Intelligent Systems，2004:111－116.

［3］方偉，孫俊，謝振平，等.量子粒子群優(yōu)化算法的收斂性分析及控制參數(shù)研究［J］.物理學(xué)報(bào)，2010，59(6):3686－3693.

［4］顏亮，姚錫凡，胡俊，等.用于車間作業(yè)調(diào)度的粒子群優(yōu)化算法［J］.管理技術(shù)，2009(6):115－119.

［5］李小華，熊禾根.基于粒子群算法的車間調(diào)度問題［J］.信息技術(shù)，2009(7):19－21.

［6］Shi Y H，Eberhart R C.Empirical Study of Particle Swarm Optimization［C］.Proceedings of 1999 Congress on Evolutionary Computation，Washington D C:IEEE，1999:1945－1949.

［7］EFGallad A，EFHawary M，Sallam A，et al.Enhancing the Particle Swarm Optimizer Via Proper Parameters Selection［C］.Proceedings of the 2002 IEEE Canadian Conference on Electrical ＆ Computer Engineering，Winnipeg:IEEE，2002:792－797.

［8］Sun J，Xu W B，F(xiàn)eng B.Man and Cybernetics［C］.IEEE International Conference on Systems，Hawaii:IEEE，2005:3049－3049.

［9］范路橋，常會(huì)友，朱旭東.一種改進(jìn)的作業(yè)車間調(diào)度算法及其實(shí)現(xiàn)［J］.計(jì)算機(jī)集成制造系統(tǒng)，2005，11(5):673－677.

［10］何利，劉永賢，謝華龍，等.基于粒子群算法的車間調(diào)度與優(yōu)化［J］.東北大學(xué)學(xué)報(bào)，2008，29(4):565－568.