新型災(zāi)變自適應(yīng)遺傳算法及其應(yīng)用①

王 策,董兆偉,孫立輝,姜軍強(qiáng),史振杰,武曉婧

(河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院,石家莊 453000)

當(dāng)前解決工業(yè)生產(chǎn)當(dāng)中最優(yōu)化問題較為熱門的算法就是以遺傳算法為代表的智能優(yōu)化算法.遺傳算法以“優(yōu)勝劣汰”的自然選擇和基因階段的遺傳變異原理作為基礎(chǔ),是一種具有很強(qiáng)的隨機(jī)搜索能力的智能算法[1].在解決多種復(fù)雜約束條件的尋優(yōu)問題時(shí),可以取得很好的搜索效果.但是在工業(yè)生產(chǎn)當(dāng)中,對(duì)算法的運(yùn)行時(shí)間要求較為苛刻,算法當(dāng)中的種群數(shù)目較少,在隨機(jī)生成種群時(shí)個(gè)體很難遍布所有極值范圍附近.在前期的全局搜索過程中,該算法很容易陷入局部最優(yōu),從而無法對(duì)其他優(yōu)秀解集區(qū)域進(jìn)行搜索,并且隨著遺傳操作的不斷進(jìn)行,種群中的個(gè)體多樣性將會(huì)不斷降低.因此解決遺傳算法的“早熟”現(xiàn)象成為算法改進(jìn)的主要方向.

為了解決“早熟”問題,在遺傳算法當(dāng)中添加了災(zāi)變操作,利用了災(zāi)變作用提高種群在遺傳操作過程中全局搜索性能[2].利用自適應(yīng)遺傳算法中交叉概率和變異概率隨進(jìn)化代數(shù)自適應(yīng)調(diào)整的原理,將交叉操作和變異操作隨災(zāi)變周期進(jìn)行自適應(yīng)調(diào)整[3],在災(zāi)變完成之后,提高個(gè)體的變異能力,增強(qiáng)了算法的局部尋優(yōu)能力.將該算法應(yīng)用于燒結(jié)配礦系統(tǒng)的建立,利用生產(chǎn)數(shù)據(jù)進(jìn)行檢驗(yàn),證明了該算法可以搜尋到極為穩(wěn)定且成本最優(yōu)的配礦方案.

1 算法改進(jìn)措施

通過大量的實(shí)驗(yàn)分析可得,在解決具有多變量的最優(yōu)化問題時(shí),遺傳算法很容易因?yàn)檫z傳算法的特性造成“早熟”現(xiàn)象.為了降低種群“早熟”現(xiàn)象的發(fā)生,該模型在傳統(tǒng)遺傳操作過程當(dāng)中添加了災(zāi)變操作.災(zāi)變主要是模擬生物進(jìn)化過程中導(dǎo)致大量物種滅絕而個(gè)別物種生存的現(xiàn)象[4].在本算法中災(zāi)變操作周期性地強(qiáng)行對(duì)大部分個(gè)體進(jìn)行初始化,保留一定量的舊種群個(gè)體指導(dǎo)種群的搜索趨勢(shì),并且在遺傳操作中配合災(zāi)變操作的周期性變化進(jìn)行自適應(yīng)調(diào)整,增強(qiáng)算法在后期種群個(gè)體相似度較高的時(shí)候搜索能力.

(1) 災(zāi)變操作

初始遺傳種群的獲得是通過未知量范圍內(nèi)的隨機(jī)產(chǎn)生獲得的,假設(shè)一個(gè)種群遺傳操作的代數(shù)為M時(shí)會(huì)使種群個(gè)體穩(wěn)定,當(dāng)遺傳操作到m(m＜M)代之后,大多數(shù)個(gè)體與最優(yōu)個(gè)體相似度較高,只有適應(yīng)度較高的個(gè)體與最優(yōu)個(gè)體相似度較低,此時(shí)將當(dāng)前種群狀態(tài)和最優(yōu)個(gè)體及其適應(yīng)度進(jìn)行保存,將種群中大多數(shù)適應(yīng)度優(yōu)秀的個(gè)體進(jìn)行刪除,隨機(jī)產(chǎn)生新的個(gè)體進(jìn)行補(bǔ)充,只保留數(shù)量較少的原種群中適應(yīng)度最差的個(gè)體保留之前的優(yōu)秀種群特征組成新種群,進(jìn)行新一輪的搜索,以此增大種群的多樣性和搜索范圍,而災(zāi)變之后保留的舊種群個(gè)體由于本身處于較為優(yōu)秀的尋優(yōu)范圍內(nèi)會(huì)對(duì)新種群個(gè)體的搜索提供收斂趨勢(shì)的引導(dǎo).本次尋優(yōu)算法主要進(jìn)行多次災(zāi)變操作,并且當(dāng)前一代災(zāi)變操作未能產(chǎn)生更為優(yōu)秀個(gè)體時(shí)增大隨機(jī)個(gè)體對(duì)進(jìn)行災(zāi)變操作的種群個(gè)體的取代數(shù)量.將種群重復(fù)m代的遺傳操作,當(dāng)災(zāi)變操作完成時(shí),種群替換為n次災(zāi)變效果中取得最優(yōu)秀個(gè)體的種群,繼續(xù)完成剩下的遺傳操作,災(zāi)變操作具體步驟如下所示.

