龍著乾 戴祖國(guó)

（海南軟件職業(yè)技術(shù)學(xué)院，海南 瓊海571400）

0 引言

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

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

1 免疫算法的發(fā)展歷程

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

圖1 生物免疫系統(tǒng)的組成結(jié)構(gòu)

當(dāng)外部病原體或細(xì)菌侵入機(jī)體時(shí)，免疫細(xì)胞能夠識(shí)別“自體”和“非自體”，迅速清除和消滅異物，確保機(jī)體的安全性。生物免疫系統(tǒng)的這種能力，具有多樣性、耐受性、大規(guī)模并行分布處理、自組織、自學(xué)習(xí)、自適應(yīng)、免疫記憶和魯棒性等特點(diǎn)，根據(jù)這種自然現(xiàn)象，人們?cè)O(shè)計(jì)了免疫算法，近年來該算法受到國(guó)內(nèi)外眾多學(xué)者的高度重視。

由生物引發(fā)的信息處理系統(tǒng)可以分為：人工神經(jīng)網(wǎng)絡(luò)，進(jìn)化計(jì)算和人工免疫系統(tǒng)。其中，人工神經(jīng)網(wǎng)絡(luò)和進(jìn)化計(jì)算已經(jīng)被廣泛地應(yīng)用于各個(gè)領(lǐng)域，并產(chǎn)生了巨大的經(jīng)濟(jì)效益和社會(huì)效益。近年來，隨著人們對(duì)免疫系統(tǒng)機(jī)理的進(jìn)一步揭示，關(guān)于人工免疫系統(tǒng)的理論研究和應(yīng)用研究倍受關(guān)注，一些研究成果已經(jīng)被廣泛用于機(jī)器學(xué)習(xí)、故障診斷、機(jī)器人行為仿真和控制、網(wǎng)絡(luò)入侵檢測(cè)和函數(shù)優(yōu)化等眾多領(lǐng)域，表現(xiàn)出卓越的性能和效率。

2 免疫算法的基本原理

基本免疫算法基于生物免疫系統(tǒng)基本機(jī)制，模仿了人體的免疫系統(tǒng)?；久庖咚惴◤捏w細(xì)胞理論和網(wǎng)絡(luò)理論得到啟發(fā)，實(shí)現(xiàn)了類似于生物免疫系統(tǒng)的抗原識(shí)別、細(xì)胞分化、記憶和自我調(diào)節(jié)的功能[6]。如果將免疫算法與求解優(yōu)化問題的一般搜索方法相比較，那么抗原、抗體、抗原和抗體之間的親和性分別對(duì)應(yīng)于優(yōu)化問題的目標(biāo)函數(shù)、優(yōu)化解、解與目標(biāo)函數(shù)的匹配程度。圖2顯示的是克隆選擇原理示意圖。

圖2 克隆選擇原理示意圖

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

（1）隨機(jī)產(chǎn)生一定規(guī)模的初始抗體種群A1，并令進(jìn)化代數(shù)k=0；

（2）對(duì)當(dāng)前第k代抗體群Ak進(jìn)行交叉操作，得到種群Bk；

（3）對(duì)Bk進(jìn)行變異操作，得到抗體群Ck；

（4）對(duì)Ck進(jìn)行接種疫苗操作，得到種群Dk；

（5）對(duì)Dk進(jìn)行免疫選擇操作，若當(dāng)前群體中包含最佳個(gè)體，則算法結(jié)束并輸出結(jié)果；否則，跳轉(zhuǎn)到步驟(2)。

3 免疫算法的改進(jìn)與優(yōu)化

人工免疫系統(tǒng)是模仿自然免疫系統(tǒng)功能的一種智能方法，是繼人工神經(jīng)網(wǎng)絡(luò)、進(jìn)化計(jì)算之后新的智能計(jì)算研究方向，是生命科學(xué)和計(jì)算機(jī)科學(xué)相交叉而形成的交叉學(xué)科研究熱點(diǎn)。

在進(jìn)化計(jì)算基礎(chǔ)上，動(dòng)態(tài)閾值免疫算法是一種適合于求解優(yōu)化多參問題的動(dòng)態(tài)閾值方法。該方法結(jié)合抗體間的相似度確定初始閾值，通過構(gòu)造閾值遞減函數(shù)約束動(dòng)態(tài)閾值的衰減幅度，避免產(chǎn)生相似的抗體，有效克服免疫克隆選擇算法優(yōu)化多參問題時(shí)產(chǎn)生的近親繁殖和早熟收斂問題。

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

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

4 結(jié)論

生物信息系統(tǒng)的計(jì)算能力受到國(guó)內(nèi)外專家學(xué)者的普遍關(guān)注。近年來，以神經(jīng)計(jì)算、進(jìn)化計(jì)算、DNA計(jì)算及免疫計(jì)算等仿生計(jì)算為代表的計(jì)算智能技術(shù)得到了空前的發(fā)展，掀起了仿生計(jì)算的新高潮。在未來信息學(xué)科發(fā)展領(lǐng)域，免疫算法及其相關(guān)的智能優(yōu)化算法將會(huì)扮演著越來越重要的角色。

［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.