王志文, 鞏旭鵬, 孫洪濤, 胡績(jī)強(qiáng)

(1. 蘭州理工大學(xué) 電氣工程與信息工程學(xué)院, 甘肅 蘭州 730050; 2. 蘭州理工大學(xué) 甘肅省工業(yè)控制先進(jìn)控制重點(diǎn)實(shí)驗(yàn)室, 甘肅 蘭州 730050; 3. 蘭州理工大學(xué) 電氣與控制工程國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心, 甘肅 蘭州 730050; 4. 曲阜師范大學(xué) 工學(xué)院, 山東 曲阜 273100)

礦山開采作業(yè)是一個(gè)以采掘?yàn)橹行?、運(yùn)輸為紐帶的大型生產(chǎn)系統(tǒng).礦產(chǎn)資源是一種不可再生資源,近年來隨著經(jīng)濟(jì)下行和礦產(chǎn)資源的逐漸枯竭,礦山必須采用高效節(jié)約的生產(chǎn)方式進(jìn)行開采生產(chǎn).信息化的不斷發(fā)展,為礦山的智能化開采提供了支持,而生產(chǎn)調(diào)度在礦山的智能化中占據(jù)著重要的部分,它是資源合理利用的重要途徑之一.

在礦山的生產(chǎn)調(diào)度中,主要使用采裝和運(yùn)輸設(shè)備來完成.目前對(duì)礦山生產(chǎn)調(diào)度模型的求解主要有兩種方式,其一是數(shù)學(xué)規(guī)劃方法,主要由整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃等方法組成.這些方法存在一定的缺陷,如目標(biāo)函數(shù)單一且對(duì)多約束問題模型求解困難,導(dǎo)致在實(shí)際應(yīng)用中存在不足.而相較于數(shù)學(xué)方法,智能優(yōu)化算法在求解相應(yīng)的模型時(shí)優(yōu)勢(shì)明顯.近年來,智能算法在礦山生產(chǎn)中應(yīng)用極為廣泛.Gilani等[1]介紹了露天礦長(zhǎng)期生產(chǎn)計(jì)劃(LTPP)的組合優(yōu)化問題,以凈現(xiàn)值(NPV)最大化為目標(biāo),在滿足約束條件下采用啟發(fā)式算法進(jìn)行研究.在露天礦開采過程中,考慮礦山可達(dá)到的最大凈現(xiàn)值來優(yōu)化品位是露天礦開采的關(guān)鍵問題之一.Ahmadi等[2]采用兩種不同的元啟發(fā)式優(yōu)化算法來確定最優(yōu)品位.尋找露天礦生產(chǎn)調(diào)度問題的最優(yōu)解是礦業(yè)界公認(rèn)的具有挑戰(zhàn)性的問題之一.Elsayed等[3]提出了一種基于差分進(jìn)化的方法和修復(fù)機(jī)制,保證了算法的可行性,并結(jié)合局部搜索技術(shù)來提高算法的性能.Paithankar等[4]使用最大流量演算法與遺傳演算法來產(chǎn)生長(zhǎng)期的生產(chǎn)調(diào)度.在不確定條件下,建立了多時(shí)段最大流量的圖結(jié)構(gòu),并用遺傳算法控制弧內(nèi)流量,以制定生產(chǎn)計(jì)劃.劉文博等[5]根據(jù)實(shí)際生產(chǎn)過程特點(diǎn),建立了規(guī)整性的開采調(diào)度問題模型,并結(jié)合拉格朗日松弛算法和啟發(fā)式算法進(jìn)行求解.

目前大多數(shù)的算法針對(duì)單一目標(biāo)函數(shù),算法的收斂性和準(zhǔn)確性有待提高,且應(yīng)用到礦山生產(chǎn)調(diào)度中不利于獲得最優(yōu)解,降低了開采效率.針對(duì)以上問題,本文提出一種改進(jìn)的遺傳算法,以采掘最小成本和礦山最小運(yùn)輸費(fèi)用為目標(biāo),構(gòu)建多目標(biāo)生產(chǎn)模型,實(shí)現(xiàn)多出礦點(diǎn)協(xié)調(diào)生產(chǎn)調(diào)度的優(yōu)化.

