免疫計算概述

前言

如今，人工智能已經(jīng)是世界各國高度重視的一個熱點領(lǐng)域，相關(guān)的研究和應(yīng)用在學(xué)術(shù)界、產(chǎn)業(yè)界都是如火如荼。一般認為，機器學(xué)習(xí)是人工智能領(lǐng)域中的熱點方向，而深度學(xué)習(xí)則是機器學(xué)習(xí)中的熱點分支。眾所周知，深度學(xué)習(xí)的前身是人工神經(jīng)網(wǎng)絡(luò)，或者更早一些的感知機，其思想來源于人類腦神經(jīng)細胞構(gòu)成的神經(jīng)網(wǎng)絡(luò)，屬于計算智能的一個分支。

在計算智能領(lǐng)域，受人體信息處理機制啟發(fā)而設(shè)計的計算模型主要包括深度學(xué)習(xí)、進化計算和免疫計算等。目前，深度學(xué)習(xí)就像正午 12 點的太陽，備受研究和開發(fā)人員喜歡，從者甚眾。相比之下，進化計算則像是早晨八九點鐘的太陽。今年 IEEE 進化計算匯刊的影響因子已達到11.169，從側(cè)面說明其影響力已經(jīng)不可小覷。至于免疫計算，則是剛剛露出曙光，還有很多不確定性和未知的東西需要探索和研究。

與深度學(xué)習(xí)和進化計算不同，免疫計算是受生物免疫系統(tǒng)中所蘊含的信息處理機制啟發(fā)而來的。生物免疫系統(tǒng)是生物體的自我保護系統(tǒng)，具有免疫防御、免疫監(jiān)視和免疫自穩(wěn)等功能，是一個復(fù)雜自適應(yīng)系統(tǒng)。因此，生物免疫系統(tǒng)可視為自然界一個典型的安全智能系統(tǒng)，其中蘊含的機制非常值得我們?nèi)ヌ剿骱脱芯?，并設(shè)計出新穎高效的免疫計算理論、方法和系統(tǒng)。

在此背景下，特邀了西安電子科技大學(xué)焦李成老師、四川大學(xué)李濤老師、深圳大學(xué)林秋鎮(zhèn)老師，以及鄭州輕工業(yè)學(xué)院張偉偉老師各自所領(lǐng)銜的團隊，對免疫計算的基本現(xiàn)狀，以及克隆選擇算法、否定選擇算法、免疫優(yōu)化圖像解釋、多目標免疫算法進行了綜述，希望能對免疫計算這一新的計算智能分支的發(fā)展有所推動。

作者：羅文堅

0 引言

免疫計算（Immune Computation）又稱為人工免疫系統(tǒng)（Artificial Immune Systems），是計算智能領(lǐng)域中新興的一個重要研究方向，其基本模型和算法受生物免疫系統(tǒng)啟發(fā)而來。從信息處理的角度來看，生物免疫系統(tǒng)是一個具有自我學(xué)習(xí)和自我保護能力的自適應(yīng)系統(tǒng)，是一個典型的安全智能系統(tǒng)，可為新一代計算智能、人工智能模型和方法提供靈感。國內(nèi)外研究者將生物免疫系統(tǒng)所隱含的信息處理機制引入計算機科學(xué)領(lǐng)域，已提出了多種免疫計算模型和算法，逐漸形成了免疫計算這一研究領(lǐng)域。

免疫計算相關(guān)的研究發(fā)軔于20世紀80年代中期， 并在 90 年代得到初步發(fā)展。1986 年，F(xiàn)armer 等首次提出了從生物免疫系統(tǒng)的自適應(yīng)機制啟發(fā)而來的機器學(xué)習(xí)模型。1990 年，Bersini和 Varela 提出了將免疫網(wǎng)絡(luò)理論用于求解自適應(yīng)問題的一些思路。同年，Ishida 提出了面向分布式故障檢測的基于免疫網(wǎng)絡(luò)原理的并行分布式處理模型。1994 年，F(xiàn)orrest 等基于免疫 T 細胞成熟機制和識別原理提出了負選擇模型和算法，這是第一個典型的免疫計算模型和方法，盡管比較簡單。隨后，從上個世紀90年代末至今，克隆選擇算法 (Clonal Selection Algorithms) 、人工免疫網(wǎng)絡(luò)算法 (Artificial Immune Network) 和樹突細胞算法（Dendritic Cell Algorithms） 相繼提出，并逐漸形成了免疫計算領(lǐng)域的四個典型研究分支，即信息負表示、克隆選擇算法、人工免疫網(wǎng)絡(luò)算法和樹突細胞算法。在應(yīng)用方面，免疫計算模型和算法已被廣泛應(yīng)用在異常檢測、網(wǎng)絡(luò)安全、隱私保護、復(fù)雜優(yōu)化問題求解、模式分析和機器學(xué)習(xí)等領(lǐng)域，均取得了不少進展。

