改進(jìn)的粒子群算法求解置換流水車(chē)間調(diào)度問(wèn)題

1、改進(jìn)的粒子群算法求解置換流水車(chē)間調(diào)度問(wèn)題摘要:針對(duì)置換流水車(chē)間調(diào)度問(wèn)題，提出了一種改進(jìn)的粒子群算法進(jìn)行求解。改進(jìn)算法引入了判斷粒子群早熟的方法，并在發(fā)現(xiàn)粒子群早熟后采用逆轉(zhuǎn)策略對(duì)種群最優(yōu)粒子進(jìn)行變異，利用模擬退火思想概率接收新的最優(yōu)粒子。種群最優(yōu)粒子的改變會(huì)引導(dǎo)粒子群跳出局部極值的約束，從而克服粒子群的早熟狀態(tài)。通過(guò)對(duì)置換流水車(chē)間調(diào)度問(wèn)題中car系列和rec系列部分基準(zhǔn)數(shù)據(jù)的測(cè)試，證明了該算法的有效性。關(guān)鍵詞:粒子群算法；多樣性；局部收斂；置換流水車(chē)間調(diào)度improved particle swarm optimization for permutation flowshop scheduli

2、ng problemzhang qi.liang1,2*，chen yong.sheng1，han bin21. college of electronic and information engineering,tongji university, shanghai 200331,china；2. college of electricity and information engineering, jiangsu university of science and technology, zhangjiagang jiangsu 215600, chinaabstract:to solve

3、 permutation flowshop scheduling problem, an improved particle swarm optimization was proposed. improved algorithm introduced a method to judge the prematurity state of the particle swarm, and used reversion strategy to mutate the best particle after the particle swarm being trapped in premature con

4、vergence, simulated annealing method was used to accept the new particle.the mutation for best particle can guide the particle swarm to escape from the local best values limit and overcome the particles premature stagnation.the simulation results based on car and recbenchmarks of permutation flowsho

5、p scheduling problem proved the effectiveness of the proposed algorithm.to solve permutation flowshop scheduling problem, an improved particle swarm optimization was proposed. improved algorithm introduced a method to judge the premature state of the particle swarm, and used reversion strategy to mu

6、tate the best particle after the particle swarm being trapped in premature convergence, and used simulated annealing method to accept the new particle. the mutation for best particle can guide the particle swarm to escape from the local best values limit and overcome the particles premature stagnati

7、on. the simulation results based on car and rec benchmarks of permutation flowshop scheduling problem prove the effectiveness of the proposed algorithm.key words:particle swarm optimization (pso); diversity; local convergence; permutation flowshop scheduling0 引言 置換流水車(chē)間調(diào)度問(wèn)題(permutation flowshop sched

8、uling problem，pfsp)是一類(lèi)經(jīng)典的加工調(diào)度問(wèn)題。該問(wèn)題通常被描述為n個(gè)工件在m臺(tái)不同的機(jī)器上加工，每個(gè)工件有m道工序，每道工序都要在不同的機(jī)器上加工，每個(gè)工件在機(jī)器上的加工順序相同，每臺(tái)機(jī)器一次在某一時(shí)刻只能加工一個(gè)工件，每臺(tái)機(jī)器加工的各工件順序相同。問(wèn)題中每個(gè)工件在每臺(tái)機(jī)器上加工的時(shí)間已知，問(wèn)題的目標(biāo)是求出工件加工順序，使得按照該加工順序加工各工件時(shí)所對(duì)應(yīng)的總完工時(shí)間cmax最小。當(dāng)m>2時(shí)，該問(wèn)題已被證明是np.難問(wèn)題1。解決pfsp的方法大致可以分為三類(lèi):一類(lèi)是精確方法，主要有列舉法、分支界定法、動(dòng)態(tài)規(guī)劃法；一類(lèi)是啟發(fā)式方法，主要有neh法；另一類(lèi)是智能優(yōu)化方法，主

9、要有遺傳算法(genetic algorithm,ga)、模擬退火(simulated annealing，sa)算法、蟻群算法、粒子群算法等。粒子群算法(particles swarm optimization,pso)是由kennedy和eberhart博士于1995年提出的一種基于群體的進(jìn)化算法2，算法原理源于對(duì)鳥(niǎo)群行為的仿真。同其他智能算法相比，粒子群算法簡(jiǎn)單、易實(shí)現(xiàn)，需要調(diào)整的參數(shù)較少，目前被廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其他領(lǐng)域3。但pso 算法存在的一個(gè)主要問(wèn)題是在優(yōu)化過(guò)程中易出現(xiàn)早熟收斂現(xiàn)象，導(dǎo)致粒子多樣性降低，易陷入局部最優(yōu)，難以尋找到全局最優(yōu)解。多種文獻(xiàn)

10、對(duì)粒子群算法進(jìn)行了改進(jìn)，并應(yīng)用到了流水車(chē)間調(diào)度問(wèn)題，取得了較好的成效。文獻(xiàn)4將粒子群算法與迭代貪心算法結(jié)合，利用迭代貪心算法中的作業(yè)毀壞和構(gòu)造操作對(duì)粒子進(jìn)行變異，降低群體發(fā)生早熟的可能;文獻(xiàn)5提出一種新的基于群體多樣性控制的pso 算法，算法使粒子在收縮狀態(tài)下充分搜索，在發(fā)散狀態(tài)下能夠飛離群體的聚集位置，不斷的收縮發(fā)散過(guò)程保證了群體能在較大的空間進(jìn)行搜索，減少了粒子群算法的早熟收斂現(xiàn)象;文獻(xiàn)6采用慣性權(quán)重線性遞減粒子群算法對(duì)置換流水車(chē)間調(diào)度問(wèn)題進(jìn)行了優(yōu)化，并針對(duì)提高求解置換流水車(chē)間調(diào)度問(wèn)題對(duì)粒子群慣性權(quán)重的取值、粒子群種群數(shù)量、粒子位置和速度的初始化以及粒子位置和速度的限制范圍等幾個(gè)方面展開(kāi)實(shí)

