劉柏麟，吳湘華

摘要：傳統(tǒng)免疫算法是通過仿真免疫系統(tǒng)的多樣性機制設計出來的一種算法。傳統(tǒng)免疫算法在求解問題時候，算法存在收斂速度慢、容易陷入局部最優(yōu)等問題。該文通過對傳統(tǒng)免疫算法中的變異函數(shù)和克隆抑制函數(shù)加以改進，以提高算法收斂速度，并使算法具有較好的全局最優(yōu)性。通過測試函數(shù)驗證改進后的算法正確有效。

關鍵詞：免疫算法；變異函數(shù)；克隆抑制；收斂速度；全局最優(yōu)

中圖分類號：G642? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）32-0017-03

1 概述

自古以來，人類通過模擬生物體的結構、功能發(fā)明了很多技術和工具，來解決生活中的問題[1]。生物免疫系統(tǒng)作為一種復雜的系統(tǒng)，它能夠對外來的入侵物質進行自我識別和清除，同時它還具有自組織、分布式、自適應、動態(tài)均衡等性能。當外來的抗原侵入體內(nèi)時，就會產(chǎn)生對應的抗體，其目的在于最大限度地確保機體的基本生理機能的正常運作，維持人體內(nèi)部的穩(wěn)定性。免疫算法基于生物免疫系統(tǒng)的免疫進化機理和信息處理機制，模擬其抗原識別和抗體增殖過程，保持抗體的多樣性[2]。傳統(tǒng)的免疫算法在局部最優(yōu)問題上有待解決以及其收斂性也有待改進，為了優(yōu)化這些問題，本文在傳統(tǒng)免疫算法的基礎上進行改進。

2 傳統(tǒng)免疫算法簡介

傳統(tǒng)免疫算法的原理是將抗體和抗原結合，進行抗體克隆、變異、選擇和記憶等過程，逐步達到抗體優(yōu)化[3]。傳統(tǒng)免疫算法將待優(yōu)化的問題的目標函數(shù)看成免疫系統(tǒng)中的抗原，算法中可行解看成免疫系統(tǒng)中的抗體，可行解的質量看成是抗體和抗原的親和度，通過進行抗體克隆、變異、選擇和記憶等操作，不斷優(yōu)化抗體，利用抗體與抗原的親和性，確定目標函數(shù)和可行解之間的匹配度，確?？尚薪獾牟町愋院投鄻有?，通過對抗體的期望生存率進行估計，以便促進較優(yōu)抗體更好地進行遺傳和變異。選擇最佳的可行解作為記憶細胞，以避免出現(xiàn)相似的可行解，進而達到加快搜索全局最優(yōu)解的目的。獨立的抗體種群進行選擇、克隆和變異等免疫操作[4]。在每次單獨群體的更新和評估之后，選擇不同種群的最優(yōu)抗體進行多組評價，也就是目前群體中的最佳抗體與上一代的最優(yōu)抗體相比較，若現(xiàn)有抗體較好，則將其作為本代的最佳抗體，反之，則將上一代的最佳抗體保存為該代的最佳抗體。最佳抗體就會被分配到各自的種群中，從而產(chǎn)生新的抗體。

免疫操作主要包括以下算子：

（1）免疫選擇：通過計算種群的抗體親和度，篩選出高質量的抗體，并進行活化；

（2）克?。嚎寺〗?jīng)過選擇后的抗體，得到多個新的種群；

（3）變異：對克隆獲得的群體進行變異處理，從而產(chǎn)生突變；

（4）克隆抑制：對變異后的群體進行優(yōu)選操作，保留親和度較高的抗體。

傳統(tǒng)免疫算法描述如下：

