摘要

本文通過對生物免疫系統對外來抗原入侵響應過程的研究,提出了對免疫遺傳算法的改進方案。

并對改進的免疫遺傳算法的步驟和有效性進行了分析,證明了算法的收斂性。具體完成了以下研究工作:首先利用生物免疫原理中的濃度調節機制和個體多樣性保持策略以及免疫記憶功能,提出了基于相似性矢量距為選擇概率的免疫遺傳算法。該算法可以有效地克服基本遺傳算法的未成熟收斂現象,既可以提高抗體的相似性又可以兼顧到抗體的多樣性,為避免算法陷入局部最優解,縮短搜索時間提供了保證。同時給出了此類算法的一般表示形式。

最后,將改進的免疫粒子群算法應用于函數優化問題。通過實驗,確定了算法中參數的取值范圍。

生命現象和生物的智能行為一直為人工智能研究者所關注。而自然免疫系統正是人工智能方法靈感的重要源泉之一。免疫系統在顯示學習、適應性、記憶機制等應用于不同計算任務的方法方面可以給人們提供豐富的靈感和啟示。從人體免疫系統發展出的計算方法已經引起許多不同領域廣泛的研究興趣。受人類自然免疫系統的啟發，現在已經提出了各種人工免疫算法。人工免疫算法是模擬自然免疫系統功能的一種智能方法，它實現一種受生物免疫系統啟發，通過學習外界物質的自然防御機理的學習技術，提供噪聲忍耐、無師學習、自組織、記憶等進化學習機理，結合了分類器、神經網絡和機器推理等系統的一些優點，因此具有提供新穎的解決問題的方法的潛力。它已經成為繼神經網絡、模糊邏輯推理和進化計算后人工智能的又一研究熱點。

思維進化算法是模擬人類思維進化過程的一種新型進化算法，其中的趨同與異化的概念對于目前正在大量廣泛研究的人工免疫算法有著重要的啟示。

根據人工免疫和思維進化的特點，本文提出了人工免疫思維進化算法。該算法借鑒了思維進化中的上述特點，引入了趨同半徑和異化半徑的概念，這樣抗體根據克隆擴增和受體編輯的原理分別進行局部競爭和全局競爭，實現了兩層搜索機制。另外，算法中強調了免疫記憶的優良抗體保持作用。

免疫遺傳算法可以看作一種新型融合算法,也是一種改進的遺傳算法,一種新型計算智能方法,是具有免疫功能的遺傳算法。與免疫算法一樣,把待求解的問題對應為抗原,問題的解對應為抗體,在許多方面表現出超越遺傳算法和免疫算法的優點,目前應用相對較為廣泛,比如神經網絡設計、問題、信號分析、色譜分析、設計等等。這些算法既保留了遺傳算法的搜索特性,克服遺傳算法由于交叉搜索而在局部搜索特性,克服遺傳算法由于交叉搜索而在局部搜索解空間上效率較差的缺點,又在很大程度上避免未成熟收斂。該算法一般形式如圖一所示。

免疫遺傳算法與免疫算法在形式上看,就是在免疫算法中加入了遺傳算子,與遺傳算法相比,增加了抗原識別、記憶功能和調節功能,沒有附加復雜的操作,沒有降低遺傳算法的魯棒性,算法兼顧了搜索速度、全局搜索能力和局部搜索能力。免疫遺傳算法一般形式只是要表明免疫機制對進化算法的作用。

免疫遺傳算法的主要特點有：

1.多樣性抗體

通過細胞分化,免疫系統可產生大量不同的抗體來抵御各種抗原。利用該特點可維持進化過程中個體的多樣性,提高全局搜索能力,避免陷入局部最優解。

2.個體濃度的抑制和促進

免疫系統的平衡機制通過對抗體的促進和抑制作用,經自我調節產生適當數量的必要抗體。利用這一特點可提高進化算法的局部搜索能力,加快計算收斂速度,從而提高個體適應環境的能力。

3.記憶能力

免疫系統的記憶功能是當適量的抗原侵入時,免疫系統會相當準確地與之響應。以后再有不同抗原入侵時,不論數量的多少,免疫系統都會迅速而且準確地與之響應。這樣能夠減少搜索時間,使之快速的收斂到最優解。

4.遺傳算子

在編碼方案、適應度函數及遺傳算子確定后,遺傳算法將利用進化過程中獲得的信息自行組織搜由于基于自然的選擇策略為“適者生存,不適應者被淘汰”,因而適應度大的個體具有較高的生存索概率。通常,適應度大的個體具有更適應環境的基因結構,再通過基因重組交叉和基因突變變異等遺傳操作,就可能產生更適應環境的后代。選擇操作消除了算法設計過程中的一個最大的障礙,即需要事先描述問題的全部特點,并要說明針對問題的不同特點算法應采取的措施。因此,我們可以解決那些復雜的非結構化問題。

