改進的粒子群算法及遺傳算法在車間作業調度中應用的比較研究

摘 要：借鑒遺傳算法及粒子群優化算法的思想，提出了一種改進的粒子群算法，并將其應用于車間作業調度問題。根據車間作業調度的目標函數建立起算法數學模型，采用改進的粒子群算法對車間作業調度進行優化，得到目標的全局最優解。仿真示例說明改進的粒子群算法優化車間作業調度的最小化加工時間目標比遺傳算法明顯更有效。

關鍵詞：車間作業調度；粒子群算法；改進的粒子群算法；遺傳算法；交叉；變異

0 引言

Job Shop調度問題（Job- shop scheduling problem，簡稱JSSP）研究具有重要的理論意義和工程價值，是目前研究最廣泛的一類典型調度問題。粒子群優化（Particle Swarm Optimizer，簡稱PSO）算法是一種基于迭代的群智能演化優化工具，最早是由Kennedy J.和 Eberhart R.于1995年提出的，目前在函數優化、神經網絡訓練及模糊系統控制等領域得到較為廣泛的應用[1]。與遺傳算法比較，PSO的優勢在于沒有許多參數需要調整[2]，簡單容易實現。本文在PSOA的基礎上提出了一種改進的粒子群算法（Improve Particle Swarm Optimizer Algorithm，簡稱IPSOA），并將其應用到JSSP離散問題的優化中。

1 車間作業調度問題（Job-Shop Scheduling Problem，簡稱JSSP）

1.1 JSSP的描述

JSSP是組合優化問題中最困難的一類，調度目標是找到使用這些共同資源的一種排序，使生產約束被滿足，同時使生產成本最低。JSSP是在m臺不同機器上加工有特定加工工序和加工時間的n個工件。調度的目標就是確定各臺機器上工件的加工順序和每個工件在各臺機器上的起始加工時間，使加工完所有工件所需的時間最少。

1.2 JSSP的數學模型

典型的JSSP問題有多種描述形式，通常采用Adams[3]提出的數學模型。是工件的工序集合，M表示機器集合，A是工序的先后順序有序對集合，Em表示在機器m上加工的工序對集合，Pi表示第i道工序的加工時間，ti表示第i道工序的開始加工時間。JSSP可以表示為：

設工件j經過m道工序操作完成，且須按照給定的工序序列Oij（i=1，2，m，j=1，2，…，n）加工，即j工件的第i道工序在機器Oij上加工；

Tij（i=1，2，…，m，j=1，2，…，n）表示工件j的第i道工序的固定加工時間；C（k，j）表示工件j在機器k上的加工結束時間；Pij=find（Oj=i）為在工序矩陣Oij中，工件j在機器i上的工序。

n×m車間作業調度問題的完工時間表示如下：

即makespan為：

JSSP中優化的一個目標是找到一個可行調度方案，使得makespan最小。

2 算法

2.1 遺傳算法（Genetic Algorithm，GA）實現的基本方法[4]

采用遺傳算法來設計問題的求解方法，針對Job -Shop實際生產情況，具體設計環節如下：

（1）編碼方案

編碼方案采用整數編碼，5×5車間作業調度問題具體編碼如圖1所示。

評價函數）

適應度函數是評價個體位串的適應性，本文根據JSSP問題的調度目標采用makespan作為算法的適應度函數。

（3）遺傳算子

為了保證良好基因遺傳給下一代，選擇是從當前群體中選擇適應度值較優的個體來生成交配池，最基本的選擇方法是適應度值比例選擇。交叉操作是進化算法中遺傳算法具備的原始性的獨有特征，通常采用的遺傳算子包括一點、兩點和多點等交叉形式。變異可以確保群體的多樣性。

（4）初始化

初始化根據工件和工序數隨機產生初始種群，以這些染色體為初始點進行迭代。種群規模可以隨具體計算情況變化。

（5）終止循環的條件

采用最大代數的方法或算法的種群適應度平均值等于最優的運算結果則停止。

2.2 改進的粒子群算法

PSO算法是一種基于迭代的群智能演化優化工具，在優化過程中系統首先初始化為一組隨機解，然后通過迭代在解空間搜尋到最優值。目前在函數優化、神經網絡訓練及模糊系統控制等領域應用較為廣泛。本文提出了一種改進的粒子群算法（Improve Particle Swarm Optimization，簡稱 IPSO），該算法是在PSO算法中采用GA算法的交叉和變異操作，并將其應用于JSSP離散問題的優化。因PSO算法只適合解決連續問題的優化，所以用PSO算法來優化JSSP的關鍵是設計一種適合離散優化問題的有效機制。本文根據JSSP的特點提出了IPSO算法，具體設計如下：

