車間生產調度優化中改進微粒群算法的應用

徐海波，仲梁維，龔文露

（上海理工大學 機械工程學院，上海 200093）

0 引言

作業車間調度問題（Job-shop scheduling problem，JSP）通常理解為運用多臺機器進行生產加工，加工包含多個工件，每個工件又包含多道工序，同時每道工序在指定的機器上進行加工。在過去相當長的時間中，算法得到了充分的研究，涌現出了不同的算法與理論，如人工神經網絡與模擬退火算法等等。不過由于算法各自的缺陷以及車間生產作業調度的復雜性，標準的算法很難滿足求解的需求。為充分發揮各種算法的優勢，取長補短，將算法進行有效地結合，可以大大提高算法的求解效率，因而混合算法應運而生，成為算法優化的一大亮點。

1 混合微粒群（PSO）算法設計

1.1 改進的微粒群算法原理

微粒通過跟蹤個體極值Pbesti（微粒本身所找到的最優解）和全局極值Pgbest（整個種群目前找到的最優解）來不斷更新自己的速度和位置，更新公式如下：

其中：vk為微粒的速度向量；k為迭代次數；xk為當前微粒的位置；w為慣性權重，決定了對微粒當前速度的繼承，w一般取（0，1）之間的隨機數；c1、c2表示群體的認知系數，使微粒具有自我總結和向群體中優秀個體學習的能力，c1、c2取（0，2）之間的隨機數；r1和r2為（0，1）之間的均勻分布的隨機數。

1.2 改進的PSO算法設計策略

微粒群算法最初用于求解連續性優化問題，具有較好的全局收斂性。不過在求解離散組合優化問題時，往往具有參數敏感、收斂速度慢等特性，因此需要對混合PSO算法做如下改進：

（1）PSO算法對于初始解具有較強的魯棒性，是因為PSO算法具有很好的全局收斂性。但在實際生產中，由于優化模型的復雜程度大小不一，這就導致了算法的收斂對初始解具有很大的依賴。本文提出優化選擇機制，既保證了初始解的多樣性，又提高了算法的收斂性能。

（2）標準PSO算法中通常采用基于編碼點的交叉方式，在復雜JSP中具有較慢的收斂速度。本文提出了一種遺傳算法的整段交叉思想，在一定范圍內提高了收斂速度。同時為了避免PSO算法因收斂速度過快而產生早熟現象，本文提出了一種遺傳算法的變異思想。結合遺傳算法的變異和交叉思想很好地提高了算法的收斂性。

（3）為保證種群全局最優解和自身最優解的突跳性，以及算法能跳出全局最優，混合微粒群算法采用模擬退火算法的Metropolis抽樣準則來作為設定全局最優解與自身最優解的接受準則。

（4）本文的混合PSO算法以機器加工時間最小為優化目標。采用優化選擇機制，將目標適應度值按從小到大的順序排序，并按照該順序選擇出種群。

1.3 混合PSO算法種群變異設計

混合PSO算法粒子的位置更新涉及每個粒子的歷史最好位置Pbesti、群體當前最好位置Pgbest和平均最優值Mbest，運用遺傳算法的變異和交叉操作，其表達式如圖1所示。

圖1 變異及交叉圖

變異操作：假設父代向量為x，隨機產生2個交換點i和j，交換向量x位于交換點i和j上的元素，其他元素不變。

交叉操作：假設父代向量為x和y，經過交叉操作產生子代向量z。首先，隨機產生2個交換點i和j，將向量x位于交換點i和j之間的元素復制到向量z的相應位置；其次將向量x上其余元素按照它們在向量y上出現的先后順序依次填入向量z的位置。粒子的位置更新流程如圖2所示。

1.4 模擬退火操作

混合PSO算法在標準PSO算法的基礎上引入模擬退火操作的Metropolis抽樣準則，參照目標函數，比較微粒與微粒自身最優解之間的適應度的大小，按照Metropolis抽樣準則接受比微粒自身最優解大的解，使自身最優解具有一定的突跳性。

圖2 微粒位置更新流程圖

2 混合PSO算法的求解流程

結合混合PSO算法的求解過程，給出混合PSO算法的求解流程圖，如圖3所示。

圖3 混合PSO算法求解流程

圖3中，Pbesti（t）表示微粒i經過t次迭代后相對目標函數適應度最小的一代微粒；Pgbest（t）表示t次迭代后所有微粒中相對目標函數適應度最優的微粒；xi（t）表示微粒i經過t次迭代時的微粒。

3 混合PSO求解實例

3.1 對FT06問題的求解

求解種群為10個粒子，計算代數為1 500代，連續計算20次，通過MATLAB 7.0軟件求解，結果顯示混合PSO能很好地解決FT06問題，它能9次取得其最優解55，其余解大多都很接近最優解55，而且平均用時達到6s左右，收斂速度比標準PSO快。

3.2 對LA01問題求解

求解種群為50個粒子，計算代數為1 500代，連續計算20次，通過MATLAB 7.0軟件求解，結果顯示混合PSO能很好地解決LA01問題，混合PSO算法求解20次中有15次取得最優解666，平均收斂代數為550，平均用時達到55s左右，收斂速度比標準PSO快。

4 結語

本文采用優化選擇機制，同時引入模擬退火算法中的Metropolis抽樣準則，使算法能跳出全局最優，并具有一定的突跳性；引入遺傳算法的交叉變異操作，提高了算法的收斂速度，也避免了早熟現象，使微粒更好地向全局最優與自身最優靠近；取長補短，提出了一種混合PSO算法。實例驗證混合PSO算法在求解車間生產作業問題中具有一定的收斂性和有效性。

［1］Wang H.Flexible flow shop scheduling：optimum，heuristics and artificial intelligence solutions［J］.Expert Systems，2005，22（2）：78-85.

［2］王萬良，吳啟迪.生產調度智能算法及其應用［M］.北京：科學出版社，2007.

［3］吳大為，陸濤棟，劉曉冰，等.求解作業車間調度問題的并行模擬退火算法［J］.計算機集成制造系統，2005，11（6）：847-850.

［4］王萬良，吳啟迪，宋毅.求解作業車間調度問題的改進自適應遺傳算法［J］.系統工程理論與實踐，2004（2）：58-62.

［5］玄光男，程潤偉.遺傳算法與工程設計［M］.北京：科學出版社，2000.

［6］周明，孫樹棟.遺傳算法原理及應用［M］.北京：國防工業出版社，1999.

［7］潘全科，朱劍英.一類解決作業車間調度問題的遺傳退火算法［J］.聊城大學學報，2005，18（1）：20-23.

［8］Reeves C.A genetic algorithm for flow shop sequencing［J］.Computers and Operations Research，1995，22（1）：5-13.