本文基于人工免疫原理,提出了一種新型的免疫遺傳算法,采用二進制編碼,通過引入小生境概念,將演化種群分為若干個小子群以實現種群隔離,采用了一種自適應式的選擇機制,并與免疫系統的克隆選擇和克隆抑制機制相結合,能夠有效的促進優秀抗體的繁殖,抑制濃度過高的抗體,保證抗體的多樣性,提高個體的適應度和防卜種群的退化,提高收斂速度。本算法的流程圖如圖二所示。

免疫系統中抗原消失很長時間,抗體形成細胞仍然具有免疫記憶,從而以后抗原入侵時,生物體根據自身免疫網絡可以很快生成對應的抗體來中和抗原。這里我們引入該功能,計算小生境內各個抗體的適應度值,如果本次計算得到的最大適應度值大于已有的最優值,則將對應的解保存到記憶表中,否則從記憶表中選擇歷次得到的最優解并進行選擇、交叉和變異操作,得出適應度更高的解作為免疫抗體。

生物體由于機體本身的新陳代謝,每天有的低激勵值細胞死亡,而代之以從骨髓中生成全新的細胞,而且新產生的細胞只有具有較強適應性的才能融合到免疫系統中。模擬免疫行為中細胞的這種現象,算法中將小生境內的低適應度值的抗體去除,并代之以隨機產生的新解。

1.計算抗體的適應度

即抗體i與抗原之間的親和度。對于求優化問題可將抗體的適應度直接取對應的目標函數值,即。

2.計算抗體i,j之間的親和度

信息墑可作為狀態分散程度的度量,因此用信息嫡來描述抗體的多樣性及等位基因概率的變化進程。如圖三所示個抗體。

設有N個抗體,抗體長度為M,等位基因的種類為S,則N個抗體第j位基因信息嫡為:

其中為第i個抗體的等位基因源于第j個基因的概率。如果在位置上所有抗體的等位基因都相同,那么等于零。

平均信息嫡為:

抗體i,j之間的新口度,反應兩抗體之間的相似度:

越大,表示抗體i,j越親和。

3.計算抗體的濃度

抗體i的濃度表示群體中相似抗體所占的比重。

其中

µ為一固定值。

4.基于抗體濃度和適應度的自適應式選擇策略

為保證群體的多樣性,通過選擇機制進行抗體的促進與抑制調節。本文中提出在每代抗體i適應值上疊加一個服從態分布的最優個體所對應的適應值,及其與該抗體的濃度相結合的方法來確定抗體i是否被選擇進行以卜的步驟。抗體i的選擇概率公式如下:

其中

——抗體i的選擇概率

——疊加正態分布變量的適應度值

——抗體i的濃度

——為自適應式的可變因子,其隨著進化代數的增加而減小。

基于抗體濃度和適應度的白適應式選擇策略能有效的抑制濃度過高的抗體繁殖,保證了抗體的多樣性,避免算法陷入局部最優值。并且,采用正態分布式的選擇策略能夠將優秀抗體附近的個體保留下來,減少收斂時間,提高算法的搜索速度。

基于免疫的粒子群算法是在免疫算法的基礎上采用粒子群優化對抗體群體進行更新，可以解決免疫算法收斂速度慢的缺點。

對于這個函數,用基于免疫的粒子群算法步驟：

1.確定學習因子c1和c2、粒子（抗體）群體個數M。

2.由logistic回歸分析映射產生M個粒子（抗體）及其速度,其中i=1,2,...,N,最后形成初始粒子（抗體）群體.

3.產生免疫記憶粒子（抗體）。計算當前粒子（抗體）群體P中粒子（抗體）的適應值并判斷算法是否滿足結束條件，如果滿足則結束并輸出結果，否則繼續運行。

4.更高局部和全局最優解，并根據下面公式更新粒子位置和速度；

5.由logistic映射產生N個新的粒子（抗體）。

6.基于濃度的粒子（抗體）選擇。用群體相似抗體百分比計算產生N+M個新粒子（抗體）的概率，依照概率大小選擇N個粒子（抗體）形成粒子（抗體）群P然后轉入第（3）步。

7.圖五為免疫粒子群算法流程圖

圖五為函數優化結果：

圖五

圖六為基于免疫粒子群優化算法收斂結果：

圖六

本文提出一種免疫粒子群優化算法,該算法保留了一般免疫算法的基于抗體生存期望值的選擇策略,以保證抗體群體的多樣性,采用了交叉和變異產生新的抗體群體。在此基礎上,應用了粒子群優化對群體進行更新,本文并沒有完全采用粒子群優化表達式對群體進行更新,而是根據免疫算法的特點對其進行了簡化,使每個個體只跟蹤全局極值,使群體進化具有更明確的方向性,從而加快算法的收斂速度。通過求解六峰駝背函數的最大值驗證了算法的有效性,并將其與一般的免疫算法進行了比較。

由于本文提出的免疫粒子群算法是在一般免疫算法的基礎上加進了粒子群更新而得到的,所以在運行速度上可能要慢些,但是收斂速度確實能夠得到滿意的性能,下一步的工作是進一步加快算法的運行速度,對算法的有效性進行更全面、更有效的驗證。