改進模擬退火算法求解煤場配煤優化問題

屈國強

（河南理工大學　經濟管理學院，河南　焦作　454000）

改進模擬退火算法求解煤場配煤優化問題

屈國強

（河南理工大學經濟管理學院，河南焦作454000）

從混煤與單煤特性參數之間呈線性關系出發，不考慮優質煤種的使用限制，建立了煤場配煤優化問題的數學模型。在此基礎上，通過把此問題歸結為多維背包問題，表明其求解性質是NP-難的。為充分利用鄰域信息，在模擬退火算法中嵌入鄰域搜索，促使算法加快收斂。數據試驗表明改進算法是有效的。

煤場；配煤；模擬退火算法

1　引言

我國煤炭產需呈逆向分布，形成“西煤東調”和“北煤南運”，大部分煤炭需要經過長途運輸才能到達消費地。同時，由于賦存各異，不同煤礦的煤質也不相同，單一煤種往往不能滿足用戶的要求。這就需要通過配煤，將煤場庫存的、不同的煤炭按一定比例進行摻配，即滿足用戶要求，又可揚長避短、物盡其用。

文獻［1］指出水分、灰分、揮發分、硫分、發熱量是評價煤質的主要指標，是計算配比的基礎。關于配煤與單煤這幾個主要指標之間是否具有線性可加性，目前有三種觀點。第一種認為主要指標之間具有線性可加性。文獻［2］從工業分析的角度，實驗表明水分、灰分、揮發分、硫分、發熱量分析基具有線性可加性。文獻［3］作為動力配煤的指導原則，指出灰分、揮發分、發熱量、硫分收到基4個指標可以線性加權計算。文獻［4］對于國家標準《動力配煤規范》進行了解析，認為煤炭的常規指標灰分、揮發分、硫分、發熱量具有較好的線性可加性。以此為基礎，文獻［3］建立了以發熱量等為約束的線性規劃模型，采用LINGO軟件求解。文獻［5］在遺傳算法中嵌入模擬退火求解。文獻［6］用加權系數法將煤質主要指標作為目標函數，轉換為單目標函數后用粒子群算法求解。

第二種觀點認為主要指標之間呈現非線性關系。文獻［7］利用RBF神經網絡建立配煤煤質預測模型，采用基于自適應罰函數的正交遺傳算法優化。文獻［8］采用Elman神經網絡預測配煤煤質后引入模擬退化算法求解。文獻［9］用BP人工神經網絡實現煤質信息的非線性映射，采用均勻設計建立適應度函數，利用遺傳算法尋優。

第三種觀點認為主要指標之間呈現線性與非線性加權關系尚不明確。文獻［10］認為在煤質參數隨機波動的不確定條件下，采用確定性動力配煤模型很難保證實際配煤的產品質量。因而采用區間規劃與機會約束規劃相結合，建立一個不確定性機會約束的非線性優化的配煤優化模型，然后轉化為2個確定性子模型求解。文獻［11］回避混煤與組成單煤特性參數之間的關系，采用帶精英策略的非支配排序遺傳算法求解。文獻［12］將灰分誤差最小等作為約束條件，運用加權平均將約束條件轉化為單目標函數，采用協同量子粒子群算法尋優。

此外，文獻［13］指出根據煤炭混合性質及行業慣例，一般選取3種煤摻配。文獻［14］指出已有算法只能對摻配比例而不能對摻配煤種進行優化。文獻［15］指出實際應用時要求穩定、準確和實時，當問題規模較大時，啟發式算法或智能優化算法成為必然選擇。文獻［16］指出對于混煤煤質分析數據一般采用算數加權平均計算或試驗獲得，在缺乏混煤試驗數據的情況下成為當然的選擇。

2　問題描述及其模型

2.1問題描述

某煤場有m種單煤，其中單煤i（i=1，2，…，m）低位發熱量、硫排放、收到基水分、收到基灰分和收到基揮發份分別是Qnet，i、Sar，i、Mar，i、Aar，i、和Var，i，重量和價格分別是Wi和Pi。現接到1份訂單，這份訂單要求的低位發熱量、硫排放、收到基水分、收到基灰分和收到基揮發份分別是Qnet'、Sar'、Mar'、Aar'和Var'，重量是W'。由于配煤工藝限制，只能從m種單煤中最多選擇b種單煤摻配，確定這b種單煤的摻配比例xi，使得配煤滿足訂單要求，且成本最小。

