基于基因片段分解的粒子群算法求解置換Flowshop問(wèn)題

郝平波，魏英姿，馮藝君

（沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110159）

流水線調(diào)度問(wèn)題（flow-shop scheduling problem，F(xiàn)SP）是許多實(shí)際流水線生產(chǎn)調(diào)度問(wèn)題的簡(jiǎn)化模型，約有25%的生產(chǎn)制造、組裝線盒信息服務(wù)設(shè)施可簡(jiǎn)化為FSP模型。FSP是一類典型的NP問(wèn)題[1]，也是目前研究最廣泛的一類調(diào)度問(wèn)題，因此其研究具有重要的理論意義和工程價(jià)值。

粒子群算法 （particle swarm optimization，PSO）[2]是由Kennedv和Eberhart于1995年對(duì)鳥(niǎo)群覓食行為研究提出來(lái)的。PSO和遺傳算法類似，是一種基于迭代的優(yōu)化算法。算法初始化為一群隨機(jī)粒子（隨機(jī)解）。然后粒子們追隨當(dāng)前的最優(yōu)粒子在解空間中探索，通過(guò)迭代找到最優(yōu)解。在每一次迭代中，粒子通過(guò)跟蹤個(gè)體極值（本身所找到的最優(yōu)解）和全局極值（整個(gè)種群目前找到的最優(yōu)解）來(lái)更新自己。與其他進(jìn)化算法相比，PSO保留了基于種群的全局搜索策略，其特有的記憶可以動(dòng)態(tài)地跟蹤當(dāng)前的搜索情況來(lái)調(diào)整下一步的搜索策略，是一種更高效的并行搜索算法，而且具有擴(kuò)展性，容易與其他算法結(jié)合。適用于處理連續(xù)優(yōu)化問(wèn)題及多點(diǎn)搜索，已成功應(yīng)用于函數(shù)優(yōu)化、多目標(biāo)優(yōu)化、動(dòng)態(tài)優(yōu)化等領(lǐng)域中。因此，PSO一經(jīng)提出，立刻引起了演化計(jì)算等領(lǐng)域?qū)W者們的廣泛關(guān)注，并在短短的幾年時(shí)間里出現(xiàn)大量的研究成果，形成了一個(gè)研究熱點(diǎn)。

1 Flowshop調(diào)度問(wèn)題描述和數(shù)學(xué)模型

Flowshop調(diào)度問(wèn)題的簡(jiǎn)化數(shù)學(xué)模型是安排n個(gè)工件在m臺(tái)機(jī)器上加工順序的問(wèn)題，每個(gè)零件在各機(jī)器上加工的順序相同，同時(shí)約定每個(gè)工件在每臺(tái)機(jī)器上只加工一次。每臺(tái)機(jī)器一次在某一時(shí)刻只能加工一個(gè)工件，各工件在各機(jī)器上所需的加工時(shí)間和準(zhǔn)備時(shí)間已知，要求得到某調(diào)度方案使得某項(xiàng)指標(biāo)最優(yōu)。進(jìn)一步，約定每臺(tái)機(jī)器加工的各工件的順序相同，則稱其為置換FlowShop調(diào)度問(wèn)題。

置換FlowShop調(diào)度問(wèn)題的數(shù)學(xué)模型如下：令tij為工件i在機(jī)器j上的加工時(shí)間，θkij為機(jī)器k上加工完工件i后馬上加工工件j所需的準(zhǔn)備時(shí)間 （無(wú)特殊說(shuō)明，=0），Ti為工件 i的加工完畢時(shí)間，不是一般性，假設(shè)各工件按機(jī)器1到m的順序進(jìn)行加工，令 π=（σ1，σ2，…，σn）為所有工件的一個(gè)排序，則以最大完成時(shí)間為指標(biāo)，即Makespan指標(biāo)：

2 粒子群算法

