量子粒子群算法在面向再制造的flow-shop問(wèn)題中的應(yīng)用

胡金濤，葉春明，葉 林

HU Jin-tao, YE Chun-ming, YE Lin

（上海理工大學(xué) 管理學(xué)院，上海 200093）

量子粒子群算法在面向再制造的flow-shop問(wèn)題中的應(yīng)用

Application of quantum particle swarm optimization algorithm in flow shop scheduling based on remanufacturing

胡金濤，葉春明，葉 林

HU Jin-tao, YE Chun-ming, YE Lin

（上海理工大學(xué) 管理學(xué)院，上海 200093）

對(duì)再制造的各環(huán)節(jié)進(jìn)行分析，研究出再制造生產(chǎn)階段的目標(biāo)——流水線生產(chǎn)。針對(duì) 粒子群優(yōu)化算法搜索空間有限、容易出現(xiàn)早熟現(xiàn)象的缺陷,采用量子粒子群算法設(shè)計(jì)單一生產(chǎn)商再制造系統(tǒng)流水線生產(chǎn)的機(jī)制，通過(guò)隨機(jī)初始種群，修正非法解，量子旋轉(zhuǎn)門更新，運(yùn)用MATLAB編程仿真測(cè)試得到大規(guī)模生產(chǎn)的優(yōu)化結(jié)果，取得較好結(jié)果。

再制造；量子粒子群；修正非法解；flow-shop

0 引言

再制造概念的提出打破了傳統(tǒng)的“從搖籃到墳?zāi)埂钡膯紊芷?，?shí)現(xiàn)了廢舊產(chǎn)品新生的過(guò)程。再制造（Remanufacturing）是指通過(guò)回收、拆卸、分揀、清洗、噴涂、翻修、及再裝配等環(huán)節(jié)，修復(fù)或改造廢舊產(chǎn)品，恢復(fù)零部件或產(chǎn)品性能的技術(shù)和活動(dòng)[1]，是實(shí)現(xiàn)綠色循環(huán)經(jīng)濟(jì)的有效途徑。目前，歐美等國(guó)汽車零部件再制造利用基本上達(dá)到80%以上，并已在技術(shù)、加工、銷售等方面形成一套完整體系，而國(guó)內(nèi)產(chǎn)品還主要集中在發(fā)動(dòng)機(jī)、變速器、電機(jī)等附加值較高的汽車零部件上，對(duì)于其他零部件無(wú)論從技術(shù)、資金還是設(shè)備上，還無(wú)暇顧及。因此，再制造工業(yè)是未來(lái)中國(guó)制造業(yè)的必經(jīng)之路。

量子計(jì)算（quantum computation, QC）的研究開始于1982年，現(xiàn)已經(jīng)成為世界各國(guó)緊密跟蹤的前沿研究領(lǐng)域之一。相對(duì)于經(jīng)典算法而言，其最本質(zhì)的特征就是利用了量子態(tài)的疊加性和相干性，以及量子比特之間的糾纏性，由此，研究者們依據(jù)量子比特的特性提出了量子進(jìn)化算法(QEA)。雖然理論上已經(jīng)證明QEAZ在尋優(yōu)過(guò)程中要比一般算法好，然而，QEA本身存在著缺陷，在操作和更新量子比特過(guò)程中，設(shè)定的參數(shù)比較多，操作繁瑣，容易早熟，特別是沒(méi)有利用其他未成熟個(gè)體攜帶的全局最優(yōu)值信息。因此，一些學(xué)者將量子計(jì)算中的一些基本概念引進(jìn)到經(jīng)典計(jì)算中，從根本上改善算法的性能。例如：Han[2]將量子概念和遺傳算法相結(jié)合，在解決經(jīng)典的組合優(yōu)化問(wèn)題上，顯示出很好的性能。Sun[3]提出了基于量子行為的微粒群算法（PSO），將微粒群算法的尋優(yōu)理念納入QEA，保留了PSO中的極值跟蹤及鄰域搜索，加速算法的收斂，Sun的算法本質(zhì)是模擬薛定諤方程，是封閉量子系統(tǒng)演化的一種方式，表現(xiàn)出了非常好的性能。

