基于免疫學習機制的遺傳算法

基于免疫學習機制的遺傳算法

1免疫遺傳算法自horad提出遺傳計算方法（ga）以來，遺傳計算方法已成為模擬生命發(fā)展機制的搜索和優(yōu)化方法，并在許多領域得到了廣泛應用，如其魯莽、合并和高效的全球搜索優(yōu)勢。然而，ga也有一些缺點，即局部多樣性和搜索能力較弱。早期，它容易進入局部最優(yōu)者，其次，最好的解算速度慢。因此，如何提高遺傳計算方法退出局部最優(yōu)者的能力，以及提高遺傳計算方法的收斂速度一直是科學家們的研究重點。為了提高遺傳算法的性能,學者們從不同角度對遺傳算法進行改進,如建立新的算法結構、改進遺傳算子、融合其他先進算法等.近些年在免疫學領域的研究,發(fā)現免疫機制對提高遺傳算法的性能具有重要的啟迪作用,所以許多學者利用免疫系統的特性來改進遺傳算法.王煦法提出一種免疫遺傳算法(ImmuneGeneticAlgorithm,IGA),該算法模擬了免疫系統基于抗體濃度的選擇策略,并通過記憶細胞分化來保留精英個體,提高了算法的全局和局部搜索能力.但該算法用平均信息熵來計算抗體的濃度存在一定的問題,一些相近的抗體之間可能得到的親和度相差較大,從而得出錯誤的抗體濃度;而且該算法不能根據種群中抗體的變化而相應地調整遺傳參數,也影響了算法的收斂性能.Chun等人借鑒免疫應答機制,提出一種免疫算法(ImmuneAlgorithm,IA),解決了電磁器件的形態(tài)優(yōu)化問題.由于該算法策略與文相似,所以有相同的問題.焦李成設計了一種新型免疫遺傳算法(IGA),該算法采用接種疫苗和免疫選擇策略,有效地防止了退化現象,并提高了算法的收斂速度.但算法中種群的多樣性沒有得到進一步改善,接種疫苗概率的選擇對算法的收斂性能影響較大,其合理的取值需反復試驗得出.本文從免疫系統識別抗原的過程獲得啟示.在免疫應答的初期,少部分含有優(yōu)良基因的抗體首先結合抗原,表現為親和度較高,而其它抗體在學習中逐漸分化,與抗原保持高親和度的抗體被克隆擴增,而低親和度的抗體被抑制或自我消亡.通過抗體對同一抗原的重復學習,免疫系統利用記憶機制不斷地強化學習,最終生成合適的抗體來消滅抗原.本文借鑒免疫系統的學習機制,將其應用到遺傳算法中,提出一種基于免疫學習機制的遺傳算法(ImmunityLearningbasedGeneticAlgorithm,ILGA).該算法充分考慮含有優(yōu)良基因的抗體對種群進化的作用,并關注成長性好的低親和度抗體,同時,為了維持種群的多樣性,引入基于濃度的選擇機制,最后利用免疫記憶機制,改善算法的全局收斂能力.通過理論分析,證明該算法具有全局收斂性,函數優(yōu)化和倒立擺控制的仿真試驗均表明此算法具有良好的性能.2基于虛實編碼的全變差遺傳算法在處理優(yōu)化問題時,ILGA用抗原對應目標函數,抗體對應目標函數的解個體,抗體群形成目標函數的解空間.其中,抗體采用實數編碼,由于實數編碼可以表示更大范圍的解空間,適合于精度要求較高的場合,對于多維、高精度要求的連續(xù)函數和非線性控制優(yōu)化問題,使用實數編碼比二進制有優(yōu)勢.一般研究認為遺傳算法的搜索和優(yōu)化能力取決于遺傳算子,所以ILGA引入免疫學習機制,將遺傳算子改進為免疫算子,并采取強化學習策略和弱小保護策略來改善遺傳算法的局部收斂能力和收斂速度.2.1免疫分析(1)抗選擇概率多態(tài)性的研究種群在進化過程中,多樣性的維持會減少早熟現象的發(fā)生,所以必須排斥種群中相似的個體,使個體盡量散布到整個解空間.算法通過引入濃度因子來調整抗體的選擇率,克隆種群中高親和度的抗體,并抑制種群中相似的抗體,這樣既能保持種群的多樣性,又能保證優(yōu)良抗體以較大的概率進入到下一代.定義1某代種群不同的兩個抗體xi、xk之間的相似度為:其中i,k=1,…,N,且i≠k,N為種群數量;j=1,…,n,n為目標解的維數值;[aj,bj]為目標函數在j維空間的約束條件.定義2給定數量為N的種群,抗體xi的濃度定義為:其中Count(φ)為計算φ的數量,γ為相似度常數,一般取0.8≤γ≤1.在適應度比例選擇機制的基礎上,增加基于濃度的調節(jié)因子,于是個體的選擇概率px為:其中α和β為調節(jié)因子,0<α,β<1,aff(x)為抗體x的親和度.從式(3)可以看出,抗體的親和度越大,選擇概率越大;抗體濃度越大,選擇概率越小.這樣既保留了與抗原親和度高的抗體,又減少了相似抗體的選擇,保證了種群在進化中的多樣性.(2)子代的取值原則針對實數編碼,交叉運算采用線性重組,可以生成略大于雙親定義線段中的任意點.設兩個進行交叉的父代個體為x1、x2,交叉后的子代為x′i:其中,ri∈[-0.5,1.5],i=1,2.若子代超出目標函數的解空間,則子代的取值原則是:如果x′i(j)>bj,則x′i(j)取2bj-x′i(j)的值;如果x′i(j)<aj,則x′i(j)取2aj-x′i(j)的值.(3)實值變異及概率化變異算子可以引入初始種群中沒有出現的新個體,并可能恢復種群經過選擇、交叉后丟失的優(yōu)良基因.變異操作采用實值變異,可以在父代和步長范圍定義的立體空間內產生更多的子代,以擴大種群的多樣性.設X為變異前的父代,則變異后子代X′為:其中,Δ=∑i=0ma(i)2i?a(i)Δ=∑i=0ma(i)2i?a(i)以1/m的概率取值1,以1-1/m的概率取值0;L為變量的取值范圍;為了獲得較大的定位精度,本文m取30.(4)遺傳多樣性檢驗因為固定的交叉算子pc和變異算子pm不能適應算法尋優(yōu)的不同情況,所以可以根據種群的實際情況,動態(tài)自適應地調整pc、pm的大小.定義3設種群的數量為N,遺傳多樣性因子gdm為:其中平均親和度為affave=1N∑i=1Naff(i)?affmaxaffave=1Ν∑i=1Νaff(i)?affmax為親和度的最大值.gdm=1,表明種群中抗體的基因相同,種群的多樣性最低.為了避免未熟收斂,交叉和變異算子必須產生新個體,減少種群多樣性的損失,需增大pm,減小pc.如果gdm?1,說明種群的多樣性比較好,為了防止變成隨機搜索,需減小pm,增大pc.自適應交叉、變異的過程如下:其中取Vmax=0.25,Vmin=0.005,0.5≤pc≤0.9,0.001≤pm≤0.25,kc和km為調節(jié)因子,kc=km=1.1,各參數的取值主要借鑒文并經過實際驗算得到.2.2優(yōu)良記憶庫的抗體的變異當抗體不斷地對同一抗原進行學習時,由于免疫記憶機制的作用,免疫系統對該抗原的應答速度將大大提高,并產生更高親和度的抗體以消滅抗原,這是一個強化式學習的過程.在本文的免疫遺傳算法中,通過建立優(yōu)良記憶庫,把歷代親和度最優(yōu)的抗體保留下來,實現種群的精英保留策略.在生物進化中,由于親和度較優(yōu)的個體含有優(yōu)良的基因,自然法則的規(guī)律是優(yōu)秀的個體將更多地得到繁衍后代的機會.在免疫系統中,抗體的個體評價值越高,其子代是優(yōu)秀個體的概率就越大,故本文對優(yōu)良記憶庫的抗體進行變異,以期望獲得更優(yōu)秀的抗體.(1)從初始種群中取小部分親和度最優(yōu)的抗體組成優(yōu)良記憶庫,如果所求目標函數要求極大值,則對每代進化的抗體群取一定比例的高親和度抗體加入到優(yōu)良記憶庫中,替代庫中親和度較低的抗體,反之亦然.設立優(yōu)良記憶庫是為了保證算法終止時得到的結果是歷代最優(yōu)的抗體.(2)將優(yōu)良記憶庫的抗體進行變異,設XM為變異前的父代,則變異后子代X′M為其中μ為比例系數,其取值與目標函數期望的精度有關;k為進化代數.從群體的整體進化過程來看,剛開始進入優(yōu)良記憶庫的抗體未必處于全局最優(yōu)解的區(qū)域內,所以變異的步長要使子代能在全局的范圍內布局,而隨著搜索到的最好解逐漸接近全局最優(yōu)解,其變異的范圍將逐漸縮小為優(yōu)秀抗體所在區(qū)域的小鄰域內.2.3抗局部搜索的功能對于一個復雜的優(yōu)化問題,全局最優(yōu)解的所在區(qū)域和大小是未知的,因此在擴大種群多樣性的同時,還要關注一些可能有助于搜索到全局最優(yōu)解的個體.如果最優(yōu)解附近區(qū)域的分布比較陡峭,則區(qū)域內抗體親和度的差別就會較大,全局最優(yōu)解的一些鄰近解將是親和度較差的抗體,而這些抗體有很好的成長性,能在進化中快速地向最優(yōu)解收斂.因此將那些子代親和度有較大改進的低親和度抗體保護起來,能促使算法有更多的機會仔細搜索該區(qū)域,有利于局部區(qū)域的搜索.將種群中抗體的親和度進行父代和子代比較,把親和度改進最大的父代抗體保留下來,使其在下代進化中承擔起局部搜索的任務,從而提高算法搜索到全局最優(yōu)的概率.2.4優(yōu)良記憶庫的構建步驟1:參數初始化.本文抗體x采用實數制編碼,編碼長度為l,S為解空間,進化代數k=0,設置收斂性條件.步驟2:種群初始化.在目標函數的解空間中隨機產生N個初始抗體組成X(0).步驟3:計算種群X(k)中每一個抗體與抗原的親和度,并建立優(yōu)良記憶庫XM.從整個種群中提取最好的n1個抗體組成優(yōu)良記憶庫XM.步驟4:收斂性判斷.如果滿足收斂條件,則終止進化進程,從優(yōu)良記憶庫中取最好的抗體得出全局最優(yōu)解.步驟5:群體進化.X(k)中的抗體按照基于濃度的選擇算子得到選擇概率,通過隨機遍歷抽樣法選取占種群比例為r的抗體組成種群XS,然后對XS進行自適應交叉和變異得到種群X′(k).步驟6:計算子種群X′(k)中抗體的親和度.步驟7:執(zhí)行強化學習策略.XM變異生成規(guī)模為2n1的種群X′M,通過基于濃度的選擇得到規(guī)模為n1的抗體群XE.步驟8:執(zhí)行弱小保護策略.根據種群變異前后親和度大小的比較,找出子代比父代改進最大的n2個父代抗體保留下來,得到群體XI.步驟9:群體更新.X′(k)按照親和度的大小和父代X(k)比較,代替父代親和度低的抗體,生成N-n1-n2個抗體群XG,與XE、XI共同組成下一代的抗體群X(k+1).步驟10:優(yōu)良記憶庫更新.從X(k+1)中取0.5n1個親和度排序在前的抗體替換優(yōu)良記憶庫中親和度較差的抗體,實現優(yōu)良記憶庫更新.步驟11:k=k+1,返回步驟4.3ilga算法收斂性證明求解n維連續(xù)函數的最小值問題minf(x),其中x∈S?Rn,S為目標函數f(x)的解空間,其任一分量Sj∈[aj,bj]為閉集,j=1,…,n.定義4設S1為全局極小點子空間,S2為非全局極小點子空間,S1∩S2=?,S1∪S2=S,全局極小值點x*∈S1.假設在每一進化代k,對父代種群X(k),變異算子作用一次后得到后代種群X′(k).對任意x∈S,如果xX(k),則存在p(k)>0,使得x∈X′(k)的概率大于p(k).定理如果ILGA滿足假設條件,則其在有限的代數進化后,以概率1收斂到全局極小值,即P{k<∞}=1,且與初始分布無關.證明:設x*(k)為第k代種群X(k)的最優(yōu)抗體,由于ILGA設有優(yōu)良記憶庫,則種群在k+1代的最優(yōu)抗體x*(k+1)滿足:其中x′i(k)為xi(k)的子代,i∈int(1,N).由假設可知,在任一進化代k,通過變異算子的作用可以將X(k)中任一抗體以不小于p(k)的概率變成搜索空間的其他抗體.因此,對于xi(k)S1,經過變異后成為S1子空間任意一點的概率不小于p(k),則子代x′i(k)落入S1子空間的概率滿足:其中x′j(k)為S1的任一抗體,j∈int(1,M),M為S1的抗體集合數.由于x′i(k)∈S1,所以它在算法中具有良好的親和度.隨著k→∞,f(x′i(k))不斷減小,在某一進化代k1,對于x′i(k1)∈S1,總存在x*(k1+1)=min(x*i(k1))成立.通過優(yōu)秀抗體的精英保留和個體自適應變異,種群向親和度改善的方向進化,種群中優(yōu)秀抗體逐漸進入最優(yōu)區(qū)域并接近最優(yōu)抗體.在進化代k2>k1,f(x*(k2))→f(x*),且P{x*(k2)∈S1}=1.而k2代進化以后,還未有任一抗體落入S1子空間的概率Pnot(k2)滿足:則上式兩端令k2→∞,可得即P{k2<∞}=1故ILGA算法收斂并與初始種群分布無關.求n維空間中連續(xù)參數優(yōu)化問題maxf(x)時,收斂性證明方法同上.4iga的概率pv本文選用benchmark問題中的兩個低維和兩個高維測試函數作為算法的優(yōu)化實例,函數表達式如下:其中,函數f1是一個單峰值的病態(tài)函數,在y=x2處有一個狹長低谷,極易陷入局部解;函數f2是多峰值函數,僅有一個最小值,但此解附近有無窮多個局部極小值解;函數f3是Step函數,如果算法不能使后代沿著正確的搜索方向變化,則很難找到最優(yōu)解;函數f4是Sinc函數,隨著維數增多而收斂難度加大,對算法跳出局部極值的能力要求較高.本文將用ILGA、IGA、IA、IGA和GA分別對低維函數求最小值,高維函數求最大值,通過30次仿真實驗比較三者的優(yōu)化能力.前三個函數的種群規(guī)模定為100,函數f4為120.GA、IGA、IA和IGA的pc、pm分別設為0.7、0.015,變量的二進制位數為20,采用兩點交叉,其中IGA的α設為0.7,IGA中更新疫苗的概率PV在[0.3,0.5]區(qū)間內取值,T0=100.對f1、f2函數,ILGA中pc、pm的初始值設為0.7、0.015,r=0.85,γ=0.85,α=0.8,β=0.7,μ=0.08,n1=n2=10;對f3、f4函數的優(yōu)化中,ILGA中pc、pm的初始值設為0.75、0.01,r=0.9,γ=0.9,α=0.7,β=0.7,n1=16,n2=10,μ=0.05.四個測試函數的優(yōu)化結果如表1所示,其中f*為算法在指定代數下獲得最優(yōu)解的目標函數值,最佳目標值為算法30次獨立運行所得的最好目標函數值.圖1給出了4個測試函數在算法GA、IA、IGA和ILGA下的性能.其中橫坐標k為進化代數,縱坐標f為每代最好的目標函數值,(a)、(b)的縱坐標為對數坐標.從收斂的結果可以看出,ILGA的尋優(yōu)能力和收斂速度都比GA有了較大的改善,且整體性能優(yōu)于IA、IGA.(1)GA在進化過程中,種群多樣性不斷地減小,使得進化趨向收斂于一些鄰近的優(yōu)秀個體,容易發(fā)生未熟收斂,如圖1(b)中GA經常收斂于次優(yōu)解0.0097,雖然進化代數增加卻無法找到更好的極小點.而IA通過抗體期望值的選擇和ILGA采用基于濃度的選擇機制都保證了解的多樣性,提高了算法在整個解空間的探索能力,使獲得全局最優(yōu)解的能力大大提高.(2)由于采取實數編碼,ILGA不但可以避免二進制的Hammingcliffs問題,而且可以利用小步長使算法高精度逼近最優(yōu)解,如圖1(a)所示,其收斂精度明顯優(yōu)于IA、IGA和GA.(3)由于GA、IGA和IA不能根據種群的變化而相應地調整遺傳參數,對不同適應度的個體采用同一交叉、變異概率,將發(fā)生退化或收斂速度變慢的現象,如圖1(c)GA和圖1(d)IA的收斂曲線所示,GA在進化后期因pc過大使得一些優(yōu)秀個體的模式被破壞而發(fā)生退化,而IA在進化早期因pm過小阻礙了新個體的產生而減緩收斂的速度.ILGA動態(tài)地調整交叉、變異概率,在保持種群多樣性的同時,推動種群向親和度改善的方向進化.(4)IA、IGA和ILGA通過記憶單元實現了種群的精英保留策略,IGA采用免疫檢測下的退火選擇,這些改進都保證了算法的全局收斂性.同時,ILGA采取強化學習和弱小保護策略,改善了算法的局部搜索能力,大大提高了算法的準確性和快速性,ILGA的收斂成功概率和平均收斂代數明顯要好于GA,并優(yōu)于IA、IGA.5fnn控制器的參數優(yōu)化設計基于ilga的fnn客戶端5.1基于ilga的立柱擺控制器設計對于倒立擺這樣復雜的非線性系統,傳統的控制方法較難實現穩(wěn)態(tài)控制,而模糊神經網絡(FuzzyNeuralNetwork,FNN)既具有模糊控制簡單有效的非線性控制作用,又具有神經網絡的學習和自適應能力,所以采用模糊神經網絡系統來設計倒立擺控制器有一定的優(yōu)勢.由于FNN控制器的參數設計是多參數尋優(yōu)問題,而FNN是局部逼近網絡,一般使用的BP算法有收斂速度慢,容易收斂到局部極值的缺點,因此本文采用基于ILGA尋優(yōu)的FNN控制器,以保證倒立擺的有效控制,控制系統結構如圖2所示.其中yi為系統實際輸出,為yd系統期望輸出.5.2模糊控制器設計二級倒立擺的控制器采用的是基于T-S模型的模糊神經網絡,該控制器有5層結構,如圖3所示.第1層為輸入層.二級倒立擺系統共有6個狀態(tài)變量,若用常規(guī)的規(guī)則庫構造方法,可能的控制規(guī)則個數是輸入變量個數的指數.為了減少控制規(guī)則的數量,輸入層的變量采用狀態(tài)合成法,輸入變量為e、ec:其中k1～k6是加權系數,加權系數的初始值以線性二次型最優(yōu)控制方法求得的狀態(tài)反饋系數作為初始值,并根據控制效果不斷調試,最后得到的加權系數為K=[14.220.5-40.615.55.2-20.5].參數中x為小車的位移,θ1、θ2分別為下、上擺與垂直方向上的夾角,x˙x˙、θ˙1θ˙1和θ˙2θ˙2分別為小車的速度及下、上擺的角速度.第2層為模糊化層.每個節(jié)點代表一個模糊語言變量(N,Z,P),兩個輸入變量取相同的隸屬度函數,論域的區(qū)間為[-5,5],節(jié)點輸出為各隸屬度函數值.隸屬度函數采用高斯隸屬函數,即其中i=1,2,分別對應輸入變量e、ec,Ii代表輸入值,aij、bij分別表示隸屬度函數的中心和寬度.第3層為模糊規(guī)則層.每一個節(jié)點代表一條模糊規(guī)則,計算出每條規(guī)則的適用度,即其中c1∈{1,2,3},c2∈{1,2,3},c1代表變量e的語言變量,c2代表變量ec的語言變量.第4層為歸一化層.實現模糊規(guī)則的歸一化計算,即第5層為輸出層.通過模糊規(guī)則后件fk和α—iα—i乘積得到控制器的節(jié)點輸出y,即模糊規(guī)則后件fk由模糊規(guī)則確定,即其中pk、qk、rk為后件參數,其區(qū)間均為[-2,2].5.3控制器設計用ILGA優(yōu)化基于T-S模型的模糊神經網絡參數,其學習過程如下:(1)確定尋優(yōu)的參數和范圍.考慮需要優(yōu)化的參數,加權系數為6個,隸屬度函數參數為12個,后件參數為27個,共有45個參數需要優(yōu)化.其中,k1∈,k2∈,k3∈[-45,-35],k4∈,k5∈[0,10],k6∈[-25,-10],隸屬度函數中心和寬度、后件參數根據各自的區(qū)間來定.(2)確定性能指標.控制器的優(yōu)劣可由被控對象的實際輸出與期望輸出的偏差大小來衡量,所以可定義指標函數J=∑(yd(k)-yi(k))2作適應度函數.考慮到小車和上、下擺的速度過大將影響到倒立擺的平衡,所以在適應度函數中加入輸出參數的速度項.而倒立擺控制的重點是保證上、下擺在零位的平衡,所以對小車的位移和速度加入調節(jié)因子來減輕它們對適應度的影響.因此,ILGA的性能指標如下:其中N為一個采樣周期內的采樣數.利用PID控制二級倒立擺時獲得的輸入輸出數據進行訓練,數據采樣時間為0.01s,一次采樣周期為2s.(3)按照ILGA算法進行優(yōu)化,種群規(guī)模為120,r=0.9,pc、pm的初始值設為0.7、0.01,γ=0.9,α=0.7,β=0.75,μ=0.01,n1=12,n2=10,進化