一種改進的免疫遺傳算法求解0-1背包問題

杜彥華 靳宗信

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

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

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

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

NIGA

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

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

圖1 免疫算子的結構圖

在NIGA中，為了對免疫算子進行綜合分析，需要建立一個算子庫，算子庫中用來存放全部迭代中的全部的優良免疫算子。免疫算子庫由兩個子庫組成：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；

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

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

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

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

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

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

（4）加入算子xi，得到yj；

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

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

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

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

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

（2）產生免疫算子庫；

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

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

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

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

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

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

NIGA求解0-1背包問題

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

表1 100次實驗結果數據

結論

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