陶文華，劉洪濤

(遼寧石油化工大學(xué) 信息與控制工程學(xué)院,遼寧 撫順 113001)

?

·信息科學(xué)·

一種混合算法在焦?fàn)t推焦計(jì)劃調(diào)度中的應(yīng)用

陶文華，劉洪濤

(遼寧石油化工大學(xué) 信息與控制工程學(xué)院,遼寧 撫順 113001)

焦?fàn)t推焦計(jì)劃安排依靠人工經(jīng)驗(yàn)法不但缺乏智能性而且準(zhǔn)確度低，文中建立了具有TSP(旅行商問(wèn)題)性質(zhì)的推焦計(jì)劃調(diào)度模型。提出一種差分進(jìn)化算法和蟻群算法的混合算法(HDE-ACO)。HDE-ACO的基本思想是利用差分進(jìn)化算法對(duì)蟻群算法的3個(gè)主要參數(shù)進(jìn)行優(yōu)化，解決蟻群算法對(duì)參數(shù)變化敏感的困難,從而提高蟻群算法尋優(yōu)精度。將HDE-ACO與其他幾種算法對(duì)多個(gè)不同的TSP進(jìn)行測(cè)試比較,結(jié)果表明HDE-ACO不僅尋優(yōu)能力強(qiáng)而且收斂速度快。最后,將HDE-ACO應(yīng)用到推焦計(jì)劃調(diào)度中，對(duì)推焦計(jì)劃調(diào)度的優(yōu)化進(jìn)行研究。

推焦計(jì)劃調(diào)度;TSP;差分進(jìn)化;蟻群算法

焦?fàn)t推焦在正常工況下運(yùn)行時(shí)往往要受到許多因素干擾，推焦計(jì)劃的合理調(diào)度能夠減少生產(chǎn)延時(shí),增加企業(yè)產(chǎn)量,提高產(chǎn)品質(zhì)量。焦?fàn)t推焦計(jì)劃調(diào)度與旅行商問(wèn)題(travelling salesman problem,TSP)有很多相似之處,可以將其歸為TSP。隨著計(jì)算機(jī)技術(shù)的不斷進(jìn)步,為TSP的求解提供了很多近代智能進(jìn)化和仿生算法,例如遺傳算法[1]、蟻群算法[2-3]、人工蜂群算法[4]、量子啟發(fā)式算法[5]、布谷鳥(niǎo)搜索算法[6]等等。

蟻群算法(ant colony optimization,ACO)被證明用來(lái)求解TSP有很好的實(shí)驗(yàn)效果。1996年M. Dorigo首先將ACO應(yīng)用到TSP[7]。ACO采用正反饋機(jī)制,隨著多數(shù)螞蟻在某條路徑上留下信息素濃度的不斷增大,后來(lái)的螞蟻選擇該路徑的概率也會(huì)增高,從而加強(qiáng)了該路徑的信息素濃度。每個(gè)螞蟻在獨(dú)立完成路徑尋優(yōu)的同時(shí),螞蟻之間不斷進(jìn)行信息交流和傳遞,避免個(gè)體陷入局部最優(yōu),保證了全局最優(yōu)性。但ACO對(duì)參數(shù)非常敏感,單純依靠人工經(jīng)驗(yàn)調(diào)整不僅效率低下而且缺乏智能性。為此可以采用一種有效的算法對(duì)ACO的參數(shù)進(jìn)行優(yōu)化處理。

差分進(jìn)化算法 (differential evolution, DE)由美國(guó)Berkeley大學(xué)的Storn和Price于1955年提出[8]。DE采用實(shí)數(shù)編碼,有全局搜索能力,簡(jiǎn)單易行。其特有的記憶種群最優(yōu)解的能力使得算法具有較好的魯棒性和較強(qiáng)的收斂性。DE在許多領(lǐng)域得到應(yīng)用研究,如路徑規(guī)劃[9]、化工生產(chǎn)[10]、圖像處理[11]等。DE非常適合解決復(fù)雜非線性優(yōu)化問(wèn)題,所以文中使用DE對(duì)ACO參數(shù)進(jìn)行優(yōu)化。

