量子粒子群算法在面向再制造的flow-shop問題中的應用

胡金濤，葉春明，葉 林

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

（上海理工大學 管理學院，上海 200093）

量子粒子群算法在面向再制造的flow-shop問題中的應用

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

胡金濤，葉春明，葉 林

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

（上海理工大學 管理學院，上海 200093）

對再制造的各環節進行分析，研究出再制造生產階段的目標——流水線生產。針對 粒子群優化算法搜索空間有限、容易出現早熟現象的缺陷,采用量子粒子群算法設計單一生產商再制造系統流水線生產的機制，通過隨機初始種群，修正非法解，量子旋轉門更新，運用MATLAB編程仿真測試得到大規模生產的優化結果，取得較好結果。

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

0 引言

再制造概念的提出打破了傳統的“從搖籃到墳墓”的單生命周期，實現了廢舊產品新生的過程。再制造（Remanufacturing）是指通過回收、拆卸、分揀、清洗、噴涂、翻修、及再裝配等環節，修復或改造廢舊產品，恢復零部件或產品性能的技術和活動[1]，是實現綠色循環經濟的有效途徑。目前，歐美等國汽車零部件再制造利用基本上達到80%以上，并已在技術、加工、銷售等方面形成一套完整體系，而國內產品還主要集中在發動機、變速器、電機等附加值較高的汽車零部件上，對于其他零部件無論從技術、資金還是設備上，還無暇顧及。因此，再制造工業是未來中國制造業的必經之路。

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

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

1 量子進化算法和粒子群算法

1.1 量子進化算法

量子進化算法（QEA）是在概率進化算法的基礎上發展起來的新的進化算法。它采用量子比特染色體編碼，通過量子門變異來進化染色體，然后觀察量子染色體的狀態來生成二進制解，最后通過量子旋轉門實現進化操作。

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

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

QEA的一般步驟如下：

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

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

3）評價P(t)的適應度，并保存最優解；

4）停止條件判斷：如果滿足停機條件，則輸出當前最優個體，算法結束，否則算法繼續；

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

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

1.2 粒子群算法（PSO）

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

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

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

為了改善微粒群算法的缺點，我們在原有的算法基礎上引入了量子計算，形成量子微粒群算法，使得算法具有強大的領域搜索能力以及極值跟蹤能力，能夠改善微粒群算法后期搜索能力。

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

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

2 面向再制造的流水車間調度問題(FSP)的QPSO算法

2.1 再制造描述

在過去的十幾年時間里，越來越多的人關注產品的回收，一方面綠色循環經濟的出現為國家的發展提供了道理，一方面制造企業間競爭的加劇促使領導人員想方設法所見成本提高質量，再制造對于企業的長遠發展舉足輕重，為企業帶來了額外利潤。如今，發達國家工業領域銷售的設備60%是再制造生產出來的?？ㄌ乇死丈虾Ｔ僦圃熘行氖袌隹偙O肖紹成曾向《中國投資》解釋了再制造的生產流程：舊件從消費者手中收上來后，被全部拆解到最后一顆螺釘，進行清洗；然后，進行篩選，其中易損件需要100%更換，一部分是可以恢復到原狀的，比如氣缸蓋，還有一部分是不需要修復的，比如螺釘，它只要清洗后就可以再次使用。把這三個部分：經過修復的、經過更換的和不需要修復的，重新組合成新的部件，這個過程就是再制造，如圖1所示。

再制造流程[6]

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

2.2 fl ow-shop描述[7]

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

對流水車間調度問題常作如下假設：

1）每個工件在機器上的加工順序相同，且是確定的；

2）每臺機器在每個時刻只能加工某個工件的某道工序；

3）一個工件不能同時在不同機器上加工；

4）工序的準備時間與順序無關，且包含在加工時間中。

車間調度問題的完工時間可以表示為：

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

2.3 粒子編碼方式

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

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

將粒子二進制編碼解碼為十進制數：

按元素值大小順序對x重新整數序規范：

則該粒子x的調度順序為：j3-j1-j2

2.4 修正非法解

將量子坍塌得到的每組二進制串xjt都轉化為n個十進制工件編號，此時每個個體都變成了n個十進制數，因此整個種群可以得到N（N 為維數）個解，也就是N中調度安排，但是由于初始化時，編碼是通過隨機產生的，所以必然存在不可行的工件編號，因此需要對不可行編碼進行修復：

1）通過ceil(log2(n))得到x的范圍，將工件號對應的x從編碼范圍內除去；

2）判斷編碼中的工件號對應的x是否重復，若重復，則找出相同的數，在剩余的編碼范圍內隨機選擇一個數，以進行工件排序，保證每行的工件對應的x值都不相同，且均在編碼范圍內。

QPSO流程步驟：

1）初始化參數；

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

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

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

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

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

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

8）評價X(t)的適應度（加工時間）；

9）標記本代粒子最優的相位為pbest,并標記粒子全局最優的相位為gbest;

10）t=t+1,采用量子旋轉門更新種群；

11）更新pbest和gbest;

12）如果滿足算法終止條件，停止，否則轉3）。

圖2 迭代最佳適應值情況

表1 Flow-Shop Benchmark問題求解結果

本文對表1中的三種問題規模進行隨機20次運行，最小偏差指的是算法運行20次找到的最小時間，與已知最優解之間的相對誤差；平均偏差指的是20次計算得到的最小時間的平均值與已知最優解之間的相對誤差。

圖2采用了QPSO對Car1（11*5）優化的結果，參數設置如下：種群規模為10，最大迭代次數為200，C1和我C2為2，采用動態權重法，從曲線的收斂情況來看，算法在第7代求得最優解，收斂速度快，很好把握了多樣化搜索的分散性和保證種群質量的收斂性之間的平衡。

3 結束語

本文是量子粒子群算法的面向再制造的flowshop調度，對于再制造下的flow-shop問題設計較為理想，僅僅考慮再制造企業生產階段的生產方式，相對生產階段，設計階段技術要求比較高，多一些有效的管理方法，就會少一些紕漏，本文運用MATLAB編程測試改進的量子粒子群算法求解flop-shop問題，取得較好的結果。

[1] 徐濱士.汽車發動機再制造效益分析及對循環經濟的貢獻[J].中國表面工程,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] 王凌,劉波.微粒群優化與調度算法[M].北京：清華大學出版社,2008.

[6] 崔培枝,姚巨坤,許藝.面向再制造全過程的管理.新技術新工藝·機械加工與自動化,2004,7.

[7] 王萬良,吳啟迪.生產調度智能算法及其應用[M].北京：科學出版社,2007.

TH166

A

1009-0134(2010)09-0064-04

10.3969/j.issn.1009-0134.2010.09.19

2009-10-26

上海市本科生創新基金（SH081025227）

胡金濤（1985 -），男，碩士研究生，研究方向為工業工程。