11、驗(yàn)研究;文獻(xiàn)7將粒子群算法與模擬退火算法相結(jié)合，避免粒子群算法出現(xiàn)早熟現(xiàn)象，并把結(jié)合后的算法應(yīng)用到求解流水車(chē)間調(diào)度問(wèn)題;文獻(xiàn)8采用混沌序列初始化粒子位置,以增強(qiáng)搜索多樣性，并在算法中嵌入有效判斷早熟停滯的方法，一旦檢測(cè)到早熟跡象，便隨機(jī)地選擇最優(yōu)解任意一維的分量值，用一個(gè)隨機(jī)值取代它，以擾亂粒子的當(dāng)前搜索軌跡，使其跳出局部最優(yōu)，克服了粒子群早熟收斂現(xiàn)象;文獻(xiàn)9通過(guò)分解搜索空間、對(duì)種群進(jìn)行變異、與模擬退火算法結(jié)合等方法，提出了可改變的進(jìn)化搜索算法(modified evolutionary programming,mep),并將算法應(yīng)用于pfsp，得到了較好的解。上述文獻(xiàn)對(duì)基于粒子群算法解決流水

12、車(chē)間調(diào)度問(wèn)題具有重要的借鑒意義。為了進(jìn)一步避免粒子群陷入局部最優(yōu)，提高算法的尋優(yōu)精度，本文在借鑒文獻(xiàn)8的基礎(chǔ)上，提出了一種控制粒子多樣性的方法。當(dāng)判斷粒子群趨于收斂時(shí)，對(duì)全局極值進(jìn)行變異，從而改變粒子的速度向量，導(dǎo)致粒子的尋優(yōu)軌跡發(fā)生變化，進(jìn)而跳出局部極值的約束。通過(guò)對(duì)流水車(chē)間調(diào)度問(wèn)題中部分car類(lèi)問(wèn)題和rec類(lèi)問(wèn)題的仿真實(shí)驗(yàn)表明：當(dāng)粒子群陷入局部最優(yōu)時(shí)，能通過(guò)該方法跳出局部極值的約束，算法尋找最優(yōu)解的能力要比一般的粒子群算法優(yōu)越，運(yùn)行效果令人滿意。2.3 粒子早熟判斷方法及改進(jìn)本文判斷粒子出現(xiàn)早熟的方法為：當(dāng)粒子的全局極值pg在連續(xù)g代后沒(méi)有改變或者改變很小但還不滿足終止條件時(shí)，認(rèn)為粒子已經(jīng)

13、處于暫時(shí)停滯狀態(tài)，粒子出現(xiàn)了早熟。當(dāng)粒子陷入局部最優(yōu)時(shí)，若無(wú)外力的作用其很難逃出局部極值的約束。為了使粒子能夠跳出局部極值，本文對(duì)能夠指導(dǎo)粒子群運(yùn)行方向的pg進(jìn)行變異，變異后粒子群會(huì)在新的pg的引導(dǎo)下改變方向，繼續(xù)尋找問(wèn)題最優(yōu)解，從而避免了粒子重復(fù)收斂于一點(diǎn)的現(xiàn)象。圖1為粒子群陷入局部最優(yōu)的情況，粒子都運(yùn)行在局部極值附近，在局部極值的約束下很難跳出。圖2為對(duì)pg進(jìn)行變異后的情況，pg由位置1跳變到位置2，粒子方向也隨著pg的改變而發(fā)生變化，從而跳出局部極值。經(jīng)過(guò)多次跳變，有利于提高尋優(yōu)速度和尋找到最優(yōu)解的可能。本文對(duì)pg采用逆轉(zhuǎn)策略進(jìn)行變異，在pg的n個(gè)加工工件中隨機(jī)產(chǎn)生兩個(gè)工件j1, j2,

14、假定j1<j2,將j2, j2-1,j1逆序插入到原來(lái)j1,j1+1,j2的位置，其余不變。假設(shè)pg所代表的工件加工序列為（2,6,4,1,5,7,3），隨機(jī)產(chǎn)生17之間的兩個(gè)數(shù)j1,j2,假定j1=2,j2=6,則變異之后pg所代表的工件加工序列為（2,7,5,1,4,6,3）。通過(guò)與標(biāo)準(zhǔn)粒子群算法以及文獻(xiàn)7和文獻(xiàn)9所提出的算法在car類(lèi)問(wèn)題和部分rec類(lèi)問(wèn)題中的求解，驗(yàn)證了本文所提出算法的有效性。本文算法的優(yōu)勢(shì)在于能夠控制粒子的多樣性，及早地使粒子跳出局部最優(yōu)解的約束，避免標(biāo)準(zhǔn)粒子群算法中的早熟現(xiàn)象。但是，由于增加了粒子的多樣性，粒子的收斂速度較慢，得到問(wèn)題最優(yōu)解時(shí)迭代次數(shù)較大。因此，減小算法的執(zhí)行時(shí)間，提高算法尋找到最優(yōu)解的概率將是進(jìn)一步研究的內(nèi)容。參考文獻(xiàn):1garey m r, johnson d s, sethi r. the complexity of flowshop and job shop chedulingj.mathematics of operations research,1976,1