現(xiàn)有的推焦計(jì)劃調(diào)度主要采用攆爐法和丟爐法,這兩種方法都是依靠人工經(jīng)驗(yàn)安排推焦順序，缺乏智能性和準(zhǔn)確性。鑒于此,本文建立推焦計(jì)劃調(diào)度模型，提出一種DE和ACO的混合算法，并將其應(yīng)用到推焦計(jì)劃調(diào)度中，經(jīng)過(guò)大量實(shí)驗(yàn)證明本文算法有很好的尋優(yōu)效果。

1 焦?fàn)t推焦計(jì)劃調(diào)度模型

TSP的數(shù)學(xué)描述:一個(gè)城市集合Q={c1,c2,…,cm}，其中每?jī)蓚€(gè)城市之間的距離為d(ci,cj)∈R+。一個(gè)旅行商經(jīng)過(guò)Q中每個(gè)城市一次的路線為R=(q1,q2，…，qi,…,qm)(qi為Q中第i個(gè)城市)，使得整個(gè)路線一周的距離最小,目標(biāo)函數(shù)為

(1)

推焦順序通常表示為a-b串序,a代表相鄰兩次推焦間隔的爐孔數(shù)目，b代表兩趟簽號(hào)對(duì)應(yīng)爐孔間隔的整數(shù)。目前,世界上主要包括5-2，9-2，2-1推焦串序,我國(guó)主要采用5-2式和9-2式。相比而言,5-2式機(jī)械行程較短。本文以2×42孔JN43-80型焦?fàn)t為例,采用5-2推焦串序,其編排順序如下:

1排簽:1,6,11,16,21,26,31,36,41,46,51,56,61,66,71,76,81；

3排簽:3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78,83；

5排簽:5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80；

2排簽:2,7,12,17,22,27,32,37,42,47,52,57,62,67,72,77,82；

4排簽:4,9,14,19,24,29,34,39,44,49,54,59,64,69,74,79,84。

正常情況下,推焦計(jì)劃會(huì)按照以上順序有條不紊的進(jìn)行。由于爐內(nèi)外存在多種干擾因素，會(huì)出現(xiàn)多種異常狀況,例如亂箋、事故影響、病號(hào)爐等。為了保證產(chǎn)品的質(zhì)量、產(chǎn)量以及減少機(jī)械損失,需要建立一個(gè)實(shí)用有效的推焦計(jì)劃調(diào)度模型。

1) 推焦過(guò)程中相鄰爐孔順序錯(cuò)亂引起懲罰:

Pi,j=Xi,jwi,j,

(2)

(3)

式中,i,j=0,1,…n，表示相鄰?fù)平範(fàn)t孔代數(shù)，且i≠j;wi,j為懲罰權(quán)值,根據(jù)推焦編排順序其值依次增大,例如,w1,11=3,w1,16=4,…,w1,84=84;n是爐孔總數(shù)目。

2) 沒(méi)有在規(guī)定時(shí)間出焦引起的懲罰:

Ji=exp(θYi)-1,

(4)

(5)

式中,θ∈(0,1)是爐體損壞和焦炭質(zhì)量影響因子;χ,γ分別表示提前出焦和延遲出焦時(shí)間影響因子,提前出焦對(duì)爐體損壞和焦炭質(zhì)量影響程度要比延遲出焦大,所以χ>1,0<γ<1;ti為第i個(gè)爐孔的計(jì)劃出焦時(shí)間,與標(biāo)準(zhǔn)出焦時(shí)間差值不大于15min;tmax和tmin分別為標(biāo)準(zhǔn)出焦時(shí)間的最大值和最小值。

3) 相鄰爐孔順序錯(cuò)亂和未按規(guī)定時(shí)間出焦引起的總懲罰:

fi,j=Pi,j+Ji+Yj。

(6)

綜上所述,在一個(gè)完整的周轉(zhuǎn)時(shí)間內(nèi)，完成所有爐孔的推焦要保證整個(gè)推焦系統(tǒng)的總懲罰最小，推焦計(jì)劃調(diào)度目標(biāo)函數(shù)為

(7)