1 礦山多目標(biāo)生產(chǎn)計(jì)劃模型

露天礦的運(yùn)輸方式多種多樣,主要包括卡車運(yùn)輸、軌道運(yùn)輸以及多種方式聯(lián)合運(yùn)輸.卡車運(yùn)輸以其靈活性強(qiáng)等優(yōu)點(diǎn)得到廣泛應(yīng)用，其整個(gè)運(yùn)輸過程是將每個(gè)鏟位的礦石和巖石運(yùn)送到相應(yīng)的卸點(diǎn).礦石的卸點(diǎn)有礦石漏和倒裝場(chǎng),巖石的卸點(diǎn)有巖石漏和巖場(chǎng).

本文假設(shè)該礦區(qū)有8個(gè)出礦點(diǎn),卡車將各出礦點(diǎn)的礦石和巖石運(yùn)輸?shù)较鄳?yīng)的卸點(diǎn).定義其生產(chǎn)調(diào)度標(biāo)準(zhǔn)集合B={Dij,Nij,Mij},分別代表出礦點(diǎn)到卸點(diǎn)的距離、出礦點(diǎn)到卸點(diǎn)的最大運(yùn)輸次數(shù)、運(yùn)輸費(fèi)用.卡車運(yùn)輸線路分布如圖1所示.

圖1 卡車運(yùn)輸路線Fig.1 Truck transportation route

本文所建立的模型是以礦山的采掘成本和卡車的運(yùn)輸費(fèi)用最小為目標(biāo),并對(duì)卸點(diǎn)礦石漏、倒排場(chǎng)1、倒排場(chǎng)2、巖石漏和巖場(chǎng)依次編號(hào)為1、2、3、4、5,建立數(shù)學(xué)模型如下：

(3)

其中：α+β=1,α、β為線性加權(quán)系數(shù),根據(jù)實(shí)際情況確定其數(shù)值；C為卡車總費(fèi)用;C1為卡車運(yùn)輸費(fèi)用;C2為礦山生產(chǎn)成本；ci為出礦點(diǎn)i采掘成本；xi為第i個(gè)采點(diǎn)的出礦量；Xij為出礦點(diǎn)i到卸點(diǎn)j的卡車數(shù)量(單位：輛；i=1,2,…,8；j=1,2,…,5)；Dij為出礦點(diǎn)i到卸點(diǎn)j的距離(單位：千米；i=1,2,…,8；j=1,2,…,5)；Nij為出礦點(diǎn)i到卸點(diǎn)j的最大運(yùn)輸次數(shù)(i=1,2,…,8；j=1,2,…,5)；Mij為出礦點(diǎn)i到卸點(diǎn)j的費(fèi)用(單位：元/千米·輛).

其中：n為出礦點(diǎn)個(gè)數(shù);L為卡車的載重量,噸；pi為出礦點(diǎn)i的礦石質(zhì)量分?jǐn)?shù);Pj為卸點(diǎn)j的需求量,噸；qi，min、qi，max分別為出礦點(diǎn)i的最低出礦量和最高出礦量.

2 遺傳算法及其改進(jìn)策略

遺傳算法是一種基于生物自然選擇與遺傳機(jī)理的隨機(jī)搜索與優(yōu)化方法[6],在很多方面都有廣泛的應(yīng)用[7].但是該算法存在諸多不足,如算法參數(shù)要求高,收斂速度慢且容易陷入局部最優(yōu)[8].

