基于禁忌搜索的蟻群算法解決焦爐推焦優化調度問題

曹嘉瑞，陶文華，曹江濤

（遼寧石油化工大學 遼寧 撫順　113001）

基于禁忌搜索的蟻群算法解決焦爐推焦優化調度問題

曹嘉瑞，陶文華，曹江濤

（遼寧石油化工大學 遼寧 撫順113001）

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

蟻群算法；禁忌搜索；優化調度；異常工況

在進行焦爐推焦計劃的編排時，因為焦爐推焦過程中會產生異常工況［1］。可以將異常工況下的焦爐作業計劃編制歸結為一個優化調度問題，近些年來，生產調度問題中智能優化算法的應用［2-3］使得有關焦爐推焦優化調度方法的研究已經取得了不錯的進展。文獻［6］將焦爐作業計劃優化調度問題等價成旅行商（TSP）問題，并采用蟻群算法進行求解，雖然實現了焦爐的優化調度，也保證了結焦時間并提高了質量，但是因為傳統蟻群算法過早的陷入局部最優而出現停滯現象，產生收斂速度和解的質量之間的矛盾。本文采用禁忌搜索算法在利用蟻群算法實現優化調度的同時最大程度的彌補這一缺點，即，在保證收斂速度的同時提高解的質量。

1　焦爐推焦的優化調度模型

焦爐優化調度中的總懲罰是由兩種現象引起的，一種是推焦順序的錯亂，一種是結焦時間過長或者過短［7］。而總懲罰越小就越能保證其質量，并且能降低損耗，以加長爐體的使用壽命。

引用文獻［6］中的調度模型：

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

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

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

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

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

Ti為i號炭化室的計劃結焦時間；Tmax和Tmin為標準結焦時間的最大值和最小值。

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

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

綜上所述，焦爐優化調度的目標函數是：編排一個完整的推焦順序使總懲罰最小：

2　蟻群算法解決優化調度問題

異常工況時，將焦爐優化調度問題歸結為TSP問題來解決。而焦爐推焦的最優解可以等價為旅行商問題中的最短路徑。

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

將旅行商模型中的N個城市等同于焦爐推焦中的n個炭化室以及m個檢修時間段，則將優化調度模型變更為旅行商模型：

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

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

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

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

當所有的螞蟻都完成了一次循環之后，只有得到全局最優解的螞蟻按照式（13）對所有路徑上的信息素改造，若螞蟻走過的路徑不是最優的，那么其信息素換為0。

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

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

3.1禁忌搜索算法

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

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

如此反復，直到滿足停止準則為止［9］。

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

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

結合兩者的優點，以及兩者結合后在TSP問題上的應用，又因焦爐優化調度問題可以歸結為TSP問題，所以，文中提出了將基于禁忌搜索的蟻群算法應用在解決焦爐優化調度的問題之上。

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

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

若一次循環找到曾經經過的最優路徑，那么也認為是無用的，同樣不選擇這條路徑也不在這條路徑上給出信息素增量，從而讓搜索的范圍繼續擴展。

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

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

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

4　仿真結果

為了對比驗證傳統蟻群算法和基于禁忌搜索的蟻群算法的結果，參數選擇分別如下：

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

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

表1為焦爐優化調度結果的比較。圖1為焦爐優化調度模擬比較圖。

表1　焦爐優化調度結果Tab.1　Coke oven operation optimization results

圖1　焦爐優化調度模擬比較圖Fig．1　The optimization scheduling simulation comparison chart of coke oven

圖1中，下側線為傳統蟻群算法結果，上側線為基于禁忌搜索的蟻群算法結果。

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

5　結束語

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

［1］于振東，蔡承祐．焦爐生產技術［M］．沈陽:遼寧科學技術出版社，2003．

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

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

［4］吳敏，朱華琦，曹衛華，等．焦爐作業計劃與優化調度系統設計與實現［J］．控制工程，2009，16（2）:176-180．

［5］鞠文波．熱軋帶鋼軋制批量計劃軟件系統開發與研究［D］．大連:大連理工大學，2005．

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

［7］王凌．智能優化算法及其應用［M］．北京:清華大學出版社&施普林格出版社，2001．

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

［9］孫延．基于蟻群算法的紡織企業生產調度技術研究［J］．電子設計工程，2015（18）:116-118．

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

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

［12］祁金佺．遺傳蟻群算法在軟件測試用例生成中的應用［J］．工業儀表與自動化裝置，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，Fushun 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

國家自然科學基金項目（61203021）

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