本文提出的量子粒子群算法利用量子比特進(jìn)行編碼，通過(guò)量子旋轉(zhuǎn)門進(jìn)行粒子更新，保留了粒子群算法的進(jìn)化方程，加入了全干擾交叉拓寬搜索的范圍，引入了變量搜索加強(qiáng)局部搜索能力，加速算法的收斂。

1 量子進(jìn)化算法和粒子群算法

1.1 量子進(jìn)化算法

量子進(jìn)化算法（QEA）是在概率進(jìn)化算法的基礎(chǔ)上發(fā)展起來(lái)的新的進(jìn)化算法。它采用量子比特染色體編碼，通過(guò)量子門變異來(lái)進(jìn)化染色體，然后觀察量子染色體的狀態(tài)來(lái)生成二進(jìn)制解，最后通過(guò)量子旋轉(zhuǎn)門實(shí)現(xiàn)進(jìn)化操作。

在量子進(jìn)化算法中，最小的信息單元為1量子比特。1量子比特的狀態(tài)可以取值0或者1，或者任一疊加態(tài)，表示如下：

因此，粒子的量子表示方法可以通過(guò)使用概率幅或相位加以表示。如第t代的種群為Q(t)={q1t,q2t,...,qnt}，qnt即為染色體，具體形式可以描述如下：

QEA的一般步驟如下：

1）初始化種群Q(t)，t=0；

2）由Q(t)生成二進(jìn)制序列P(t)；

3）評(píng)價(jià)P(t)的適應(yīng)度，并保存最優(yōu)解；

4）停止條件判斷：如果滿足停機(jī)條件，則輸出當(dāng)前最優(yōu)個(gè)體，算法結(jié)束，否則算法繼續(xù)；

5）更新Q(t)，t=t+1，返回2）。

算法中，Q(t)表示量子染色體的種群，P(t)表示二進(jìn)制染色體種群，在第t代中，Q(t)={q1t,q2t,...,qnt}，P(t)= {X1t,X2t,...,Xnt}（n表示種群大?。?，每個(gè)二進(jìn)制解 Xjt(j=1,2,...,n)是長(zhǎng)度為m的二進(jìn)制串，它是由量子比特幅|αit|2或者|βit|2得到的，對(duì)應(yīng)二進(jìn)制情況的過(guò)程是隨機(jī)產(chǎn)生一個(gè)[0,1]數(shù)，若它大于|αit|2，取1，否則取0。在第5）步更新Q(t)中，采用量子旋轉(zhuǎn)門對(duì)Q(t)進(jìn)行更新，量子門的設(shè)計(jì)有多種形式，如非門、受控非門、Hadamard門等，最常用的量子旋轉(zhuǎn)門如下：

1.2 粒子群算法（PSO）

PSO最早是由Kennedy和Eberhart于1995年提出的[4]。受到人工生命（Artificial Life）的研究結(jié)果啟發(fā)，PSO的基本概念源于對(duì)鳥群捕食行為的研究。PSO算法首先初始化一群隨機(jī)粒子，然后通過(guò)進(jìn)化（迭代）來(lái)找到最優(yōu)解。在粒子的每一次進(jìn)化中，通過(guò)跟蹤兩個(gè)極值來(lái)更新自己，一個(gè)極值是粒子本身所能找到的最優(yōu)解，即個(gè)體極值pbest，另一個(gè)是整個(gè)群體目前找到的最優(yōu)解，即全局極值gbest。粒子找到這兩個(gè)極值后，就根據(jù)下面兩個(gè)公式更新自己的速度和位置：

