基于ｍｅｔａ種群理論的免疫遺傳算法
2008-01-01 00:00:00吳蕓吳清鋒周昌樂
計算機應用研究 2008年5期
摘要：自然meta－種群中局部種群之間存在相對隔離和種群個體冒險遷徙的機制，提出了一種基于meta－種群理論的免疫遺傳算法。該算法模擬了自然meta－種群中局部種群克隆、生殖、變異和自然滅絕等自然過程。其主要步驟包括初始種群，種群及其個體適應度計算，選擇，克隆變異、交叉生殖、含記憶B細胞個體克隆和局部種群滅絕及其最優個體的冒險遷徙等。該算法的特點是模擬了meta－種群的自然機制，具有并行性，能夠產生高適應能力的個體并不斷地更新，直到最優個體的出現。對兩種問題進行了模擬實驗，并與普通遺傳算法IMA進行了比較，結果表明所提出的算法能以較少的迭代次數完成最優解的尋找。
關鍵詞：meta－種群； 免疫遺傳算法； 記憶B細胞； 優化
中圖分類號：TP301．6文獻標志碼：A
文章編號：1001-3695(2008)05-1312-03
從人類開始思考人的起源問題開始，自然系統處理各種信息的能力和對環境的適應性機理就不斷地被人類科學地認識。因此，工程技術人員受生物和人類自然機制的啟發，也不斷地發掘和研究各種人工算法，模擬自然機制對各種信息進行有效處理。其中模擬達爾文遺傳進化機制和人類免疫系統而提出的人工遺傳算法和免疫算法已經有效地用于模式識別和分類、學習和記憶、歸納概括、分布檢驗以及各種優化組合問題等。
自然系統并不等價于單一種群，而是種群的有機集合。在19世紀70年代以前，生物地理學家和生態學家就廣泛注意到生境在時間和空間上的異質作用將對種群動態、群落結構記憶物種多樣性和種群內的遺傳多態性產生重要的影響。著名的生態學家Levins在20世紀60年代末發展了meta－種群理論。它是種群的概念在一個更高層次的抽象和概括，描述了局部種群的滅絕和新的局部種群不斷建立之間的動態平衡[1]。本文在介紹免疫遺傳算法和meta－種群理論的基礎上，提出并討論了基于meta－種群理論的免疫遺傳算法（MIGA）。利用對TSP優化與傳統遺傳算法的比較，并對不同病種的中醫臨床數據進行了有效分型。
1免疫遺傳算法
基于達爾文自然選擇機制的傳統遺傳算法屬于隨機優化算法，由初始可行解的產生、編碼、解碼和評估機制組成。但其在進化過程中容易產生退化現象，將導致迭代次數過多以及陷入局部最優陷阱。為了克服上述不足，在傳統的遺傳算法中引入免疫因子，形成免疫遺傳算法，即在遺傳過程中引入免疫系統中的記憶B細胞。記憶B細胞的群體能夠保留適應度高的多個不同的個體[2]，在種群進化中，比最優個體選擇法具有更多的優點。由于記憶B細胞的存在，加上遺傳優勢選擇的作用，使遺傳向提高適應度方向發展，避免了盲目性。因此，傳統遺傳算法的優勢選擇過程由記憶B細胞的選擇、克隆和變異三個過程代替，從而形成免疫遺傳算法。
2Meta－種群理論
在生物界中，由于各種各樣的原因而導致了生物種群棲息地的破碎化，從而形成了一個個空間上、行為上等相對隔離的生境斑塊。同時也正是因為棲息地的破碎化而使得一個較大的生物種群被分割成許多小的局部種群。Meta－種群理論所描述的就是在斑塊生境中，在空間上具有一定的距離（空間隔離），但彼此間通過擴散個體相互聯系在一起的許多小種群或局部種群的集合。相對隔離的每個局部種群都面臨著滅絕和入侵的過程，但冒險遷移能夠對具有不穩定性的局部種群進行調解，從而達到整個meta－種群的動態平衡。
3基于meta－種群理論的免疫遺傳算法
引入免疫因子（記憶B細胞）的遺傳算法是一級遺傳。在此基礎上引入meta－種群理論的遺傳算法是二級遺傳，即在多種群并行遺傳操作，同時利用了meta－種群處理適應能力低下的種群（將其滅絕）以及滅絕種群中個別優良個體的冒險遷移機制。因此基于meta－種群理論的免疫遺傳算法具有上述免疫遺傳算法優點的同時，進一步提高了算法的并行處理問題和全局搜索最優解的能力。
3．1算法
算法主要步驟如下：
a）問題定義。待優化目標問題及其約束條件視為適應能力評估因子。目標問題在約束條件下現階段的最優解視為具有記憶B細胞的個體。
3．2算法的收斂性分析
局部種群在遺傳過程中不斷地保留當前最優解的情況下，傳統遺傳算法可以收斂到全局最優解，其收斂性已經得到證明。MIGA框架與傳統遺傳類似。本算法采用了對記憶B細胞的變異操作和保留適應度高的個體組成新一代的局部種群，它增加了局部種群的多樣性，并保留了更多不同的當代最優個體。MIGA是并行遺傳算法，隨著meta－種群的進化而不斷地更新最優個體，淘汰適應度低的局部種群，從而能夠加速MIGA找到全局最優解，所以也可收斂到全局最優。
4模擬實驗
4．1TSP優化
TSP是一個典型的易于描述但難以處理的NP問題。簡而言之，就是尋找一條最短的遍歷n個城市的路徑，每個城市只能遍歷一次，最后回到出發點。或者說，搜索整個數子集X={1，2，3，…，n}（表示對n個城市的編號）的一個排列P(X={v1，v2，v3，…，vn}) ，使得Td=∑n-1i=1d(vi，vi+1)+d(v1，vd)的值最小。其中：d(vi，vi+1)表示城市vi到vi+1的距離[2]。
在本算法中，一個可行解就被視為含有記憶B細胞的個體；種群個體的適應度由suit_pi=1-1/disi計算確定。對城市的遍歷次序作為局部種群個體染色體的編碼，交換操作采用貪婪交換法，變異操作采用兩點對換變異法。MIGA中，meta－種群規模為6~10個，每個局部種群規模隨機確定，設定小于200，因此每個局部種群的規模大小不一致。簡單遺傳算法中，種群規模隨機確定，設定小于200。以30個城市為例，在相同迭代次數下，MIGA和普通GA（IGA）的性能比較結果如圖1所示。
由圖1和表1可以看出，在迭代相同次數的情況下，MIGA所得到的解比IGA得到的解更優；同時，迭代次數越多，MIGA能夠比IGA更快地接近全局最優解。
另一方面，在MIGA遺傳計算過程中，模擬了自然生物適應能力差而導致種群滅絕的情況，即局部種群由于適應能力逐漸降低，從而導致局部種群的滅絕，在優化過程就會出現如圖2所示的情形。
4．2中醫八綱辨證神經網絡參數優化
本文中所指的神經網絡是用于中醫八綱辨證計算的神經網絡[3]。初始的八綱辨證神經網絡是一個任意的具有三層神經元的前饋式神經網絡。為了使其優化成為適合中醫八綱辨證計算的神經網絡，本文采用MIGA優化其參數。Meta－種群規模為6~10個，每個局部種群規模隨機確定，設定小于100，因此每個局部種群的規模大小不一致。IGA中，種群規模隨機確定，設定小于100。一個可行解仍被視為含有記憶B細胞的個體，可以直接選擇克隆繁殖。種群個體的適應度由suit_pi=α×Ei(Ts)+(1-α)×Ei(Vs)計算確定。其中：E(T)=1/mse(x)；α是隨機值；Ts和Vs是訓練樣本集和有效樣本集。
對同一初始神經網絡，在迭代次數相同的情況下，MIGA表現出比IGA以更少的迭代次數尋找最優神經網絡參數，如圖3、4所示。
5結束語
本文對meta－種群生物模式和免疫遺傳進行了介紹，基于meta－種群生物模式提出了一種優化算法，并分析了該算法的收斂性。該算法屬于隨機優化算法，同時它具有突出的并行性特點，應用于并行計算機進行計算能極大地提高全局最優解的尋找速度。對TSP和中醫八綱辨證神經網絡的優化實驗結果表明，本文提出的優化算法在相同迭代次數內能找到比普通GA更優的解。
參考文獻：
[1]陶毅. Meta－種群的理論與實踐[C]//中國科學院生物多樣性委員會·生物多樣性研究的原理和方法.北京:中國科學技術出版社，1994:55-68.
[2]羅印升.人工免疫算法在函數優化中的應用[J].西安交通大學學報，2003，37(8):840-843.
[3]吳蕓. 中醫舌診八綱辨證神經網絡知識庫構建[J]. 計算機應用研究，2006， 23(6):188－189，198.
[4]王自強. 分類規則挖掘的免疫算法[J].西安交通大學學報， 2005，39(2):111－114.
[5]CLUNE J， GOINGS S， PUNCH B， et al. Investigations in meta－GAs: pananceas or pipe dreams?[C]//Proc of Workshop on Genetic and Evolutioncery Computation. New York: ACM Press， 2005:235-241.
[6]JUANG C F， LIOU Y C. On the hybrid of genetic algorithm and particle swarm optimization for evolving recurrent neural network[C]//Proc of International Joint Conference on Neural Network. 2004:2285-2288.
[7]TAN Zheng－hua. Hybrid evolutionary approach for designing neural networks for classification[J]. IEEE Electronics Letters， 2004，40(15):955-957.
[8]XIAO Shou－zhong， PENG Cheng－lin， WANG Zhi－sheng， et al. Using the algebraic sum method in medical expert systems[J]. IEEE Engineering in Medicine and Biology， 1996，15(3):80-82.
[9]WANG Wei－yen. Evolutionary learning of BMF fuzzy－neural network using a reduced－form genetic algorithm[J]. IEEE on Systems， Man and Cybernetics: Part B， 2003，33(6):966-976.
[10]朱文鋒.中醫診斷學[M]. 北京：中國中醫藥出版社，2004.
[11]周志華.神經網絡及其應用[M]. 北京：清華大學出版社，2004.
[12]董長虹.MATLAB神經網絡與應用[M]. 北京：國防工業出版社，2005.
“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”
