克隆選擇算法綜述

0 引言

生物免疫系統是脊椎動物為了保護機體抗御病原體等“非我”（non-self）的侵害所進化出的防御機制。鑒于其具有自學習、記憶機制、模式識別、動態(tài)自適應、動態(tài)魯棒性和并行性等優(yōu)越的特質，生物免疫系統為解決實際復雜工程問題提供了大量的仿生靈感。人工免疫系統（Artificial Immune System, AIS）通過模擬生物免疫系統功能、原理和模型來構造算法，被廣泛應用于函數優(yōu)化、異常檢測、模式識別和工業(yè)工程等諸多領域。

由于生物免疫系統自身的復雜性，形成了多種免疫學說。其中，Burnet 在 1959 年提出克隆選擇學說構建了克隆選擇算法的基礎?？寺∵x擇學說解釋了在抗原刺激下適應性免疫反應的基本特征，其基本思想是只有那些能識別抗原的細胞才被選擇進行增殖，而那些不能識別抗原的細胞則不被選擇，被選擇的細胞通過增殖和超變異的過程提升其親和度直至達到親和度成熟。根據克隆選擇理論，De Castro 等通過仿生免疫反應中的親和度成熟過程，提出了克隆選擇算法 CLONALG，成功應用于字母識別、多模態(tài)函數優(yōu)化、組合優(yōu)化和 TSP 問題等，掀起了免疫克隆選擇算法的研究熱潮。

隨著研究的深入，克隆選擇算法被不斷改進，并與其他策略混合，在多模態(tài)優(yōu)化、約束優(yōu)化、動態(tài)優(yōu)化、多目標優(yōu)化、模式識別和路徑優(yōu)化等領域取得了亮眼的成績。本文重點闡述克隆選擇算法的基本原理、研究現狀和需要進一步研究的熱點問題。

1 克隆選擇算法

由于生物免疫系統龐大且復雜，為便于模型設計，從計算的角度可以將生物免疫系統原理進行簡化。“非我”的物質被統稱為抗原，免疫系統受抗原刺激引發(fā)免疫應答產生抗體?？贵w能與抗原產生特異性結合。抗體通過其抗體決定基和抗原的抗原決定基之間的模式互補匹配，來與它能識別的抗原結合。結合的強度取決于模式匹配程度，這種結合力稱為親和度。親和度越高，抗原與抗體之間的關聯越緊密。特定的抗體分子對不同的抗原具有不同的親和力?？贵w也能和其他抗體結合，這樣抗體便具有識別抗原又被其他抗體識別的“雙重身份”。如圖 1 所示，在生物免疫系統克隆選擇過程中，與抗原親和度高的抗體被選擇，然后通過克隆快速增殖分化，并通過超變異調整自身抗體與抗原親和度直至親和度成熟（affinity maturation），產生最佳抗體，最終消除抗原。一些抗體會轉化為記憶細胞，當遭遇相同或相似抗原攻擊時能迅速反應。

圖 1 生物免疫系統克隆選擇過程

克隆選擇算法（Clonal Selection Algorithm, CSA）是通過仿生生物免疫系統通過克隆選擇實現適應性免疫過程的計算模型?？寺∵x擇算法的基本框架如算法 1 所示。通常情況下，需要解決的問題被映射為抗原，問題的解被映射為抗體。

算法 1 克隆選擇算法基本框架

-----------------------------------------------

輸入：種群數目，相關參數設定等

輸出：問題的解

------------------------------------------------

Step 1: 初始化：產生初始抗體種群

Step 2: 親和度計算：計算抗體 - 抗原親和度，即抗

體的適應度值

Step 3: 選擇：選擇 m 個與抗原親和度高的抗體

Step 4: 克?。簩λx擇的抗體進行克隆操作

Step 5: 超變異：對克隆個體實施超變異操作

Step 6: 對新產生的抗體的親和度進行評估

Step 7: 選擇親和度高的 n 個抗體到下一代

Step 8: 受體編輯：隨機產生 d 個抗體，加入到種群中

Step 9: 終止條件判斷。如果終止條件未滿足則算法

繼續(xù)，否則結束，輸出最優(yōu)抗體及其適應度值。返回 Step4

2 關鍵算子定義及其改進

