一種基于生物免疫遺傳學的新優化方法論文
1引目
簡單遺傳算法(SimpieGeneticAigorithm,簡記為SGA)是由Michigan大學的Hoiiand教授等創立的,主要理論基礎是生物進化論和群體遺傳學。SGA的基本特征是:利用群體進化一一即在求解過程中,通過使種群不斷優化,從而找到滿意解或最優解。對于許多常規方法難以有效解決的非線性優化問題,
SGA往往能夠奏效,因此在許多工程問題的解決中,SGA獲得了廣泛的應用。
SGA在理論上借鑒生物進化理論以及遺傳學機理,已經形成了一套較為完善的算法體系,然而在實際使用中,還有許多問題有待進一步研宄探討。例如,對于單調函數或單峰值函數,在初始時很快向最優值逼近,但是在最優值附近收斂較慢;而對于多峰值函數的優化問題,它往往出現“早熟”即收斂于局部極值。宄其原因,主要是通常使用的SGA的選擇策略多采用個體繁殖機會同其適應值成正比例的方法,這樣就很容易導致超級個體問題和多個相似數字串問題[l]。交叉算子的設計一般都采用隨機交叉的方式,由兩個個體的交叉產生兩個新個體,其結果是父代與子代間很相似,這也會導致如上的問題。因此,有必要研宄如何改進SGA,采用合適的算法加快多峰值函數的尋優速度和質量。
另一方面,目前許多有關智能系統的研宄都是圍繞人腦智能及其學習機制進行的。這些擬人化方法都忽略了與人腦行為方式并不明顯相關的另一類智能系統——免疫系統。生物體的免疫系統具備很高的智能級(highieveiofinteiigence),但它與人腦的行為方式的確沒有明顯聯系。由于實際的生物體免疫系統具備免疫記憶、記憶開發(長期和短期)、混沌識別、自適應網絡調節等許多優良功能,因此,我們可以考慮模擬其實際行為規律,設計出相應的數學算法來解決實際問題。
在免疫系統中產生的抗體是用于對付和消除外來抗原的。如果我們進行類比——對于一個優化問題而言,抗原對應問題的目標函數而抗體對應問題的最優解,那么免疫系統的特點對于改進和提高遺傳算法的能力就具有重要的啟迪作用。文中模擬部分免疫特點(如自我免疫等)對SGA進行改進而設計出一種免疫遺傳算法,該算法的優化能力相對SGA而言有一定的改進。本文對如何有效模擬免疫重組、免疫記憶、混沌增殖等免疫行為而設計出免疫遺傳算法以更好地進行多峰值函數的尋優進行探討。
2免疫遺傳學思想及免疫遺傳算法設計
2。1免疫遺傳學基本思想
在生物醫學科學領域,免疫遺傳學(Immunogenetics)
作為免疫學(Immunoiogy)和遺傳學(Genetics)這兩門學科的邊緣學科,豐富和發展了現代遺傳學理論。免疫遺傳的研宄說明了免疫物質不僅受遺傳基因的控制,而且由此發生的免疫功能(免疫應答)也同樣受到遺傳調控。
當傳染媒介侵入生物系統后,免疫系統的工作就是中和或者清除異物。免疫系統模型如圖l所示。免疫系統的特點詳述如下:
。1)基因重組:當外來抗原(antigen)侵入生物體時,免疫系統先對不同的抗原進行識別,針對不同的抗原生成對應的抗體(antibody)進行中和或破壞?贵w的產生是通過DNA分子上特定段的任意重組進行的[2]。
。2)網絡作用:當一個抗體傳遞給生物體中的B細胞時,一次免疫響應就啟動了。如果與抗原匹配,B細胞將被激活。B細胞的激勵水平不僅依賴于其與抗原匹配的程度,而且依賴于它同機體免疫系統
時刻第i個個體的濃度,mj表示抗體i、間的親和系數,m_t_(表示抗體i、(間的排斥系數,a"分別表示抗體i對于其它抗體和抗原的交互作用率,(i表示抗體i的自然死亡率,^表示抗體i與抗原間的匹配率,N為抗體數目。
按照式(1)、(2)的計算結果,如果激勵水平超過閾值,B細胞將生成自身的許多克。╟lones),而這個行為又將啟動一個變異機制——在抗體分子的編碼基因(genes)中產生變異。反之,如果激勵水平低于閾值,B細胞不會自我復制,并且到時候死亡。這樣,在免疫理論中很重要的一點需要引起我們注意的是:傳遞一個抗原給能夠約束它的B細胞不僅引起B細胞對抗原的分析,而且會導致許多新的B細胞的生成。所有的這些B細胞可以依次分析抗原并進一步產生B細胞——這是新的B細胞生成方式之一。
。1)混沌增殖。對于有關細胞生長方面的研宄,文中針對白細胞生成控制模型進行了討論,表明在確定性的時間系統中存在著內在混沌的可能性;同時,第三軍醫大學的徐啟旺對綠膿桿菌的生長作了初步的探討,實驗結果表明:細菌的生長不是同步分裂而是呈現混亂無序的混沌態增殖,因此其本質是一種波形狀態的生命活動并伴隨以非線性動態的混沌增殖;煦缋碚撝,通過Iogistic方程:+1(t)=(^,Xi)=(l—x)i=0,l,2,…)生成的混沌序列是遺傳學中用以描述昆蟲數目世代變化規律的方程,可以用于模擬免疫細胞的增殖方式。混沌序列較通常的`RANDOM函數相比,具有更好的隨機性、快速性——這是由混沌的本身特色決定,因此可以更好保持多樣性,并能夠有效解決全局搜索能力和局部搜索能力的矛盾。
。2)免疫變異:高等生物尤其是哺乳動物,在進化進程中對多種多樣的病原體或異原性蛋白甚至人工合成的抗原都能夠產生相對應的抗體。實際上一個淋巴細胞只產生一種抗體,而生物體內的確存在成千上萬種抗體,這種適應性功能的發展程度很讓人驚訝。基因是抗體的基本單體,對于淋巴系統能夠產生如此多種的抗體分子,體細胞突變學說(somaticmuta?tiontheory,Cohn,l968)認為數量如此巨大的基因貯存在種質(即生殖細胞染色體)中是不可能的,也是不經濟的。該學說認為種質傳下來的只是少量V基因(一種基本基因),而V基因的多樣性主要是由于個體發育期間體細胞突變造成的。這一說法也得到了Leder等人的支持。這些變異主要反映在高可變區(hv區域,抗體分子的一部分)上,主要由它決定了抗體的多樣性。這已為許多觀察結果所支持^]所以,我們可以看到,變異機制在抗體的生成及多樣性的維持方面起到了重要的作用。
(3)免疫選擇:由于免疫過程中許多的變異行為會破壞抗體對抗原的親和力——即使假定變異機制是在完全隨機的情況下。因此免疫系統需要通過有選擇地增加高親和力的抗體數目來解決這個問題。
。4)免疫記憶:在抗原消失后數月甚至數年,抗體形成細胞仍然具有免疫記憶。因此以后抗原侵入時生物體根據自身免疫網絡可以很快生成對應的抗體來中和抗原。
。5)免疫代謝:由于機體本身的新陳代謝,每天有5%的低激勵值B細胞死亡,而代之以從骨髓中生成全新B細胞。只有那些與網絡中已存在B細胞具有較強親和力的新B細胞才會加入到免疫系統中,否則將死亡。
。6)濃度控制:在免疫研宄中我們發現免疫過程完成后機體內抗體濃度不會過高,否則,正常體細胞會受到損害。這是免疫行為的另一個重要特點。
(7)隔離小生境:研宄發現,生物在進化過程中,之所以具有形成許多物種的能力,主要是因為生物群具有分化小種群的能力,小種群沿著不同的方向進化,彼此間差距越來越大,漸漸由同一物種分化為許多不同的種。其中隔離起著非常重要的作用——它防止了被隔離種群間的雜交,因而防止了其間基因的交流。隔離對于種群的分化是很有幫助的。因此,為了進一步保證群體中個體的多樣性,我們在算法的設計中引入小生境(mce)技術。
如上所述,我們可以看到:免疫行為的許多特點能夠使免疫細胞的多樣性較好地得到維持,因而我們可以考慮模擬生物體的實際免疫行為設計出一種新的優化算法——免疫遺傳算法(ImmunogeneticAlgorithm),簡記為IGA,它較SGA而言將更加有利于尋優。
2。2免疫遺傳算法的設計
根據2。1節中討論的內容,我們可以進行免疫遺傳算法的設計。根據免疫行為的特點,我們設計了如下幾個核心模擬
算法:
。1)小生境:模擬隔離小生境特點,引入小生境技術[1],將演化種群分為若干個小子群以實現隔離。這包含在初始抗體生成中。
。2)重組:模擬基因重組,在子群內將各基因位統一編碼,然后進行基因的隨機重組。這里不使用SGA的交叉算子,因而可以有效地避免父代與子代間的相似問題。
。3)免疫變異:以類似SGA的方式和較大的概率進行變異操作。
。4)抗體產生:模擬免疫網絡作用、免疫選擇和濃度控制,我們進行以下工作。差分計算式(1):令s中其它B細胞的親和度。根據Jerne提出的免疫網絡理論(見圖2),計算抗體激勵水平及濃度的動態方程如下:
按照式(1)、(2)的計算結果,如果激勵水平超過閾值,B細胞將生成自身的許多克。╟lones),而這個行為又將啟動一個變異機制——在抗體分子的編碼基因(genes)中產生變異。反之,如果激勵水平低于閾值,B細胞不會自我復制,并且到時候死亡。這樣,在免疫理論中很重要的一點需要引起我們注意的是:傳遞一個抗原給能夠約束它的B細胞不僅引起B細胞對抗原的分析,而且會導致許多新的B細胞的生成。所有的這些B細胞可以依次分析抗原并進一步產生B細胞——這是新的B細胞生成方式之一。
(1)混沌增殖。對于有關細胞生長方面的研宄,文[4]中針對白細胞生成控制模型進行了討論,表明在確定性的時間系統中存在著內在混沌的可能性;同時,第三軍醫大學的徐啟旺對綠膿桿菌的生長作了初步的探討,實驗結果表明:細菌的生長不是同步分裂而是呈現混亂無序的混沌態增殖,因此其本質是一種波形狀態的生命活動并伴隨以非線性動態的混沌增殖[4];煦缋碚撝校ㄟ^Iogistic方程:+1(t)=(^,Xi)=
。╨—x)i=0,l,2,…)生成的混沌序列是遺傳學中用以描述昆蟲數目世代變化規律的方程,可以用于模擬免疫細胞的增殖方式;煦缧蛄休^通常的RANDOM函數相比,具有更好的隨機性、快速性——這是由混沌的本身特色決定,因此可以更好保持多樣性,并能夠有效解決全局搜索能力和局部搜索能力的矛盾。
。2)免疫變異:高等生物尤其是哺乳動物,在進化進程中對多種多樣的病原體或異原性蛋白甚至人工合成的抗原都能夠產生相對應的抗體。實際上一個淋巴細胞只產生一種抗體,而生物體內的確存在成千上萬種抗體,這種適應性功能的發展程度很讓人驚訝。基因是抗體的基本單體,對于淋巴系統能夠產生如此多種的抗體分子,體細胞突變學說(somaticmuta?tiontheory,Cohn,l968)認為數量如此巨大的基因貯存在種質(即生殖細胞染色體)中是不可能的,也是不經濟的。該學說認為種質傳下來的只是少量V基因(一種基本基因),而V基因的多樣性主要是由于個體發育期間體細胞突變造成的。這一說法也得到了Leder等人的支持。這些變異主要反映在高可變區(hv區域,抗體分子的一部分)上,主要由它決定了抗體的多樣性。這已為許多觀察結果所支持^]所以,我們可以看到,變異機制在抗體的生成及多樣性的維持方面起到了重要的作用。
。3)免疫選擇:由于免疫過程中許多的變異行為會破壞抗體對抗原的親和力——即使假定變異機制是在完全隨機的情況下。因此免疫系統需要通過有選擇地增加高親和力的抗體數目來解決這個問題。
。4)免疫記憶:在抗原消失后數月甚至數年,抗體形成細胞仍然具有免疫記憶。因此以后抗原侵入時生物體根據自身免疫網絡可以很快生成對應的抗體來中和抗原[l0]。
。5)免疫代謝:由于機體本身的新陳代謝,每天有5%的低激勵值B細胞死亡,而代之以從骨髓中生成全新B細胞。只有那些與網絡中已存在B細胞具有較強親和力的新B細胞才會加入到免疫系統中,否則將死亡。
(6)濃度控制:在免疫研宄中我們發現免疫過程完成后機體內抗體濃度不會過高,否則,正常體細胞會受到損害。這是
免疫行為的另一個重要特點[1Q]。
。7)隔離小生境:研宄發現,生物在進化過程中,之所以具有形成許多物種的能力,主要是因為生物群具有分化小種群的能力,小種群沿著不同的方向進化,彼此間差距越來越大,漸漸由同一物種分化為許多不同的種。其中隔離起著非常重要的作用——它防止了被隔離種群間的雜交,因而防止了其間基因的交流。隔離對于種群的分化是很有幫助的。因此,為了進一步保證群體中個體的多樣性,我們在算法的設計中引入小生境(mce)技術[1’11]。
如上所述,我們可以看到:免疫行為的許多特點能夠使免疫細胞的多樣性較好地得到維持,因而我們可以考慮模擬生物體的實際免疫行為設計出一種新的優化算法——免疫遺傳算法(ImmunogeneticAlgorithm),簡記為IGA,它較SGA而言將更加有利于尋優。
2。2免疫遺傳算法的設計
根據2。1節中討論的內容,我們可以進行免疫遺傳算法的設計。根據免疫行為的特點,我們設計了如下幾個核心模擬
算法:
。1)小生境:模擬隔離小生境特點,引入小生境技術[1],將演化種群分為若干個小子群以實現隔離。這包含在初始抗體生成中。
。2)重組:模擬基因重組,在子群內將各基因位統一編碼,然后進行基因的隨機重組。這里不使用SGA的交叉算子,因而可以有效地避免父代與子代間的相似問題。
(3)免疫變異:以類似SGA的方式和較大的概率進行變異操作。
。4)抗體產生:模擬免疫網絡作用、免疫選擇和濃度控制,我們進行以下工作。差分計算式(1):令
根據式(3)、(4)的迭代,計算出相應抗體的濃度ai(n),再按照SGA的方法計算出第i個個體的適應值與平均適應值
之比SGASlct_prop(i),計算min(a;(n),SGASlct_propi(n));再考慮機體中抗體濃度不能夠過大的原則,進行濃度控制。算法如下:
ifmin(〇(n),SGAslct_propi(n))>規定濃度then
復制概率copy_prob,n)=規定濃度
elsecopy_probi(n)=min(a(n),SGAslct_prop(n))
以此實現模擬免疫系統選擇性地增加高親和力的抗體數目的行為以及免疫過程完成后機體內抗體濃度不會過高的現象。
。1)免疫記憶:各子群依次計算完畢后,計算總群體的最大適應值。如果本次計算得到的最大適應值大于免疫網絡中已存在抗體所能夠提供的最大適應值,則將對應的個體作為新抗體加入抗體記憶表中,本次最大適應值加入抗體適應值表;否則,啟動免疫記憶,根據抗體表中所記憶的歷史抗體,利用logistic方程尋找出新的高適應值個體作為更好的免疫抗體,混沌初始值分為歷史抗體及抗體的變異個體兩種。此方法模擬如下免疫行為:當激勵水平超過閾值時,機體B細胞將生成自身的許多克。╟lones),同時啟動變異機制——在抗體分子的編碼基因(genes)中產生變異。
(2)免疫代謝:模擬免疫行為中細胞的混沌增殖現象,找出子群內5%的低激勵水平個體并去除;利用logistic方程從免疫記憶表中生成新的高適應值個體加入種群中。
免疫遺傳算法具體流程如下:
步驟1初始抗體生成(n=1((含小生境隔離);
步驟2對于第m個子群進行以下的操作:
(1)免疫重組;(2)免疫變異;(3)抗體生成;(4)免疫記憶;(5)免疫代謝;(6)群體更新
步驟3各子群體依次計算完畢后,如果n>指定演化代數,則結束計算,否則n=n+1,轉到第2步。
IGA算法分析:(1)在多峰值函數的尋優中,IGA的局部搜索能力和全局搜索能力是一對矛盾。而我們希望遺傳算法具有自動在解空間隨機探索新點的能力,同時能夠在某一區域內很快收斂最優解。顯然,IGA很難滿足我們的要求。因為IGA的選擇算子和交叉算子的設計方法往往會導致父代與子代間很相似,因而很難脫離局部極值。其主要賴以擺脫局部極值的變異算子的變異概率若取得太大,固然會增強全局搜索能力,但是又會導致局部搜索能力降低;為解決此問題,本文在IGA的設計中,引入了隔離小生境和混沌的思想。隔離小生境技術將遺傳的競爭過程分為子群體間的競爭和子群體內個體間的競爭兩級——前者體現為全局搜索能力,后者體現為局部搜索能力,這樣通過兩級競爭,就有效地解決了局部搜索能力和全局搜索能力的矛盾。(2)隔離機制的引入使子群體的進化既同整個群體的進化密切相關,又有相對獨立性,這有利于種群個體多樣性的維持;同時,子群體的進化可以并行處理,這將大大提高優化的速度。(3)為了解決由于SGA的選擇和交叉算子設計方式而導致父子代間的相似問題,本文模擬免疫行為中抗體濃度的控制和基因的重組而設計了濃度控制策略和重組算子以進一步維持個體的多樣性。(4)本文提出了模擬免疫記憶和新陳代謝而將混沌思想引入到SGA中的方法。利用混沌對初值的敏感性以及隨機性、規律性、遍歷性,算法可以有效地跳出局部收斂點以更快地收斂于最大值,從而能夠比較有效地解決通常遇到的“早熟”問題。
3實驗研究
本文以多峰值函數/(x,y)=(_1)#(x2+2y2_0。3cos(3兀x)—0。4cos(4^y))+4為例,用IGA進行尋優比較研究。該函數有很多個局部極大值,其中最大值為4。7,此時x,y均取值為0。為了更好的體現本文算法的優化能力,我們還對本文的IGA與文[7]的算法(記為“[7]”)進行優化比較。實驗中,自變量x,y取值范圍是[—1,1],種群大小為50,個體編碼長度均為20位。算法[7]的交叉概率取0。4,隨機取1位變異。IGA中隨機取2位變異。實際計算20代。定義的y次方,則我們可以定義個體間綜合激勵系數的計算公式為:
。1)將個體按位異或,得到新個體k
。2)計算出個體k直接對應的十進制整數/(k);
。3)_(k)
3、=2!編碼位數—1。
實驗結果比較如下(以下各圖縱坐標表示最大適應值,圖3中橫坐標表示演化代數,圖4中橫坐標表示統計次數)
從實驗的得到的各圖形和表格數據的比較中,我們可以看到:在多峰值函數的優化過程中,本文的IGA具有良好的搜索能力。
4結論
通過實驗比較,我們可以看到IGA具有更強的尋優性能,結果令人滿意。由于IGA具備能夠有效地解決局部搜索能力和全局搜索能力的矛盾、有效維持種群多樣性、較好地防止早熟等優點,從而對今后的實際規劃和設計工作能夠起到良好的促進和幫助作用。但是由于實際上抗體是一個具有變區(VAQ)和常區(C區)的二官能分子(bifunctionalmolecules),而本文的算法主要根據V區的規律而設計的,因此如何將C、V兩個區的特點綜合考慮設計出更好的算法是值得以后繼續深入研宄的。
【一種基于生物免疫遺傳學的新優化方法論文】相關文章:
5.醫學免疫的論文