杜彥華 靳宗信

（1.黃河科技學院 圖書館，河南 鄭州 450063；2.黃河科技學院 信息工程學院，河南 鄭州 450063）

在現代科技高速發(fā)展的過程中，隨著交叉學科的發(fā)展，從生物體各個信息處理系統(tǒng)中抽取相應的人工模型已成為研究的熱點。人工免疫模型正在為科學貢獻力量，以其為基礎的各種模型已經應用于科學的各個領域。

傳統(tǒng)的遺傳算法存在缺陷，例如在迭代后期容易出現退化現象，算法的收斂速度慢等。但傳統(tǒng)遺傳算法的改進算法較多，已被成功用于科學的不同領域。

生物作為計算問題的思想源泉，已經為科學工作者提供了許多解決問題的思路。生物免疫系統(tǒng)自身的許多機制，如適應性、記憶性和多樣性等機制能被用來解決各種計算任務，在此基礎上發(fā)展起來的計算方法已經成為一門學科，已經引起不同領域學者的關注。根據生物免疫系統(tǒng)與傳統(tǒng)遺傳算法結合而產生的免疫算法已經表現出良好的性能，本文將生物免疫系統(tǒng)產生多樣性抗體的產生機制加入到傳統(tǒng)的遺傳算法中，提出了一種新型的免疫遺傳算法。為了檢測此算法的特性，使用經典的0-1背包問題進行檢驗，仿真實驗結果表明此算法能夠很快找到全局最優(yōu)解，克服遺傳算法的缺點，表現出較高的效率。

NIGA

在傳統(tǒng)的遺傳算法中加入生物體產生抗體的多樣性機制，即加入免疫算子，不僅保留了原算法本身的優(yōu)良特性，還可以抑制算法在迭代過程中出現的退化現象，提高算法的收斂速度。免疫算子對應于待求解問題的解的一些特征信息。NIGA的執(zhí)行效率在很大程度上取決于免疫算子的選取。免疫算子的好壞，即生成抗體的優(yōu)劣不會影響算法的收斂性，只會影響算法的收斂速度和免疫算子在整個算法中的作用。所以免疫算子的優(yōu)劣直接影響了算法的好壞。本文改進了提取免疫算子的方法，并把這種方法加入到免疫遺產算法中去，得到了一種新型的免疫遺產算法（NIGA）。使用經典的NP難問題對其進行檢驗后，表明此算法能夠很快找到當前最優(yōu)解。

根據生物學的相關知識，生物染色體上的固定位置上的基因位可以決定生物的性狀。也就是說，基因通過兩個方面影響生物的性狀，第一個是基因本身堿基的順序，第二個是基因本身在染色體上的位置，由此可知，雖然兩個基因的堿基順序相同，但把它們放在染色體的不同位置，生物體就會表現出不同的性狀。本文的免疫算子是一個基因串，其包含一個或多個基因位。為了使免疫算子發(fā)揮更大的作用，在產生免疫算子時對其位置信息也進行保存。免疫算子的結構如圖1所示：

圖1 免疫算子的結構圖

在NIGA中，為了對免疫算子進行綜合分析，需要建立一個算子庫，算子庫中用來存放全部迭代中的全部的優(yōu)良免疫算子。免疫算子庫由兩個子庫組成：H1和H2，其中子庫H1中存放的算子的長度為2，H2中免疫算子的長度為Bl，Bl的長度可以通過計算得到。

免疫算子庫H2中算子的長度可用下面的公式來計算：

其中：rand為隨機數；α，β，γ分別取0.615，0.855和0.951，均為經驗值。

根據操作的需要，在算法運行的過程中要始終保持免疫算子庫中算子的數量不變。為了達到這個目的，當每次有新的算子加入算子庫后，都要對庫中所有的免疫算子按照適應度進行排序，保留適應度較大的算子。其中免疫算子庫的大小可用下面的公式來計算：

上式中m表示算法中種群的數量，η表示調整系數。

子庫H1的建立方法為：

（1）從抗體群中隨機選取一個抗體，此抗體的所有基因位組成集合A，A={g1，g2，Λgn}；

（2）在集合A中隨機選取一基因位g1，由基因g1與A-{g1}中的所有基因組成長度不同的基因段，并計算每個基因段的適應度；

（3）把計算后的基因段按照適應度進行從大到小排序，選取前k1個基因段組成子庫H1；

子庫H2的建立方法為：

（1）計算群體中所有抗體的適應度，并按照適應度按照從大到小的順序排序；

（2）在集合A中隨機選取一個基因位g1，在排序后的每個抗體中找到相應的基因g1，選取以g1開頭，長度l為的基因段；

（3）把所有的基因段按照適應度排序，選取適應度最大的k2個基因段組成H2；

由于每個免疫算子本身包含了其在解中的位置信息，所以在注射疫苗時可以根據該信息所標注的位置進行注射，而不是采用隨機注射的方式，從而使疫苗注射的位置更加合理。

更重要的是，在向抗體中加入算子時，除了要有效利用算子自身攜帶的位置信息以外，還要防止新算子的加入而導致已有算子的破壞。當這種情況發(fā)生時，以保留適應度高的算子為準。

基因中注射算子的算法如下：

（1）在免疫算子庫中按輪盤賭的方法選取一個算子xi；

（2）在群體中也采用輪盤賭的方式選取一個抗體yj，根據xi所含的位置信息，在yj中找到加入算子的相應位置；

（3）找到抗體yj中xi與算子相沖突的部分，并將其刪除；

（4）加入算子xi，得到y(tǒng)j；

（5）進行免疫檢測，即計算yj的適應度，并與yj的適應度進行比較，取適應度較大著進入下一代；

此算法的流程圖如圖2所示。

圖2 加入算子及檢測過程流程圖

綜合上述，本文中NIGA的步驟如下：

（1）使用隨機的方法產生初始種群Po；

（2）產生免疫算子庫；

（3）計算種群的適應度；

（4）進行適應度判斷，若種群中包含最佳個體，即找到最優(yōu)解，則終止算法并輸出結果，否則繼續(xù)以下操作；

（5）對第k代種群Pk進行交叉和變異操作，得到種群Ak；

（6）向種群Ak中的每個個體注射疫苗后進行免疫選擇，得到下一代種群Pk+1；

該算法的流程圖如圖3所示。

圖3 改進的免疫遺傳算法流程圖

NIGA求解0-1背包問題

為了驗證本文所提出的NIGA算法的全局尋優(yōu)能力和有效性，現以0-1背包作為測試算例，并引用參考文獻中的數據。從表1可以看出：NIGA比一般的遺傳算法（IGA）更容易找到最優(yōu)解。

表1 100次實驗結果數據

結論

本文提出了一種新的免疫算子的提取方法，并用這種方法建立了免疫算子庫，結合生物免疫系統(tǒng)的特性提出了一種新的免疫遺傳算法（NIGA），把NIGA應用于0-1背包問題的求解中，仿真結果表明，NIGA能夠抑制遺傳算法在迭代過程中出現的退化現象，提高算法的收斂速度。