通過(guò)比較式(1)和式(7)發(fā)現(xiàn)，推焦計(jì)劃調(diào)度問(wèn)題和TSP非常相似。區(qū)別在于TSP計(jì)算整個(gè)路線一周距離，包含路徑列表中起點(diǎn)和終點(diǎn)的距離，而推焦計(jì)劃調(diào)度問(wèn)題不計(jì)算推焦順序中始、末爐孔的懲罰。每個(gè)爐孔可以比作TSP中的每個(gè)城市,兩爐孔之間的懲罰比作TSP中兩城市之間的距離,本文將推焦計(jì)劃調(diào)度問(wèn)題轉(zhuǎn)換為TSP求解。

2 混合優(yōu)化算法

2.1 蟻群算法(ACO)

(8)

螞蟻在(i,j)之間會(huì)留下一定量的信息素,當(dāng)所有螞蟻遍歷完所有城市時(shí)，要進(jìn)行城市間信息素的更新。然而,為了減少蟻群算法被調(diào)用的次數(shù),本文采用全局異步特性與精英策略相結(jié)合的信息素更新方式。

全局異步信息素更新是指蟻群算法每一次被調(diào)用時(shí)，信息素不清零,并且每代迭代時(shí),當(dāng)本代解優(yōu)于上一代最優(yōu)解時(shí)進(jìn)行更新,否則不進(jìn)行更新。全局異步信息素更新規(guī)則為

(9)

(10)

(11)

式中,ρ∈(0,1)表示信息素的揮發(fā)程度;T為蟻群進(jìn)化迭代次數(shù);Lk(T)表示第k只螞蟻第T次迭代路徑長(zhǎng)度;Lbest(T-1)表示第T-1代全局最優(yōu)值;Q是信息素總量，為常數(shù)。

精英策略信息素更新是指對(duì)本次迭代全局最優(yōu)路線中的信息素更新,這種策略能使本代最優(yōu)路線進(jìn)入下一代。精英策略信息素更新規(guī)則為

(12)

綜上,全局異步特性與精英策略相結(jié)合的信息素更新公式為

(13)

ACO計(jì)算步驟如下:

Step1 ACO參數(shù)初始化。確定參數(shù)α,β,ρ,m,n以及最大迭代次數(shù)Tmax。給定T=1,k=1。初始化信息素矩陣Tau和禁忌表tabuk。

