免疫算法的基本原理及其優化改進方法概述

龍著乾 戴祖國

（海南軟件職業技術學院，海南 瓊海571400）

0 引言

在生命科學領域中，人們已經對遺傳(Heredity)與免疫(Immunity)等自然現象進行了廣泛深入的研究。20世紀60年代Bagley和Rosenberg等學者在對這些研究成果進行分析與理解的基礎上，借鑒其相關內容和知識，特別是遺傳學方面的理論與概念，并將其成功應用于工程科學的某些領域，收到了良好的效果[1]。遺傳算法在迭代過程中，存在隨機地、沒有指導地迭代搜索，因此種群中的個體在提供了進化機會的同時，也無可避免地產生了退化的可能。由于遺傳算法的交叉和變異算子相對固定，導致在求解一些復雜優化問題時，容易忽視問題的特征信息對求解問題時的輔助作用。

由于遺傳算法在模仿人類智能信息處理方面還存在嚴重不足，導致國內外研究者力圖將生命科學中的免疫概念引入到工程實踐領域，通過相關的知識與理論，構建新的智能搜索算法，從而來提高算法的整體性能[2-3]。為了實現上述目標，研究人員將免疫概念及其理論應用于遺傳算法，在保留原算法優良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特征信息或知識來抑制其優化過程中出現的退化現象，這種在遺傳算法基礎上誕生的新智能算法稱為免疫算法(Immune Algorithm)。

1 免疫算法的發展歷程

Immune(免疫)是從拉丁文Immunise衍生而來的，在早些時期，人醫學專家就注意到傳染病患者在病愈后，對該病有不同程度的免疫力。在醫學研究領域，免疫是指機體接觸抗原性異物的一種生理反應[4]。免疫系統有能力自動產生很多不同抗體，免疫系統的控制機制會自動完成調節功能，從而自適應產生滿足一定需求的抗體[5]。如果上述過程能連續反復地進行，就能構成對自身的免疫，人體就會通過所有淋巴細胞的作用實現了調節機制。圖1描述的是生物免疫系統的組成結構。

圖1 生物免疫系統的組成結構

當外部病原體或細菌侵入機體時，免疫細胞能夠識別“自體”和“非自體”，迅速清除和消滅異物，確保機體的安全性。生物免疫系統的這種能力，具有多樣性、耐受性、大規模并行分布處理、自組織、自學習、自適應、免疫記憶和魯棒性等特點，根據這種自然現象，人們設計了免疫算法，近年來該算法受到國內外眾多學者的高度重視。

由生物引發的信息處理系統可以分為：人工神經網絡，進化計算和人工免疫系統。其中，人工神經網絡和進化計算已經被廣泛地應用于各個領域，并產生了巨大的經濟效益和社會效益。近年來，隨著人們對免疫系統機理的進一步揭示，關于人工免疫系統的理論研究和應用研究倍受關注，一些研究成果已經被廣泛用于機器學習、故障診斷、機器人行為仿真和控制、網絡入侵檢測和函數優化等眾多領域，表現出卓越的性能和效率。

2 免疫算法的基本原理

基本免疫算法基于生物免疫系統基本機制，模仿了人體的免疫系統。基本免疫算法從體細胞理論和網絡理論得到啟發，實現了類似于生物免疫系統的抗原識別、細胞分化、記憶和自我調節的功能[6]。如果將免疫算法與求解優化問題的一般搜索方法相比較，那么抗原、抗體、抗原和抗體之間的親和性分別對應于優化問題的目標函數、優化解、解與目標函數的匹配程度。圖2顯示的是克隆選擇原理示意圖。

圖2 克隆選擇原理示意圖

免疫算法是基于生物免疫學抗體克隆的選擇學說，而提出的一種新人工免疫系統算法-免疫克隆選擇算法（Immune Clonal Selection Algorithm，ICSA）。該算法具有自組選擇學習、全息容錯記憶、辯證克隆仿真和協同免疫優化的啟發式人工智能。由于該方法收斂速度快，求解精度高，穩定性能好，并有效克服了早熟和騙的問題，成為新興的實用智能算法。免疫算法的基本實現步驟如下：