其中，d表示粒子的維度，i表示第i個(gè)粒子(j=1,2,...,n)，t表示迭代的次數(shù)， Xit(Xi1t,Xi2t,...,Xidt)表示t時(shí)刻d維搜索空間中的第i個(gè)粒子的位置，Vit(vi1t,vi2t,...,vidt)表示t時(shí)刻d維搜索空間中的第i個(gè)微粒的速度，ω表示慣性權(quán)因子，c1,c2為正的加速常數(shù)，rand()為在0到1之間均勻分布的隨機(jī)數(shù)[5]。

1.3 量子微粒群優(yōu)化算法(QPSO)

為了改善微粒群算法的缺點(diǎn)，我們?cè)谠械乃惴ɑA(chǔ)上引入了量子計(jì)算，形成量子微粒群算法，使得算法具有強(qiáng)大的領(lǐng)域搜索能力以及極值跟蹤能力，能夠改善微粒群算法后期搜索能力。

借鑒微粒群算法的速度更新公式，QPSO算法粒子的更新方式是：

其中pid,pgd,c1,c2,xid的定義與PSO中的定義相同。

2 面向再制造的流水車間調(diào)度問(wèn)題(FSP)的QPSO算法

2.1 再制造描述

在過(guò)去的十幾年時(shí)間里，越來(lái)越多的人關(guān)注產(chǎn)品的回收，一方面綠色循環(huán)經(jīng)濟(jì)的出現(xiàn)為國(guó)家的發(fā)展提供了道理，一方面制造企業(yè)間競(jìng)爭(zhēng)的加劇促使領(lǐng)導(dǎo)人員想方設(shè)法所見成本提高質(zhì)量，再制造對(duì)于企業(yè)的長(zhǎng)遠(yuǎn)發(fā)展舉足輕重，為企業(yè)帶來(lái)了額外利潤(rùn)。如今，發(fā)達(dá)國(guó)家工業(yè)領(lǐng)域銷售的設(shè)備60%是再制造生產(chǎn)出來(lái)的。卡特彼勒上海再制造中心市場(chǎng)總監(jiān)肖紹成曾向《中國(guó)投資》解釋了再制造的生產(chǎn)流程：舊件從消費(fèi)者手中收上來(lái)后，被全部拆解到最后一顆螺釘，進(jìn)行清洗；然后，進(jìn)行篩選，其中易損件需要100%更換，一部分是可以恢復(fù)到原狀的，比如氣缸蓋，還有一部分是不需要修復(fù)的，比如螺釘，它只要清洗后就可以再次使用。把這三個(gè)部分：經(jīng)過(guò)修復(fù)的、經(jīng)過(guò)更換的和不需要修復(fù)的，重新組合成新的部件，這個(gè)過(guò)程就是再制造，如圖1所示。

再制造流程[6]

圖1為再制造的流程圖，從回收階段到使用階段企業(yè)需要對(duì)回收產(chǎn)品做多方面處理，其技術(shù)難點(diǎn)就是壽命評(píng)估和修復(fù)，這就對(duì)企業(yè)的再制造能力形成了考驗(yàn)，雖然再制造為制造業(yè)的生產(chǎn)趨勢(shì)，不過(guò)再制造本身具有很大的不確定性，主要表現(xiàn)在產(chǎn)品的回收質(zhì)量，檢測(cè)拆卸及再制造可靠性，對(duì)于生產(chǎn)調(diào)度提出了很高的要求。在生產(chǎn)階段，我們不討論回收產(chǎn)品質(zhì)量，拆卸，可靠性及成本的不確定性，由于回收的產(chǎn)品再制造企業(yè)在設(shè)計(jì)階段將其分門別類，對(duì)于一般通用件，企業(yè)再制造生產(chǎn)過(guò)程仍然是基于flow-shop的調(diào)度。

2.2 fl ow-shop描述[7]

