秦志偉

摘 要：針對(duì)協(xié)同粒子群算法容易早熟和停滯的問題，提出了一種基于精英綜合學(xué)習(xí)的協(xié)同粒子群（ECLCPSO）算法。該算法在協(xié)同粒子群算法的基礎(chǔ)上，采用精英庫種群和普通種群并行協(xié)同進(jìn)化架構(gòu)。精英庫種群由高適應(yīng)度個(gè)體構(gòu)成，進(jìn)行自我綜合學(xué)習(xí)，普通種群中個(gè)體向精英庫種群進(jìn)行精英學(xué)習(xí)。為了避免算法陷入局部最優(yōu)，引入了擾動(dòng)機(jī)制。將該算法應(yīng)用于Flow shop調(diào)度問題上，和另外三種優(yōu)化算法進(jìn)行比較，仿真結(jié)果證明改進(jìn)的算法收斂速度快且精度高，優(yōu)化性能較好。

關(guān)鍵詞：協(xié)同；粒子群；精英學(xué)習(xí)；流水車間調(diào)度

1 引言

當(dāng)今的制造技術(shù)正由自動(dòng)化、數(shù)字化、網(wǎng)絡(luò)化向智能化方向發(fā)展，智能制造（Intelligent Manufacturing，IM）被工業(yè)界和學(xué)術(shù)界普遍認(rèn)為代表了制造業(yè)的發(fā)展方向，隨之帶來的智能調(diào)度問題成為研究的熱點(diǎn)。特別是工業(yè)4.0的提出，使得智能調(diào)度在智能制造中的智能工廠和智能物流兩方面扮演著核心大腦的角色，是智能制造的基礎(chǔ)。而流水車間調(diào)度問題（Flow Shop Scheduling Problem，F(xiàn)SSP），作為許多實(shí)際流水線上的簡(jiǎn)化模型，它已被是一個(gè)典型的NP-hard問題1[1]，因此其研究具有重要的理論意義和工程意義。

雖然協(xié)同粒子群算法可以有效地改善傳統(tǒng)算法效率低、魯棒性差的問題，但容易陷入局部極值。由此，本文以確定型無限中間存儲(chǔ)方式的流水車間作為研究對(duì)象，并以整個(gè)流水車間工件的加工時(shí)間Makespan為目標(biāo)函數(shù)，在將精英策略和綜合學(xué)習(xí)策略有效地結(jié)合一起，并引入擾動(dòng)機(jī)制，來改進(jìn)協(xié)同粒子群算法，提高協(xié)同粒子群算法的收斂速度和精度。

2 數(shù)學(xué)描述

本文以流水車間工件加工時(shí)間 Makespan為目標(biāo)函數(shù)。Makespan可以描述為從第一個(gè)加工工件開始加工到最后一個(gè)工件完工所經(jīng)歷的時(shí)間，問題具體描述如下：

一個(gè)n x m的確定型流水車間調(diào)度問題就是n個(gè)工件在n臺(tái)機(jī)器上流水加工的過程，假設(shè)工件按機(jī)器1～m的順序依次加工，令tij表示工件i在機(jī)器j上的加工時(shí)間，Cij表示工件i在機(jī)器j上的加工完成時(shí)間，Cmax表示所有工件加工完成時(shí)間，即Makespan。任給一個(gè)調(diào)度方案，即工件的加工排序，按照工件加工的次序，任意工件ik在機(jī)器j上的完成時(shí)間可以分為以下3種情況：[2]

，

上述模型即是FSSP優(yōu)化的一個(gè)目標(biāo)，可以看出，流水車間調(diào)度問題就是尋找一種可行的調(diào)度方案，使得加工周期最小，也就是說，求解最小的makespan。

3 精英綜合學(xué)習(xí)的協(xié)同粒子群算法流程