因此,許多學(xué)者研究改進(jìn)標(biāo)準(zhǔn)遺傳算法,以此來彌補(bǔ)算法存在的缺陷.仲兆滿等[9]通過改變種群的規(guī)模來減少近親的交配.Goldberg等[10]提出一種間接性交配策略避免近親雜交.Strickberger和任芳等[11-12]根據(jù)表現(xiàn)型的相似與否來選擇交配的對(duì)象,即選型交配這一策略避免近親雜交.吉根林[13]將遺傳算法與爬山算法相結(jié)合,提出自適應(yīng)變異概率的優(yōu)化算法.張超群等[14]提出動(dòng)態(tài)參數(shù)編碼,即動(dòng)態(tài)地改變參變量的定義域,有更好的搜索范圍來克服二進(jìn)制編碼帶來的精度與效率不高,且過早收斂的問題.牛琳[15]針對(duì)柔性作業(yè)車間調(diào)度中遺傳算法局部收斂的問題,結(jié)合柔性作業(yè)車間調(diào)度的特點(diǎn),采用模擬退火算法融合遺傳算法對(duì)調(diào)度領(lǐng)域進(jìn)行了研究.楊進(jìn)帥等[16]通過定義多目標(biāo)規(guī)劃的非隸屬度,調(diào)節(jié)控制參數(shù)來增強(qiáng)局部搜索能力,指導(dǎo)個(gè)體尋找最優(yōu)值.

本文首先給出近親度的判別式,在此基礎(chǔ)上引入異種機(jī)制,避免了父代之間的近親雜交,得到更優(yōu)良的子代.

2.1 基于禁止近親雜交的算法

在基因進(jìn)行交叉過程中,標(biāo)準(zhǔn)遺傳算法的交叉概率一般為給定的,這忽略了個(gè)體之間的相似度,并使得父代的優(yōu)秀基因遭到破壞,導(dǎo)致算法不能收斂或出現(xiàn)局部收斂的情況.為了解決該問題,本文在此引入近親度的概念,提出一種禁止近親雜交的自適應(yīng)遺傳算法(adaptive genetic algorithm,AGA).

在遺傳算法的后期,近親個(gè)體間的雜交會(huì)導(dǎo)致種群多樣性的破壞,進(jìn)而使算法收斂速率降低甚至不能收斂.因此本文引入近親度這一概念,并給出了判斷相似度的函數(shù)和閾值.根據(jù)這一標(biāo)準(zhǔn)對(duì)雙親進(jìn)行篩選,如若超出閾值,則強(qiáng)行淘汰其中一方,重新選擇配對(duì)方[17].相似度定義如下：

定義其在n維空間中的距離為

(9)

(10)

如果p(T)大于算法給定的近親繁殖判據(jù)pb,則認(rèn)為第T代種群發(fā)生了近親繁殖.即近親繁殖的判別式為

(11)

相似度能夠更直觀地反應(yīng)個(gè)體之間的差異,為了明確這種差異是否需要進(jìn)行變異,可引入交叉臨界值.如果相似度值小于該值,則說明將要雜交的個(gè)體為近親,繼而重新選擇交叉的個(gè)體,這樣就避免了由于近親雜交而產(chǎn)生不良個(gè)體,保證遺傳操作的正常進(jìn)行.

2.2 最優(yōu)保持策略

在遺傳優(yōu)化過程中,理論上來說遺傳算子和選擇機(jī)制可以使子代的平均適應(yīng)度高于父代.但由于遺傳算法的不確定性,子代中的最優(yōu)個(gè)體并不總是優(yōu)于父代中的最優(yōu)個(gè)體.為提高優(yōu)化效率,保證算法能夠更加精確地收斂于全局最優(yōu)解,本文引入了最優(yōu)保持策略.具體的操作方法是在選擇的過程中,允許父代和子代競(jìng)爭(zhēng),使適應(yīng)度較高的個(gè)體具有較大的生存概率,確保能夠進(jìn)入下一次循環(huán)繼續(xù)參加遺傳優(yōu)化過程.

最優(yōu)保持策略的作用是顯而易見的.根據(jù)遺傳算法的模式定理,采用最優(yōu)保持策略的簡(jiǎn)單遺傳算法可以概率收斂于全局最優(yōu)解,而不采用最優(yōu)保持策略的簡(jiǎn)單遺傳算法則不能以概率收斂于全局最優(yōu)解.由此可見最優(yōu)保持策略的重要性.

