第14講--計算機(jī)地質(zhì)學(xué)---免疫遺傳算法與地質(zhì)應(yīng)用

1、西安科技大學(xué)薛喜成 計算機(jī)地質(zhì)學(xué)主要內(nèi)容14.1 免疫遺傳算法概述14.2 免疫遺傳算法基本原理14.3 免疫遺傳算法的算法設(shè)計14.4 免疫遺傳算法地質(zhì)應(yīng)用14.1 免疫遺傳算法概述 傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)，隱層結(jié)構(gòu)至今沒有一個完整的理論、公式確定，而BP神經(jīng)網(wǎng)絡(luò)的核心就在于隱層、隱單元數(shù)目及其連接權(quán)。其中隱單元不僅對建立的神經(jīng)網(wǎng)絡(luò)模型的性能影響很大，而且是訓(xùn)練時出現(xiàn)“過擬合”的直接原因，若隱單元數(shù)太少，網(wǎng)絡(luò)可能根本不能訓(xùn)練或網(wǎng)絡(luò)性能很差；若隱單元數(shù)太多，雖然可使網(wǎng)絡(luò)的系統(tǒng)誤差減小，但一方面使網(wǎng)絡(luò)訓(xùn)練時間延長，另一方面，訓(xùn)練容易陷入局部極小點(diǎn)而得不到最優(yōu)點(diǎn)，也是訓(xùn)練時出現(xiàn)“過擬合”的內(nèi)在原因。

2、通常情況下BP神經(jīng)網(wǎng)絡(luò)的泛化能力隨著網(wǎng)路的學(xué)習(xí)能力提高而提高，而過擬合是指隨著學(xué)習(xí)能力的提高，網(wǎng)絡(luò)的泛化能力反而下降的現(xiàn)象。通常隱單元采用修剪法或增長法來確定，采用這種方法常出現(xiàn)網(wǎng)絡(luò)泛化能力差、收斂速度慢、易陷入局部極小，導(dǎo)致預(yù)測結(jié)果的誤差增加。遺傳算法較以往傳統(tǒng)的搜索算法具有使用方便，魯棒性強(qiáng)、便于并行處理等優(yōu)點(diǎn)，因而廣泛應(yīng)用于組合算法、結(jié)構(gòu)設(shè)計、人工智能等領(lǐng)域。 動物三大支柱系統(tǒng)中的神經(jīng)網(wǎng)絡(luò)系統(tǒng)、遺傳進(jìn)化系統(tǒng)已被人們廣泛研究，這里還將引入第三大系統(tǒng)免疫系統(tǒng)，基于免疫原理的遺傳算法可有效地改善遺傳算法的未成熟收斂缺陷，提高遺傳算法的全局和局部搜索能力。 名詞 魯棒性：魯棒性（robustne

3、ss）就是系統(tǒng)的健壯性。它是在異常和危險情況下系統(tǒng)生存的關(guān)鍵。比如說，計算機(jī)軟件在輸入錯誤、磁盤故障、網(wǎng)絡(luò)過載或有意攻擊情況下，能否不死機(jī)、不崩潰，就是該軟件的魯棒性。所謂“魯棒性”，是指控制系統(tǒng)在一定（結(jié)構(gòu)，大小）的參數(shù)攝動下，維持某些性能的特性。根據(jù)對性能的不同定義，可分為穩(wěn)定魯棒性和性能魯棒性。14.2 免疫遺傳算法基本原理 （1）免疫遺傳算法概述 基本遺傳算法（Simple Genetic Algorithm，簡稱SGA）是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法，它是美國密執(zhí)根大學(xué)的霍勒德（J.H.Holland）于1975年首先提出來的。遺傳算法具有簡單通用、魯棒性強(qiáng)、

4、全局并發(fā)搜索等特點(diǎn)。它是一種全局化搜索算法，尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問題。在理論上已經(jīng)形成了一套較為完善的算法體系，然而在實(shí)際使用中，還有許多問題有待于進(jìn)一步研究探討。例如，對于單調(diào)函數(shù)或單峰函數(shù)，在初始時很快向最優(yōu)值逼近，但是在最優(yōu)值附近收斂較慢； 而對于多峰函數(shù)的優(yōu)化問題，它往往會出現(xiàn)“早熟”，即收斂于局部極值。為此，人們正對基本遺傳算法（SGA）作不斷的改進(jìn)和提高，生物體的免疫系統(tǒng)具有很強(qiáng)的自適應(yīng)性，而實(shí)際問題的求解過程與生物免疫機(jī)制十分類似?；诿庖咴淼倪z傳算法（Immunity Genetic Algorithm，簡稱IGA）就是一種對傳統(tǒng)遺傳算法的改進(jìn)。通過對