Step2 計(jì)算每?jī)蓚€(gè)城市之間的距離d(i,j),(0

Step3 根據(jù)當(dāng)前時(shí)刻的tabuk確定第k只螞蟻的位置,按照式(8)和當(dāng)前時(shí)刻的allowedk選擇下一個(gè)城市。

Step4 下一時(shí)刻更新第k只螞蟻的禁忌表tabuk和允許訪問(wèn)的路徑表allowedk。

Step5 如果k≤m,則k=k+1，返回到Step3。否則，執(zhí)行下一步。

Step6 按照式(13)更新信息素矩陣Tau。

Step7 如果T≤Tmax,則T=T+1，返回到Step3。反之,則輸出計(jì)算結(jié)果。

2.2 DE種群初始化

(14)

式中,pi,j表示第i個(gè)個(gè)體的第j維變量值;hj和lj分別為j維變量的搜索上下界,rand為0～1之間均勻分布的隨機(jī)數(shù)。

本文以ACO中的α,β,ρ作為控制變量;控制向量p=[α,β,ρ];問(wèn)題維數(shù)d=3;l=[0,0,0]是3個(gè)變量搜索下界;h=[5,5,1]是3個(gè)變量搜索上界。

2.3 DE變異操作

變異操作的目的就是為當(dāng)代種群個(gè)體pi(G)產(chǎn)生一個(gè)參照體。其中，i∈(1,2,…,NP)從當(dāng)代種群中任意選取3個(gè)個(gè)體pr1(G),pr2(G),pr3(G),按照以下規(guī)則取得目標(biāo)個(gè)體ti(G)。

ti(G)=pr1(G)+F×[pr2(G)-pr3(G)],

(15)

F=F(0)×2φ,

(16)

(17)

其中，r1≠r2≠r3≠i;G為DE種群進(jìn)化代數(shù);Gmax是種群最大進(jìn)化代數(shù);F是自適應(yīng)縮放比例因子,F(0)是F的初始值;實(shí)驗(yàn)已經(jīng)證明F取值在0.5附近，且隨進(jìn)化過(guò)程逐漸減小會(huì)對(duì)算法有利。

2.4 DE交叉操作

將當(dāng)代個(gè)體pi(G)與目標(biāo)個(gè)體ti(G)進(jìn)行變量交換,保留較優(yōu)的個(gè)體變量,增強(qiáng)局部搜索能力。二項(xiàng)交叉的執(zhí)行方式如下:

(18)

cr=0.5×(1+rand)。

(19)

vi,j(g)為測(cè)試個(gè)體vi(g)的變量;ri,j(G)表示第G代第i個(gè)個(gè)體的第j個(gè)變量對(duì)應(yīng)生成的均勻分布的隨機(jī)數(shù);rnd為1～d之間均勻分布的整數(shù);rand是均勻分布的隨機(jī)數(shù);cr表示自適應(yīng)交叉概率,其取值在0.5～1范圍對(duì)算法有利。

2.5 DE選擇操作

比較測(cè)試個(gè)體vi(G)和當(dāng)代個(gè)體pi(G),選擇較優(yōu)者進(jìn)入下一代,采用這種方式保證了下一代種群個(gè)體pi(G+1)優(yōu)于當(dāng)代種群個(gè)體pi(G),這是一種貪婪選擇方式。即

pi(G+1)=

(20)

式中,ACO[]表示以ACO作為DE的適應(yīng)度函數(shù),即DE調(diào)用ACO。

綜上，HDE-ACO算法基本步驟如下：

Step1 DE以ACO參數(shù)α,β,ρ作為控制變量進(jìn)行初始化,求得初始種群。參數(shù)上下界上文已給出,G=1,i=1。需要確定參數(shù)Gmax，NP，Tmax，Q，F(xiàn)(0)。

Step2 按照式(15)和式(18)對(duì)第G代初始種群進(jìn)行DE變異和交叉操作得到測(cè)試種群。

Step3 將第G代初始種群的第i個(gè)個(gè)體代入ACO求得計(jì)算結(jié)果ACO[pi(G)]。

Step4 將測(cè)試種群的第i個(gè)個(gè)體代入ACO求得計(jì)算結(jié)果ACO[vi(G)]。

Step5 按照式(20)確定初始種群的第i個(gè)個(gè)體或測(cè)試種群的第i個(gè)個(gè)體是否進(jìn)入下一代。

Step6 如果i≤NP,則i=i+1，返回到Step3。如果達(dá)到終止條件,則執(zhí)行下一步。

Step7 如果G≤Gmax,則G=G+1,返回到Step2。

Step8 如果滿足終止條件,則輸出相應(yīng)的計(jì)算結(jié)果。

所有實(shí)驗(yàn)程序在Matlab2010環(huán)境下運(yùn)行,PC機(jī)主頻為2.30 GHz,內(nèi)存2GB。所有實(shí)驗(yàn)結(jié)果以數(shù)值最小化為基準(zhǔn)。

2.6 算法性能測(cè)試

由于TSP問(wèn)題的求解難度大,一般以TSP作為平臺(tái)檢驗(yàn)優(yōu)化算法的性能[12]。使用文中算法與文獻(xiàn)[13-15]中算法分別對(duì)6個(gè)城市規(guī)模不等的基準(zhǔn)TSP進(jìn)行測(cè)試。為保證算法公平比較,所有算法迭代次數(shù)均為15。其他參數(shù)在以下算法描述中給出,為了分析方便4種算法，分別用“#1”，“#2”，“#3”，“#4”表示。

#1(文獻(xiàn)[13]算法):蟻群算法。其采用的參數(shù)為,α=1，β=2，ρ=0.65，Q=10。

#2(文獻(xiàn)[14]算法):改進(jìn)的粒子群算法。粒子群算法依靠大規(guī)模粒子和多次迭代尋優(yōu),本文將粒子個(gè)數(shù)增加到500。

#3(文獻(xiàn)[15]算法):蟻群和遺傳混合算法。其參數(shù)為:α=1，β=5，ρ=0.7，Q=100，交叉概率pc=0.9，變異概率pm=0.9。

#4(HDE-ACO):參數(shù)設(shè)置為,Gmax=15，NP=12，Tmax=5，Q=100，F(xiàn)(0)=0.2。

以上算法對(duì)6個(gè)TSP各自求解5次,實(shí)驗(yàn)數(shù)值統(tǒng)計(jì)如表1～6所示;6個(gè)TSP的全局最優(yōu)值的變化如圖1～6所示,橫坐標(biāo)表示算法迭代次數(shù),縱坐標(biāo)表示每次迭代得到的全局最優(yōu)值。

表1 Burma14的數(shù)值統(tǒng)計(jì)結(jié)果

Tab.1 Numerical statistics of Burma14

算法平均值最優(yōu)值#133643222#233933178#332643157#433683123

表2 Oliver30的數(shù)值統(tǒng)計(jì)結(jié)果

Tab.2 Numerical statistics of Oliver30

算法平均值最優(yōu)值#14899146137#27988465920#34957846820#44539644196

表3 St70的數(shù)值統(tǒng)計(jì)結(jié)果

Tab.3 Numerical statistics of St70

算法平均值最優(yōu)值#18969979140#2242e+003212e+003#39051884956#48470074317

表4 Gr96的數(shù)值統(tǒng)計(jì)結(jié)果

Tab.4 Numerical statistics of Gr96

算法平均值最優(yōu)值#16892559159#2240e+003215e+003#37418168067#46853755449

表5 Ch150的數(shù)值統(tǒng)計(jì)結(jié)果

Tab.5 Numerical statistics of Ch150

算法平均值最優(yōu)值#1105e+004788e+003#2424e+004381e+004#3120e+004973e+003#4714e+003681e+003

表6 Pr226的數(shù)值統(tǒng)計(jì)結(jié)果

Tab.6 Numerical statistics of Pr226

算法平均值最優(yōu)值#1138e+005966e+004#2138e+006128e+006#3174e+005153e+005#4807e+004783e+004

圖1 Burma14的全局最優(yōu)值的變化Fig.1 The global optimal value change of Burma14

圖2 Oliver30的全局最優(yōu)值的變化Fig.2 The global optimal value change of Oliver30

圖3 St70的全局最優(yōu)值的變化Fig.3 The global optimal value change of St70

圖4 Gr96的全局最優(yōu)值的變化Fig.4 The global optimal value change of Gr96

圖5 Ch150的全局最優(yōu)值的變化Fig.5 The global optimal value change of Ch150

圖6 Pr226的全局最優(yōu)值的變化Fig.6 The global optimal value change of Pr226

Burma14和Oliver30是小規(guī)模問(wèn)題。由表1可見(jiàn),#4的平均值比#1大0.04，比#3大1.04,差距都不大。#4的最優(yōu)值比其他算法都小,但差距不大。由表2可見(jiàn), #4的平均值比#1的小7.3%,比#2的小43.2%,比#3的小8.4%。#4的最優(yōu)值比#1的小4.2%,比#2的小33%,比#3的小5.6%。

對(duì)于Burma14的求解,#4的尋優(yōu)結(jié)果最好。

但是，與#1，#2，#3差別不大,對(duì)于Oliver30,#4的尋優(yōu)結(jié)果最好,#1和#3能力相當(dāng),#2效果欠佳。

St70和Gr96是中等規(guī)模問(wèn)題, 由表3可見(jiàn), #4的平均值比#1的小5.6%,比#2的小65%,比#3的小6.4%。#4的最優(yōu)值比#1的小6.1%,比#2的小65%,比#3的小19.4%。由表4可見(jiàn),#4的平均值比#1的小0.6%,比#2的小71%,比#3的小7.6%。#4的最優(yōu)值比#1的小6.3%,比#2的小74.2%,比#3的小18.5%。通過(guò)比較表3和表4可得:對(duì)于St70和Gr96的求解,#4的尋優(yōu)結(jié)果最好,#1與#4差別不大,#2效果最差。

Ch150和Pr226是大規(guī)模問(wèn)題,由表5可見(jiàn),#4的平均值比#1的小32%,比#2的小83.2%,比#3的小40.5%。#4的最優(yōu)值比#1的小13.6%,比#2的小82.1%,比#3的小30%。由表6可見(jiàn),#4的平均值比#1的小41.5%,比#2的小94.2%,比#3的小53.6%。#4的最優(yōu)值比#1的小18.9%,比#2的小93.9%,比#3的小48.8%。通過(guò)比較表5和表6可得:#4的尋優(yōu)結(jié)果明顯優(yōu)于#1，#2，#3,其中#2效果最差。

由圖1～6可知，在15次迭代過(guò)程中#4的收斂速度和尋優(yōu)結(jié)果最好,說(shuō)明對(duì)于不同規(guī)模的問(wèn)題，#4不易陷入局部最優(yōu),具有較高的尋優(yōu)精度。

通過(guò)表1～6以及圖1～6可知,#2一直處于弱勢(shì),這主要是由于本文選取迭代次數(shù)過(guò)小導(dǎo)致。為了實(shí)驗(yàn)的嚴(yán)謹(jǐn)性和科學(xué)性,本文加大#2的迭代次數(shù)并求解6個(gè)TSP,#2對(duì)每個(gè)TSP求解5次。圖7表示#2求解6個(gè)TSP的全局最優(yōu)值過(guò)程變化,表7是#2和#4的數(shù)值統(tǒng)計(jì)對(duì)比表。

表7 #2和#4的數(shù)值統(tǒng)計(jì)

Tab.7 Numerical statistics of #2 and #4

TSP #2 #4 迭代次數(shù)平均值最優(yōu)值迭代次數(shù)平均值最優(yōu)值Burma14200310330881533683123Oliver302004684342374154539644196St7010008773771792158470074317Gr9610008303758232156853755449Ch1501000161e+004101e+00415714e+003681e+003Pr2261000440e+005197e+00515681e+003783e+004

圖7 #2求解TSP的全局最優(yōu)值變化Fig.7 The global optimal value change of TSP obtained by #2

由表7中數(shù)值比較可知,對(duì)于小規(guī)模問(wèn)題，#2的平均值以及最優(yōu)值與#4的差距不大,對(duì)于大規(guī)模問(wèn)題，#4的平均值與最優(yōu)值遠(yuǎn)小于#2的。對(duì)于St70問(wèn)題，#2的最優(yōu)值比#4的小,對(duì)于Gr96問(wèn)題，#4的最優(yōu)值比#2的小,說(shuō)明對(duì)于中等規(guī)模問(wèn)題#2和#4的尋優(yōu)能力相當(dāng)。因此可知，#2求解中小規(guī)模問(wèn)題時(shí),求解精度與#4相差不大，甚至略優(yōu)于#4。但是，對(duì)于大規(guī)模問(wèn)題，其求解精度遠(yuǎn)遠(yuǎn)不如#4。#2在求解大中規(guī)模問(wèn)題時(shí)需要多達(dá)千次的迭代,這種方法需要較高的時(shí)間成本，所以此法不可取。

總之,對(duì)于不等規(guī)模的路徑尋優(yōu)問(wèn)題,#4的尋優(yōu)能力要優(yōu)于其他算法。

3 仿真研究

焦?fàn)t推焦計(jì)劃調(diào)度模型參數(shù)選?。簍max=17.917(h),tmin=18.083(h),θ=0.5,χ=2,γ=0.5。HDE-ACO選取的參數(shù)與上文中#4的相同。焦?fàn)t推焦計(jì)劃調(diào)度具有隨機(jī)性，文中主要從以下3種情況進(jìn)行研究。優(yōu)化后的推焦順序?qū)嶋H按照系統(tǒng)總懲罰最優(yōu)原則求得。表8是人工經(jīng)驗(yàn)推焦計(jì)劃安排和文中算法優(yōu)化調(diào)度后系統(tǒng)總懲罰值比較表。以下結(jié)果基于Matlab 2010求得。