一般情況下，煤場庫存各種單煤的數量都是較大的。為使問題簡化，這里假設庫存各種單煤的重量Wi遠遠超過訂單要求的重量W'。

2.2數學模型

目標函數（1）表示最小化配煤的成本。約束條件（2）表示摻配的單煤種類限制，最多選擇3種單煤進行參配，其中[xi]表示大于或等于xi的最小整數；約束條件（3）表示比例約束，構成訂單的各種摻配煤的比例之和等于1；約束條件（4）、（5）和（6）分別表示混煤的硫排放、收到基水分、收到基灰分不能超過訂單的要求；約束條件（7）和（8）分別表示混煤的收到基揮發份和低位發熱量不能低于訂單的要求；約束條件（9）表示庫存各種單煤的數量遠遠超過訂單要求的數量；約束條件（10）表示決策變量xi取值范圍，其中xi=1表示訂單全部由單煤i組成，xi=0表示單煤i不參與摻配。

在上述模型中，決策變量xi共有m個。其中，最多有m-1個決策變量取0，最少有m-b個決策變量取0；最多有b個、最少有0個決策變量取值大于零且小于1；最多有1個決策變量取值等于1。因此，這是一個混合整數線性規劃模型。

假設已經選定了b種煤進行摻配，則上述模型退化為一個線性規劃模型，較易求解。因此，上述模型求解的難點在于如何在m個決策變量中選出符合約束要求的b個非零的決策變量。

2.3背包問題與所求問題計算性質n

2.3.1背包問題。假定有n個物體和一個背包，物體i有質量wi，價值為pi，而背包的載荷能力為M。若將物體i的一部分xi（1≤i≤n，0≤xi≤1）裝入背包中，則有價值在約束條件下，使目標函數極大，此處0≤xi≤1，pi＞0，1≤i≤n。這個問題稱為背包問題（knapsack problem，KP）［17］。

2.3.2問題計算性質

性質：煤場配煤優化問題的計算性質是NP-難的。

證明：在煤場配煤優化問題中，可以把每種單煤映射為一個物體，單煤的硫分、水分、灰分、揮發份和發熱量分別映射為這個物體屬性的5個維度。同時，把訂單映射為一個背包，訂單的硫分、水分、灰分、揮發份和發熱量分別映射為裝入背包后物品5個維度累積的約束，訂單的重量映射為這個背包的載荷能力。這樣，煤場配煤優化問題就可以映射為5維約束的背包問題。

多維背包問題是典型的組合優化問題，計算性質是NP-難的，煤場配煤優化問題的計算性質必然也是NP-難的。

3　算法實現步驟

模擬退火（Simulated Annealing，SA）算法是基于Mente Carlo迭代求解的一種全局概率型搜索算法，是對鄰域搜索算法的擴展。與一般鄰域搜索算法不同，SA算法以一定的概率選擇鄰域中目標值相對較小的狀態，能夠在多項式時間內給出一個近似最優解［18］。當待解決的問題復雜性較高而且規模較大時，特別是對問題的鄰域知識了解甚少的情況下，采用SA算法最合適。

（1）初始解生成方法。為了增強初始解的隨機性及克服初值依賴性，在所有摻配煤種中，隨機選取3種煤生成初始解。這個初始解可能是可行解，也可能是非可行解。但是，隨著迭代的進行，非可行解將逐漸被淘汰，搜索的區域將逐漸集中到可行解分布的區域。

（2）鄰域策略。采用交換的策略產生鄰域解。例如，在一次鄰域搜索過程中，當前解摻配煤種是（2，5，8），未參與配煤的煤種是（1，3，4，6，7，9，10）。取出煤種2，分別放入煤種1、3、4、6、7、9和10，構成了摻配煤種（2，5，8）的7個鄰域解，類似的鄰域解共有21個。對于不滿足約束，即不滿足訂單要求的非可行解，不再搜索其鄰域，使搜索空間減小，加快搜索進程。

（3）新解產生機制。新解的產生分兩步進行：