（1）隨機產生一定規模的初始抗體種群A1，并令進化代數k=0；

（2）對當前第k代抗體群Ak進行交叉操作，得到種群Bk；

（3）對Bk進行變異操作，得到抗體群Ck；

（4）對Ck進行接種疫苗操作，得到種群Dk；

（5）對Dk進行免疫選擇操作，若當前群體中包含最佳個體，則算法結束并輸出結果；否則，跳轉到步驟(2)。

3 免疫算法的改進與優化

人工免疫系統是模仿自然免疫系統功能的一種智能方法，是繼人工神經網絡、進化計算之后新的智能計算研究方向，是生命科學和計算機科學相交叉而形成的交叉學科研究熱點。

在進化計算基礎上，動態閾值免疫算法是一種適合于求解優化多參問題的動態閾值方法。該方法結合抗體間的相似度確定初始閾值，通過構造閾值遞減函數約束動態閾值的衰減幅度，避免產生相似的抗體，有效克服免疫克隆選擇算法優化多參問題時產生的近親繁殖和早熟收斂問題。

自適應免疫算法(Adaptive Immune Algorithm,AIA)屬于一種動態的免疫優化算法。該算法的交叉算子隨著群體規模動態變化，同時選擇概率也是隨著抗體的濃度進行動態更新。AIA算法能較好地跳出算法的局部最優值，從而在一個更大的范圍內找尋最優解。自適應免疫算法引入了領域的概念，通過擴展和突變操作對多個可行解進行領域搜索，實現了在局部和全局范圍內同時尋優。

一種基于局部高斯變異算子的免疫克隆選擇算法（Immune Clonal Selection Algorithm Introduced into Local Gaussian Mutation Operator，ICSA-LGMO）是混合免疫算法[7]。在該算法執行過程中，高斯變異繼承了高斯分布具有的集中性、對稱性和均勻變動性等優良特征，具有較好的局部搜索能力。該算法的改進措施主要是通過構造并引入局部高斯變異算子指導抗體基因變異，利用局部高斯變異的小步長不斷地自適應調整與變換，實現抗體基因在局部區域上的擾動，搜索原抗體附近比原抗體更好滿足問題的新抗體和基因，從而形成新的抗體。

4 結論

生物信息系統的計算能力受到國內外專家學者的普遍關注。近年來，以神經計算、進化計算、DNA計算及免疫計算等仿生計算為代表的計算智能技術得到了空前的發展，掀起了仿生計算的新高潮。在未來信息學科發展領域，免疫算法及其相關的智能優化算法將會扮演著越來越重要的角色。

［1］M.Kaya,Multi-objective genetic algorithm based approaches for mining optimized fuzzy association rules,Soft Comput,2006,10(7)：578-586.

［2］Hisao Ishibuchi,Takashi Yamamoto.Fuzzy rule selection by multi-objective Genetic local search algorithm and rule evaluation measures in data mining[J].Fuzzy Sets and Systems,2004,141(2)：59-88.

［3］A.Jaszkiewicz,Genetic local search for multi-objective combinatorial optimization,European J[J].Oper.Res.2002,137(1)：50-71.

［4］T.Hong,C.Chen,Y.Wu,Y.Lee,A GA-based fuzzy mining approach to achieve a trade-off between number of rules and suitability of membership functions,Soft Comput[Z].2006,10(11)：1091-1101.

［5］Weisheng Dong,Guangming Shi,Li Zhang.Immune memory clonal selection algorithms for designing stack filters[J].Neurocomputing,2007,70(3)：777-784.

［6］LI Yang-Yang,JIAO Li-Cheng.Quantum-Inspired Immune Clonal Algorithm for SAT Problem[J].Chinese Journal of Computers,2007,30(2)：176-183.

［7］Riyaz,s.,Selwyn P.Efficient genetic algorithm based data mining using feature selection with hausdorff distance[J].Information Technology and Management,2005,6(4)：315-331.