步驟1：參數(shù)的設定，在算法運行之前確定各個參數(shù)的取值。步驟2：初始化種群，根據(jù)設定的參數(shù)，隨機生成初始的抗體種群。步驟3：判定是否已達最大迭代代數(shù)，達到最大迭代代數(shù)則結束循環(huán)，并將執(zhí)行步驟9；否則繼續(xù)執(zhí)行步驟4。步驟4：抗原識別，根據(jù)問題構造相應的測試函數(shù)，染色體編碼代表抗體。步驟5：計算函數(shù)目標值，將種群中的抗體引入測試函數(shù)，得到相應的函數(shù)目標值，將其作為各抗體的親和度。步驟6：記憶單元的活化，向記憶單元內(nèi)添加高親和度的抗體，并執(zhí)行免疫操作。步驟7：執(zhí)行免疫操作，主要執(zhí)行的操作是選擇操作、克隆操作、變異操作和克隆抑制操作；選擇算子，即在群體中擇優(yōu)，篩選更優(yōu)的抗體以便于克??；克隆算子是將選定的抗體復制到新的種群中；變異算子是指在克隆后所形成的種群中進行的突變；克隆抑制是指在變異后群體中重新篩選出具有較高親和力的抗體。步驟8：種群刷新，根據(jù)刷新比例從種群中隨機產(chǎn)生剩余個體，和上一步所保留的抗體刷新種群，并返回執(zhí)行步驟3。步驟9：結束記憶細胞迭代，當達到指定的代數(shù)時，停止產(chǎn)生和選擇記憶細胞。

免疫算法是模仿生物免疫學和基因進化機理構造的優(yōu)化搜索算法，是免疫計算的一種最重要形式和對生物免疫過程的一種數(shù)學仿真[4]。其主要特性如下：

（1）該算法模擬了免疫反應過程，是一種具有全局搜索功能的優(yōu)化算法。其對高質量抗體局部搜索時通過變異算子和種群刷新來生成新的個體，并在一定范圍內(nèi)尋找新的可能解區(qū)間，并保證了算法的全局收斂性。

（2）該算法采用了生物免疫系統(tǒng)中的多樣性維持機制，并根據(jù)抗體濃度的大小來判斷抗體的優(yōu)劣。這種方法既能有效地抑制高濃度抗體，又能保證個體的多樣性，從而保證全局收斂。

（3）生物免疫系統(tǒng)可以隨時對抗原進行良好的識別[6]。該算法利用了啟發(fā)式的智能搜索機制，能夠在不受問題和初始值約束的情況下，從較差的解群體中尋找最優(yōu)解，具有很好的魯棒性。

（4）該算法無需集中控制，能夠進行并行運算。此外，免疫算法的優(yōu)化過程是一個多進程并行的過程。它能在尋找問題的最優(yōu)解的過程中，獲得多個次最優(yōu)解，即在尋找最優(yōu)解的情況下，獲得了更好的選擇，特別適用于多模式優(yōu)化問題。

（5）該算法在保持解的多樣性的同時，既采用了選擇、變異算子，又加入了隨機初始化群體，從而提高了解抗體的選擇能力，使算法能在全局最優(yōu)條件下收斂。然而，與其他的智能算法相比，該算法在解決函數(shù)問題時，不能很好地收斂于全局最優(yōu)，而且隨著時間的推移，其收斂速度和精確度也會逐步下降。

（6）該算法在優(yōu)化多峰函數(shù)方面有較慢的收斂速度和精度較差的問題，通過簡單的提高抗體種群規(guī)模可以擴大免疫算法的搜索范圍，但是仍然會出現(xiàn)抗體退化、收斂速度慢的問題。

3 傳統(tǒng)免疫算法的改進

從免疫系統(tǒng)的角度出發(fā)，數(shù)值函數(shù)優(yōu)化是在一定范圍內(nèi)找到最佳值，相當于抗體種群進化來鑒別單個抗原?？乖c待解決的問題對應，最佳抗體與待解問題的最佳值對應，而函數(shù)值則與抗體與抗原的親和程度對應。本文對免疫變異算子克隆抑制算子進行改進。

3.1 免疫變異算子改進

在傳統(tǒng)的免疫算法中，大多數(shù)使用單點變異或者隨機取反來實現(xiàn)算法。本文定義變異點數(shù)量n，將算子從單點變異設置為多點變異，可以直觀地分析收斂速度隨著變異點數(shù)量n的改變有何變動，避免產(chǎn)生局部最優(yōu)的問題，同時種群中的多樣性也得到提高。免疫變異算子im_mutation描述如下：