第一步：為加快收斂速度，找到局部最優解，搜索當前解的7個鄰域，若目標函數有改進，則替換為新的當前解；否則不替換。

第二步：為增強新解的隨機性，避免陷入局部最優，在當前解的基礎上，隨機取出一種摻配煤種，再隨機放入一種未摻配煤種。若目標函數有改進，則替換為新的當前解；否則采用Metropolis準則確定是否接受這個新解。即若min｛1，exp（-Δprice/t）｝＞random［0，1］，則接受；否則拒絕。其中，Δprice是當前配煤方案和新產生的配煤方案的成本差，t是當前溫度。

（4）降溫方法

①初始溫度。初始溫度的確定應折中考慮優化質量和優化效率。為此，采用t0=-（Pricemax-Pricemin）/log10pr計算初始溫度。其中，Pricemax和Pricemin分別是摻配煤種的最高和最低價格，pr是初始接受概率。

②降溫函數。采用的降溫函數是Tk+1=Tk·r，其中，r是降溫系數。

③每一溫度迭代步長。采用固定的迭代步長l，迭代步長等于摻配煤種數。

（5）終止準則。在相同的溫度內，得到的當前解連續若干步迭代沒有改進，或溫度下降到終止溫度，迭代終止。本文確定的沒有改進的迭代步長等于摻配煤種數。

上述算法涉及到的參數包括初始溫度t0、初始接受概率pr、降溫系數r、迭代步長l、在相同溫度內得到的當前解沒有改進的連續迭代步數d、終止溫度tmin。

4　計算試驗與分析

采用MATLAB2013a在IntelCore/i5-3470/CPU3.0GHz/ RAM4.0GB上編程試驗。

4.1計算數據

截止目前，煤場配煤優化問題尚沒有一個統一的比較算例，本文采用文獻［19］中10種原煤的數據進行計算說明。訂單要求：Qnet'≥23.0MJ/kg，Var'≥25% ，Sar'≤1.0%，Mar'≤10%，Aar'≤30%。

采用窮舉法計算，得知：（1）解空間大小為720個，實際上不可行解有40個，可行解有34個。其中，一種煤直接銷售的可行解有2個，2種和3種煤摻配的可行解分別有17個和15個。（2）最優解僅有一個，由煤種3、7、9按13.75%、22.67%和63.57%摻配，成本287.491 0，Qnet'=24.4MJ/kg，Var'=25.0%，Sar'=1.0%，Mar'=2.5%，Aar'=19.7%。（3）平均耗時5.99s。

4.2計算結果與分析

目前，SA算法參數的確定沒有一個統一的方法，參數的選擇仍然依賴于一些啟發式準則和待求解問題的性質。結合實際問題數據，經過多次計算和試驗，設定參數如下：t0=65、pr=0.1、r=0.9、l=10、tmin=0.1，d=10。

為簡便起見，將上述算法命名為SA1。作為對比，將SA1中去掉鄰域搜索部分的算法命名為SA2。

在相同條件下，采用SA1和SA2分別進行10輪試驗，每輪試驗進行200次，每次試驗均找到了最優解。實驗結果見表1。可以看到，SA1比SA2平均耗時降低56.35%，標準差降低69.10%，表明SA1比SA2計算速度快且穩定。

究其原因，SA2在產生新解的時候，沒有利用任何當前解鄰域的信息，進行的是“盲跳”；SA1則充分利用了當前解交換鄰域的信息，對當前解的交換鄰域進行了系統的搜索，找到局部最優解，促使SA算法從一個目標函數更小的區域“起跳”，“下山”速度加快了。因此，SA1計算速度更快且穩定性提高了。

表1　SA1和SA2計算耗時（單位：s）

5　結束語

優化配煤即可以滿足客戶需求、提高經濟效益，又可以促進配煤理論的發展，具有一定的實踐價值和理論意義。本文把煤場配煤優化問題歸結為多維背包問題，表明其求解性質是NP-難的。為充分利用鄰域信息，在SA算法中嵌入鄰域搜索，促使SA算法加快收斂。下一步將重點研究面向多訂單的煤場配煤優化問題及其高效算法。

［1］戴財勝.動力配煤的理論與應用研究［D］.北京:中國礦業大學（北京校區），2000.

