陶文華，劉洪濤

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

?

·信息科學·

一種混合算法在焦爐推焦計劃調度中的應用

陶文華，劉洪濤

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

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

推焦計劃調度;TSP;差分進化;蟻群算法

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

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

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

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

1 焦爐推焦計劃調度模型

TSP的數學描述:一個城市集合Q={c1,c2,…,cm}，其中每兩個城市之間的距離為d(ci,cj)∈R+。一個旅行商經過Q中每個城市一次的路線為R=(q1,q2，…，qi,…,qm)(qi為Q中第i個城市)，使得整個路線一周的距離最小,目標函數為

(1)

推焦順序通常表示為a-b串序,a代表相鄰兩次推焦間隔的爐孔數目，b代表兩趟簽號對應爐孔間隔的整數。目前,世界上主要包括5-2，9-2，2-1推焦串序,我國主要采用5-2式和9-2式。相比而言,5-2式機械行程較短。本文以2×42孔JN43-80型焦爐為例,采用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。

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

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

Pi,j=Xi,jwi,j,

(2)

(3)

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

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

Ji=exp(θYi)-1,

(4)

(5)

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

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

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

(6)

綜上所述,在一個完整的周轉時間內，完成所有爐孔的推焦要保證整個推焦系統(tǒng)的總懲罰最小，推焦計劃調度目標函數為

(7)

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

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

2.1 蟻群算法(ACO)

(8)

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

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

(9)

(10)

(11)

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

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

(12)

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

(13)

ACO計算步驟如下:

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

Step2 計算每兩個城市之間的距離d(i,j),(0

Step3 根據當前時刻的tabuk確定第k只螞蟻的位置,按照式(8)和當前時刻的allowedk選擇下一個城市。

Step4 下一時刻更新第k只螞蟻的禁忌表tabuk和允許訪問的路徑表allowedk。

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

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

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

2.2 DE種群初始化

(14)

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

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

2.3 DE變異操作

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

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

(15)

F=F(0)×2φ,

(16)

(17)

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

2.4 DE交叉操作

將當代個體pi(G)與目標個體ti(G)進行變量交換,保留較優(yōu)的個體變量,增強局部搜索能力。二項交叉的執(zhí)行方式如下:

(18)

cr=0.5×(1+rand)。

(19)

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

2.5 DE選擇操作

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

pi(G+1)=

(20)

式中,ACO[]表示以ACO作為DE的適應度函數,即DE調用ACO。

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

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

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

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

Step4 將測試種群的第i個個體代入ACO求得計算結果ACO[vi(G)]。

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

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

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

Step8 如果滿足終止條件,則輸出相應的計算結果。

所有實驗程序在Matlab2010環(huán)境下運行,PC機主頻為2.30 GHz,內存2GB。所有實驗結果以數值最小化為基準。

2.6 算法性能測試

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

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

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

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

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

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

表1 Burma14的數值統(tǒng)計結果

Tab.1 Numerical statistics of Burma14

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

表2 Oliver30的數值統(tǒng)計結果

Tab.2 Numerical statistics of Oliver30

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

表3 St70的數值統(tǒng)計結果

Tab.3 Numerical statistics of St70

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

表4 Gr96的數值統(tǒng)計結果

Tab.4 Numerical statistics of Gr96

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

表5 Ch150的數值統(tǒng)計結果

Tab.5 Numerical statistics of Ch150

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

表6 Pr226的數值統(tǒng)計結果

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ī)模問題。由表1可見,#4的平均值比#1大0.04，比#3大1.04,差距都不大。#4的最優(yōu)值比其他算法都小,但差距不大。由表2可見, #4的平均值比#1的小7.3%,比#2的小43.2%,比#3的小8.4%。#4的最優(yōu)值比#1的小4.2%,比#2的小33%,比#3的小5.6%。

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

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

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

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

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

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

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

Tab.7 Numerical statistics of #2 and #4

TSP #2 #4 迭代次數平均值最優(yōu)值迭代次數平均值最優(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中數值比較可知,對于小規(guī)模問題，#2的平均值以及最優(yōu)值與#4的差距不大,對于大規(guī)模問題，#4的平均值與最優(yōu)值遠小于#2的。對于St70問題，#2的最優(yōu)值比#4的小,對于Gr96問題，#4的最優(yōu)值比#2的小,說明對于中等規(guī)模問題#2和#4的尋優(yōu)能力相當。因此可知，#2求解中小規(guī)模問題時,求解精度與#4相差不大，甚至略優(yōu)于#4。但是，對于大規(guī)模問題，其求解精度遠遠不如#4。#2在求解大中規(guī)模問題時需要多達千次的迭代,這種方法需要較高的時間成本，所以此法不可取。

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

3 仿真研究

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

情況1 爐孔無錯亂，并且按時出焦這種情況就是正常工況下的推焦調度,考慮這種情況的目的是為了驗證本文算法對推焦調度優(yōu)化的準確性。優(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 爐孔部分錯亂、全部按時出焦。隨機選取爐號為6，9，7，25的爐孔發(fā)生推焦順序錯亂。

優(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 爐孔部分錯亂、部分未按時出焦。錯亂爐孔依然是6，9，7，25,爐孔i的計劃出焦時間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)總懲罰人工經驗HDE?ACO1002>27273?4132541325

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

4 總 結

基于NP-hard問題的求解，文中提出一種DE和ACO的混合算法。混合算法利用DE優(yōu)化ACO參數,解決ACO對參數變化敏感的問題。混合算法主要特點是采用自適應DE參數,解決了DE參數的難調性的困難;全局異步特性與精英策略相結合的信息素更新策略被引進到ACO中,減少了ACO被一次調用需要多次迭代的問題。使用文中算法與文獻[13-15]中的算法對多個TSP問題測試比較,實驗結果證明經過少次迭代，文中算法表現(xiàn)出很強的尋優(yōu)能力和較快的收斂速度。將文中算法應用到焦爐推焦計劃調度中,其優(yōu)化后的推焦順序準確度高,能夠使系統(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

國家自然科學基金資助項目(61473140); 國家自然科學基金青年基金資助項目(61203021)

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

TP18

A

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