在d維搜索空間中第i個(gè)粒子的位置和速度分別表示為Xi=[xi,1，xi，2，…，xi，d]和 Vi=[vi，1，vi，2，…，vi，d]。 通過(guò)評(píng)價(jià)各粒子的目標(biāo)函數(shù)。 確定 t時(shí)刻每個(gè)粒子所經(jīng)過(guò)的最佳位置（pbest）Pi=[pi，1，pi，2，… ，pi，d]以及群體的最佳位置（gbest）Pg，按如下公式更新各粒子的速度和位置：

其中，ω為慣性因子，c1和c2為正的加速度常數(shù)，r1和r2為0到1之間的隨機(jī)數(shù)。通過(guò)設(shè)置粒子的速度區(qū)間[vmin，vmax]和位置區(qū)間[xmin，xmin]，可以對(duì)粒子的移動(dòng)做適當(dāng)?shù)南拗啤?/p>

粒子群算法流程：

Step1:隨機(jī)初始化種群中每個(gè)粒子的位置和速度。

Step2:評(píng)價(jià)每個(gè)粒子，將當(dāng)前各粒子的位置和目標(biāo)值存放在各粒子的pbest中，將所有pbest中目標(biāo)值最優(yōu)的個(gè)體的位置和目標(biāo)值存放在gbest中。

Step3:按式（1）和式（2）更新各粒子的速度和位置。

Step4:評(píng)價(jià)種群中的所有粒子，更新pbest和gbest。

Step5:若滿足終止條件，則輸出gbest及其目標(biāo)值，否則返回Step3。

3 粒子群優(yōu)化算法求解Flowshop調(diào)度問(wèn)題

3.1 解的描述

采用n維粒子群優(yōu)化算法求解n個(gè)工件的置換流水車間調(diào)度問(wèn)題。 粒子的位置 Xi=[xi，1，xi，2，…，xi，n]蘊(yùn)含了工件排列順序。本文采用ROV規(guī)則[3]提取工件的加工順序。表1給出了將維數(shù)為6的粒子位置轉(zhuǎn)換為6個(gè)工件順序的實(shí)例。

表1 粒子的位置及其對(duì)應(yīng)的ROV值Tab.1 Particle position and its corresponding value ROV

首先，賦予值最小xi，1的分量位置ROV值1，接下來(lái)賦予xi，6對(duì)應(yīng)的分量位置 ROV 值 2， 然后分別賦予 xi，3，xi，5，xi，2和 xi，4分量位置ROV值3，4，5和6，從而得到工件的加工次序，即π=（1，5，3，6，4，2）。

3.2 粒子群算法的初始化及其基因片段[4]的分解

在粒子群算法中，粒子的位置和速度的初始值通過(guò)在區(qū)間[0，1]上的均勻分布隨機(jī)產(chǎn)生。個(gè)體最優(yōu)解的初始值為個(gè)體的初始解。適應(yīng)值F（x）初始值都設(shè)為0。初始種群的生成，本文提出了一種貪婪的生成方法。

例如：粒子的位置 Xi=[xi，1，xi，2，…，xi，n]，種群大小為popsize，將其分成 m 個(gè)基因片 段[xi，1，xi，2，… ，xi，n1]，[xi，n1+1 ，xi，n1+2 ，…，x i，n2]，…，[xi，nm-2+1 ，xi，nm-2-2 ，…，xi，nm-1]， [xi，nm-1+1 ，xi，nm-1+2 ，…，xi，n]i∈[1，popsize]，適應(yīng)值為 F（x）。 本文初始種群的生成：

經(jīng)適應(yīng)值的計(jì)算，找到基因片段 1 的最優(yōu)排序[xk，1，kk，2，…，xk，n1],k∈[1，popsize])。 接著生成

種群對(duì)基因片段2進(jìn)行最優(yōu)調(diào)度，直到對(duì)基因片段m調(diào)度完畢。將得到一組最優(yōu)排序。

例如：粒子的位置 Xi=[xi，1，xi，2，…，xi，d]中 d=25，將其平均分成5個(gè)基因片段，即每個(gè)基因片段5個(gè)工件。每個(gè)基因片段有5！種排序，則整個(gè)片段有5×5！種排序。這遠(yuǎn)遠(yuǎn)比整個(gè)片段25！種排序少得多。從而提升了解的收斂和程序的運(yùn)行速度。如果基因片段中工件不夠，則以0補(bǔ)齊。