［2］陳亞飛，陳懷珍，崔風海.煤炭行業標準《動力配煤導則》［J］.煤質技術，2006，（5）:17-19.

［3］姜英.國家標準《動力配煤規范》的制定與實施［J］.煤質技術，2012，（1）:1-3.

［4］郭德銘.平頂山煤業集團配煤優化方案研究［D］.北京:北京交通大學，2009.

［5］Xi J G，Ming C，Jia W W.Coal blending optimization of coal preparation production process based on improved GA［J］. Procedia Earth and Planetary science，2009，（1）:654-660.

［6］劉永江，高正平，韓義，等.基于粒子群算法的火電廠優化配煤研究［J］.鍋爐技術，2012，43（5）:18-24.

［7］夏季，陸攀，華志剛，等.電站鍋爐全局優化智能配煤模型的建立及系統開發［J］.動力工程學報，2010，30（7）:512-517.

［8］劉艷軍.電廠動力配煤煤質預測模型與優化模型研究［D］.長沙:中南大學，2011.

［9］劉玉嬌，張海英，關海盈.基于多種算法的多目標配煤優化方法［J］.熱力發電，2014，43（9）:108-112.

［10］張曉萱，黃國和，席北斗，等.電廠優化的不確定性機會約束非線性規劃方法［J］.中國機電工程學報，2009，29（5）:11-15.

［11］夏季，華志剛，彭鵬，等.基于非支配排序遺傳算法的無約束多目標優化配煤模型［J］.中國機電工程學報，2011，31（2）:85-90.

［12］董虎勝，陸萍，鐘寶江.基于協同量子粒子群的自動配煤系統研究［J］.制造業自動化，2014，36（1）:74-77.

［13］劉麗敏.肥城煤炭配送中心配煤模型研究［D］.青島:山東科技大學，2011.

［14］孫云峰，王國華.一種新型煤炭物流節點-“煤炭超市”的生產計劃建模［J］.物流技術，2007，26（11）:94-96.

［15］周俊虎，沈彬彬，陳寅彪，等.基于遺傳算法的動力配煤的Boltzmann優化模型的研究［J］.動力工程，2003，23（4）:547-551.

［16］阮偉，周俊虎，湯龍華，等.優化配煤理論的研究以及配煤專家系統多目的開發［J］.動力工程，1999，19（6）:434-437.

［17］宋文，吳晟，杜亞軍.算法設計與分析［M］.重慶:重慶大學出版社，2001.

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

［19］殷春根，周俊虎，駱仲泱，等.人工神經網絡方法在優化動力配煤中的應用研究［J］.煤炭學報，1997，22（4）:343-348.

Solution of Coal Yard Scheduling Optimization Problem Using Improved Simulated Annealing Algorithm

Qu Guoqiang
（School of Economics&Management，Henan Polytechnic University，Jiaozuo 454000，China）

In this paper，we established the mathematical model for the optimization of the coal yard scheduling problem without considering the limitation for the use of the high-quality coal varieties.Then on such basis，we classified the problem as a multi-dimensional packing problem and demonstrated that it was a NP-hard problem.Next，we incorporated the neighborhood search algorithm into the simulated annealing algorithm to accelerate its convergence.A numerical example at the end showed that the algorithm was effective.

coal yard；coal scheduling；simulated annealing algorithm

TQ520.62；F224

A

1005-152X（2016）06-0090-04

10.3969/j.issn.1005-152X.2016.06.020

2016-04-12

國家自然科學基金“科學采礦視域中我國煤炭成本缺失與完全補償的理論與實證研究”（51304066）；河南省政府決策研究招標一般課題“新常態視閾下河南先進制造業發展模式和路徑選擇研究”（2015B117）；河南省教育廳科學技術研究重點項目軟科學計劃項目“煤炭供應鏈構建及其計劃與調度優化研究”（14B630009）；河南理工大學博士基金項目“面向訂單的煤炭供應鏈計劃與調度智能優化研究”（SZB2013-34）

屈國強（1970-），男，河南義馬人，博士，講師，碩士生導師，主要研究方向：煤炭物流與供應鏈、生產計劃與調度、智能優化算法等。