① 對(duì)第i代種群進(jìn)行判斷,如果為第一代種群,即初始種群,將該種群作為災(zāi)變保留種群進(jìn)行保存,將該種群中的適應(yīng)度最優(yōu)個(gè)體作為災(zāi)變最佳個(gè)體進(jìn)行保存,然后進(jìn)行遺傳操作.判斷代數(shù)i是否處于災(zāi)變截止代數(shù)N×m內(nèi),如果是則進(jìn)入步驟②,如果進(jìn)化代數(shù)i不處于災(zāi)變截止代數(shù)內(nèi)則繼續(xù)進(jìn)行遺傳操作.

② 判斷種群進(jìn)化代數(shù)i是否為設(shè)定的災(zāi)變操作代數(shù),如果是則進(jìn)入步驟③,否則繼續(xù)進(jìn)行遺傳操作.

③ 當(dāng)判斷為災(zāi)變操作代數(shù)時(shí),將當(dāng)前進(jìn)化過m代之后的種群中的全局最佳適應(yīng)度與災(zāi)變最佳個(gè)體的適應(yīng)度進(jìn)行比較,如果全局最佳適應(yīng)度更加優(yōu)秀,則將該全局最佳個(gè)體作為新的災(zāi)變最佳個(gè)體進(jìn)行保存,該進(jìn)化種群作為新的災(zāi)變最佳種群進(jìn)行保存,然后將進(jìn)化種群中根據(jù)適應(yīng)度排序后的前pop個(gè)個(gè)體進(jìn)行初始化處理,然后將處理過的種群進(jìn)行一定代數(shù)的遺傳操作.

(2) 災(zāi)變周期自適應(yīng)遺傳操作

為了與災(zāi)變的周期性重復(fù)進(jìn)行良好的配合,該算法對(duì)交叉操作和變異操作進(jìn)行改進(jìn),令其隨災(zāi)變過程周期性自適應(yīng)變化,增強(qiáng)算法從災(zāi)變開始到所有災(zāi)變操作完成過程當(dāng)中對(duì)搜索范圍的尋優(yōu)能力.在所有災(zāi)變操作完成之后,種群個(gè)體已分布于各個(gè)極值的附近,為了尋找到這些范圍中的最優(yōu)極值,需要對(duì)這些優(yōu)秀個(gè)體所處的局部范圍進(jìn)一步搜索.本算法在災(zāi)變期間的尋優(yōu)過程中跟隨代數(shù)逐漸增大交叉、變異概率,增大優(yōu)秀個(gè)體間基因交流的可能性,在災(zāi)變操作完成之后,通過非線性函數(shù)的特點(diǎn)快速增大交叉、變異概率,同時(shí)利用變異操作中變異范圍的自適應(yīng)縮小,對(duì)每個(gè)個(gè)體的附近范圍進(jìn)行探索,增強(qiáng)局部搜索能力.

① 災(zāi)變周期自適應(yīng)交叉操作

通過對(duì)交叉概率進(jìn)行自適應(yīng)變化提高種群變異的全局搜索能力,具體調(diào)整情況如下所示：

Pc是交叉概率,上式當(dāng)中Num為當(dāng)前已發(fā)生的災(zāi)變次數(shù).種群每次進(jìn)行m代遺傳操作之后就進(jìn)行一次災(zāi)變操作,交叉概率K1為小于1 的定值.當(dāng)i≥w時(shí),交叉概率進(jìn)行自適應(yīng)變化.K2為一整數(shù),調(diào)節(jié)交叉概率的變化范圍.

② 災(zāi)變周期自適應(yīng)變異操作