Flow-shop調(diào)度問(wèn)題是一種典型的組合優(yōu)化問(wèn)題，一般可以描述為：n個(gè)工件在m臺(tái)機(jī)器上加工，一個(gè)工件分為k道工序，每道工序要求不同的機(jī)器加工。n個(gè)工件在m臺(tái)機(jī)器上的加工順序相同，工件i在機(jī)器j上的加工時(shí)間是給定的，設(shè)為tij(i=1,2,…,n;j=1,2,…,m)。調(diào)度問(wèn)題的目標(biāo)函數(shù)是求n個(gè)工件的最優(yōu)加工順序，使最大流程時(shí)間最小。

對(duì)流水車間調(diào)度問(wèn)題常作如下假設(shè)：

1）每個(gè)工件在機(jī)器上的加工順序相同，且是確定的；

2）每臺(tái)機(jī)器在每個(gè)時(shí)刻只能加工某個(gè)工件的某道工序；

3）一個(gè)工件不能同時(shí)在不同機(jī)器上加工；

4）工序的準(zhǔn)備時(shí)間與順序無(wú)關(guān)，且包含在加工時(shí)間中。

車間調(diào)度問(wèn)題的完工時(shí)間可以表示為：

最大流程時(shí)間為cmax=c(jn,m)

2.3 粒子編碼方式

本文采用二進(jìn)制的基于工件的編碼方式，對(duì)于n個(gè)工件，m臺(tái)機(jī)器的flow-shop問(wèn)題，每個(gè)粒子對(duì)應(yīng)n維向量，每個(gè)向量用ceil(log2(n))位二進(jìn)制染色體編碼表示，即每個(gè)粒子用ceil(log2(n))*n位二進(jìn)制量子染色體表示，量子染色體由量子比特坍縮而成。

例如工件數(shù)為3，若某粒子的染色體表示如下：

將粒子二進(jìn)制編碼解碼為十進(jìn)制數(shù)：

按元素值大小順序?qū)重新整數(shù)序規(guī)范：

則該粒子x的調(diào)度順序?yàn)椋簀3-j1-j2

2.4 修正非法解

將量子坍塌得到的每組二進(jìn)制串xjt都轉(zhuǎn)化為n個(gè)十進(jìn)制工件編號(hào)，此時(shí)每個(gè)個(gè)體都變成了n個(gè)十進(jìn)制數(shù)，因此整個(gè)種群可以得到N（N 為維數(shù)）個(gè)解，也就是N中調(diào)度安排，但是由于初始化時(shí)，編碼是通過(guò)隨機(jī)產(chǎn)生的，所以必然存在不可行的工件編號(hào)，因此需要對(duì)不可行編碼進(jìn)行修復(fù)：

1）通過(guò)ceil(log2(n))得到x的范圍，將工件號(hào)對(duì)應(yīng)的x從編碼范圍內(nèi)除去；

2）判斷編碼中的工件號(hào)對(duì)應(yīng)的x是否重復(fù)，若重復(fù)，則找出相同的數(shù)，在剩余的編碼范圍內(nèi)隨機(jī)選擇一個(gè)數(shù)，以進(jìn)行工件排序，保證每行的工件對(duì)應(yīng)的x值都不相同，且均在編碼范圍內(nèi)。

QPSO流程步驟：

1）初始化參數(shù)；

2）令t=0，初始化Q(t)；

3）由Q(t)觀測(cè)得到P(t)；

4）由P(t)生成序列Y(t)；

5）由于生成的十進(jìn)制整數(shù)Y(t)，因此對(duì)該十進(jìn)制序列進(jìn)行修正非法解，使之成為每行的數(shù)值都不相等。

6）在修正非法解后，對(duì)該十進(jìn)制序列進(jìn)行二進(jìn)制轉(zhuǎn)化，再通過(guò)一定機(jī)制將其轉(zhuǎn)化為概率幅矩陣，以便得到更新后的相位陣；

