一種改進(jìn)的免疫算法研究

劉柏麟，吳湘華

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

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

中圖分類(lèi)號(hào)：G642? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）32-0017-03

1 概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 免疫變異算子改進(jìn)

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

算子1：免疫變異算子im_mutation

功能：對(duì)克隆得到的種群進(jìn)行n點(diǎn)隨機(jī)變異

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

輸出：進(jìn)行變異操作后形成的種群mupop

具體執(zhí)行過(guò)程：

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

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

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

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

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

（6）將（4）中返回的元素作為序列，對(duì)每一個(gè)序列指定的變異點(diǎn)值進(jìn)行取反運(yùn)算；

（7）輸出進(jìn)行變異后的形成的種群mupop。

3.2 克隆抑制算子改進(jìn)

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

算子2：克隆抑制算子inhibit_clone

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

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

輸出：個(gè)體進(jìn)行克隆抑制操作后形成的種群newpop

具體執(zhí)行過(guò)程：

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

（2）計(jì)算出群體中每條染色體個(gè)體的目標(biāo)值objvalue；

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

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

（5）輸出個(gè)體進(jìn)行克隆抑制操作后的形成的種群newpop。

4 實(shí)驗(yàn)仿真

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

本文中免疫算法優(yōu)化的評(píng)估標(biāo)準(zhǔn)是綜合考慮最優(yōu)目標(biāo)值、方差、熵值，體現(xiàn)實(shí)際免疫系統(tǒng)的多樣性[7]。方差表示種群在某個(gè)空間的分布情況，信息熵表示種群中個(gè)體的混亂程度。方差定義為：[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）]表示個(gè)體在種群中的占比。當(dāng)方差和熵值都比較大的時(shí)候，說(shuō)明搜索空間大而且種群多樣性強(qiáng)，適合初始種群情況。如果種群的方差小、熵值大，說(shuō)明搜索空間較小且種群的多樣性比較強(qiáng)。如果種群的方差大、熵值小，說(shuō)明搜索空間較大且種群的多樣性較為弱。當(dāng)熵值和方差都趨于一定的極小值時(shí)，群體中的最優(yōu)個(gè)體占比最大，此時(shí)免疫算法無(wú)法找到更優(yōu)解，即可判定收斂。

3.1 仿真參數(shù)設(shè)定

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

4.2 仿真結(jié)果分析

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

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

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

[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] 張曉.人工免疫算法改進(jìn)及其應(yīng)用研究[D].西安：陜西師范大學(xué)，2017.

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

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

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

[6] 石剛.改進(jìn)免疫克隆選擇算法的研究與應(yīng)用[D].沈陽(yáng)：東北大學(xué)，2011.

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

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