2.3 異種機(jī)制

變異算子在遺傳算法中是一個(gè)很重要的因素.如果變異概率選擇過大,則會(huì)破壞算法的穩(wěn)定性；如果選擇過小,則會(huì)影響種群多樣性的保持.

事實(shí)上,自適應(yīng)隨機(jī)變異的實(shí)質(zhì)都是根據(jù)從優(yōu)化過程中反饋回來的適應(yīng)度函數(shù)信息,不斷縮小搜索范圍,進(jìn)而求得最優(yōu)解.這有利于算法的迅速收斂,但也增大了近親繁殖的概率.為解決這一問題,本文探索性地提出了異種機(jī)制以防止早熟收斂,提高收斂效率.

異種機(jī)制即是在遺傳優(yōu)化過程中擴(kuò)大其搜索范圍,選擇搜索范圍之外的種子進(jìn)入到算法中,進(jìn)而增加種群的多樣性.它模擬的是人工干預(yù)物種進(jìn)化,獲取優(yōu)良物種的過程.其作用機(jī)理是：

1) 對(duì)遺傳優(yōu)化過程進(jìn)行監(jiān)控,若發(fā)生了近親繁殖,則啟動(dòng)異種機(jī)制；

2) 在縮小了的搜索范圍之外選擇數(shù)個(gè)異種,用以代替現(xiàn)有種群中適應(yīng)度較低的個(gè)體；

3) 將加入異種的現(xiàn)有種群生成子代,再進(jìn)行下一次循環(huán).

2.4 異種的選取

異種的選取方法有兩種：一種是不考慮近親繁殖本身的特點(diǎn),在近親繁殖個(gè)體所在的鄰域內(nèi)完全隨機(jī)地選擇；另一種則是考慮近親繁殖發(fā)生的特點(diǎn),根據(jù)近親繁殖的趨勢(shì)選擇異種的方法.

(12)

隨機(jī)選取異種的方法與變異操作相類似,即：

(13)

其中：τ是在[-1,1]上取值的隨機(jī)數(shù)；bh是異種機(jī)制的最大突變半徑.

為使異種的選取具備自適應(yīng)變焦的能力,可將bh取為當(dāng)前繁殖代數(shù)T的函數(shù)：

(14)

其中:bhs、bhl是第k個(gè)設(shè)計(jì)變量在遺傳優(yōu)化過程中選取異種的上界和下界.

用這種方法得到的異種是：

(15)

2.5 終止條件

GA算法的終止條件也是極為重要的一個(gè)因素.在算法收斂問題的判斷上,已有很深入的研究.Brest等[18]預(yù)先給定收斂代數(shù)來判斷終止與否；Pan和Zhang等[19-20]首先給定適應(yīng)度值,再依設(shè)定的閾值判斷適應(yīng)度值之間的差異是否達(dá)到收斂標(biāo)準(zhǔn).盡管這些標(biāo)準(zhǔn)都較為簡(jiǎn)單,易于操作,但是機(jī)械化比較嚴(yán)重,并不能根據(jù)實(shí)時(shí)情況作出判斷.

隨著演化的進(jìn)行,個(gè)體間的差異越來越小,所以近親度也成為一個(gè)重要的因素.

本文提出一種新的終止條件,即將近親度和種群聚集度相結(jié)合,這種方法具有自適應(yīng)性.本文中指標(biāo)滿足以下兩個(gè)條件時(shí),算法終止.

1) 種群聚集度：種群間的距離和適應(yīng)度之間的距離都在0.1%以內(nèi)；

2) 近親度p(T)：p(T)>99%.

算法流程如圖2所示.

圖2 AGA算法流程Fig.2 AGA algorithm flow

2.6 算法結(jié)果測(cè)試

本文選擇精英策略、輪盤賭選擇和二進(jìn)制編碼,所有的測(cè)試函數(shù)都被計(jì)算200次,設(shè)置種群規(guī)模為20.當(dāng)近親度大于設(shè)定閾值時(shí),禁止近親策略開始起作用.為了進(jìn)一步驗(yàn)證改進(jìn)算法,利用多個(gè)測(cè)試函數(shù)(見表1)主要比較全局收斂率、平均收斂代數(shù)、尋找到最優(yōu)值的平均值及其方差.

