基于MAZAK 柔性制造線的粒子群與免疫算法研究?

張 利，孟祥凱，劉文生

（武漢輕工大學(xué) 機(jī)械工程學(xué)院，湖北 武漢 430023）

1 車(chē)間調(diào)度優(yōu)化問(wèn)題的描述

車(chē)間調(diào)度優(yōu)化問(wèn)題可描述為：有n個(gè)工件在m臺(tái)機(jī)器上加工，在已有的工序要求下，在工件的加工順序及時(shí)間給定的條件下，將n個(gè)工件在機(jī)器上排序，使得生產(chǎn)周期與加工時(shí)間最短、最優(yōu)［1］。

由于日本MAZAK柔性制造生產(chǎn)線在現(xiàn)代制造業(yè)中得到了較廣泛的應(yīng)用，因此本文將智能算法中的克隆免疫遺傳算法和粒子群算法運(yùn)用在生產(chǎn)調(diào)度中，以提高生產(chǎn)效率，且可得到比較直觀的仿真結(jié)果［2］。

2 免疫遺傳算法的優(yōu)化過(guò)程

免疫算法所求解的問(wèn)題即抗原，首先提取抗原中的特征信息——疫苗；然后對(duì)疫苗處理將其轉(zhuǎn)變?yōu)榍蠼鈫?wèn)題方案；再將這個(gè)方案轉(zhuǎn)變成免疫算子來(lái)具體操作，抗原所提取的疫苗有多個(gè)，可將其進(jìn)行組合后再注射。在提取疫苗的過(guò)程中，通過(guò)接種疫苗來(lái)提高適應(yīng)度，而免疫選擇則是為了防止種群退化。

2.1 免疫遺傳算法接種疫苗［3］

設(shè)種群c＝（m1，…，），則對(duì)c種群接種的疫苗就是按比例λ（0＜λ≤1）得到的qλ＝λq個(gè)個(gè)體的變異，qλ為總的種群數(shù)量，疫苗是特定的特征信息。

2.2 免疫遺傳算法免疫選擇

圖1 免疫遺傳算法基本流程

3 粒子群算法的優(yōu)化過(guò)程

粒子群算法（Particle Swarm Optimization，PSO）是由美國(guó)的Kennedy博士和Eberhar博士于1995年提出的一種基于群智能的進(jìn)化算法。在粒子群的優(yōu)化算法當(dāng)中，粒子在一個(gè)n維的空間上搜索時(shí)，每個(gè)粒子的位置是一個(gè)所要解答的問(wèn)題的解，它持續(xù)地調(diào)整自己所處的位置來(lái)進(jìn)行解的優(yōu)化。本文中，第d維第i個(gè)粒子所處的位置用Xid來(lái)表示，用Pid表示粒子群中粒子搜索到的解，用Pgd表示所有的粒子所經(jīng)歷的最好位置［5］，用表示粒子群的速度。因此，第d維的第i個(gè)粒子在某一時(shí)刻的速度為：

其中：ω為權(quán)重；η1，η2為粒子當(dāng)中兩個(gè)解的參數(shù)值；rand（）為隨機(jī)生成的函數(shù)值。因此，由式（1）可以得到粒子群下一代的位置為：

重新構(gòu)造下一位置X′id的粒子速度V′id，其中粒子移動(dòng)的算式為：

其中：α與β為隨機(jī)數(shù)，α，β∈［0，1］。交換序列（Xid→Pid）以概率α保留，基本的工序操作為α（Xid→Pid）；同樣地，交換序列（Xid→Pgd）以概率β保留，基本操作由β（Xid→Pgd）表示［6］。從式（2）、式（3）當(dāng)中可以看出，它們是PSO算法求解的主要算子，并且在式子當(dāng)中，α的值對(duì)局部最優(yōu)移動(dòng)的影響很大，當(dāng)其增大時(shí)，粒子位置Pid也開(kāi)始向最優(yōu)解移動(dòng)；同樣，β的值對(duì)局部的影響也很大，當(dāng)其越大，對(duì)粒子位置Pgd的影響就越大。圖2為粒子群算法的調(diào)度過(guò)程。

4 實(shí)驗(yàn)仿真與結(jié)果分析

本文采用經(jīng)典的10/10/G/Cmax的Job shop調(diào)度問(wèn)題，通過(guò)仿真得到求解結(jié)果，并確定是否是最優(yōu)的結(jié)果。

圖2 粒子群算法的調(diào)度過(guò)程

