免疫計(jì)算概述

前言

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

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

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

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

作者：羅文堅(jiān)

0 引言

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

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

伴隨著免疫計(jì)算研究的發(fā)展，一系列相關(guān)的學(xué)術(shù)活動(dòng) 也 隨之誕生和發(fā)展起來(lái)。IEEE 計(jì)算智能協(xié)會(huì)下的演化計(jì)算技術(shù)委員會(huì)（IEEE CIS ECTC）專門成立了Task Force on Artificial Immune Systems 用于推動(dòng)免疫計(jì)算領(lǐng)域的研究與發(fā)展。近年來(lái)，在IEEE Symposium Series on Computational Intelligence （IEEE SSCI）系列會(huì)議中，都有舉行 IEEE Symposium on Immune Computation（IEEEIComputation）免疫計(jì)算研討會(huì)。而演化計(jì)算領(lǐng)域的重要會(huì)議 IEEE Congress on Evolutionary Computation（CEC）已舉辦過多年的人工免 疫 系 統(tǒng) 主 題 研 討 會(huì)（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 等國(guó)際知名學(xué)術(shù)期刊都曾出版過以免疫計(jì)算為主題的 專 刊（Special Issue）。2015 年，免疫計(jì)算領(lǐng)域的兩位知名學(xué)者 Stephanie Forrest 和DipankarDasgupta 當(dāng)選 IEEE Fellow，其主要貢獻(xiàn)均包括免疫計(jì)算方面的研究工作。

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

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

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

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

2 代表性模型和算法

2.1 信息負(fù)表示

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

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

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

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

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

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

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

2.2 克隆選擇算法

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

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

（1）初始化：隨機(jī)生成含有 N 個(gè)抗體的種群。

（2）親和度評(píng)估：逐個(gè)計(jì)算種群中每一個(gè)抗體與抗原的親和度。

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