表1 測(cè)量函數(shù)

標(biāo)準(zhǔn)遺傳算法(SGA)和改進(jìn)自適應(yīng)遺傳算法(AGA)的性能比較如表2所列.可以看出,雖然種群規(guī)模較小,但是通過禁止近親策略改進(jìn)的AGA算法的收斂率有明顯提高.AGA算法計(jì)算出最優(yōu)值的平均值,更加接近最優(yōu)理論值,最優(yōu)值的方差也明顯減小.說明改進(jìn)的算法提高了算法的全局收斂率,在避免早熟方面起到了重要作用.

表2 數(shù)值計(jì)算結(jié)果

3 用遺傳算法求解調(diào)度模型

在采用染色體設(shè)計(jì)相應(yīng)的卡車數(shù)量時(shí),首先將染色體進(jìn)行初始化編碼,再依據(jù)本文提到的近親度判別式進(jìn)行判斷,如若種群沒有發(fā)生近親繁殖,則直接進(jìn)行解碼,得到調(diào)度方案；否則應(yīng)采用異種機(jī)制,避免近親繁殖,使其調(diào)度方案更接近實(shí)際要求.

3.1 染色體編碼

本文采用二進(jìn)制編碼方式,假設(shè)出礦點(diǎn)與卸點(diǎn)之間的卡車數(shù)量在8輛以內(nèi),對(duì)Xi1、Xi2、Xi3、Xi4、Xi5進(jìn)行編碼,則只需3位二進(jìn)制就可以表示所有的卡車數(shù),編碼如表3所列.

表3 編碼格式

露天礦中的出礦點(diǎn)由第一行表示,第二行代表各出礦點(diǎn)對(duì)應(yīng)的卸點(diǎn),第三行代表0-1變量.當(dāng)出礦點(diǎn)到卸點(diǎn)有卡車運(yùn)行時(shí),其3位二進(jìn)制編碼不為零,否則為零.如出礦點(diǎn)1到倒排場(chǎng)2被安排了5輛車,則Xi3對(duì)應(yīng)編碼為101.所顯示的不同的編碼代表不同的調(diào)度方式.

3.2 近親度判斷

3.3 染色體解碼

運(yùn)用遺傳算法將卡車調(diào)度進(jìn)行優(yōu)化得到最優(yōu)解,并轉(zhuǎn)換基因型為表現(xiàn)型.經(jīng)過遺傳操作,將得到的最優(yōu)染色體進(jìn)行解碼.首先對(duì)染色體從左到右每3位進(jìn)行分組,得到卡車數(shù)量.再將得到的10個(gè)分組每5個(gè)分為一組,則每一組代表一個(gè)出礦點(diǎn),即得到兩個(gè)出礦點(diǎn).每個(gè)3位二進(jìn)制數(shù)轉(zhuǎn)化成十進(jìn)制數(shù),即得到出礦點(diǎn)到卸點(diǎn)的卡車數(shù)量，如表4所列.

表4 染色體解碼

由表4中染色體可看出,鏟位1到礦石漏、倒排場(chǎng)1、倒排場(chǎng)2、巖場(chǎng)分派的卡車數(shù)量分別為5、3、5、1,到巖石漏沒有分派車輛.鏟位2到礦石漏、倒排場(chǎng)1、巖石漏和巖場(chǎng)分派的車輛數(shù),分別為6、2、4、3,到倒排場(chǎng)2沒有分派車輛.即可得到一種調(diào)度方案.

4 實(shí)驗(yàn)仿真與結(jié)果分析

4.1 各鏟位出礦量?jī)?yōu)化