情況1 爐孔無(wú)錯(cuò)亂，并且按時(shí)出焦這種情況就是正常工況下的推焦調(diào)度,考慮這種情況的目的是為了驗(yàn)證本文算法對(duì)推焦調(diào)度優(yōu)化的準(zhǔn)確性。優(yōu)化后的推焦順序完全符合5-2推焦順序。

優(yōu)化后的推焦順序:

1→6→11→16→21→26→31→36→41→46→51→56→61→66→71→76→81→

3→8→13→18→23→28→33→38→43→48→53→58→63→68→73→78→83→

5→10→15→20→25→30→35→40→45→50→55→60→65→70→75→80→

2→7→12→17→22→27→32→37→42→47→52→57→62→67→72→77→82→

4→9→14→19→24→29→34→39→44→49→54→59→64→69→74→79→84。

情況2 爐孔部分錯(cuò)亂、全部按時(shí)出焦。隨機(jī)選取爐號(hào)為6，9，7，25的爐孔發(fā)生推焦順序錯(cuò)亂。

優(yōu)化后的推焦順序:

1→11→16→21→6→26→31→36→41→46→51→56→61→66→71→76→81→

3→8→13→18→23→28→33→38→43→48→53→58→63→68→73→78→83→

5→10→15→20→30→35→40→25→45→50→55→60→65→70→75→80→

