免疫算法

在生命科學領域中，人們已經對遺傳(Heredity)與免疫(Immunity)等自然現象進行了廣泛深入的研究。六十年代Bagley和Rosenberg等先驅在對這些研究成果進行分析與理解的基礎上，借鑑其相關內容和知識，特別是遺傳學方面的理論與概念，並將其成功應用於工程科學的某些領域，收到了良好的效果。時至八十年代中期，美國Michigan大學的Hollan教授不僅對以前的學者們提出的遺傳概念進行了總結與推廣，而且給出了簡明清晰的算法描述，並由此形成一般意義上的遺傳算法(GeneticAlgorithm)GA。由於遺傳算法較以往傳統的搜索算法具有使用方便、魯棒性強、便於並行處理等特點，因而廣泛應用於組合優化、結構設計、人工智能等領域。另一方面，Farmer和Bersini等人也先後在不同時期、不同程度地涉及到了有關免疫的概念。遺傳算法是一種具有生成+檢測 (generate and test)的迭代過程的搜索算法。從理論上分析，迭代過程中，在保留上一代最佳個體的前提下，遺傳算法是全局收斂的。然而，在對算法的實施過程中不難發現兩個主要遺傳算子都是在一定發生概率的條件下，隨機地、沒有指導地迭代搜索，因此它們在為羣體中的個體提供了進化機會的同時，也無可避免地產生了退化的可能。在某些情況下，這種退化現象還相當明顯。另外，每一個待求的實際問題都會有自身一些基本的、顯而易見的特徵信息或知識。然而遺傳算法的交叉和變異算子卻相對固定，在求解問題時，可變的靈活程度較小。這無疑對算法的通用性是有益的，但卻忽視了問題的特徵信息對求解問題時的輔助作用，特別是在求解一些複雜問題時，這種忽視所帶來的損失往往就比較明顯了。實踐也表明，僅僅使用遺傳算法或者以其為代表的進化算法，在模仿人類智能處理事物的能力方面還遠遠不足，還必須更加深層次地挖掘與利用人類的智能資源。從這一點講，學習生物智能、開發、進而利用生物智能是進化算法乃至智能計算的一個永恆的話題。所以，研究者力圖將生命科學中的免疫概念引入到工程實踐領域，藉助其中的有關知識與理論並將其與已有的一些智能算法有機地結合起來，以建立新的進化理論與算法，來提高算法的整體性能。基於這一思想，將免疫概念及其理論應用於遺傳算法，在保留原算法優良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特徵信息或知識來抑制其優化過程中出現的退化現象，這種算法稱為免疫算法(ImmuneAlgorithm)IA。下面將會給出算法的具體步驟，證明其全局收斂性，提出免疫疫苗的選擇策略和免疫算子的構造方法，理論分析和對TSP問題的仿真結果表明免疫算法不僅是有效的而且也是可行的，並較好地解決了遺傳算法中的退化問題。

抗原：在生命科學中，是指能夠刺激和誘導機體的免疫系統使其產生免疫應答，並能與相應的免疫應答產物在體內或體外發生特異性反應的物質。在我們的算法中，是指所有可能錯誤的基因，即非最佳個體的基因。

抗體：在生命科學中，是指免疫系統受抗原刺激後，免疫細胞轉化為漿細胞併產生能與抗原發生特異性結合的免疫球蛋白，該免疫球蛋白即為抗體。在本文中是指根據疫苗修正某個個體的基因所得到的新個體。其中，根據疫苗修正某個個體基因的過程即為接種疫苗，其目的是消除抗原在新個體產生時所帶來的負面影響。

免疫疫苗：根據進化環境或待求問題，所得到的對最佳個體基因的估計。

免疫算子：同生命科學中的免疫理論類似，免疫算子也分兩種類型：全免疫和目標免疫，二者分別對應於生命科學中的非特異性免疫和特異性免疫。其中，全免疫是指羣體中每個個體在變異操作後，對其每一環節都進行一次免疫操作的免疫類型；目標免疫則指個體在進行變異操作後，經過一定判斷，個體僅在作用點處發生免疫反應的一種類型。前者主要應用於個體進化的初始階段，而在進化過程中基本上不發生作用，否則將很有可能產生通常意義上所説的“同化現象”；後者一般而言將伴隨羣體進化的全部過程,也是免疫操作的一個常用算子。

免疫調節：在免疫反應過程中，大量的抗體的產生降低了抗原對免疫細胞的刺激，從而抑制抗體的分化和增殖，同時產生的抗體之間也存在着相互刺激和抑制的關係，這種抗原與抗體、抗體與抗體之間的相互制約關係使抗體免疫反應維持一定的強度，保證機體的免疫平衡。

免疫記憶：指免疫系統將能與抗原發生反應的抗體作為記憶細胞保存記憶下來，當同類抗原再次侵入時，相應的記憶細胞被激活而產生大量的抗體，縮短免疫反應時間。

抗原識別：通過表達在抗原表面的表位和抗體分子表面的對位的化學基進行相互匹配選擇完成識別，這種匹配過程也是一個不斷對抗原學習的過程，最終能選擇產生最適當的抗體與抗原結合而排除抗原。

1. 隨機產生初始父代種羣A1，根據先驗知識抽取疫苗；

2. 若當前羣體中包含最佳個體，則算法停止運行並輸出結果；否則，繼續；

3.對當前第k代父本種羣Ak進行交叉操作，得到種羣Bk；

4. 對Bk進行變異操作，得到種羣Ck；

5. 對Ck進行接種疫苗操作，得到種羣Dk；

6. 對Dk進行免疫選擇操作，得到新一代父本Ak+1，轉至第二步。

step1:在GitHub上下載常用的 scikit-opt庫。

step2:定義目標函數，並執行免疫算法

from sko.IA import IA_TSP_g as IA_TSP
ia_tsp = IA_TSP(func=cal_total_distance, n_dim=num_points, pop=500, max_iter=2000, Pm=0.2,                
                T=0.7, alpha=0.95)
best_points, best_distance = ia_tsp.fit()
print('best routine:', best_points, 'best_distance:', best_distance)