7）采用上文提到的編碼方式將十進(jìn)制序列轉(zhuǎn)換成工件的排列，本文的維度為10，因此將得到10個(gè)工件的排列X(t)。

8）評(píng)價(jià)X(t)的適應(yīng)度（加工時(shí)間）；

9）標(biāo)記本代粒子最優(yōu)的相位為pbest,并標(biāo)記粒子全局最優(yōu)的相位為gbest;

10）t=t+1,采用量子旋轉(zhuǎn)門更新種群；

11）更新pbest和gbest;

12）如果滿足算法終止條件，停止，否則轉(zhuǎn)3）。

圖2 迭代最佳適應(yīng)值情況

表1 Flow-Shop Benchmark問(wèn)題求解結(jié)果

本文對(duì)表1中的三種問(wèn)題規(guī)模進(jìn)行隨機(jī)20次運(yùn)行，最小偏差指的是算法運(yùn)行20次找到的最小時(shí)間，與已知最優(yōu)解之間的相對(duì)誤差；平均偏差指的是20次計(jì)算得到的最小時(shí)間的平均值與已知最優(yōu)解之間的相對(duì)誤差。

圖2采用了QPSO對(duì)Car1（11*5）優(yōu)化的結(jié)果，參數(shù)設(shè)置如下：種群規(guī)模為10，最大迭代次數(shù)為200，C1和我C2為2，采用動(dòng)態(tài)權(quán)重法，從曲線的收斂情況來(lái)看，算法在第7代求得最優(yōu)解，收斂速度快，很好把握了多樣化搜索的分散性和保證種群質(zhì)量的收斂性之間的平衡。

3 結(jié)束語(yǔ)

本文是量子粒子群算法的面向再制造的flowshop調(diào)度，對(duì)于再制造下的flow-shop問(wèn)題設(shè)計(jì)較為理想，僅僅考慮再制造企業(yè)生產(chǎn)階段的生產(chǎn)方式，相對(duì)生產(chǎn)階段，設(shè)計(jì)階段技術(shù)要求比較高，多一些有效的管理方法，就會(huì)少一些紕漏，本文運(yùn)用MATLAB編程測(cè)試改進(jìn)的量子粒子群算法求解flop-shop問(wèn)題，取得較好的結(jié)果。

[1] 徐濱士.汽車發(fā)動(dòng)機(jī)再制造效益分析及對(duì)循環(huán)經(jīng)濟(jì)的貢獻(xiàn)[J].中國(guó)表面工程,2005(1)：1-7.

[2] Han K,Kim JH.Genetic quantum algorithm and its application to combinatorial optimization problems[C]//Proceedings of the 2000 IEEE Conference on Evolutionary Computation,Piscataway,IEEE Press,2000：1354-1360.

[3] Sun J,Feng B,Xu WB.Particle swarm optimization with particles having quantum behavior[c]//Proceedings of IEEE Conference on Evolutionary Computation,2004：326-331.

[4] Kennedy J,Eberhart R.Particle Swarm Optimization[C].In：IEEE International Conference on Neural Networks, Perth,Australia,1995：1942-1948.

[5] 王凌,劉波.微粒群優(yōu)化與調(diào)度算法[M].北京：清華大學(xué)出版社,2008.

[6] 崔培枝,姚巨坤,許藝.面向再制造全過(guò)程的管理.新技術(shù)新工藝·機(jī)械加工與自動(dòng)化,2004,7.

[7] 王萬(wàn)良,吳啟迪.生產(chǎn)調(diào)度智能算法及其應(yīng)用[M].北京：科學(xué)出版社,2007.

TH166

A

1009-0134(2010)09-0064-04

10.3969/j.issn.1009-0134.2010.09.19

2009-10-26

上海市本科生創(chuàng)新基金（SH081025227）

胡金濤（1985 -），男，碩士研究生，研究方向?yàn)楣I(yè)工程。