5、TSP問題（又稱商旅問題）求解的實(shí)驗(yàn)表明，基于免疫原理的遺傳算法可有效改善未成熟收斂缺陷，提高遺傳算法的全局和局部搜索能力。 （2）免疫遺傳算法基本原理 免疫算法將實(shí)際求解問題的目標(biāo)函數(shù)對應(yīng)為抗原，而問題的解對應(yīng)為抗體。由生物免疫原理可知，生物免疫系統(tǒng)對入侵生命體的抗原通過細(xì)胞的分裂和分化作用，自動產(chǎn)生相應(yīng)的抗體來抵御，這一過程被稱為免疫應(yīng)答。在免疫應(yīng)答過程中，部分抗體作為記憶細(xì)胞保存下來，當(dāng)同類抗原再次侵入時，記憶細(xì)胞被激活并迅速產(chǎn)生大量抗體，使再次應(yīng)答比初次應(yīng)答更快更強(qiáng)烈，體現(xiàn)了免疫系統(tǒng)的記憶功能?？贵w與抗原結(jié)合后，會通過一系列的反應(yīng)而破壞抗原。同時，抗體與抗體之間也相互促進(jìn)和抑制，以維持

6、抗體的多樣性及免疫平衡，這種平衡是根據(jù)濃度機(jī)制進(jìn)行的，即抗體的濃度越高，則越受抑制；濃度越低，則越受促進(jìn)，體現(xiàn)了免疫系統(tǒng)的自我調(diào)節(jié)功能。 與生物免疫系統(tǒng)的功能相對應(yīng)，基于免疫原理的遺傳算法與標(biāo)準(zhǔn)遺傳算法相比，具有如下顯著特點(diǎn)：具有免疫記憶功能，該功能可以加快搜索速度，提高遺傳算法的總體搜索能力；具有抗體的多樣性保持功能，利用該功能可以提高遺傳算法的局部搜索能力；具有自我調(diào)節(jié)功能，這種功能可用于提高遺傳算法的全局搜索能力，避免陷入局部解?？傊?，免疫遺傳算法既保留了遺傳算法隨機(jī)全局并行搜索的特點(diǎn)，又在相當(dāng)大程度上避免未成熟收斂，確保快速收斂于全局最優(yōu)解。14.3 免疫遺傳算法的算法設(shè)計14.3.1

7、 免疫算子 免疫算子的設(shè)計思想：引入信息熵來判斷抗體的多樣性，即等位基因概率的變化過程。設(shè)免疫系統(tǒng)有N個抗體組成，每個抗體有M位基因。每個抗體的每位可供選擇的字母表中共有s個字母：k1，k2，ks。其結(jié)構(gòu)下圖所示： 我們將抗原定義為BP神經(jīng)網(wǎng)絡(luò)的隱層結(jié)構(gòu)，則此時的抗體為最優(yōu)的隱層結(jié)構(gòu)。為了從抗體群中找出適應(yīng)度較優(yōu)的抗體，并產(chǎn)生新的抗體群，須比較抗體與抗體之間、抗體與抗原的親和力。 抗體間的親和力：用于表明兩抗體之間的相似度。任意兩個抗體v和抗體w間的親和力為： 上式中的H(2)為任意兩個抗體v和抗體w的平均信息熵。H(2)可以通過下式計算獲得。 抗原與抗體的親和力：用于表明抗體對抗原的識別程度