3.3 綜合學(xué)習(xí)與基因片段間的合作

3.3.1 綜合學(xué)習(xí)策略

找局部最優(yōu)值較大的粒子，隨機(jī)的與其他粒子的局部最優(yōu)值比較，選取適應(yīng)值較小的一個(gè)替換該粒子的局部最優(yōu)值。

3.3.2 基因片段間的合作

找出每個(gè)粒子所經(jīng)過(guò)的最佳位置pbest以及群體發(fā)現(xiàn)的最佳位置gbest。利用式（1）和式（2）更新粒子的速度和位置。根據(jù)目標(biāo)函數(shù)更新基因片段中各粒子的最優(yōu)適應(yīng)值、最優(yōu)位置和基因片段全局最優(yōu)適應(yīng)值。

3.4 種群局部搜索

將每次迭代后得到的基因片段最優(yōu)解的最佳值作為初始解，做交換局部搜索[5]。 具體地說(shuō)，假設(shè)[xk，1，xk，2，…，xk，n1]，

k∈[1，popsize]為得到的基因片段最優(yōu)解，如果 i≠k，將[xk，1，xk，2，…，xk，n1]與[xi，1，xi，2，…，xi，n1]交換。

3.5 算法流程

Step1:確定Pso的控制參數(shù)。包括種群規(guī)模，最大迭代代數(shù)，慣性因子等。

Step2:初始種群的生成，并將其分成個(gè)基因片段。

Step3:計(jì)算每個(gè)粒子的目標(biāo)函數(shù)，如果粒子的當(dāng)前解優(yōu)于個(gè)體最優(yōu)解，更新個(gè)體最優(yōu)解，利用個(gè)體最優(yōu)解更新全局最優(yōu)解。

Step4:根據(jù)4.3和4.4更新所有粒子的速度和位置。

Step5:計(jì)算每個(gè)粒子的目標(biāo)函數(shù)。

Step6:對(duì)于每一個(gè)粒子，如果當(dāng)前解優(yōu)于個(gè)體最優(yōu)解，則更新個(gè)體最優(yōu)解，利用個(gè)體最優(yōu)解更新全局最優(yōu)解。

Step7:如果停止條件滿足，則輸出全局最優(yōu)解；否則，轉(zhuǎn)Step4。

4 仿真結(jié)果

為測(cè)試算法的性能，本文通過(guò)對(duì)Rec系列基準(zhǔn)測(cè)試。本文用MATLAB7.1編程。硬件環(huán)境的處理器主頻為2.53 GHz，內(nèi)存為0.99 G，操作系統(tǒng)為Windows XP。參數(shù)設(shè)置為：c1=c2=2，慣性因子ω=0.4，粒子最小位置值xmin=0，粒子最大位置值xmax=1。粒子最小速度值vmin=0，粒子最大速度值vmax=1。對(duì)于Rec系列的IPSO（本文算法）算法，粒子種群規(guī)模為50，迭代次數(shù)為100。PSO算法，Rec01到Rec23種群規(guī)模為50，迭代次數(shù)為100，Rec25到Rec41種群規(guī)模為50，迭代次數(shù)為500。每個(gè)算例獨(dú)立運(yùn)行50次。

設(shè)A表示本實(shí)驗(yàn)取得的最優(yōu)值，B表示平均值，C表示最差值，C*表示已知最優(yōu)值。則最佳相對(duì)誤差：BRE=（A-C*）/C*×100%、 平均相對(duì)差:ARE=（B-C*）/C*×100%、 最差相對(duì)誤差:WRE=（C-C*）/C*×100%[6]分別表示 50 次運(yùn)行得到的最佳值、平均值以及最差值與C*的相對(duì)誤差。表2記錄了本文仿真的實(shí)驗(yàn)數(shù)據(jù)。