變異操作是提高種群多樣性的重要手段,為了使種群在遺傳操作后期,收斂程度較高的時(shí)候增強(qiáng)種群的搜索能力,提高種群基因多樣性,在改進(jìn)算法當(dāng)中對(duì)變異概率進(jìn)行了關(guān)于迭代代數(shù)的自適應(yīng)調(diào)整[5],使變異概率在完成災(zāi)變操作以后逐漸增大,具體調(diào)整情況如下：

式中,Pm是變異概率,w為m的N倍,為停止所有災(zāi)變操作的截止代數(shù),N為總災(zāi)變次數(shù).當(dāng)i＜w時(shí),種群每次進(jìn)行m代遺傳操作之后就進(jìn)行一次災(zāi)變操作,此時(shí)變異概率為小于1 的定值K3.當(dāng)i≥w時(shí),變異概率進(jìn)行自適應(yīng)變化,并且不再進(jìn)行災(zāi)變操作.當(dāng)執(zhí)行了w代遺傳操作之后,將替換后的種群繼續(xù)執(zhí)行V-w代遺傳操作,對(duì)變異概率進(jìn)行自適應(yīng)調(diào)整,V為實(shí)際的總的迭代代數(shù),K4為一整數(shù),調(diào)節(jié)變異概率的變化范圍.

變異操作方法是隨機(jī)選擇個(gè)體中的基因位置,對(duì)被選中的基因xj進(jìn)行如下自適應(yīng)操作,變異結(jié)果為x′j：

式中,r′,r為0～1 之間的隨機(jī)產(chǎn)生數(shù),Num為發(fā)生變異操作時(shí)已經(jīng)發(fā)生過的災(zāi)變操作的次數(shù),m為災(zāi)變周期,M為遺傳操作中種群的穩(wěn)定周期,xj,min和xj,max代表一個(gè)配礦方案中第j個(gè)變量的配比范圍下限和上限.

2 算法仿真應(yīng)用

為了檢測(cè)改進(jìn)算法的有效性,本文利用鋼廠的燒結(jié)配礦數(shù)據(jù)進(jìn)行分析,將尋找最低成本配礦方案為目的解析為最優(yōu)化問題建立尋優(yōu)模型.所以此次尋優(yōu)問題的目標(biāo)就是在指定的約束條件下,利用工人經(jīng)驗(yàn)約束配比范圍,尋找成本最低的配礦方案.該問題作為工業(yè)生產(chǎn)問題,具有多變量、多約束條件、解集區(qū)域分布復(fù)雜等特點(diǎn),十分符合對(duì)改進(jìn)算法的性能進(jìn)行檢測(cè).

(1) 模型建立

當(dāng)配料所使用的原料有n種時(shí),目標(biāo)函數(shù)主要目的是計(jì)算每噸混合原料的成本cost元.計(jì)算方式可以如下表示.

式中,cj表示的是第j種原料的噸單價(jià)(元)；xj表示第j種原料的配比,%,成本cost,元.H2Oj為第j 種燒結(jié)原料的水含量的百分比,%,Burnj為第j種燒結(jié)原料的燒損比,%.

配料的過程當(dāng)中,配料工作人員主要通過各種原料的庫(kù)存量,價(jià)格等因素配合自己在實(shí)際生產(chǎn)過程中積累到的經(jīng)驗(yàn)對(duì)每種原料的配比進(jìn)行范圍約束,同時(shí)保證所有的原料配比之和為1.該約束條件的表達(dá)式如下所示：

式中,xj,min,xj,max表示第j種原料配比范圍的上下限,%.每種原料的配比xj范圍主要通過初始化模型時(shí)對(duì)所有原料進(jìn)行約束,在執(zhí)行遺傳操作時(shí)始終保持種群中所有個(gè)體包含的配比處于各自的約束范圍內(nèi).為了降低算法的計(jì)算量,配比和為1 的約束條件將會(huì)以懲罰項(xiàng)的形式添加到最終的適應(yīng)度函數(shù)當(dāng)中,該懲罰項(xiàng)的建立形式如下所示.

式中,以 β作為懲罰因子,是一個(gè)正整數(shù),P為懲罰函數(shù).

燒結(jié)礦當(dāng)中各種化學(xué)成分和堿度是衡量燒結(jié)礦好壞的重要質(zhì)量指標(biāo),如果超出該范圍會(huì)對(duì)鋼鐵質(zhì)量和燒結(jié)設(shè)備造成嚴(yán)重影響.第q種化學(xué)成分和堿度的約束條件如下所示：

