曹嘉瑞，陶文華，曹江濤

（遼寧石油化工大學(xué) 遼寧 撫順　113001）

基于禁忌搜索的蟻群算法解決焦?fàn)t推焦優(yōu)化調(diào)度問題

曹嘉瑞，陶文華，曹江濤

（遼寧石油化工大學(xué) 遼寧 撫順113001）

針對焦?fàn)t推焦過程中，計劃編制在保證結(jié)焦時間、提高焦炭質(zhì)量等因素下減小總懲罰的難點，文中提出一種基于禁忌搜索的蟻群算法解決此焦?fàn)t推焦優(yōu)化調(diào)度問題。焦?fàn)t推焦過程中存在亂箋等異常工況，利用傳統(tǒng)蟻群算法對歸結(jié)為TSP問題的焦?fàn)t推焦優(yōu)化調(diào)度模型進行求解，但傳統(tǒng)蟻群算法容易過早的陷入局部最優(yōu)的狀態(tài)，且會發(fā)生停滯的狀況，產(chǎn)生收斂速度與最優(yōu)解之間的矛盾。本文采用基于禁忌搜索的蟻群優(yōu)化算法對焦?fàn)t推焦優(yōu)化調(diào)度模型求解，實驗結(jié)果證實基于禁忌搜索的蟻群算法優(yōu)于傳統(tǒng)蟻群算法在保證收斂速度的同時提高最優(yōu)解的質(zhì)量，驗證了該方法的可行性。

蟻群算法；禁忌搜索；優(yōu)化調(diào)度；異常工況

在進行焦?fàn)t推焦計劃的編排時，因為焦?fàn)t推焦過程中會產(chǎn)生異常工況［1］?？梢詫惓９r下的焦?fàn)t作業(yè)計劃編制歸結(jié)為一個優(yōu)化調(diào)度問題，近些年來，生產(chǎn)調(diào)度問題中智能優(yōu)化算法的應(yīng)用［2-3］使得有關(guān)焦?fàn)t推焦優(yōu)化調(diào)度方法的研究已經(jīng)取得了不錯的進展。文獻［6］將焦?fàn)t作業(yè)計劃優(yōu)化調(diào)度問題等價成旅行商（TSP）問題，并采用蟻群算法進行求解，雖然實現(xiàn)了焦?fàn)t的優(yōu)化調(diào)度，也保證了結(jié)焦時間并提高了質(zhì)量，但是因為傳統(tǒng)蟻群算法過早的陷入局部最優(yōu)而出現(xiàn)停滯現(xiàn)象，產(chǎn)生收斂速度和解的質(zhì)量之間的矛盾。本文采用禁忌搜索算法在利用蟻群算法實現(xiàn)優(yōu)化調(diào)度的同時最大程度的彌補這一缺點，即，在保證收斂速度的同時提高解的質(zhì)量。

1　焦?fàn)t推焦的優(yōu)化調(diào)度模型

焦?fàn)t優(yōu)化調(diào)度中的總懲罰是由兩種現(xiàn)象引起的，一種是推焦順序的錯亂，一種是結(jié)焦時間過長或者過短［7］。而總懲罰越小就越能保證其質(zhì)量，并且能降低損耗，以加長爐體的使用壽命。

引用文獻［6］中的調(diào)度模型：

1）緊鄰的兩個炭化室號的順序錯亂引起的懲罰：

其中，i，j=0，1，2…n，i≠j；q為懲罰的權(quán)值；n為炭化室總數(shù)目。

2）結(jié)焦時間過長或者過短引起的懲罰：

其中，β表示結(jié)焦時間發(fā)生改變的狀況下，受損的程度加大的快慢以及質(zhì)量降低的快慢。而式（3）中減1可以保證出爐期間爐體無礙和焦炭質(zhì)量的無損，且無懲罰。

α則表示結(jié)焦時間的變化對爐體壽命的損壞程度的大小和對焦炭質(zhì)量的損壞程度的大小，因為提前推焦的影響大于延遲推焦，所以選擇α＞1。

Ti為i號炭化室的計劃結(jié)焦時間；Tmax和Tmin為標(biāo)準(zhǔn)結(jié)焦時間的最大值和最小值。

3）緊鄰的兩個炭化室的總懲罰為：

檢修時間段包括在編排中，但其引起的懲罰為0。

綜上所述，焦?fàn)t優(yōu)化調(diào)度的目標(biāo)函數(shù)是：編排一個完整的推焦順序使總懲罰最?。?/p>

2　蟻群算法解決優(yōu)化調(diào)度問題

異常工況時，將焦?fàn)t優(yōu)化調(diào)度問題歸結(jié)為TSP問題來解決。而焦?fàn)t推焦的最優(yōu)解可以等價為旅行商問題中的最短路徑。

楊年豐說著，微微向前探過身子，逼視著坐在地上的高河：“年喜說的，跟你講述的不一樣啊。”說著，楊年豐再次用手指點了點床上的兩張照片。

將旅行商模型中的N個城市等同于焦?fàn)t推焦中的n個炭化室以及m個檢修時間段，則將優(yōu)化調(diào)度模型變更為旅行商模型：