伴隨著免疫計算研究的發(fā)展，一系列相關(guān)的學(xué)術(shù)活動 也 隨之誕生和發(fā)展起來。IEEE 計算智能協(xié)會下的演化計算技術(shù)委員會（IEEE CIS ECTC）專門成立了Task Force on Artificial Immune Systems 用于推動免疫計算領(lǐng)域的研究與發(fā)展。近年來，在IEEE Symposium Series on Computational Intelligence （IEEE SSCI）系列會議中，都有舉行 IEEE Symposium on Immune Computation（IEEEIComputation）免疫計算研討會。而演化計算領(lǐng)域的重要會議 IEEE Congress on Evolutionary Computation（CEC）已舉辦過多年的人工免 疫 系 統(tǒng) 主 題 研 討 會（Special Session）。

IEEE Transactions on Evolutionary Computation、IEEE Transactions on Emerging Topics in Computational Intelligence、Applied Soft Computing、Swarm and Evolutionary Computation、Natural Com-putation、Information Sciences、Engineering Applications of Artificial Intelligence、Neural Computing and Applications、Swarm Intelligence、Genetic Programming and Evolvable Machines 和 Theoretical Computer Sciences 等國際知名學(xué)術(shù)期刊都曾出版過以免疫計算為主題的 專 刊（Special Issue）。2015 年，免疫計算領(lǐng)域的兩位知名學(xué)者 Stephanie Forrest 和DipankarDasgupta 當(dāng)選 IEEE Fellow，其主要貢獻均包括免疫計算方面的研究工作。

1 生物免疫系統(tǒng)簡述

生物免疫系統(tǒng)是生物體的自我保護系統(tǒng)，它代表著一系列生物學(xué)結(jié)構(gòu)和復(fù)雜的生物、化學(xué)反應(yīng)。免疫系統(tǒng)承擔(dān)著檢測、清除各類病原體和有害物質(zhì)，保護生物體生命健康的重大責(zé)任。人類對免疫系統(tǒng)的研究有著悠久的歷史，直到今天，免疫系統(tǒng)依然是人類醫(yī)學(xué)和生命科學(xué)最重要的研究對象之一。在這些研究中，許多免疫學(xué)模型和專門學(xué)說被提出，比如克隆選擇學(xué)說、免疫網(wǎng)絡(luò)模型、免疫危險理論等，這些研究成果為計算機科學(xué)與技術(shù)研究者提供了靈感，為免疫計算的誕生和發(fā)展提供了生物免疫學(xué)基礎(chǔ)。

從構(gòu)成上來說，免疫系統(tǒng)由免疫器官、免疫細胞和免疫分子等構(gòu)成。其中，免疫器官主要負責(zé)制造免疫細胞，如脾臟和胸腺等。免疫細胞是與免疫應(yīng)答過程有關(guān)的細胞，如淋巴細胞和吞噬細胞等；而免疫分子則大多是由免疫細胞分泌的物質(zhì)，如抗體和補體等。

與許多系統(tǒng)類似，生物免疫系統(tǒng)也是一個分層系統(tǒng)，且一般分為三層。第一層由皮膚和粘膜等構(gòu)成的物理屏障；第二層主要依靠殺菌物質(zhì)和吞噬細胞等的防御功能，第一層和第二層是天生的非特異性免疫機制。第三層則是特異性免疫機制，也稱為獲得性免疫，免疫系統(tǒng)通過各種反應(yīng)識別入侵的病原體，并產(chǎn)生特異性的免疫反應(yīng)；病原體清除之后，部分免疫細胞可能成為記憶細胞并長期存在于體內(nèi)。當(dāng)相同病原體再次入侵時，特異性免疫系統(tǒng)會快速產(chǎn)生強有力的特異性免疫效果。值得一提的是，在免疫計算中，主要依靠的免疫學(xué)理論基礎(chǔ)就是第三層特異性免疫相關(guān)的理論和實驗研究成果。

2 代表性模型和算法

2.1 信息負表示

信息負表示（Negative Representation of Information）是免疫計算領(lǐng)域中的一個重要分支。這是一種新穎的數(shù)據(jù)表示方法，它由免疫T 細胞的“自我 - 非我”識別機制啟發(fā)而來：生物免疫系統(tǒng)中，能識別“自我”的免疫 T 細胞會被消滅，而不能識別“自我”的免疫 T 細胞則會成熟，并被用來識別“非我”。受到這一機制的啟發(fā)，信息負表示模型存儲和操作的一般是原始信息的補集（或其子集）。信息負表示有負選擇（Negative Selection）算法、負數(shù)據(jù)庫（Negative Databases）和負調(diào)查（Negative Surveys）三個主要研究方向。

負選擇算法（又稱為陰性選擇算法）最早由 Forrest 等于 1994 年提出，并在過去的 20 多年間得到了廣泛的研究。一個典型的負選擇算法可以概括為三步。首先，根據(jù)實際環(huán)境構(gòu)造自我樣本集合 S。接著，生成一個檢測器集合 D。特別地，D 中的每個檢測器都不能與 S 中的任何一個樣本匹配。最后，用檢測器集合 D 來監(jiān)測異常數(shù)據(jù)。只要被監(jiān)測數(shù)據(jù)能與 D 中任一檢測器匹配，那么它就被認為是異常數(shù)據(jù)。