式中,wq為計(jì)算出的燒結(jié)礦中第q種元素的含量(%).同時(shí)PHmin,PHmax是堿度的上下限(%),堿度定義為燒結(jié)礦中氧化鈣和二氧化硅的含量之比.化學(xué)成分和堿度的約束條件也將以懲罰項(xiàng)的形式添加到最終的適應(yīng)度函數(shù)當(dāng)中,懲罰項(xiàng)建立方法如下：

式中,的兩個(gè)懲罰因子?、θ為正整數(shù),W為懲罰項(xiàng).

最佳個(gè)體將會(huì)成為通過搜索遺傳過程中所有個(gè)體當(dāng)中適應(yīng)度最小的個(gè)體.適應(yīng)度函數(shù)的建立如下所示,當(dāng)一個(gè)配礦方案的各項(xiàng)約束超出范圍情況越嚴(yán)重時(shí)懲罰程度就會(huì)越大,適應(yīng)度就越大.

(2) 編碼方案

基于燒結(jié)原料的種類十分豐富,每次生產(chǎn)前所需配料的種類有十幾種,所以為了降低計(jì)算量,節(jié)省計(jì)算時(shí)間,算法中采用實(shí)數(shù)編碼方式,以多個(gè)實(shí)數(shù)組成種群中的個(gè)體.

(3) 選擇方法

隨機(jī)產(chǎn)生的初始種群的個(gè)體適應(yīng)度差別不大,難以通過輪盤選擇等方法對(duì)個(gè)體進(jìn)行選擇.該遺傳算法通過此特點(diǎn)對(duì)選擇方法進(jìn)行改進(jìn),使其更好的選取優(yōu)秀個(gè)體,引導(dǎo)收斂方向,具體選擇方法如下：

先將所有個(gè)體按照適應(yīng)度由小到大的順序進(jìn)行排序,對(duì)前25%個(gè)體數(shù)量翻倍,組成新種群前50%的個(gè)體,前25%到50%的個(gè)體直接放入新種群中.計(jì)算種群中所有個(gè)體與當(dāng)前全局最佳個(gè)體的相似度,對(duì)個(gè)體基于相似度由大到小排序,選擇與當(dāng)前最優(yōu)個(gè)體相似度高的個(gè)體對(duì)種群進(jìn)行補(bǔ)全,相似度計(jì)算采用歐氏距離計(jì)算方法[6],計(jì)算公式如下所示：

式中,D表示相似度,n表示個(gè)體中所有的基因個(gè)數(shù),xbest,j是當(dāng)前搜索到的最佳方案中第j種原料的配比(%).

(4) 交叉操作

需要配比的原料有十幾種,所以該問題是一種多維求解的問題,而且通過大量實(shí)驗(yàn)發(fā)現(xiàn)優(yōu)秀解集都處于一個(gè)相對(duì)較小的范圍當(dāng)中.種群中每個(gè)個(gè)體含有多種變量,和采用二進(jìn)制編碼的種群個(gè)體具有一定的相似性.該算法通過對(duì)不同個(gè)體進(jìn)行隨機(jī)選擇多個(gè)位置,交換相同位置上的基因?qū)崿F(xiàn)交叉操作[7].這種方法可以利用現(xiàn)有的種群基因增強(qiáng)種群的多樣性,同時(shí)又不會(huì)使種群中的個(gè)體逃離當(dāng)前的最優(yōu)解集范圍,在該問題的研究當(dāng)中取得了很好的效果,具體的交叉方式如下圖所示,兩個(gè)被隨機(jī)選擇出的個(gè)體S和個(gè)體K,在給兩個(gè)個(gè)體中隨機(jī)選擇出若干個(gè)基因位置,將兩個(gè)個(gè)體相同基因位置上的基因進(jìn)行交換.結(jié)果見圖1.

圖1 個(gè)體交叉結(jié)果

改進(jìn)的遺傳算法的主要執(zhí)行步驟如圖2所示.

圖2 改進(jìn)遺傳算法步驟

3 仿真結(jié)果對(duì)比

在解決這種非線性尋優(yōu)問題時(shí),遺傳算法、蟻群算法、差分算法、粒子群算法是最為常用的幾種智能進(jìn)化算法.為了驗(yàn)證改進(jìn)的遺傳算法的尋優(yōu)效果,本文以河北某鋼廠的實(shí)際生產(chǎn)數(shù)據(jù)作為試驗(yàn)數(shù)據(jù)進(jìn)行測(cè)試,設(shè)置算法種群個(gè)體數(shù)為200,迭代代數(shù)為250,每進(jìn)行50 代遺傳操作之后進(jìn)行一次災(zāi)變操作,直到完成250 代的所有遺傳操作為止,交叉概率設(shè)為0.5,變異概率設(shè)為0.4.表1為鋼廠工程師總結(jié)出的燒結(jié)礦成分范圍作為約束條件,分別使用災(zāi)變自適應(yīng)遺傳算法和自適應(yīng)遺傳算法[8,9]、蟻群算法、差分算法、粒子群算法進(jìn)行尋優(yōu)測(cè)試,進(jìn)行仿真對(duì)比[10].