4.1 免疫遺傳算法仿真分析

克隆免疫遺傳算法繼承了遺傳算法的高度并行迭代模式［7］，采用原始克隆免疫算法的基本參數(shù)數(shù)據(jù)如下：初始抗體數(shù)為60，替換抗體為350，克隆選擇概率0.8，克隆細(xì)胞數(shù)80，迭代次數(shù)70。

在MATLAB 2013a下得到的免疫遺傳算法的調(diào)度仿真加工曲線為圖3～圖5所示。

圖3 免疫遺傳算法最優(yōu)完成時(shí)間變化曲線

圖4 免疫遺傳算法親和度曲線

圖5 免疫遺傳算法加工時(shí)間曲線

圖3為免疫遺傳算法最優(yōu)完成時(shí)間變化曲線，可以看到，在迭代過(guò)程中隨著迭代次數(shù)增加響應(yīng)時(shí)間持續(xù)下降，最后恒定。圖4為免疫遺傳算法親和度曲線，親和度的變化不是恒定的，而是上下波動(dòng)的。圖5為免疫遺傳算法加工時(shí)間曲線，它呈現(xiàn)與迭代次數(shù)有關(guān)的上下波動(dòng)，其中迭代次數(shù)在20～40之間是最好的。

對(duì)10個(gè)工件、10臺(tái)機(jī)器進(jìn)行作業(yè)調(diào)度，每個(gè)工件分別在10臺(tái)機(jī)器上各加工一次，由免疫遺傳算法得到的調(diào)度甘特圖見(jiàn)圖6。

圖6 免疫遺傳算法調(diào)度甘特圖

4.2 粒子群算法仿真分析

通過(guò)對(duì)10個(gè)工件、10臺(tái)機(jī)器進(jìn)行作業(yè)調(diào)度，每個(gè)工件分別在10臺(tái)機(jī)器上各加工一次，每個(gè)工件的加工路線與每道工序?qū)?yīng)的加工時(shí)間T與機(jī)器Js矩陣如下：

由粒子群算法得到的調(diào)度甘特圖如圖7所示。對(duì)比圖6與圖7可以看出，兩圖的調(diào)度順序完全不同，其中粒子群算法最優(yōu)完成時(shí)間為1 128s，而免疫算法的調(diào)度最優(yōu)完成時(shí)間為1 306s，遠(yuǎn)遠(yuǎn)地大于粒子群調(diào)度算法的最優(yōu)調(diào)度時(shí)間。由此可以看出在柔性生產(chǎn)調(diào)度中粒子群算法優(yōu)于免疫遺傳算法。

圖7 粒子群算法調(diào)度甘特圖

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

本文以日本MAZAK柔性生產(chǎn)線為基礎(chǔ)，通過(guò)對(duì)兩種算法的仿真比較分析，可以得到較為優(yōu)秀的調(diào)度值。從兩種算法的對(duì)比中可以看到，粒子群算法要優(yōu)于免疫遺傳算法調(diào)度，得到解的時(shí)間也相對(duì)較短。在今后的作業(yè)調(diào)度中，智能化調(diào)度將會(huì)得到更加廣泛的應(yīng)用。

［1］于穎，李永生，樸孝春.粒子群算法在工程優(yōu)化設(shè)計(jì)中的應(yīng)用［J］.機(jī)械工程學(xué)報(bào)，2008，44（12）：226－231.

［2］宋曉宇，曹陽(yáng)，孟秋宏.求解Job Shop調(diào)度問(wèn)題的粒子群算法研究［J］.系統(tǒng)工程與電子技術(shù)，2008，30（12）：2398－2401.

［3］王凌.車(chē)間調(diào)度及其遺傳算法［M］.北京：清華大學(xué)出版社，2003.

［4］Rui Zhang，Shiji Song，Cheng Wu.A two－stage hybrid particle swarm optimization algorithm for the stochastic job shop scheduling problem ［J］. Knowledge－Based Systems，2012，27：393－406.

［5］李小華，熊禾根.基于粒子群算法的車(chē)間作業(yè)調(diào)度問(wèn)題［J］.信息技術(shù)，2009（7）：19－21.

［6］何利，劉永賢，謝華龍.基于粒子群算法的車(chē)間調(diào)度與優(yōu)化［J］.東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，29（4）：555－568.

［7］Sha D Y，Lin Hsing－Hung.A multi objective PSO for job－shop scheduling problems［J］.Expert Systems with Applications，2009（6）：1065－1070.