Step 1 初始化。確定m和n的數(shù)量，m是加工機(jī)器的數(shù)量，n是工件的數(shù)量，設(shè)定算法的協(xié)同種群個(gè)數(shù)、初始的子群粒子位置及速率，將粒子的個(gè)體最優(yōu)位置設(shè)置為粒子的當(dāng)前位置，隨機(jī)選擇一個(gè)粒子作為種群最優(yōu)位置。

Step 2 按照適應(yīng)度大小對(duì)每個(gè)子群粒子的適應(yīng)值進(jìn)行升序排序。

Step 3 根據(jù)Pareto 的精英理論中的 80 /20 法則選擇每個(gè)子群的20%個(gè)體組建精英庫種群。

Step 4 對(duì)于精英庫種群，每個(gè)個(gè)體隨機(jī)地向精英庫種群中的其他兩個(gè)個(gè)體學(xué)習(xí)，取適應(yīng)度好的就更新當(dāng)前個(gè)體。

Step 5 對(duì)于普通種群，每個(gè)個(gè)體都可以通過隨機(jī)地向精英庫種群中的某個(gè)個(gè)體學(xué)習(xí)，若適應(yīng)度得到改善就更新當(dāng)前個(gè)體。

Step 6 判斷 t-tn是否大于擾動(dòng)因子n。若是，則重置粒子速率；否則繼續(xù)。

Step 7 重復(fù) step 2～step 7，確定各粒子應(yīng)選擇的 pbest值。

Step 8 更新迭代次數(shù)，若還在迭代范圍內(nèi)，則轉(zhuǎn)到步驟step 2；否則，停止更新。

Step 9 輸出整個(gè)粒子群（包括精英庫種群）的全局最優(yōu)適應(yīng)度，算法運(yùn)行結(jié)束。

4 仿真結(jié)果及分析

本文采用的編碼是實(shí)數(shù)編碼轉(zhuǎn)換為自然數(shù)編碼的策略。將一個(gè)隨機(jī)的粒子按照權(quán)重分量升序排列得到對(duì)應(yīng)的新粒子序列，而新粒子序列所對(duì)應(yīng)于原粒子的位置就可以組合成一個(gè)新的自然數(shù)序列。

取劃分因子為5，慣性權(quán)重ω=0.4，學(xué)習(xí)因子c1=c2=2，自主學(xué)習(xí)概率Pc=0.3，擾動(dòng)因子n=150，種群規(guī)模popsize=150。分別將每種算法運(yùn)行10次。

圖1中可以看出，對(duì)于確定型流水車間調(diào)度問題，無論在搜索最優(yōu)值上還是收斂速度上，GA、PSO、CPSO的結(jié)果都沒有ECLCPSO好，這說明 ECLCPSO求解Flow shop問題的有效性。

5 結(jié)論

本文研究了Flow Shop調(diào)度問題，以工件的加工時(shí)間Makespan為目標(biāo)函數(shù)。針對(duì)協(xié)同粒子群優(yōu)化算法（CPSO） 容易早熟和停滯的問題的缺陷，本文提出一種精英綜合學(xué)習(xí)的協(xié)同粒子群算法（ECLCPSO）。該算法在 CPSO 算法的基礎(chǔ)上，將精英策略和綜合學(xué)習(xí)策略有效地結(jié)合一起，組成了新的學(xué)習(xí)機(jī)制，并引入了擾動(dòng)機(jī)制，將其通過與GA、PSO、CPSO進(jìn)行仿真比較分析，仿真結(jié)果表明改進(jìn)的算法收斂速度快且精度高，優(yōu)化性能好，驗(yàn)證了其解決Flow shop問題的有效性。

參考文獻(xiàn)

[1]王凌.車間調(diào)度及其遺傳算法[M].清華大學(xué)出版社，2003（05）：109-110

[2]張順，徐震浩，顧幸生.用改進(jìn)的協(xié)同免疫算法求解FlowShop調(diào)度問題[J].東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，42（s1）：157-162.