2→12→17→22→7→27→32→37→42→47→52→57→62→67→72→77→82→

4→14→19→24→9→29→34→39→44→49→54→59→64→69→74→79→84。

情況3 爐孔部分錯(cuò)亂、部分未按時(shí)出焦。錯(cuò)亂爐孔依然是6，9，7，25,爐孔i的計(jì)劃出焦時(shí)間ti=17.75+0.5×rand。

優(yōu)化后的推焦順序:

1→11→16→21→6→26→31→36→46→51→56→61→76→81→

8→13→18→28→33→43→48→53→63→68→73→83→

5→10→15→30→40→25→35→55→60→65→70→75→80→

2→12→17→22→27→37→42→47→52→57→62→67→77→

4→19→24→29→14→39→44→54→59→64→69→74→79→84→41→71→

3→23→38→58→78→20→45→50→7→32→72→82→29→34→49→66。

表8 系統(tǒng)懲罰比較

Fig.8 The comparison of system penalty

情況系統(tǒng)總懲罰人工經(jīng)驗(yàn)HDE?ACO1002>27273?4132541325

表8中,兩種方法在情況1(正常工況)下的系統(tǒng)總懲罰值均為0。情況2下,HDE-ACO求得的系統(tǒng)總懲罰值為27，而人工經(jīng)驗(yàn)法求解結(jié)果大于27。情況3下,HDE-ACO求得的系統(tǒng)總懲罰值為413.25，而人工經(jīng)驗(yàn)法求解結(jié)果遠(yuǎn)大于27。情況2和情況3屬于異常工況,通過(guò)情況2和情況3各自系統(tǒng)總懲罰值比較,證明HDE-ACO智能調(diào)度優(yōu)化得到的懲罰效果要優(yōu)于人工經(jīng)驗(yàn)推焦計(jì)劃安排，即HDE-ACO求得的推焦調(diào)度精度高。

