基于隨機機制的仿生智能算法研究

基于隨機機制的仿生智能算法研究

微織構工藝過程的優(yōu)化問題和知識進化策略化工過程是一個動態(tài)過程，隨著時間的推移而改變。隨著時間的推移，它改變了空間的轉移。隨著能源和環(huán)境問題對人類生存的挑戰(zhàn)日益加劇,人們也越來越關心化工過程的運行性能及控制指標。而基于穩(wěn)態(tài)模型的控制策略無力更好地解決此類問題,因此動態(tài)優(yōu)化是流程工業(yè)發(fā)展的必然趨勢。國內外學者對于化工動態(tài)優(yōu)化問題的研究方法主要分為:基于龐特里亞金極值原理;貝爾曼最佳原理的數(shù)值方法;優(yōu)化與控制策略結合的線性規(guī)劃法;迭代動態(tài)規(guī)劃(iterativedynamicprogramming,IDP);各類智能算法。前兩種主要是處理較為簡單的問題;Luus提出的IDP逐代補償離散化導致的系統(tǒng)誤差,在保證每代的計算量不顯著增加的情況下逐代尋優(yōu)以逼近最優(yōu)解,但其效率偏低,且無法保證全局最優(yōu)解在已求得解的附近。目前智能算法主要集中于模仿自然選擇層面上模擬生物進化的仿生計算,并不帶有知識的形成和積累機制,從而求解的過程中缺乏知識的有效引導,遇到具有較高操作變量的情況,算法甚至會陷入不收斂的情況。化工過程動態(tài)優(yōu)化問題具有高度的非線性,使用智能方法處理這類問題時,一種有效的策略是離散時域后,使用分段函數(shù)逐次逼近最優(yōu)解,將該問題轉化成為NLP后進行處理。但是該策略中使用Runge-Kutta法計算常微分方程會占用算法的大部分計算代價,處理時的效率也不能令人滿意。知識進化算法受到波普爾的知識進化論的指導,該理論認為在人類進化過程中逐漸獲得的知識是人類社會加速進化的重要原因。劉純青等根據知識進化論的原理,建立了知識進化策略的基本框架,利用12個代表性的無約束非線性函數(shù)對該策略進行測試,并得出了知識進化的速度高于生物進化的速度的結論。嚴太山等提出的求解無約束優(yōu)化問題的知識進化算法(UOP-KEA)在解決無約束優(yōu)化問題時獲得較好結果,并證明了知識進化算法的收斂性。在諸多實際問題中,盡管知識進化策略能夠加快進化的收斂速度,但是如何有效地提取高維空間的知識及如何利用知識的問題并未得到解決。本文針對化工動態(tài)優(yōu)化問題的特點,提出了一種改進的知識進化算法(improvedknowledgeevolutionalgorithm,IKEA),該方法能夠通過提取進化中產生的隱含信息并加以利用,提高算法效率,實現(xiàn)對一類終端時間給定,終端狀態(tài)無約束動態(tài)優(yōu)化問題的有效求解,并取得較滿意的結果。1動態(tài)優(yōu)化問題的描述和算法的描述1.1化工過程方程動態(tài)優(yōu)化問題的一般形式表述如下minJ(u)=Φ[x(tf)]+∫tf0Ψ[x(t),u(t)]dts.t.{˙x=f[x(t),u(t),t]umin≤u(t)≤umaxxmin≤x(t)≤xmaxx(0)=x0h(x(t),u(t))=0g(x(t),u(t))≤0(1)minJ(u)=Φ[x(tf)]+∫tf0Ψ[x(t),u(t)]dts.t.?????????????????????x˙=f[x(t),u(t),t]umin≤u(t)≤umaxxmin≤x(t)≤xmaxx(0)=x0h(x(t),u(t))=0g(x(t),u(t))≤0(1)針對于化工過程,該方程可以解釋為:如何選擇合適的控制策略u使得系統(tǒng)的性能指標J在滿足質量和能量守恒的情況下,并在滿足約束條件下達到最優(yōu)。1.2基于知識進化的化工動態(tài)優(yōu)化NFL(nofreelunch)理論認為,相關知識的指導能夠使進化算法與問題更加匹配,能夠有效提高進化算法的效率。根據該理論并針對化工動態(tài)優(yōu)化的特點,本文構建一種改進的知識進化算法,該算法能有效減少動態(tài)優(yōu)化問題候選解的評價次數(shù)。算法的基本框架如圖1所示。算法的關鍵算子包括子群更新、知識提取、進化及對進化的引導算子。由于知識的進化和知識對種群進化方向的影響是進化加快的關鍵,因而下文主要討論知識的提取及知識對種群個體進化的影響。算法的框架如圖2所示。2基于實際個體生成策略先驗知識指導下的初始化策略:由盲目隨機產生的新個體通常分布不均且個體的編碼混亂,波動過大,不符合化工過程的特性。根據化工過程生產操作連續(xù)性的特點,解決上述問題需要提出一種可行的符合過程實際個體生成策略:初始化種群時,將個體相鄰位的差值限定在限幅δ內;同時為了不遺漏可能存在的波動較大的最優(yōu)策略,也以一定概率允許相鄰位超過限幅δ的個體的存在。在種群的初始化完成后,建立種群的剩余壽命矩陣(remaininglifetimematrix,RLM),通過引入這種個體的老化機制以保持種群的多樣性。2.1bb知識組成知識知識庫由取值空間知識(KA)、精英群體知識(KE)、最優(yōu)個體知識(KB)3類知識組成。這3類知識提取種群空間中個體的特征并更新和進化知識,并通過引導遷移機制和取值空間收縮機制兩種機制來影響種群空間的進化方向。此外,最優(yōu)個體KB在算法迭代結束時,將作為算法的最優(yōu)控制策略輸出。2.1.1基本規(guī)則+1+KA是種群經過歸納后的特征信息,記錄優(yōu)勢個體的每一維變量的區(qū)間信息,用于指導子群更新。該知識的獲得方法為:將控制變量范圍在其可變動范圍內等分成m個子區(qū)間后,每代進化完成后,對其中最優(yōu)個體的每一維分析其所在區(qū)間,并進行計分。規(guī)則如下scoregn(i,mi)={(scoregn-1(i,mi)-β)α+1+βifxbestgni∈mi(scoregn(i,mi)-β)α+βelse(2)scoregn(i,mi)={(scoregn?1(i,mi)?β)α+1+β(scoregn(i,mi)?β)α+βifxbestgni∈mielse(2)其中,遺忘因子α用于逐代減少早期計分的影響能力,基礎概率因子β的作用是保證未產生優(yōu)勢個體的區(qū)域仍然有被選中產生新個體的可能,避免算法陷入局部最優(yōu),本文中取α=0.8,β=0.5。在針對時域離散段數(shù)較多(N≥40)或搜索域較復雜的動態(tài)優(yōu)化問題,引入了一種取值空間的逐代收縮機制能夠使得算法更快收斂,因而需要將計分規(guī)則進行相應調整。若精英群體知識KE的個體連續(xù)10代第i維取值都在控制變量的第γ(1≤γ≤m)個子域中,則認為該子域為第i維的優(yōu)勢域。對于尚未選中優(yōu)勢域的第i維,仍按照式(2)計分;而對于已經選中優(yōu)勢域的第i維則不再計分,而根據當前最優(yōu)個體的分布所在進行控制域的收縮,從而確定個體最優(yōu)域[Di,min,Di,max],規(guī)則如下。(1)計算[uminm[Di,min,Di,max]=[(umax-umin)(j-1)m,(umax-umin)jm][Di,min,Di,max]=[(umax?umin)(j?1)m,(umax?umin)jm](2)適應度下限及上限Dgn+1i,min={xbestgniifxbestgni≤Dgni,minorfitness(xbestgni)≤LowgniDgni,minelseDgn+1i,min={xbestgniDgni,minifxbestgni≤Dgni,minorfitness(xbestgni)≤LowgnielseLowgn+1i,min={fitness(xbestgn)ifxbestgni≤Dgni,minorfitness(xbestgn)≤LowgniLowgni,minelseDgn+1i,max={xbestgniifxbestgni≥Ιgni,minorfitness(xbestgn)≤ΗighgniDgni,minelseLowgn+1i,min={fitness(xbestgn)Lowgni,minifxbestgni≤Dgni,minorfitness(xbestgn)≤LowgnielseDgn+1i,max={xbestgniDgni,minifxbestgni≥Igni,minorfitness(xbestgn)≤HighgnielseΗighgn+1i,min={fitness(xbestgn)ifxbestgni≥Ιgni,minorfitness(xbestgn)≤ΗighgniΗighgni,minelseHighgn+1i,min={fitness(xbestgn)Highgni,minifxbestgni≥Igni,minorfitness(xbestgn)≤Highgnielse式中Dgn+1i,min、Dgn+1i,max和Dgni,minDgni,max分別表示第gn+1和gn兩代的第i維的個體最優(yōu)域下限及上限;Lowgni,min及Lowgn+1i,min表示兩代優(yōu)勢個體的適應度下限;類似地,Highgni,min和Highgn+1i,min則表示兩代優(yōu)勢個體的適應度上限。2.1.2壓縮算子+壓縮搜索精英群體知識KE指每代從種群中提取的若干優(yōu)秀個體的集合。該知識在每一代進化完成后從種群空間中提取并更新,然后利用KE通過單純形搜索,試圖發(fā)現(xiàn)性能更優(yōu)的個體。其提取和更新策略為:當所求最優(yōu)值為極小值情況下,每個子群中的適應值最小的個體作為該子群的代表個體被記錄用于更新精英群體知識。KE的更新策略為滾動刷新:在進化中不斷使用最新提取的個體代替KE最老的個體。KE中的個體均為各代的優(yōu)秀個體,其包含著較多的優(yōu)秀基因位,因此在KE中進行單純形搜索往往能夠得到更為優(yōu)秀的個體以代替KE中較差的個體,并以此進化KE。在單純形交叉中,采用擴張算子可以使新的單純形在原先單純形的外圍,此時的單純形搜索具有較好的外圍探索能力;采用壓縮算子可以使新的單純形在原先單純形的內部,使其具有較好的內部挖掘能力。IKEA采取一種獨特的擴張策略,該策略能夠根據單純形搜索的N+1個個體的距離關系選擇采取擴張或壓縮搜索算子εi=dmeandmax(εt-εo)+εo(3)式中εi為每次單純形的擴張系數(shù),εt及εo分別為最大的壓縮系數(shù)及最大的擴張系數(shù),dmean為個體間平均歐氏距離,dmax為KE中個體間的最大距離。由式(3)可見,當個體間的平均距離較大時,單純形搜索的擴張策略將偏向于壓縮算子,進行單純形內部的挖掘;相反,當個體間的平均距離較小時,擴張策略將偏向于擴張算子,進行單純形外圍的開發(fā)。該策略根據解的分布情況自動調整至合適的單純形搜索方式,增加尋找到更優(yōu)解的概率,從而加快KE的進化。2.2基因位的丟失設計IKEA時,因為不采用個體隨機變異機制而采用引導遷移策略,從而能夠避免隨機變異導致一些個體的優(yōu)秀基因位的丟失,這些被隨機變異的優(yōu)秀基因位需要重新花費較大的計算代價才能被重新獲得。但在進化后期,由于取值空間的縮小,常會導致種群中個體的多樣性不足。因而需要設計一種子群更新策略和種群個體的引導遷移策略,使得算法能夠在保證種群的多樣性的同時,又能夠避免隨機變異導致優(yōu)秀個體的喪失,從而增加算法的收斂速度。2.2.1非優(yōu)勢子群的nndom種群空間完成一代進化后,將種群內所有個體按照適應度排序后記錄個體所屬的子群。將排序前25%的個體認為是優(yōu)勢個體,而含有最多優(yōu)勢個體的子群則被稱為該代的優(yōu)勢子群Ndom,該子群的全部個體保留并進入下一代進化。其余子群稱為非優(yōu)勢子群Nndom,按照式(4)評價各非優(yōu)勢子群。Si=σcelite2+ζ×var+(1-σ-ζ)×mean(4)評價后舍棄評分最低的1～2個子群,按照取值空間知識(KA)重新生成新的子群。參數(shù)celite為該子群的獎勵系數(shù),即優(yōu)勢個體中屬于該子群的數(shù)目,體現(xiàn)子群的個體優(yōu)秀程度;參數(shù)var為子群的方差,體現(xiàn)子群個體的多樣性;參數(shù)mean指的是子群平均適應度,體現(xiàn)子群的整體質量。σ、ζ為評分權重系數(shù),IKEA分別取σ=0.3,ζ=0.4。而被保留的非優(yōu)勢子群,首先保留屬于其中的優(yōu)勢個體,然后對其余個體進行引導遷移。2.2.2全局最優(yōu)個體矩陣仿照PSO的思想:不使用突變算子,而是根據群體和個體本身的信息逐漸將個體移動到好的區(qū)域。IKEA設計了一種引導遷移策略。該策略分為兩個部分:引導向量的更新及個體的引導遷移策略。當種群進化一代后,將種群的全局最優(yōu)個體pg記入知識庫中全局最優(yōu)個體矩陣GM中,將GM中的最優(yōu)個體認為是最優(yōu)個體知識KB。更新規(guī)則如下ΚB={pgiffitness(pg)<fitness(ΚB)ΚBotherwise對于Nndom中需要遷移的個體則分別計算其引導向量并進行引導遷移,pgid為所屬子群中的最優(yōu)個體vid=wvid+c1r1(pgid-xid)+c2r2(pgd-xid)x(t+1)=x(t)+vid慣性權重采用線性遞減權重w=wmax-(wmax-wmin)tgn式中t為當前進化代數(shù),wmax=0.9,wmin=0.4。當連續(xù)三代fitness(pg(t))-fitness(pg(t-1))<θ時,IKEA認為算法陷入停滯,就不再對個體進行引導遷移,而舍棄所有非優(yōu)勢子群Nndom,在整個控制域內重新生成新個體。2.2.3多態(tài)體老化和壽命獎勵的一般自加回歸系統(tǒng)rlm為了保證種群的多樣性,IKEA對種群內所有個體進行壽命限制,避免算法陷入局部最優(yōu)。該策略分為兩個部分:個體老化和壽命獎勵。個體老化:在進化開始時,根據化工動態(tài)優(yōu)化問題的復雜性分別設定不同的初值;每進化一代,所有個體對應的剩余壽命矩陣(RLM)中的元素自減1。壽命獎勵:對于在整個種群平均適應度之上的個體,該個體對應的剩余壽命矩陣(RLM)中的元素自加0.5;優(yōu)勢個體對應的剩余壽命矩陣(RLM)中的元素自加1。在每代結束時,舍棄剩余壽命耗盡的個體,在所在子群的最優(yōu)個體附近根據取值空間知識重新生成個體。2.3精英群體知識更新綜上所述,算法的執(zhí)行順序如下。(1)初始化:候選解按照先驗知識指導下的初始化策略進行初始化。評價個體后提取種群的取值空間知識(KA)、精英群體知識(KE)、最優(yōu)個體知識(KB)3類知識,用以初始化知識庫。建立剩余壽命矩陣RLM。(2)種群空間中的個體按照子群更新策略進行更新,并在KA指導下補充新個體。然后,根據老化機制進行個體老化以及壽命獎勵。(3)個體以復制擴增,交叉,評價篩選等機制進行進化;在評價篩選后,知識庫自種群中提取KA、KE、KB,按照規(guī)則更新知識庫。(4)種群空間中的個體在異化后,根據規(guī)則及引導向量進行引導遷移。(5)在精英群體知識KE進行單純形搜索,嘗試發(fā)現(xiàn)更優(yōu)秀的個體,并更新KB。(6)判斷是否滿足終止條件,若滿足則輸出最優(yōu)控制序列及其適應度;否則進行新一代的進化,跳轉至第(2)步。3采用改進的知識開發(fā)算法自下而上對化工動態(tài)優(yōu)化的應用選取4個具有代表性的化工及生化動態(tài)過程,測試本文所提出的IKEA的尋優(yōu)性能。3.1控制ca、cb的含量,并進行空間知識測試其數(shù)學模型如下maxJ(tf)=CB(tf)s.t.{dCAdt=-k1C2AdCBdt=k1C2A-k2CB298≤Τ≤398,CA(0)=1,CB(0)=0?tf=1k1=4×103e-2500/Τ,k2=6.2×105e-5000/Τ在批式反應器中發(fā)生(A→B→C)反應,在反應過程中對反應溫度T進行控制,以使反應結束時中間產物B的濃度達到最優(yōu)。式中CA、CB分別表示物質A、B的濃度,T為溫度控制變量。本文以該算例測試取值空間知識的作用,在將時域離散10份(N=10)的情況下,追蹤取值空間知識隨進化而變化的趨勢。圖3中z軸為歸一化后的計分,也就是該區(qū)間產生新個體的概率;x軸為控制域的子區(qū)間;y軸為時域離散段數(shù)。從圖3中可以看出,取值空間隨著進化逐漸聚合在最優(yōu)個體所對應的控制序列附近,新個體將以較大概率生成在最優(yōu)個體附近,這有利于增加算法效率,減少不必要的搜索代價。3.2xbdz、zf其數(shù)學模型如下maxJ(zf)=1-xA(zf)-xB(zf)s.t.{dxAdz=u(z)[10xB(z)-xA(z)]dxBdz=-u(z)[10xB(z)-xA(z)]-[1-u(z)]xB(z)0≤u(z)≤1xA(0)=1,xB(0)=0,zf=12在該管式反應器中,在兩種催化劑的作用下發(fā)生(A?B→C)反應,上式中z為管式反應器的長度,u(z)表示第一種催化劑在管中z坐標位置的含量。為了提高原料的利用率,使反應結束時目標產物C濃度達到最大,需要對管中的催化劑采取最優(yōu)分配。3.3生物反應器處理工藝優(yōu)化問題該模型由Park等于1988年提出。該模型的數(shù)學表達如下maxJ(tf)=z1z5{dz1dt=g1(z2-z1)-uz5z1dz2dt=g2z3-uz5z2dz3dt=g3z3-uz5z3dz4dt=-7.3g3z3+uz5(20-z4)dz5dt=u,0<u<10z1(0)=0,z2(0)=0,z3(0)=1,z4(0)=5,z5(0)=1,tf=15式中g1=4.75g30.12+g3,g2=z40.1+z4exp(-5z4),g3=21.87z4(z4+0.4)(z4+62.5),為蛋白質分泌速率常數(shù)。該生物反應器以葡萄糖為營養(yǎng)劑生產SUC2-s2蛋白。該優(yōu)化問題是單控制變量問題,優(yōu)化的目的是在反應結束時使分泌蛋白的產量maxJ(tf)=z1z5達到最大。3.4目標函數(shù)的優(yōu)化該模型由Lee等于1994年提出。該模型的數(shù)學表達如下maxJ(tf)=x1(tf)x4(tf)-Q∫tft0u2(t)dt{dx1dt=u1+u2dx2dt=μx2-u1+u2x1x2dx3dt=u1x1Cnf-u1+u2x1x3-Y-1μx2dx4dt=Rfpx2-u1+u2x1x4dx5dt=u2x1Cif-u1+u2x1x5dx6dt=-k1x6dx7dt=k2(1-x7)x(0)=(1,0.1,40,0,0,1,0)Q=5tf=10h其中Rfp=0.095x30.108+x3+x23/14814.8(0.0005+x50.022+x5),μ=0.407x30.108+x3+x23/14814.8[x7(0.220.22+x5)+x6],k1=k2=0.09x50.034+x5,Y=0.51,0≤u≤10該優(yōu)化問題是多控制變量問題,優(yōu)化的目的是使用盡可能少的誘導劑產生盡可能多的外源蛋白質,使反應結束時實現(xiàn)經濟收益J(tf)=x1(tf)x4(tf)-Q∫tft0u2(t)dt最大。3.5算例2:群體規(guī)模對算法性能的影響為了測試IKEA算法的性能,采用上述4個算例作為測試算例。IKEA的主要計算代價由個體的評價次數(shù)決定,而評價次數(shù)與群體規(guī)模相關。因此,本次測試將對不同群體規(guī)模下對算法的性能影響,通過測試選擇對于每一個算例,分別測試4種情況。對于每種情況分別獨立運行10次,測試后分別統(tǒng)計均值、最優(yōu)值及下四分位數(shù),而后根據算法性能分析不同群體規(guī)模下的算法性能。在表1列出不同群體規(guī)模下對4個測試算例的優(yōu)化結果。(1)對于3.1節(jié)中算例1這類例子,算法的優(yōu)化結果并沒有隨著群體規(guī)模的擴大而變好。這就說明了處理此類例子僅使用小規(guī)模的種群就能夠使得算法得到較好的優(yōu)化結果,而小規(guī)模群體能夠在每一代的進化中消耗較少的評價次數(shù),從而較好地減少了計算代價。對于這類算例,群體規(guī)模的算法性能的影響較小。(2)對于3.2～3.4節(jié)中算例2～4這類例子,含有較多的局部最優(yōu)點。因而使用IKEA優(yōu)化此類算例若僅使用較小的種群規(guī)模會導致種群多樣性的匱乏,而IKEA的算法策略會導致進化較易陷入局部最優(yōu)且不易跳出局部極值點。但是,若群體的規(guī)模過大,雖然在進化過程中的多樣性得到保證,但會在每一代進化中耗費大量的評價次數(shù)。若在規(guī)定的評價次數(shù)的限制下,因為總進化代數(shù)的減少,常常會導致優(yōu)化性能反而不如規(guī)模適中的群體規(guī)模的優(yōu)化結果。綜上所述,群體規(guī)模(包括群體總規(guī)模、子群數(shù)和子群規(guī)模的組合方式)的變動對IKEA有較大的影響,其本質原因在于IKEA所采用的取值空間知識和引導遷移策略。在相同的計算代價下,若群體規(guī)模過小,經過引導遷移后,優(yōu)秀個體對于其他個體的影響過大,往往會導致群體的多樣性不佳,繼而導致算法性能的整體下降。而另一方面,過大的種群耗費的評價次數(shù)也會相應地增加,從而減少種群的進化代數(shù),所得到的優(yōu)化結果可能并不令人滿意。同樣,不合適的子群數(shù)和子群規(guī)模的組合也會導致算法的性能下降,這主要是由于算法采用的老化機制和子群更新策略導致的。最后,根據不同群體規(guī)模下算法性能測試,確定不同算例的最佳種群規(guī)模,在表中以粗體表示。表1中,子群組合=子群規(guī)?！磷尤簲?shù)。3.6引入知識密度在3.1～3.4節(jié)中4個算例利用IKEA進行尋優(yōu),以上算例被很多動態(tài)優(yōu)化算法用于作為測試問題,所求的優(yōu)化結果如圖4～圖7所示。由于算法的隨機性,針對每個算例均進行10次計算,表2給出了本算法與已有文獻最優(yōu)解的比較,從表中分析可得IKEA在不明顯降低優(yōu)化質量的條件下,計算代價具有一定優(yōu)勢。3.1～3.4節(jié)中4個算例的狀態(tài)方程較為復雜,因而不適合使