2.1 親和度

親和度是對抗體質量進行評價的度量。根據不同的問題和編碼方式，親和度的定義各有不同。在模式識別和路徑優(yōu)化等問題中，通常采用二值編碼或者整數編碼等方式。此時，通常選擇相似度距離計算方法，比如漢明距離和曼哈頓距離作為親和度的衡量標準。對于連續(xù)優(yōu)化問題，通常以實數編碼實現，一般采用目標函數本身，或者是歐式距離來衡量。在處理多模態(tài)問題時需要同時考慮抗體與抗原的匹配度，以及抗體的多樣性，親和度被細化為抗原 -抗體親和度和抗體 - 抗體親和度并分別定義。

2.2 克隆

克隆是無性繁殖，復制自身的過程?？寺∵x擇的過程如圖 2 所示。在克隆增殖過程中，抗體克隆子代的數目與抗原的親和度值正比，即越優(yōu)秀的個體產生的克隆子代越多。因此，在算法實現時，克隆子代的數目也遵循與其比例克隆的定義方式。比例克隆在當前最優(yōu)的局部增加搜索，能增強局部搜索能力。如果優(yōu)化過程旨在單個抗體種群中定義多個最優(yōu)值，那么可以選擇種群中的所有抗體參與克隆過程。此時，比例克隆不再適用，新的克隆個數被重新定義為每個抗體都將擁有相同的克隆數目，即等比例克隆。

圖 2 克隆選擇算法中的克隆、超變異和選擇過程

相較于遺傳算法的兩個父代通過交叉產生兩個子代（2-2），粒子群算法一個父代通過位置更新生成一個子代（1-1）的產生方式，克隆操作的一個父代在一次迭代中就產生了多個子代（1-Nc）。這種方式雖然為產生更優(yōu)秀的子代提供了更多的可能性，但顯然也帶來了計算資源的大量消耗。因此，為節(jié)約計算資源，有時會給克隆數目增加上界的閾值限制。極端情況下，克隆個數被設定為 1 個，這與 1-1 的設定在生成子代數目上幾乎一致。

2.3 超變異

超變異是指高頻的變異，抗體通過這種高頻的變異修改自身可變區(qū)域結構，以期提升與抗原的親和度。不同于遺傳算法中的交叉操作，超變異直接在單個父代上進行，隨機選擇一個或者一段基因位進行改變，能顯著增加抗體的多樣性。在克隆選擇過程中，超變異的頻率一般遵循與抗體的親和度成反比的規(guī)律，即適應度高的個體其變異的頻度越低。

在遺傳算法中，變異是與交叉算子配合使用的，變異頻率通常較低，而且變異的主要的是增加算法的跳出局部最優(yōu)的開拓能力。而在克隆選擇算法中，變異算子作為主要算子之一，需要同時兼顧局部的勘探能力和全局的開拓能力，因此其設計更為復雜，每個抗體的突變率可以各不相同。在親和度低的地方，則突變率較大，增加全局開拓能力；而在親和度高的地方，變異率較低，增加局部勘探能力。

在克隆選擇算法中，不同編碼方式有不同變異算子的實施方式。對于二值編碼或者整數編碼，往往采取某些基因位或者基因段上值的改變，而對于實數編碼其操作方式更加多樣，常用的方式有采用親和度的負指數函數，也有高斯變異和柯西變異等方式。超變異的實施主要集中在控制變異的步長上。在具體問題背景下，超變異的設定有時也與循環(huán)次數等相關，即變異的步長隨著迭代次數的增加變小，從全局搜索逐漸到局部搜索。

2.4 選擇

選擇是指新產生的子代會以一定的生存幾率存活或者死亡。一般來說，適應度值高的個體被選取到下一代繼續(xù)生存的幾率更大。在實際操作中，常用的方法有以下幾種。

（1）輪盤賭選擇：它屬于比例選擇操作，首先將適應度值歸一化，然后把概率分布看作一個輪盤，輪盤的每一個切片的大小都與歸一化后的個體選擇概率成比例，選擇的過程如同旋轉輪盤，它停止旋轉時，最上方的切片對應的個體即被選擇。

（2）錦標賽選擇：錦標賽選擇從群體中隨機選擇 nts 個個體作為一組，其中 nts