4 總 結(jié)

基于NP-hard問(wèn)題的求解，文中提出一種DE和ACO的混合算法?；旌纤惴ɡ肈E優(yōu)化ACO參數(shù),解決ACO對(duì)參數(shù)變化敏感的問(wèn)題?；旌纤惴ㄖ饕攸c(diǎn)是采用自適應(yīng)DE參數(shù),解決了DE參數(shù)的難調(diào)性的困難;全局異步特性與精英策略相結(jié)合的信息素更新策略被引進(jìn)到ACO中,減少了ACO被一次調(diào)用需要多次迭代的問(wèn)題。使用文中算法與文獻(xiàn)[13-15]中的算法對(duì)多個(gè)TSP問(wèn)題測(cè)試比較,實(shí)驗(yàn)結(jié)果證明經(jīng)過(guò)少次迭代，文中算法表現(xiàn)出很強(qiáng)的尋優(yōu)能力和較快的收斂速度。將文中算法應(yīng)用到焦?fàn)t推焦計(jì)劃調(diào)度中,其優(yōu)化后的推焦順序準(zhǔn)確度高,能夠使系統(tǒng)懲罰最優(yōu)。

[1] MAITY S, ROY A, MAITI M. A modified genetic algorithm for solving uncertain constrained solid travelling salesman problems[J].Computers & Industrial Engineering, 2015, 83(2):273-296.

[2] ESCARIO J B, JIMENEZ J F, GIRON-SIERRA J M. Ant colony extended:Experiments on the travelling salesman problem[J].Expert Systems with Applications, 2015, 42(1):390-410.