從表2可見(jiàn)，IPSO算法明顯好于PSO算法。在20個(gè)子問(wèn)題中，IPSO在每個(gè)子問(wèn)題上都取得了優(yōu)于PSO算法的解，在5個(gè)子問(wèn)題上取得了最優(yōu)解。從運(yùn)行過(guò)程來(lái)看，IPSO算法取得解得時(shí)間要遠(yuǎn)小于PSO算法。

從圖1中可以看出，隨著迭代次數(shù)的增加，PSO陷入了局部最優(yōu)，而IPSO在PSO陷入局部最優(yōu)之前就通過(guò)擴(kuò)大搜索范圍找到了比PSO更好的解。

圖2為在Rec 07上的甘特圖，從圖2中可以看出，工件被合理地分配在各機(jī)器上進(jìn)行加工。

從實(shí)驗(yàn)結(jié)果我們可以發(fā)現(xiàn)采用基因片段分解的粒子群算法[7]在求解置換流水調(diào)度問(wèn)題上求解性能良好，所求解均好于PSO算法的結(jié)果，為求解置換流水線調(diào)度問(wèn)題提供了一種新的途徑。

表2 本文算法求解Rec系列若干問(wèn)題仿真結(jié)果Tab.2 This algorithm Rec Series simulation results of a number of issues

圖1 在Rec 07上的運(yùn)行情況Fig.1 The operation of Rec 07

圖2 在Rec 07上的甘特圖Fig.2 The gantt chart of Rec 07

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

本文提出了基因片段分解的粒子群算法求解置換流水車間調(diào)度問(wèn)題，采用了基因片段分解的方法，初始個(gè)體最優(yōu)解基于貪婪方法得到，算法中結(jié)合粒子群算法的全局搜索能力和交換粒子位置的局部搜索能力將解決連續(xù)優(yōu)化問(wèn)題的標(biāo)準(zhǔn)粒子群優(yōu)化算法成功應(yīng)用于Flowshop調(diào)度問(wèn)題中，為解決生產(chǎn)調(diào)度問(wèn)題提供了一個(gè)高速有效的尋優(yōu)算法。通過(guò)對(duì)不同維數(shù)的基準(zhǔn)問(wèn)題進(jìn)行計(jì)算機(jī)仿真，仿真結(jié)果表明了本文提出算法的有效性與可行性。

[1]Garey M R，Johnson D S，Sethi R.The complexity of flowshop and job-shop scheduling[J].Mathematics of Operations Research，1976，1（1）:117-l29.

[2]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of International Conference on Neural Networks.Piscataway，N.J.，USA:IEEE Press，1995:1942-1948.

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

[4]梁艷春，馮大鵬，周春光.遺傳算法求解旅行商問(wèn)題時(shí)的基因片段保序[J].系統(tǒng)工程理論與實(shí)踐，2000，20（4）:7-12.LIANG Yan-chun，F(xiàn)ENG Da-peng，ZHOU Chun-guang.Order preserving of gene section for solving traveling salesman probeloms using genetic algorithms[J].System Engineering-Theory&practice， 2000，20（4）:7-12.

[5]任紅燕，張文國(guó).一種新的求解置換Flowshop問(wèn)題的粒子群算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2008，17（5）:3-4.REN Hong-yan，ZHANG Wen-guo.A novel particle swarm optimization algorithm for permutation flowshop problem[J].Computer System Applications，2008，17（5）:3-4.

[6]周鵬.求解置換流水車間調(diào)度問(wèn)題的混合蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（17）:191-193.ZHOU Peng.Hybdd ant colony algorithm for permutation flow shop scheduling problem [J].Computer Engineering and Applications，2009，45（17）:191-193.

[7]葉紅權(quán),郭益輝.粒子群算法在電力系統(tǒng)低頻振蕩辯識(shí)中的應(yīng)用[J].陜西電力,2009,37（3）：35-38.YE Hong-quan,GUO Yi-hui.Application of Particle Swarm Optimization in the Identification of Low-frequency Oscillation in Power System [J].Shaanxi Electric Power，2009,37（3）：35-38.