設(shè)C=｛c1，c2，…，cN｝為N個城市的集合，dij表示城市i、j之間的距離，其中，

上式中，α用來控制信息素濃度的相對重要程度；β則用來控制啟發(fā)式信息的相對重要程度；ηij（t）是節(jié)點i轉(zhuǎn)移到節(jié)點j上的啟發(fā)信息；j（t）表示在節(jié)點（i，j）之間的信息素濃度。

上式中，ρ為一個（0，1）的常數(shù)，表示局部殘留信息素的相對重要程度，程度越大，信息素濃度揮發(fā)的越慢，反之越快；表示第k只螞蟻在時刻（t，t+1）之間，節(jié)點i和j之間的路徑上增加的信息素濃度。

上式中，dij為節(jié)點i，j之間的懲罰，Q是常量，表示每一只螞蟻所特有的信息素總量。

當(dāng)所有的螞蟻都完成了一次循環(huán)之后，只有得到全局最優(yōu)解的螞蟻按照式（13）對所有路徑上的信息素改造，若螞蟻走過的路徑不是最優(yōu)的，那么其信息素?fù)Q為0。

其中，ρ1是在（0，1）間，表示全局殘留信息素的相對重要程度；dLbnc是第nc次循環(huán)中最優(yōu)解的懲罰之和。

3　基于禁忌搜索的蟻群算法求解

3.1禁忌搜索算法

禁忌搜索算法是在1986年被提出的，其擴大局部領(lǐng)域搜索，是一種整體逐步求解最優(yōu)的算法［8］．對初始解進行“移動”產(chǎn)生可行的鄰域解，獲取最優(yōu)鄰域解當(dāng)做新的初始解來完成解空間的局部搜索。禁忌搜索算法可以抑制搜索過程易于過早的陷入局部最優(yōu)的缺點，想要防止迂回搜索則是要利用禁忌策略來限制搜索過程過早的陷入局部最優(yōu)，而且可以同時利用特赦標(biāo)準(zhǔn)開釋被禁忌的好狀態(tài)。

在給定的初始解的鄰域當(dāng)中確定多個待選解。若最優(yōu)待選解對應(yīng)的目標(biāo)值較比于目前最好解的狀態(tài)好，則可以忽略目標(biāo)值的禁忌特性，并用此目標(biāo)值替換初始解和目前最好解的狀態(tài)，將此目標(biāo)值對應(yīng)的對象放入禁忌表的同時修改其任期。若無較比目前最好解更好的最優(yōu)待選解，則選擇非禁忌的最優(yōu)解當(dāng)做新的初始解，忽略其與初始解的好壞對比，將其對應(yīng)的對象放入禁忌表并修改任期。

如此反復(fù)，直到滿足停止準(zhǔn)則為止［9］。

3.2基于禁忌搜索的蟻群算法

蟻群算法在工作的過程中容易過早的出現(xiàn)進入局部最優(yōu)的狀況。而禁忌搜索算法則具有變通的記憶功能［10］，能夠在搜索過程當(dāng)中接受非優(yōu)解。為了能夠獲得最佳全局最優(yōu)解的概率，禁忌搜索算法可以在搜索時及早的離開局部最優(yōu)解，轉(zhuǎn)向其他區(qū)域。

結(jié)合兩者的優(yōu)點，以及兩者結(jié)合后在TSP問題上的應(yīng)用，又因焦?fàn)t優(yōu)化調(diào)度問題可以歸結(jié)為TSP問題，所以，文中提出了將基于禁忌搜索的蟻群算法應(yīng)用在解決焦?fàn)t優(yōu)化調(diào)度的問題之上。

在螞蟻結(jié)束一次循環(huán)之后，挑出本次循環(huán)中路徑最長和最短的對象分別放進兩個不同的禁忌表中，以備在下次選路時避免選擇存在于禁忌表中的路徑。

若一次循環(huán)結(jié)束，螞蟻找到的解與劣解相同，我們認(rèn)為是不好的而不選擇這條路徑，也不會在這條路徑上得到信息素增量。

若一次循環(huán)找到曾經(jīng)經(jīng)過的最優(yōu)路徑，那么也認(rèn)為是無用的，同樣不選擇這條路徑也不在這條路徑上給出信息素增量，從而讓搜索的范圍繼續(xù)擴展。

將蟻群算法和禁忌搜索算法結(jié)合主要利用禁忌搜索算法的長期記憶功能夠改進搜索的開發(fā)性。

利用負(fù)信息素φij的形式來記憶已經(jīng)訪問過的點（t）。對于每個邊（i，j），γ是常量，λij代表邊（i，j）的使用頻率。若邊（i，j）包含在任意解中，λij（t）加1，則λij（0）=1。以此，轉(zhuǎn)移概率改為：

上式中使用邊（i，j）越多，負(fù)信息素φij的值越小，從而比其他使用頻率小的邊的釋放量越少。因此可以提高對使用頻率小的邊的探索性。

4　仿真結(jié)果