[3] MAVROVOUNIOTIS M, YANG S. A memetic ant colony optimization algorithm for the dynamic travelling salesman problem[J].Soft Computing, 2011, 15(7):1405-1425.

[4] KIRAN M S, ISCAN H, GüNDüZ M. The analysis of discrete artificial bee colony algorithm with neighborhood operator on traveling salesman problem[J].Neural Computing and Applications, 2013, 23(1):9-21.

[5] BANG J, RYU J, LEE C, et al. A Quantum heuristic algorithm for the traveling salesman problem[J].Journal of the Korean Physical Society, 2012, 61(12):1944-1949.

[6] OUAARAB A, AHIOD B, YANG X S. Discrete cuckoo search algorithm for the travelling salesman problem[J].Neural Computing and Applications, 2014, 24(7-8):1659-1669.

[7] NARASIMHA K V, KIVELEVITCH E, SHARMA B, et al. An ant colony optimization technique for solving min-max multi-depot vehicle routing problem[J].Swarm and Evolutionary Computation, 2013, 13(5)：63-73.

[8] ZOU Dexuan, LIU Haikuan, GAO Liqun, et al. An improved differential evolution algorithm for the task assignment problem[J].Engineering Applications of Artificial Intelligence, 2011, 24(4):616-624.

[9] LAI Mingyong, CAO Erbao. An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows[J].Engineering Applications of Artificial Intelligence, 2010, 23(2): 188-195.

[10] CHEN Xu, DU Wenli, QIAN Feng. Multi-objective differential evolution with ranking-based mutation operator and its application in chemical process optimization[J].Chemometrics and Intelligent Laboratory Systems, 2014, 136(16):85-96.

[11] ALI M, AHN C W, SIARRY P. Differential evolution algorithm for the selection of optimal scaling factors in image watermarking[J].Engineering Applications of Artificial Intelligence, 2014, 31:15-26.

[12] WANG Yong. The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem[J].Computers & Industrial Engineering, 2014, 70(2): 124-133.

[13] RAGHAVENDRA B V. Solving traveling salesmen problem using ant colony optimization algorithm[J].Applied & Computational Mathematics, 2015,4(6):1-8.

[14] GAO Yuxi, WANG Yanming, PEI Zhili. An improved particle swarm optimization for solving generalized travelling salesman problem[J].International Journal of Computing Science & Mathematics, 2012, 3(4):385-393.

[15] WANG Chunxiang，GUO Xiaoni. A hybrid algorithm based on genetic algorithm and ant colony optimization for Traveling Salesman Problems[C]∥The 2nd International Conference on Information Science and Engineering. IEEE, 2010: 4257-4260.

(編 輯 李 靜)

Application of a hybrid algorithm in coke pushing planning and scheduling of coke oven

TAO Wenhua， LIU Hongtao

(School of Information and Control Engineering, Liaoning Shihua University, Fushun 113001， China)

Coke pushing plan of coke oven is arranged by artificial experiences, which is not only lack of intelligence, but also lack of accuracy. In view of this, a coke pushing plan scheduling model that has the nature of Traveling Salesman Problem is built in this paper. In order to obtain a more accurate solution for the problem, a hybrid algorithm of Differential Evolution and Ant Colony Optimization (HDE-ACO) is presented in this paper. The basic idea of HDE-ACO is that DE is used to optimize three parameters of ACO, thus overcoming the difficulty that ACO is sensitive to parameter change. Then, the optimization accuracy of ACO can be improved. HDE-ACO and several other algorithms are used to optimize multiple different TSPs. The comparison results show that HDE-ACO has not only a strong ability of searching optimal solution but also a faster convergence rate. Finally, HDE-ACO is applied to coke pushing plan scheduling and the optimization of coke pushing plan is divided into three kinds of cases to study.

coke pushing planing and scheduling; TSP; differential evolution; ant colony optimization

2015-09-03

國(guó)家自然科學(xué)基金資助項(xiàng)目(61473140); 國(guó)家自然科學(xué)基金青年基金資助項(xiàng)目(61203021)

陶文華，女，浙江紹興人，教授，從事智能算法的研究與應(yīng)用。

TP18

A

10.16152/j.cnki.xdxbzr.2016-06-008