8、，把它定義為該抗體的適應(yīng)度。抗體v和抗原v的親和力為： 其中表示抗原和抗體之間的適應(yīng)度，其計算公式為： 計算上式中的網(wǎng)絡(luò)總誤差E時，先從種群中取一條染色體，恢復(fù)成相應(yīng)的BP神經(jīng)網(wǎng)絡(luò)，將訓(xùn)練樣本帶入網(wǎng)絡(luò)中進(jìn)行迭代，并由下式計算出網(wǎng)絡(luò)的總誤差E，由上式計算出f1： 上式中Ti(x)和Oi(x)分別為第x個訓(xùn)練樣本的第i個輸出節(jié)點(diǎn)的期望輸出和實(shí)際輸出。M，N分別為訓(xùn)練樣本總數(shù)和輸出節(jié)點(diǎn)總數(shù)。 的適應(yīng)度值越大，則表示該網(wǎng)絡(luò)性能越好；適應(yīng)度值越小，則表示該網(wǎng)絡(luò)的性能越差。 通過上式可以看出，抗體適應(yīng)度越大，則復(fù)制選擇概率越大；抗體的濃度越高，則復(fù)制選擇概率越小。 通過免疫算子既保留了遺傳算法的全局搜索能

9、力，又有效地保持抗體的多樣性，避免了未成熟收斂現(xiàn)象。 名詞信息熵：1948年香農(nóng)（Claude Elwood Shannon）長達(dá)數(shù)十頁的論文“通信的數(shù)學(xué)理論”成了信息論正式誕生的里程碑。在他的通信數(shù)學(xué)模型中，清楚地提出信息的度量問題，他把哈特利的公式擴(kuò)大到概率pi不同的情況，得到了著名的計算信息熵H的公式：H=-pi log pi。 名詞抗體：早在一個世紀(jì)以前，就有人發(fā)現(xiàn)機(jī)體受外來抗原物質(zhì)刺激后，能產(chǎn)生一種與該抗原發(fā)生特異性結(jié)合的物質(zhì)，稱為抗體。抗原是能使機(jī)體產(chǎn)生一系列免疫反應(yīng)的物質(zhì)，如細(xì)菌、病毒或其代謝產(chǎn)物?？贵w有抵抗傳染病的能力，是抗原進(jìn)入人體后，刺激機(jī)體產(chǎn)生的一種與該抗原相結(jié)合的特異性

10、物質(zhì)，如免疫球蛋白。14.3.2 染色體編碼設(shè)計 傳統(tǒng)遺傳算法的染色體是單層的，當(dāng)染色體編碼較長時，染色體中短基因組的實(shí)際交叉、變異概率過小，容易導(dǎo)致抗體群缺乏多樣性。其表現(xiàn)為：抗體群中個體的短基因組的相似性大，算法收斂速度慢?？梢圆捎萌龑咏Y(jié)構(gòu)的染色體來設(shè)計BP神經(jīng)網(wǎng)絡(luò)的優(yōu)化方案，其具體結(jié)構(gòu)如下圖所示： 第一層是隱層結(jié)構(gòu)基因組，用二進(jìn)制編碼，用于表示BP神經(jīng)網(wǎng)絡(luò)中隱層的數(shù)目，此層的編碼總長度表示網(wǎng)絡(luò)隱層的最大值；編碼上的某一位為1時表示該隱層激活，為0時表示該隱層未被激活，其下層的基因組也未被激活。上圖中此層的編碼為“1010”表示有2個隱層。 第二層是神經(jīng)元基因組，采用二進(jìn)制編碼，表示某隱層

11、下的神經(jīng)元個數(shù)，其中一個位表示一個神經(jīng)元，此位上的值為0時，表示此神經(jīng)元處于休眠狀態(tài)，其下層的基因組也處于休眠狀態(tài)；為1表示此神經(jīng)元處于激活狀態(tài)，并能產(chǎn)生有效輸出，其下層基因組也處于工作狀態(tài)。上圖中此層上的編碼“1110”表示第1個隱層上有3個神經(jīng)元。 第三層基因組采用十進(jìn)制編碼，表示上層神經(jīng)元的所有閥值、權(quán)值。每一位代表一個權(quán)值（從左到右分別為該神經(jīng)元的閾值、連接權(quán)值）。此層最后的W0基因片段為輸出層的閥值及連接權(quán)值，這些權(quán)值的個數(shù)與當(dāng)前染色體中最后隱層中激活的神經(jīng)元個數(shù)有關(guān)，如果最后隱層中有n個激活的神經(jīng)元，則輸出層每個神經(jīng)元必有1個閥值和n個權(quán)值。14.3.3 遺傳操作 首先接受一個抗原