（1）交叉和變異操作

交叉操作可分為：一段、二段、三段和四段交叉。一段交叉首先是在第一個父代中隨機選取兩個交叉點，然后把二交叉點間的工件序列復制到子代，最后在子代的其他位置依次用第二個父代的因子來代替。

Nearchou Ac在[5]中闡述了六種變異操作，對于不同規模的JSSP，最佳的變異操作方法是移動變異操作，該操作的工作原理是先隨機選取一個移動點和一個插入點，然后對工件系列進行移動。

（2）最小化加工時間的JSSP改進粒子群算法的迭代模式

假設在一個由m個粒子組成的D維搜索空間中，其中表示第i個粒子在D維搜索空間中的位置。是第i個粒子的飛行速度，是迄今為止第i個粒子搜索到的最佳位置，是迄今為止整個粒子群搜索到的最佳位置[6]。IPSO的遞推方程如下：

在（2-1）、（2-2）、（2-3）和（2-4）中，k為迭代代數，為粒子i在第k次迭代時飛行速度矢量的第d維分量；是粒子i在第k次迭代時位置矢量的第d維分量；是粒子i個體最優位置的第d維分量；為群體最優位置的第d維分量，顯然，和都是符號或者自然數；是交叉算子符號，代表兩個粒子或者速度進行交叉操作；，分別表示變異隨機選擇的速度和粒子，然后覆蓋原來相對應的速度和粒子，rN表示總共需要變異的速度與粒子總數。

（3）IPSO算法的步驟

步驟l：初始化迭代代數k=0，迭代終止代數Maxgen，產生規模為psize的初始種群，計算種群中各粒子的適應值，從種群中選出第一代中的最優粒子PgBest；

步驟2：用公式（2-1）得到2×psize個粒子，計算其適應值，從中選出適應值較小的psize個粒子作為速度，再隨機選擇rN個速度用公式（2-2）進行變異，然后覆蓋原來對應的速度。同理，利用公式（2-3）和（2-4）產生下一代粒子。判斷，若新種群中各粒子適應值低于個體歷史最低適應值，用新的最低粒子代替歷史適應值最低粒子個體PiBest，同樣判斷新種群中的粒子適應值若低于全局最優值，用現在的全局最優粒子代替粒子PgBest；若k=Maxgen，轉至步驟3，否則令k=k+1，轉至步驟2。

3 IPSO和GA優化JSSP的仿真結果

對10×10的車間作業調度問題采用遺傳算法和改進的粒子群算法進行調度，10個工件的加工工藝路線和加工時間如表1所示。

圖2是10×10 JSSP最優調度結果的甘特（Gantt）圖。

經過多次反復調試，在取進化代數為3 000、群體規模為30的情況下，采用IPSO算法和GA算法優化10×10 和20×5的JSSP典型例子，搜索最優解過程的收斂曲線比較圖如圖3所示。

圖3中a線和c線分別表示GA算法優化JSSP典型例子時平均值和最優值的收斂速度，b線和d線分別表示IPSO算法優化JSSP典型例子時平均值和最優值的收斂速度。收斂曲線圖的橫坐標表示進化代數，縱坐標表示適應度。

4 結語

IPSO算法是基于PSO算法的思想，它們迭代方程不同，但信息來源相似，有用的信息都是主要來自個體歷史最優粒子和全局最優粒子。IPSO算法相比PSO算法迭代方程添加了類似于GA的交叉和變異操作，即增加了粒子種群的多樣性。在IPSO算法與GA算法中種群都是隨機產生的，種群中的粒子是通過適應值進行評估的。GA更新種群是隨機選擇的染色體進行交叉和變異操作，基本PSO算法的粒子更新是基于權重的合并，IPSO算法采用了類似于GA中的交叉和變異操作，通過PiBest和PgBest信息共享來進行種群更新的。IPSO算法與GA相比，更易于搜索到全局最優值。仿真算例說明IPSO算法用于優化JSSP的最小Makespan目標相比GA更為有效。

參考文獻

[1]潘全科，孫志峻，朱儉英.基于遺傳算法在車間作業高度優化[J].信息與控制，2003，31（3）：216-218.

[2]Nearchou AC.The effect of various operators on the genetic search for large scheduling problems[J].International journal of production economics，2004，（88）：191-203.

[3]陳群賢.近似粒子群算法在Flow-shop調度中的應用.上海電機學院學報，2006，9（2）：16-18.