一種多目標優化問題的免疫算法

1pareto最優解的獲得及驗證自1985年以來，多目標嵌入式算法已成為解決多目標優化問題的主要工具。許多科學家已經提出了基于權重系數的多目標進化算法。其關鍵在于確定權重系數。然而，需要大量的初始知識來嚴格限制初始群體的分布。然而，基于該群體的多目標進化算法（）可以在很大程度上克服基于權重系數的多目標進化算法的許多缺點，如群體多樣性差、初始知識不足、最短的pareto解等。該方法具有很高的靈活性，能夠有效搜索最合適的pareto解。其重要在于其設計和選擇適應方案的適應性。特別是，文獻中的speas充分利用了最合適者的概念，并以新的小規模生態方式提高了群體的多樣性。同時，在進化的群體中，在它們的基礎上生存的最優異體在它們之外進行選擇，并通過不斷更新獲得最合適的pareto最好的個體來獲得最合適的pareto最好的解。但是，根據作者的實踐，很難在該方法中獲得最合適的解。每個子目標同時應盡可能實現最小最合適的解。因此，即使它是用來解決每個子目標為多模態函數的多目標優化問題的，也很難獲得預期結果，因此也不適合決策者進行有效選擇。可是,免疫系統具有學習、記憶、自適應、自組織、分布性以及群體多樣性等特點,模擬其原理開發免疫算法解決工程問題,已成為計算智能中正在興起的研究領域,并且有些免疫算法在單目標函數優化、模式識別、數據挖掘、組合優化及機器學習等方面得到了有效應用.尤其經仿真獲知,構建免疫算法能有效地解決復雜的多目標優化問題,但這方面的結果極為罕見.為此,本文基于免疫應答原理及小生境概念,提出多目標免疫算法(MOIA:MultiobjectiveOptimizationImmuneAlgorithm),并與公認為很好的算法SPEA進行比較,獲知MOIA優于SPEA.MOIA的主要思想是:首先復制當前抗體群中最好抗體作為抗原進入抗原群(初始抗原群為空集),并通過一種新的聚類算法不斷更新抗原群,其目的是保存較好的Pareto最優個體,接著這抗原群作用于當前抗體群;然后選擇當前抗體群中識別能力(親和力)強的抗體繁殖一定數目的克隆細胞,這些克隆細胞進入親和突變框架,并選擇親和力高的抗體作為記憶細胞,未被選擇繁殖的抗體之間通過相互抑制,消除相同和相似的抗體,未被消除的抗體作為記憶細胞,然后隨機產生一定數目的新抗體進入記憶細胞群,此群體作為新抗體群,這構成隨機搜索鏈,即抗體群→選擇→克隆→突變→再選擇及未被選擇繁殖的抗體抑制、吸收新成員→新抗體群,這種鏈為一進化過程.2群體vppareto設D?Rn是有界閉區域,f:D→Rm為取值于Rm中的映射,則多目標極小化模型可描述為:(VΡ)minx∈Df(x)=[f1(x)?f2(x),?,fm(x)]Τ其中D稱為可行解域,x∈D稱為可行解.不妨設f(x)≥0,x∈D.由于區間[0,1]與區間[a,b]之間存在可逆映射,因此也不妨設D中元素的每一分量皆在區間[0,1]上取值.若xi=[xi1,xi2,…,xin]T,i=1,2,滿足x1j≤x2j,1≤j≤n且存在1≤j0≤n使得x1j0<x2j0,則稱x1優于x2,記為x1≤x2;若x′∈D,在D中不存在x,使得f(x)≤f(x′),則稱x′是(VP)的Pareto最優解;稱D的非空子集X為群體;x∈D稱為個體;若x′∈X,群體X中不存在優于x′的其它個體,則稱x′是(VP)相對于群體X的Pareto最優個體,簡稱Pareto最優個體.以下簡要敘述免疫應答原理.在免疫系統中,免疫應答扮演著重要角色,任何抗原入侵免疫系統時,其皆作免疫應答.當抗原入侵機體時,免疫系統產生的抗體數量較少,機體抵御抗原的能力較弱,抗原清除也比較慢.由于免疫系統具有學習、識別、記憶、自保護、多樣性和自適應等特點,其經過一段時間后,抗體數目增加較快,這些抗體被激活、分化和繁殖,經由親和突變達到親和成熟,提高識別能力,此時,抗原被清除較快.剩余的抗體中,一部分抗體應答能力弱或產生自反應,被有效地清除,其余的抗體作為記憶細胞存于免疫系統中,防御同一抗原再次入侵,這種應答稱為免疫應答.此過程是一種進化過程,模擬其機理并構建免疫算法可解決多目標優化問題.3抗體群x中抗體的激活多目標優化免疫算法的運行機制如圖1所示.設抗體Ab(即(VP)的可行解)和抗原Ag(即(VP)的Pareto最優個體)表示為n維向量(分量取值于區間[0,1]上的有理數).由于免疫系統的每個B細胞僅攜帶一種類型的抗體,因此本文將B細胞與抗體視為同一.用|.|指群體規模,‖.‖表示n維向量的范數.用S表示由所有抗體構成的抗體空間,并設S為有限集,記N=|S|.用S≤N表示由所有規模不超過N的非空群體構成的抗體群空間.對于給定的抗原群Y,抗原刺激免疫系統,使得抗體群X中的部分抗體被激活,抗體Ab的親和力計算由下確定aff(Ab)=1+1|Y|∑j=1?f(Ab)f(Agj)?,Ab∈X,Agj∈Y(1)其中,<.,.>表示n維向量的內積.在此,用內積比用歐氏距離更能確切地刻畫抗體識別抗原群的總體能力.親和力越高的抗體,識別抗原群的能力越強;反之,則越弱.設x,y∈X,若f(x)≤f(y),則置dy(x)=1.于是可引入X中抗體的增強度strength(x)=∑y∈Xdy(x)下面將圖1中各操作定義為算子.定義1所謂克隆選擇,是指在給定的選擇率ζ‰下,在抗體群中選擇部分抗體的映射,Ts:S≤N→S.即設X0為抗體群X中Int(ζ‰|X|)個親和力較高的抗體構成的群體,其中Int(.)表示取整函數.按如下概率規則選擇Int(ζ‰|X|)個抗體Ρ(ΤCS(X)i=Xi)={1,Xi∈X00,Xi?X0定義2設X為給定的抗體群,所謂細胞克隆是指抗體群到S≤N的一個映射,Tc:S→S≤N,它是隨機映射,其作用方式是,對于Ab∈X,按其繁殖率λ復制NAb個克隆細胞,即ΝAb=(|Y|-1λaff(Ab))θ其中λ為區間[1/(2(1+aff(Ab))),1/(1+aff(Ab))]上的隨機數,1<θ<1.5為參數.此定義表明對于給定的抗體群X,抗體繁殖的克隆細胞個數與其親和力成正比,且每一抗體所繁殖的克隆細胞個數都大于給定抗原群的規模.親和突變是提高抗體識別抗原能力的主要途徑,識別能力強的抗體遭受突變的可能性小;反之,則突變的可能性大.定義3設Ag為給定的抗原,所謂親和突變是指抗體空間S到自身的隨機映射,Tm:S→S,即(1)超級突變：對于與ab對應的ab，隨機生成[0]中的隨機數，使ab轉化為abAb′←Ab+β(Ag-Ab)其中,α與Ab對Ag的親和力成正比.此處選定為α=1-exp(-∥Ag-Ab∥)(2)(2)免疫選擇算子對抗體Ab,以突變率α作為概率,對其各基因位置上的基因在0到9之間隨機突變,其中α由式(2)確定.基因位置指Ab的小數點后的數所對應的位置.高親和力抗體所繁殖的克隆細胞經突變后,有的細胞的親和力提高,有的卻降低,而親和力降低的細胞將被隨機產生的新抗體或已存在的其它抗體抑制并最終被消除.為此引入免疫選擇算子.定義4所謂免疫選擇指在抗體群中選擇抗體,它是隨機映射,Tis:S≤N→S,按如下概率規則Ρ{Τ(X)i=Xi}=exp(aff(Xi)/Τn)∑xj∈Xexp(aff(xj)/Τn)選擇抗體群X中的抗體,其中Tn=ln((T0/n)+1)為退溫函數,T0為初始溫度,n為時間.從免疫機理的角度,其免疫選擇反映了隨著時間的延長,抗體已達到親和成熟,幾乎不受突變的影響,免疫系統處于相對平衡狀態.定義5所謂吸收新成員是指在抗體空間S中隨機選擇一個抗體的映射.用T(S)表示選擇的抗體,Td(S)表示選擇的d個抗體.定義6設X是抗體群,所謂小生境抑制是指在小生境中選擇一個親和力最高的抗體的映射,Tch:S≤N→S.即設Xi,i=1,2,…,q,是X的q個子群,X=q∪i=1Xi,xi是Xi中親和力最高的抗體,按下列概率規則選擇q個抗體Ρ(Τch(X)=Xi)={1Xi=xi,i=1,2,?,q0否則4使用多目標優化免疫算法為了定量地度量抗原群中抗原之間的關系,引入二元函數d:R×R→R,被給定為d(x,y)={0x＞y1x≤y由于抗原群Y中抗原之間具有相互競爭力,這些抗原對免疫系統的激勵具有強弱之分,因此抗原群Y中每一抗原有激活其它抗原的能力,這稱為激活力,由下式確定D(Ag)=|Y|∑j=1R(f(Ag),f(Agj))|Y|∑i,j=1R(f(Agi),f(Agj)),Ag,Agi,Agj∈Y其中R(F1,F2)=m∑i=1d(xi,yi),F1=[x1,x2,?,xm]Τ,F2=[y1,y2,?,ym]Τ于是抗原群聚類算法可描述如下:(1)置初始抗原群為C;(2)將C按∥Agi-Agj∥＜σ(3)劃分為子群,選出每個子群中激活力最高的一個抗原構成抗原群C′;(3)若‖C′‖>N0,則C←C′,并調整參數σ及返回步驟(2);否則結束.于是利用定義1至定義6及抗原群聚類算法可描述多目標優化免疫算法如下:(1)隨機產生初始抗體群A0,初始抗原群B0為空集.(2)復制An中增強度最高的抗體作為抗原入抗原群Bn,并用抗原聚類算法消去Bn中冗余的抗原;若An∩Bn=φ,則復制An中最高增強度的一個抗體作為抗原于Bn中,此抗原群作用抗體群An.(3)按選擇率ξ‰將An作用克隆選擇算子,選擇Nn=Int(ξ‰|An|)個親和力較高的抗體構成抗體群An1,其余的抗體構成An2.(4)按類似于式(3)的方式將An2劃分為子群,并作用小生境抑制算子,獲記憶細胞群An21.(5)將An1作用細胞克隆及親和突變算子,每抗體Ab所繁殖的NAb個克隆中|Bn|個克隆相應與Bn中抗原作用超突變算子;對其余的每個克隆Ab,隨機選擇Bn中的一個抗原Ag,并將Ab作用均勻隨機突變算子.將此兩步所獲的克隆組合并消除相同的克隆,獲抗體群An11.(6)An11作用免疫選擇算子,選擇Int(η‰|An11|)個抗體構成抗體群An12.(7)隨機產生dn=Int(μ‰|An|)+1個新抗體插入記憶細胞群An21∪An12,獲下一抗體群An+1.(8)若滿足終止條件,則結束;否則,返回步驟(2).此免疫算法有許多特征,如:群體規模動態調整及群體并行搜索Pareto最優解;合理體現Pareto最優解的概念;利用免疫選擇及突變算子增強搜索能力;隨機產生新抗體,增強群體多樣性及提高搜索速度;Pareto最優個體被保存于抗原群且抗原群不斷更新;群體合作進化及引入小生境技術等.5基于an的多目標優化模型為敘述方便,稱S≤N中每一元素為狀態,表示為i.由該算法可知An→(An1,An2)→(An1,A21)→(An11,An21)→(An12,An21)→(An12,An21,Τdn(S))→An+1構成一隨機搜索過程.用Ain表示n時刻抗體群處于狀態i,則Ain經一步轉移為Ajn+1時,狀態j由三部分構成,即j=(j1,j2,j3),其中Aj1n+1=ΤisΤmΤcΤs(Ain)=Aj1n12,Aj1n+1=Τch(Ain\Τs(Ain)),Aj3n+1=Τdn(S)由于An在狀態i條件下,Tdn(S)僅與狀態i有關,An+1僅與時刻n所處狀態及Bn中抗原有關,與n時刻以前的任何狀態無關,同時狀態空間S為有限維,因此該算法可描述為有限馬爾可夫鏈.但由于突變算子Tm與時間n有關,因而此馬氏鏈是非齊次的.用P(Ain)表示n時刻An處于狀態i的概率,P(Ajn+1|Ain)表示Ain經一步轉移為Ajn+1的概率.設M*為多目標優化極小化模型(VP)的Pareto最優解構成的集合.于是,可獲如下結論,其證明可基于文獻及文獻的方法獲之,限于篇幅,在此省略結論的證明.定理1若0<μ<ξ(1-ηNθ%),則有2≤|An|≤|A1|+1ζ%(1-Νθη%)-μ%此定理表明,在該算法中,抗體群的規模始終是有限數,且由于新抗體產生的隨機性,抗體群的規模不恒同.引理1設i,j∈S≤N,i∩M*≠φ,j∩M*=φ,則必有Ρ(Ajn+1|Ain)=0引理2設i,j1∈S≤N,i∩M*≠φ,j1∩M*=φ,則Ρ(Aj1n+1|Ain)≤εn,εn→0,n→∞引理3對任意i∈S≤N,必有Ρ(An+1∩Μ*=φ|Ain)≤(1-|Μ*||S|)1+μ%定理2若0<μ<ξ(1-ηNθ0%),則多目標優化免疫MOIA算法是概率收斂的,即limn→∞Ρ(An∩Μ*≠φ)=1.6spea求解為了驗證MOIA解決多優化問題的有效性,將此算法與SPEA進行比較.在比較中,對于SPEA,參數選定為:群體大小80,交叉概率0.6,突變概率0.001,外記憶集的規模為200,迭代次數200;對于MOIA,選擇初始抗體群體為80,ζ=