基于基因片段分解的粒子群算法求解置換Flowshop問題

郝平波，魏英姿，馮藝君

（沈陽理工大學 信息科學與工程學院，遼寧 沈陽 110159）

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

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

1 Flowshop調度問題描述和數學模型

Flowshop調度問題的簡化數學模型是安排n個工件在m臺機器上加工順序的問題，每個零件在各機器上加工的順序相同，同時約定每個工件在每臺機器上只加工一次。每臺機器一次在某一時刻只能加工一個工件，各工件在各機器上所需的加工時間和準備時間已知，要求得到某調度方案使得某項指標最優。進一步，約定每臺機器加工的各工件的順序相同，則稱其為置換FlowShop調度問題。

置換FlowShop調度問題的數學模型如下：令tij為工件i在機器j上的加工時間，θkij為機器k上加工完工件i后馬上加工工件j所需的準備時間 （無特殊說明，=0），Ti為工件 i的加工完畢時間，不是一般性，假設各工件按機器1到m的順序進行加工，令 π=（σ1，σ2，…，σn）為所有工件的一個排序，則以最大完成時間為指標，即Makespan指標：

2 粒子群算法

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

其中，ω為慣性因子，c1和c2為正的加速度常數，r1和r2為0到1之間的隨機數。通過設置粒子的速度區間[vmin，vmax]和位置區間[xmin，xmin]，可以對粒子的移動做適當的限制。

粒子群算法流程：

Step1:隨機初始化種群中每個粒子的位置和速度。

Step2:評價每個粒子，將當前各粒子的位置和目標值存放在各粒子的pbest中，將所有pbest中目標值最優的個體的位置和目標值存放在gbest中。

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

Step4:評價種群中的所有粒子，更新pbest和gbest。

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

3 粒子群優化算法求解Flowshop調度問題

3.1 解的描述

采用n維粒子群優化算法求解n個工件的置換流水車間調度問題。 粒子的位置 Xi=[xi，1，xi，2，…，xi，n]蘊含了工件排列順序。本文采用ROV規則[3]提取工件的加工順序。表1給出了將維數為6的粒子位置轉換為6個工件順序的實例。

表1 粒子的位置及其對應的ROV值Tab.1 Particle position and its corresponding value ROV

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

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

在粒子群算法中，粒子的位置和速度的初始值通過在區間[0，1]上的均勻分布隨機產生。個體最優解的初始值為個體的初始解。適應值F（x）初始值都設為0。初始種群的生成，本文提出了一種貪婪的生成方法。

例如：粒子的位置 Xi=[xi，1，xi，2，…，xi，n]，種群大小為popsize，將其分成 m 個基因片 段[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]，適應值為 F（x）。 本文初始種群的生成：

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

種群對基因片段2進行最優調度，直到對基因片段m調度完畢。將得到一組最優排序。

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

3.3 綜合學習與基因片段間的合作

3.3.1 綜合學習策略

找局部最優值較大的粒子，隨機的與其他粒子的局部最優值比較，選取適應值較小的一個替換該粒子的局部最優值。

3.3.2 基因片段間的合作

找出每個粒子所經過的最佳位置pbest以及群體發現的最佳位置gbest。利用式（1）和式（2）更新粒子的速度和位置。根據目標函數更新基因片段中各粒子的最優適應值、最優位置和基因片段全局最優適應值。

3.4 種群局部搜索

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

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

3.5 算法流程

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

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

Step3:計算每個粒子的目標函數，如果粒子的當前解優于個體最優解，更新個體最優解，利用個體最優解更新全局最優解。

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

Step5:計算每個粒子的目標函數。

Step6:對于每一個粒子，如果當前解優于個體最優解，則更新個體最優解，利用個體最優解更新全局最優解。

Step7:如果停止條件滿足，則輸出全局最優解；否則，轉Step4。

4 仿真結果

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

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

從表2可見，IPSO算法明顯好于PSO算法。在20個子問題中，IPSO在每個子問題上都取得了優于PSO算法的解，在5個子問題上取得了最優解。從運行過程來看，IPSO算法取得解得時間要遠小于PSO算法。

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

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

從實驗結果我們可以發現采用基因片段分解的粒子群算法[7]在求解置換流水調度問題上求解性能良好，所求解均好于PSO算法的結果，為求解置換流水線調度問題提供了一種新的途徑。

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

圖1 在Rec 07上的運行情況Fig.1 The operation of Rec 07

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

5 結束語

本文提出了基因片段分解的粒子群算法求解置換流水車間調度問題，采用了基因片段分解的方法，初始個體最優解基于貪婪方法得到，算法中結合粒子群算法的全局搜索能力和交換粒子位置的局部搜索能力將解決連續優化問題的標準粒子群優化算法成功應用于Flowshop調度問題中，為解決生產調度問題提供了一個高速有效的尋優算法。通過對不同維數的基準問題進行計算機仿真，仿真結果表明了本文提出算法的有效性與可行性。

[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]王凌，劉波.微粒群優化與調度算法[M].北京:清華大學出版社，2008.

[4]梁艷春，馮大鵬，周春光.遺傳算法求解旅行商問題時的基因片段保序[J].系統工程理論與實踐，2000，20（4）:7-12.LIANG Yan-chun，FENG 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]任紅燕，張文國.一種新的求解置換Flowshop問題的粒子群算法[J].計算機系統應用，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]周鵬.求解置換流水車間調度問題的混合蟻群算法[J].計算機工程與應用，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]葉紅權,郭益輝.粒子群算法在電力系統低頻振蕩辯識中的應用[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.