已知該礦區(qū)有8個(gè)出礦點(diǎn),各鏟位礦石產(chǎn)量、礦石品位及其采掘成本如表5所列.算法參數(shù)設(shè)置與前文一致.在出礦生產(chǎn)中,出礦量指標(biāo)為1.5≤xi≤8(萬噸).將遺傳算法優(yōu)化前后各出礦點(diǎn)的出礦量進(jìn)行對(duì)比,如圖3所示.優(yōu)化后得到的出礦量為x=(6.34,4.26,5.04,4.05,3.56,2.82,5.32,2.98),出礦點(diǎn)總產(chǎn)量為34.37萬噸,相比于計(jì)劃產(chǎn)量28.42萬噸,優(yōu)化算法后得到的產(chǎn)量有顯著提高.

表5 各鏟位礦石產(chǎn)量和礦石品位

圖3 各出礦點(diǎn)出礦量?jī)?yōu)化前后對(duì)比Fig.3 Comparison before and after the optimization of ore drawing amount at each ore drawing point

4.2 目標(biāo)函數(shù)優(yōu)化

采用改進(jìn)遺傳算法及其標(biāo)準(zhǔn)遺傳算法對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化,經(jīng)過各代的逐次運(yùn)算,分別得到兩種算法的求解迭代曲線,如圖4所示.各出礦點(diǎn)到卸點(diǎn)的距離、最大車輛數(shù)即車次數(shù)據(jù)如表6和表7所列.

表6 各鏟位到各卸點(diǎn)之間的距離

表7 各鏟位到各卸點(diǎn)之間的車次

圖4 最優(yōu)適應(yīng)度值Fig.4 Optimal fitness value

由圖4可以看出，在遺傳算法的初始階段，迭代次數(shù)在10左右時(shí)，適應(yīng)度值曲線變動(dòng)較大，很快得到改善.在以后的各代中，AGA算法在120～130代之間開始趨于平穩(wěn)，驗(yàn)證了所改進(jìn)算法在解決礦山開采問題上的可行性；SGA算法在尋優(yōu)過程中會(huì)陷入局部最優(yōu)，而AGA算法相對(duì)于SGA算法有更好的尋優(yōu)結(jié)果,更符合所期望的目標(biāo)值.此外,在收斂時(shí)間方面,優(yōu)化后的算法消耗時(shí)間更短.進(jìn)一步驗(yàn)證了所提改進(jìn)算法的優(yōu)越性.

5 結(jié)論

本文綜合考慮實(shí)際礦山生產(chǎn)調(diào)度相關(guān)要素,以卡車運(yùn)輸和礦山開采成本最小為目標(biāo)函數(shù),考慮礦石品位等約束條件,構(gòu)建多目標(biāo)生產(chǎn)調(diào)度模型,提高礦山資源的合理利用.此外,本文提出的改進(jìn)算法具有較強(qiáng)的自適應(yīng)搜索和避免近親雜交的能力,保證了后代的優(yōu)良基因,增加了種群多樣性,改善了經(jīng)典遺傳算法的早熟停滯現(xiàn)象.為進(jìn)一步驗(yàn)證改進(jìn)算法,利用多個(gè)經(jīng)典函數(shù)測(cè)試其算法性能,結(jié)果顯示改進(jìn)算法的性能有了明顯提高.結(jié)合該改進(jìn)算法對(duì)礦山生產(chǎn)調(diào)度進(jìn)行深入分析,驗(yàn)證了改進(jìn)算法在該問題上的優(yōu)越性.最后依據(jù)礦山生產(chǎn)作業(yè)數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn),得到的各鏟位的出礦量和采掘、運(yùn)輸成本更符合礦山開采需求.

本文只在確定性條件下分析了礦山的生產(chǎn)調(diào)度,在以后的研究中,應(yīng)將不確定因素考慮進(jìn)來,實(shí)現(xiàn)生產(chǎn)調(diào)度對(duì)隨機(jī)因素的實(shí)時(shí)管控.

致謝：本文得到甘肅省工業(yè)控制先進(jìn)控制重點(diǎn)實(shí)驗(yàn)室開放基金(2019KFJJ03)項(xiàng)目的資助，在此表示感謝.