表1 質(zhì)量指標(biāo)

以某一日期數(shù)據(jù)進(jìn)行試驗(yàn)為例,多種算法的實(shí)際尋優(yōu)效果如圖3-圖7所示,縱軸代表成本(元),橫軸代表迭代代數(shù).

通過圖3與圖4至圖6相比較,自適應(yīng)遺傳算法在最優(yōu)方案的搜索效果上要優(yōu)于蟻群算法、差分算法和粒子群算法,但是在執(zhí)行了130 代遺傳操作之后,尋優(yōu)結(jié)果基本穩(wěn)定在544.75(元)附近,此時(shí)種群趨于“成熟”無法搜索到更加優(yōu)秀的個(gè)體.而與圖7的災(zāi)變遺傳算法相比較,可以明顯的看到,在前200 代遺傳操作中因?yàn)樘砑恿藶?zāi)變操作,根據(jù)災(zāi)變周期自適應(yīng)調(diào)整的遺傳算略可以增強(qiáng)遺傳算法的全局搜索效果,實(shí)際搜索范圍覆蓋的更加完整,比自適應(yīng)遺傳算法更高效地搜索優(yōu)秀個(gè)體區(qū)域,獲得更優(yōu)個(gè)體,充分說明了全局搜索效果更佳,搜索結(jié)果更優(yōu)秀.完成所有的災(zāi)變操作之后,在200 代到250 代遺傳操作過程中,配合交叉和變異操作的自適應(yīng)調(diào)整,搜索范圍快速收斂,在種群個(gè)體相似度較高的情況下隨代數(shù)增多個(gè)體間的基因交流,逐步降低變異范圍,增大了個(gè)體在局部范圍的搜索能力,進(jìn)一步優(yōu)化搜索結(jié)果,如圖7所示取得了更加優(yōu)秀的效果.

圖3 自適應(yīng)遺傳算法

圖4 蟻群算法

圖5 差分算法

圖6 粒子群算法

圖7 災(zāi)變自適應(yīng)遺傳算法

同時(shí)將各個(gè)算法的尋優(yōu)結(jié)果當(dāng)中燒結(jié)礦的化學(xué)成份進(jìn)行對(duì)比,結(jié)果如表2所示,可以看到,災(zāi)變自適應(yīng)遺傳算法遺傳算法可以在保證燒結(jié)礦質(zhì)量指標(biāo)的前提下,有效地降低原料成本.

如表3所示的最優(yōu)配礦方案與鋼廠企業(yè)的生產(chǎn)方案計(jì)算數(shù)據(jù)相比較,可以看到基于災(zāi)變的自適應(yīng)遺傳算法可以在有效的經(jīng)驗(yàn)配比范圍內(nèi)得到成本優(yōu)于企業(yè)人工配比的方案.

表2 燒結(jié)礦成份對(duì)比

表3 原料配比對(duì)照

4 結(jié)束語(yǔ)

該改進(jìn)遺傳算法通過特殊的選擇方法和交叉方法將搜索范圍不斷向優(yōu)秀搜索區(qū)域靠攏,同時(shí)通過變異概率的后期自適應(yīng)變化,增強(qiáng)了局部搜索能力,為優(yōu)秀解的選擇奠定了基礎(chǔ),而災(zāi)變操作的加入,增強(qiáng)了算法的全局搜索能力,解決了傳統(tǒng)遺傳算法的“早熟”問題,很好的在全區(qū)域內(nèi)進(jìn)行搜索,有利于全局最優(yōu)解的確定.針對(duì)燒結(jié)配礦的成本最低問題,結(jié)合燒結(jié)礦的各種非線性的質(zhì)量指標(biāo)約束,該改進(jìn)算法的尋優(yōu)結(jié)果十分穩(wěn)定.通過上述數(shù)據(jù)對(duì)比結(jié)果可知,該算法可以明顯的改善配料方法,而且尋優(yōu)配礦方案經(jīng)鋼鐵企業(yè)驗(yàn)證可以在滿足企業(yè)生產(chǎn)的情況下降低原料成本,為鋼鐵企業(yè)帶來很好的經(jīng)濟(jì)效益.