負選擇算法已經(jīng)被應(yīng)用于如異常檢測、錯誤檢測、網(wǎng)絡(luò)與計算機安全等多個領(lǐng)域。例如，Dasgupta 等利用負選擇算法進行時序反常數(shù)據(jù)的監(jiān)控；Moncayo 等將負選擇算法用于檢測飛行器故障；Wang 等使用負選擇算法識別病毒和惡意代碼。

負數(shù)據(jù)庫是信息負表示的主要模型和重要研究方向之一， 這一概念最早由Esponda 及其同事在 2004 年前后提出。在負數(shù)據(jù)庫中，存儲和操作的是原始數(shù)據(jù)的補集。根據(jù)數(shù)據(jù)存儲的形式，負數(shù)據(jù)庫可以分為二進制負數(shù)據(jù)庫和實值負數(shù)據(jù)庫。當(dāng)前的研究以二進制負數(shù)據(jù)庫為主，因此這里僅扼要介紹二進制負數(shù)據(jù)庫。記全集為 U = {0, 1}n，DB = {x1, x2, ..., xm} 為包含m 個二進制串的正數(shù)據(jù)庫（即原始數(shù)據(jù)），那么 U?DB 為正數(shù)據(jù)庫的補集。為了壓縮存儲空間，引入符號 *，用來表示 0 和 1 中的任意一個。由此，U? DB 的壓縮表示形式就稱為 DB 的負數(shù)據(jù)庫（NDB）。NDB 中的每條記錄均可能包含三個符號 0、1、*。其中，值為 0 和 1 的位置稱為確定位，而值為 * 的位置稱為不確定位。舉例來說，如果 DB={000}，那么，一個可能的 NDB 則為 {1**, *1*, **1}。值得一提的是，二進制負數(shù)據(jù)庫能與 SAT 公式一一對應(yīng)，逆轉(zhuǎn)負數(shù)據(jù)庫則與求解對應(yīng)的 SAT 公式等價。因此，對負數(shù)據(jù)庫的研究而言，許多針對 SAT 問題的研究成果都是可以直接利用的。事實上，許多負數(shù)據(jù)庫生成算法就是由 SAT 公式生成算法轉(zhuǎn)化而來。

負數(shù)據(jù)庫已用于隱私保護、安全認證等多個領(lǐng)域。例如，Dasgupta 等使用負數(shù)據(jù)庫避免了認證過程中在前端直接暴露認證服務(wù)器數(shù)據(jù)；Luo 等則使用負數(shù)據(jù)庫提高了哈希口令認證的安全性。

負調(diào)查最早于 2006 年由 Esponda 等提出，是一種在保護受訪者隱私的前提下收集敏感信息的方法。在涉及到一些敏感或隱私信息的時候，若采用傳統(tǒng)的問卷調(diào)查手段，受訪者往往不愿意提供真實的信息。在負調(diào)查中，只要求被調(diào)查用戶選取一個（或一部分）與實際情況不相符合的類別（稱為負類別），并返回給數(shù)據(jù)收集者。而收集者，在收集完所用戶返回的負類別之后，便可以通過統(tǒng)計學(xué)的方法，估算出真實類別的分布。根據(jù)受訪者返回的負類別數(shù)量，負調(diào)查可以分為單選負調(diào)查和多選負調(diào)查兩類。而根據(jù)受訪者選擇不同選項的概率，負調(diào)查則可以分為均勻負調(diào)查和非均勻負調(diào)查，這里的“是否均勻”指的是受訪者是否以相同的概率選擇不同選項。

負調(diào)查既可用于收集敏感信息，還可用于隱私保護的數(shù)據(jù)發(fā)布等領(lǐng)域。例如，Horey 等就利用負調(diào)查技術(shù)收集傳感器網(wǎng)絡(luò)中的敏感信息；Luo 等使用負調(diào)查收集網(wǎng)絡(luò)購物的商品評價信息；Du 等在 2014 年提出了負發(fā)布概念和對應(yīng)的兩個數(shù)據(jù)負發(fā)布方法。

2.2 克隆選擇算法

克隆選擇算法由生物免疫學(xué)中的克隆選擇學(xué)說啟發(fā)而來?？寺∵x擇算法的基本免疫學(xué)原理是，識別出入侵病原體的免疫細胞會進行快速的增殖，而在增殖過程中免疫細胞會發(fā)生變異，克隆變異的結(jié)果是產(chǎn)生更高親和度的免疫細胞，從而使得免疫系統(tǒng)能夠更高效地識別和清除病原體，這是生物免疫系統(tǒng)自學(xué)習(xí)和自適應(yīng)特性的體現(xiàn)。

典型的克隆選擇算法由選擇、增殖、突變等基本策略組合而成，大致可分為五個步驟。

（1）初始化：隨機生成含有 N 個抗體的種群。

（2）親和度評估：逐個計算種群中每一個抗體與抗原的親和度。

（3）抗體再生：將種群中的抗體按照親和度降序排序，選擇前 n（