算子1：免疫變異算子im_mutation

功能：對克隆得到的種群進行n點隨機變異

輸入：克隆后形成的種群pop，變異點數(shù)量n

輸出：進行變異操作后形成的種群mupop

具體執(zhí)行過程：

（1）設置變異點數(shù)量n；

（2）輸入克隆后得到的種群pop，令i = 1，j = 1；

（3）i <= px時執(zhí)行（4），否則執(zhí)行（7）；

（4）返回行向量index，包含從1到px沒有重復元素的整數(shù)隨機排列；

（5）j <= n時執(zhí)行（6）且j值增1，否則i值增1返回（3）；

（6）將（4）中返回的元素作為序列，對每一個序列指定的變異點值進行取反運算；

（7）輸出進行變異后的形成的種群mupop。

3.2 克隆抑制算子改進

通常，克隆抑制算子是對變異后的種群進行則最優(yōu)個體，進行種群刷新迭代。傳統(tǒng)免疫算法抑制后截取的個體數(shù)一般為常數(shù)，沒有充分研究該值對算法的影響，改進后的算法定義抑制后截取的個體數(shù)k，篩選出具有較高的親和度的k個抗體，親和度較低的抗體達到抑制效果。k取值過小不利于尋找全局最優(yōu)解和收斂代數(shù)可能較大，k取值過大，每代運算時間會增加，影響收斂速度，克隆抑制算子k值的選取對收斂效果起到極其關鍵的作用，通過研究k值對算法效率的影響，以指導在實際問題中如何更好地進行克隆抑制操作?？寺∫种扑阕觟nhibit_clone描述如下：

算子2：克隆抑制算子inhibit_clone

功能：在經(jīng)過變異后的種群中取出k個最優(yōu)個體

輸入：變異后形成的種群pop，求解區(qū)間bounds，抑制后截取個體數(shù)k

輸出：個體進行克隆抑制操作后形成的種群newpop

具體執(zhí)行過程：

（1）輸入變異后的二進制種群pop，求解區(qū)間bounds，抑制后截取個體數(shù)k；

（2）計算出群體中每條染色體個體的目標值objvalue；

（3）根據(jù)親和度大小排序，逆序；

（4）截取第1行到第k行作為新的二進制種群；

（5）輸出個體進行克隆抑制操作后的形成的種群newpop。

4 實驗仿真

4.1 算法的最優(yōu)解截止代數(shù)判定

本文中免疫算法優(yōu)化的評估標準是綜合考慮最優(yōu)目標值、方差、熵值，體現(xiàn)實際免疫系統(tǒng)的多樣性[7]。方差表示種群在某個空間的分布情況，信息熵表示種群中個體的混亂程度。方差定義為：[D（X）=k=1，2，3...[X-E（X）]2pk]，其中[X]表示種群，[E（X）]表示種群均值，[pk]表示分布概率。熵值定義為：[H（X）=-k=1，2，3...p（xi）log2p（xi）]其中[p（xi）]表示個體在種群中的占比。當方差和熵值都比較大的時候，說明搜索空間大而且種群多樣性強，適合初始種群情況。如果種群的方差小、熵值大，說明搜索空間較小且種群的多樣性比較強。如果種群的方差大、熵值小，說明搜索空間較大且種群的多樣性較為弱。當熵值和方差都趨于一定的極小值時，群體中的最優(yōu)個體占比最大，此時免疫算法無法找到更優(yōu)解，即可判定收斂。

3.1 仿真參數(shù)設定

為了驗證算子改進后，免疫算法在求解函數(shù)中各種優(yōu)化問題時的改進效果及優(yōu)越性，選擇幾個常用測試函數(shù)進行仿真，下面以測試函數(shù)f（x） = x + 10× sin（5×x） + 7×cos（4×x），x∈[-10，10]，進行詳細的數(shù)據(jù)分析。種群大小設置為100，精度設置染色體長度為18，單次克隆個體數(shù)為10，種群刷新比例為0.3，進化代數(shù)設置為100代，變異點n取1～4，抑制操作后截取的個體數(shù)取1～4，本文設置了兩個變量對算法進行改進，變異點數(shù)量n和抑制后截取個體數(shù)k。對兩者進行單一變量分析，判斷算法收斂性能是否提升。