為了對比驗證傳統(tǒng)蟻群算法和基于禁忌搜索的蟻群算法的結(jié)果，參數(shù)選擇分別如下：

蟻群算法：α=2，β=3，ρ=0．7，ρ1=0．6，Q=100，γ=115

基于禁忌搜索的蟻群算法：α=2，β=3，ρ=0．7，ρ1=0．6，Q= 100，γ=115，r′=2。

表1為焦?fàn)t優(yōu)化調(diào)度結(jié)果的比較。圖1為焦?fàn)t優(yōu)化調(diào)度模擬比較圖。

表1　焦?fàn)t優(yōu)化調(diào)度結(jié)果Tab.1　Coke oven operation optimization results

圖1　焦?fàn)t優(yōu)化調(diào)度模擬比較圖Fig．1　The optimization scheduling simulation comparison chart of coke oven

圖1中，下側(cè)線為傳統(tǒng)蟻群算法結(jié)果，上側(cè)線為基于禁忌搜索的蟻群算法結(jié)果。

從表1和圖1可以看出蟻群算法收斂速度快但是解的質(zhì)量較差，而基于禁忌搜索的蟻群算法則在保證收斂速度的同時將解的質(zhì)量提高了。

5　結(jié)束語

相比普通的蟻群算法［9-11］，本文使用禁忌搜索在其基礎(chǔ)上進行改進，在保證收斂速度的同時將解的質(zhì)量提高，成功的解決了收斂速度和解的質(zhì)量之間的矛盾。實驗獲得了最佳的優(yōu)化調(diào)度結(jié)果，證實了該方法的可行性。

［1］于振東，蔡承祐．焦?fàn)t生產(chǎn)技術(shù)［M］．沈陽:遼寧科學(xué)技術(shù)出版社，2003．

［2］張利，劉文生．基于兩種遺傳算法的柔性制造線仿真優(yōu)化［J］．武漢工業(yè)學(xué)院學(xué)報，2013（9）:44-47．

［3］張旭君，呂志民．連鑄軋集成計劃與調(diào)度組批模型及算法［J］．控制與決策，2013，28（8）:1257-1262．

［4］吳敏，朱華琦，曹衛(wèi)華，等．焦?fàn)t作業(yè)計劃與優(yōu)化調(diào)度系統(tǒng)設(shè)計與實現(xiàn)［J］．控制工程，2009，16（2）:176-180．

［5］鞠文波．熱軋帶鋼軋制批量計劃軟件系統(tǒng)開發(fā)與研究［D］．大連:大連理工大學(xué)，2005．

［6］汪定偉，王俊偉，王洪峰，等．智能優(yōu)化算法［M］．北京:高等教育出版社，2007．

［7］王凌．智能優(yōu)化算法及其應(yīng)用［M］．北京:清華大學(xué)出版社&施普林格出版社，2001．

［8］徐麗．具有禁忌搜索能力的螞蟻算法［D］．天津:河北工業(yè)大學(xué)，2007．

［9］孫延．基于蟻群算法的紡織企業(yè)生產(chǎn)調(diào)度技術(shù)研究［J］．電子設(shè)計工程，2015（18）:116-118．

［10］向虹佼，呂光宏，明麗洪．基于蟻群系統(tǒng)的QoS單播路由算法［J］．電子科技，2014（1）:53-56．

［11］葉楓．雙向收斂蟻群算法在云計算資源調(diào)度中的QoS應(yīng)用［J］．電光與控制，2014（11）:93-96．

［12］祁金佺．遺傳蟻群算法在軟件測試用例生成中的應(yīng)用［J］．工業(yè)儀表與自動化裝置，2013（6）:112-116．

The ant colony algorithm based on tabu search to solve the optimal of operation problem of coke oven

CAO Jia-rui，TAO Wen-hua，CAO Jiang-tao
（Liaoning Shihua University，F(xiàn)ushun 113001，China）

For coke oven coke pushing，in the process of planning in coking time，improve the quality of coke，etc to reduce total penalty factors is difficult，this paper puts forward a kind of ant colony algorithm based on tabu search to solve the optimal operation problem of coke oven pusher．In the process of coke oven coke pushing the disorderly depicting abnormal conditions，such as use of traditional ant colony algorithm to boil down to the TSP problem of coke oven coke pushing are applied to solve the optimal scheduling model，but the traditional ant colony algorithm is easy to fall into a state of local optimum，early and stagnant situation happens，the contradiction between the convergence speed and the optimal solution．In this paper，the ant colony optimization algorithm based on tabu search for coke oven pushing optimization scheduling model，the experimental results confirmed that the ant colony algorithm based on tabu search is better than the traditional ant colony algorithm in convergence speed and improve the quality of the optimal solution and verify the feasibility of this method．

ant colony algorithm；tabu search；optimization scheduling；abnormal operating conditions

TN05

A

1674－6236（2016）02-0065-03

2015-04-02稿件編號：201504015

國家自然科學(xué)基金項目（61203021）

曹嘉瑞（1991—），女，遼寧遼陽人，碩士。研究方向：控制理論與控制工程。