12、（對應(yīng)特定問題），然后隨機(jī)產(chǎn)生一組初始抗體（對應(yīng)候選解）；接著計算每一代抗體的適應(yīng)度，對抗體進(jìn)行交叉和變異；再通過基于抗體濃度和親和力的群體更新策略生成下一代抗體群；直到滿足終止條件，算法結(jié)束。將結(jié)果代入BP神經(jīng)網(wǎng)絡(luò)中，進(jìn)行網(wǎng)絡(luò)訓(xùn)練、評估。具體過程如下圖。 算法中的遺傳操作主要有： （1）選擇 淘汰適應(yīng)度差的個體，選擇適應(yīng)度高的個體，按照“適者生存”的原則對個體進(jìn)行復(fù)制。有時可采用“輪盤賭（Roulette Wheel）”的方法實(shí)現(xiàn)選擇。其基本思想是：如下圖所示，各個個體被選中的幾率與其選擇概率pv大小成正比，選擇概率pv大的個體被選中的幾率就越大；反之，選擇概率pv越低的個體被選中的幾率就越

13、小。 其具體執(zhí)行過程是：首先，計算出每個個體的選擇概率pv（各個個體選擇概率之和等于1），然后使用模擬賭盤操作，即隨機(jī)生成一個（0，1）之間的浮點(diǎn)數(shù)，表示賭盤指針的位置，由此來判斷某個個體是否被選中。 （2）交叉 交叉是把兩個父個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作，它的目的是為了能夠在下一代產(chǎn)生新的個體。實(shí)踐中常用到兩點(diǎn)交叉。 兩點(diǎn)交叉（Two-point Crossover）是指在個體編碼串中隨機(jī)設(shè)置了兩個交叉點(diǎn)，然后再進(jìn)行部分基因交換。 其具體操作過程是：首先，在相互配對的兩個個體編碼串中隨機(jī)設(shè)置兩個交叉點(diǎn)。然后，交換兩個個體在所設(shè)定的兩個交叉點(diǎn)之間的部分染色體。如下圖所示。 （3

14、）變異 對于編碼中的任一位，以一定的概率進(jìn)行變異。對染色體中第1、2層的二進(jìn)制編碼，變異操作只是簡單地將基因取反，即將“1”變?yōu)椤?”，將“0”變?yōu)椤?”；對于第3層上的十進(jìn)制的編碼，則根據(jù)變異幾率將某一位或某幾位用 -0.5，0.5上的隨機(jī)實(shí)數(shù)替換原來的十進(jìn)制數(shù)。 （4）終止條件 終止條件根據(jù)具體的情況有很多種方法，較為常用的方法是將迭代次數(shù)作為終止條件，當(dāng)達(dá)到某一預(yù)先設(shè)定的迭代次數(shù)后終止。采用判斷個體的平均濃度趨于穩(wěn)定作為終止條件也是將為常見的方法。通常多以最大迭代次數(shù)作為終止條件，即當(dāng)網(wǎng)絡(luò)達(dá)到最大迭代次數(shù)后停止迭代，同時將搜索到適應(yīng)度最大的個體作為對BP神經(jīng)網(wǎng)絡(luò)優(yōu)化的結(jié)果。 名詞輪盤賭：俄羅斯輪盤賭（Russian roulette）是一種殘忍的賭博游戲。與其他使用撲克、色子等賭具的賭博不同的是，俄羅斯輪盤賭的賭具是左輪手槍和人的性命。俄羅斯輪盤賭的規(guī)則很簡單：在左輪手槍的六個彈槽中放入一顆或多顆子彈，任意旋轉(zhuǎn)轉(zhuǎn)輪之后，關(guān)上轉(zhuǎn)輪。游戲的參加者輪流把手槍對著自己的頭，扣動板機(jī)；中槍的當(dāng)然是自動退出，怯場的也為輸，堅(jiān)持到最后的就是勝者。旁觀的賭博者，則對參加者的性命壓賭注。 據(jù)說，這種賭博始于第一次世界大戰(zhàn)，戰(zhàn)敗的沙俄士兵在軍營里借酒澆愁，用這種游戲助興。于是這種賭博方式，就被稱為“俄羅