4.2 仿真結果分析

使用單一變量原則固定一個種群，變異點數(shù)量n和抑制后截取個體數(shù)k兩者選取一個作為變量，進行免疫算法操作，通過觀察最優(yōu)目標值與最優(yōu)值占比關系、方差和熵值關系，得出收斂代數(shù)。通過以上方法，對比多個不同種群的收斂代數(shù)，觀察變異點數(shù)量n和抑制后截取個體數(shù)k這兩個變量對算法收斂速度的影響。以下對初始種群pop1進行具體舉例。

（1）當初始種群pop1和抑制后截取個體數(shù)k =1固定不變時，單一變量變異點數(shù)量n=1時，在進化代數(shù)G的變化下，最優(yōu)目標值與其占比關系見圖1，方差和熵值關系見圖2。

由此可知，當抑制后截取個體數(shù)k=1，變異點數(shù)量n=1時，種群在44代時收斂。

同理，由此可知，當抑制后截取個體數(shù)k=1，變異點數(shù)量n=2時，種群在11代時收斂；當抑制后截取個體數(shù)k=1，變異點數(shù)量n=3時，種群在23代時收斂；當抑制后截取個體數(shù)k=1，變異點數(shù)量n=4時，種群在20代時收斂；當變異點數(shù)量n=3， 抑制后截取個體數(shù)k=2時，種群在12代時收斂；當變異點數(shù)量n=3， 抑制后截取個體數(shù)k=3時，種群在13代時收斂；當變異點數(shù)量n=3， 抑制后截取個體數(shù)k=4時，種群在8代時收斂。

以此類推，通過以上方法測試六組不同的種群，運用單一變量原則，觀察變異點數(shù)量n和克隆抑制后截取個體數(shù)k的改變對算法收斂性能的影響。

當k=1時，收斂代數(shù)如表1：

當n=3時，收斂代數(shù)如表2：

通過以上的仿真數(shù)據(jù)可知，固定始種群和變異點數(shù)量，抑制后截取個體數(shù)設置為變量；亦或固定初始種群和抑制后截取個體數(shù)，變異點數(shù)量設置為變量，可以明顯地觀察到算法收斂速度變化。當n值和k值過小時，都會使收斂性能下降。由此判斷，想要提高算法的收斂性能，可以在變量上選擇采用多點變異n和適當選取抑制后截取個體數(shù)k。

5 結論

免疫算法是一種以人工免疫系統(tǒng)為基礎的學習算法，它具有較強的自主性和應答性，同時還具備了一定的搜索和優(yōu)化的能力。其基本思想是將抗體與抗原結合，經(jīng)過抗體選擇、克隆、變異、記憶等步驟，使抗體得到最優(yōu)。本文通過設置變異點數(shù)量與克隆抑制后截取個體數(shù)，對算法進行了改進和創(chuàng)新。

參考文獻：

[1] Mohammadi M，Raahemi B，Akbari A，et al.Improving linear discriminant analysis with artificial immune system-based evolutionary algorithms[J].Information Sciences，2012，189：219-232.

[2] 張曉.人工免疫算法改進及其應用研究[D].西安：陜西師范大學，2017.

[3] 馬春連.基于人工免疫系統(tǒng)的多目標進化算法的研究[D].淮南：安徽理工大學，2014.

[4] 汪桂金，胡劍鋒.多種群人工免疫算法在多峰函數(shù)上的優(yōu)化[J].南昌大學學報（工科版），2018，40（3）：299-302，306.

[5] 蔡自興，龔濤.免疫算法研究的進展[J].控制與決策，2004，19（8）：841-846.

[6] 石剛.改進免疫克隆選擇算法的研究與應用[D].沈陽：東北大學，2011.

[7] 孫寧.人工免疫優(yōu)化算法及其應用研究[D].哈爾濱：哈爾濱工業(yè)大學，2006.

【通聯(lián)編輯：朱寶貴】