智能信息處理導(dǎo)論第7章-免疫算法課件

1、第七章 免疫算法第七章 免疫算法7.1 免疫算法的生物學(xué)基礎(chǔ)7.1.1 免疫系統(tǒng)的形態(tài)空問7.1.2 免疫應(yīng)答7.1.3 多樣性7.1.4 克隆選擇和擴(kuò)增7.1 免疫算法的生物學(xué)基礎(chǔ)7.1.1 免疫系7.1.1 免疫系統(tǒng)的形態(tài)空問基本概念和技術(shù)術(shù)語：(1)免疫：指機(jī)體免疫系統(tǒng)識(shí)別自身與異己物質(zhì)，并通過免疫應(yīng)答排除抗原性異物，以維持機(jī)體生理平衡的功能。(2)免疫應(yīng)答：是指抗原進(jìn)入機(jī)體后，免疫細(xì)胞對(duì)抗原分子的識(shí)別、激活、分化、增殖和效應(yīng)的過程。(3)抗原與抗體：誘導(dǎo)免疫系統(tǒng)產(chǎn)生免疫應(yīng)答的物質(zhì)稱為抗原(antigen)；能與抗原進(jìn)行特異性結(jié)合的免疫細(xì)胞稱為抗體(antibody)。(4)親和力(af

2、finity)：免疫細(xì)胞的表面受體和抗原決定基都是復(fù)雜的含有電荷的三維結(jié)構(gòu)，二者的結(jié)構(gòu)和電荷越互補(bǔ)，就越有可能相互結(jié)合，結(jié)合的強(qiáng)度即是親和力。7.1.1 免疫系統(tǒng)的形態(tài)空問基本概念和技術(shù)術(shù)語：7.1.1 免疫系統(tǒng)的形態(tài)空問(5)變異(mutation)：在生物免疫系統(tǒng)中，細(xì)胞與抗原結(jié)合后被激活，然后產(chǎn)生高頻變異。這種克隆擴(kuò)增期間產(chǎn)生的變異形式，使得免疫系統(tǒng)能夠適應(yīng)不斷變化的外來入侵。(6)細(xì)胞：即淋巴細(xì)胞，它在胸腺中成熟，功能包括調(diào)節(jié)其他細(xì)胞的活動(dòng)和直接襲擊宿主感染細(xì)胞。(7)細(xì)胞：即淋巴細(xì)胞，來源于骨髓淋巴樣前體細(xì)胞，成熟的細(xì)胞存在于淋巴結(jié)、血液、脾、扁桃體等組織和器官中，細(xì)胞是體內(nèi)產(chǎn)生抗體

3、的細(xì)胞，在清除病原體過程中受到刺激，分泌抗體結(jié)合抗原，但其發(fā)揮免疫作用要受輔助細(xì)胞的幫助。7.1.1 免疫系統(tǒng)的形態(tài)空問(5)變異(mutatio7.1.1 免疫系統(tǒng)的形態(tài)空問如圖所示，在形態(tài)空間內(nèi)有一個(gè)體積為V的區(qū)域，其中含有抗體（用 來表示）和抗原（用表示）的形狀互補(bǔ)區(qū)域。假設(shè)一個(gè)抗體能識(shí)別所有在其周圍體積 范圍內(nèi)的互補(bǔ)的抗原。7.1.1 免疫系統(tǒng)的形態(tài)空問如圖所示，在形態(tài)空間7.1.2 免疫應(yīng)答免疫系統(tǒng)的兩種免疫應(yīng)答類型：固有性免疫應(yīng)答；適應(yīng)性免疫應(yīng)答。免疫算法主要是利用適應(yīng)性免疫應(yīng)答的應(yīng)答原理，適應(yīng)性免疫應(yīng)答又分為兩種類型，初次免疫應(yīng)答和二次免疫應(yīng)答。7.1.2 免疫應(yīng)答免疫系統(tǒng)的兩種

4、免疫應(yīng)答類型：固有性免7.1.3 多樣性免疫系統(tǒng)的多樣性，本質(zhì)就是抗體的多樣性，即產(chǎn)生盡可能多的抗體對(duì)抗千變?nèi)f化的抗原。免疫系統(tǒng)的多樣性的實(shí)現(xiàn)： 體細(xì)胞高頻變異 受體編輯 隨機(jī)生成新抗體7.1.3 多樣性免疫系統(tǒng)的多樣性，本質(zhì)就是抗體的多樣性7.1.4 克隆選擇和擴(kuò)增基本思想：只有那些能夠識(shí)別抗原的細(xì)胞才進(jìn)行擴(kuò)增，只有這些細(xì)胞才能被免疫系統(tǒng)選擇并保留下來，而那些不能識(shí)別抗原的細(xì)胞則不被選擇，也不能進(jìn)行擴(kuò)增。擴(kuò)增過程：抗體C分化成許多克隆細(xì)胞，每一個(gè)克隆細(xì)胞受到刺激后又開始克隆，這樣，增加了免疫系統(tǒng)中清除異物的抗體的數(shù)量。7.1.4 克隆選擇和擴(kuò)增基本思想：只有那些能夠識(shí)別抗原智能信息處理導(dǎo)論P(yáng)

5、PT第7章_免疫算法7.2 免疫優(yōu)化算法概述7.2.1 人工免疫系統(tǒng)的定義7.2.2 免疫算法的提出7.2.3 免疫算法中涉及的術(shù)語簡介7.2.4 免疫算法的算法思想7.2.5 免疫算法的收斂性7.2.6 免疫算法與免疫系統(tǒng)的對(duì)應(yīng)7.2.7 常見免疫算法7.2.8 免疫算子說明7.2 免疫優(yōu)化算法概述7.2.1 人工免疫系7.2.1 人工免疫系統(tǒng)的定義人工免疫系統(tǒng)的幾種定義：De Castro為人工免疫系統(tǒng)下的第一個(gè)定義認(rèn)為：“人工免疫系統(tǒng)是遵循可信的生物學(xué)范例人類免疫系統(tǒng)原理的數(shù)據(jù)處理、分類、表示和推理策略系統(tǒng)”。Timmis為人工免疫系統(tǒng)給出的第一個(gè)定義則認(rèn)為：“人工免疫系統(tǒng)是基于自然免疫

6、系統(tǒng)方法的計(jì)算系統(tǒng)”。Dasgupta給出的定義是：“人工免疫系統(tǒng)是由生物免疫系統(tǒng)啟發(fā)而來的智能策略所組成，主要用于信息處理和問題解決”。7.2.1 人工免疫系統(tǒng)的定義人工免疫系統(tǒng)的幾種定義：7.2.1 人工免疫系統(tǒng)的定義De Castro后來為人工免疫系統(tǒng)給出了第二個(gè)定義：“人工免疫系統(tǒng)是受生物免疫系統(tǒng)啟發(fā)而來的用于求解問題的適應(yīng)性系統(tǒng)”。Timmis后來也為人工免疫系統(tǒng)給出了第二個(gè)定義，即：“人工免疫系統(tǒng)是一種由理論生物學(xué)啟發(fā)而來的計(jì)算范式，借鑒了一些免疫系統(tǒng)的功能、原理和模型并用于復(fù)雜問題的解決”。莫宏偉給出的人工免疫系統(tǒng)的定義為：“人工免疫系統(tǒng)是基于免疫系統(tǒng)機(jī)制和理論免疫學(xué)而發(fā)展的各種

7、人工范例的特稱。7.2.1 人工免疫系統(tǒng)的定義De Castro后來為人7.2.3 免疫算法中涉及的術(shù)語簡介抗原：在生命科學(xué)中，是指能夠刺激和誘導(dǎo)機(jī)體的免疫系統(tǒng)使其產(chǎn)生免疫應(yīng)答，并能與相應(yīng)的免疫應(yīng)答產(chǎn)物在體內(nèi)或體外發(fā)生特異性反應(yīng)的物質(zhì)。在我們的算法中，是指所有可能錯(cuò)誤的基因，即非最佳個(gè)體的基因?？贵w：在生命科學(xué)中，是指免疫系統(tǒng)受抗原刺激后，免疫細(xì)胞轉(zhuǎn)化為漿細(xì)胞并產(chǎn)生能與抗原發(fā)生特異性結(jié)合的免疫球蛋白，該免疫球蛋白即為抗體。在本文中是指根據(jù)疫苗修正某個(gè)個(gè)體的基因所得到的新個(gè)體。7.2.3 免疫算法中涉及的術(shù)語簡介抗原：在生命科學(xué)中，7.2.3 免疫算法中涉及的術(shù)語簡介免疫疫苗：根據(jù)進(jìn)化環(huán)境或帶球

8、問題，所得到的對(duì)最佳個(gè)體基因的估計(jì)。免疫算子：全免疫和目標(biāo)免疫，全免疫是指群體中每個(gè)個(gè)體在變異操作后，對(duì)其每一環(huán)節(jié)都進(jìn)行一次免疫操作的免疫類型；目標(biāo)免疫則指?jìng)€(gè)體在進(jìn)行變異操作后，經(jīng)過一定判斷，個(gè)體僅在作用點(diǎn)處發(fā)生免疫反應(yīng)的一種類型。免疫調(diào)節(jié)：在免疫反應(yīng)過程中，大量的抗體的產(chǎn)生降低了抗原對(duì)免疫細(xì)胞的刺激，從而抑制抗體的分化和增殖，同時(shí)產(chǎn)生的抗體之間也存在著相互刺激和抑制的關(guān)系，這種抗原與抗體、抗體與抗體之間的相互制約關(guān)系使抗體免疫反應(yīng)維持一定的強(qiáng)度，保證機(jī)體的免疫平衡。7.2.3 免疫算法中涉及的術(shù)語簡介免疫疫苗：根據(jù)進(jìn)化環(huán)7.2.3 免疫算法中涉及的術(shù)語簡介免疫記憶：指免疫系統(tǒng)將能與抗原發(fā)生反

9、應(yīng)的抗體作為記憶細(xì)胞保存記憶下來，當(dāng)同類抗原再次侵入時(shí)，相應(yīng)的記憶細(xì)胞被激活而產(chǎn)生大量的抗體，縮短免疫反應(yīng)時(shí)間?？乖R(shí)別：通過表達(dá)在抗原表面的表位和抗體分子表面的對(duì)位的化學(xué)基進(jìn)行相互匹配選擇完成識(shí)別，這種匹配過程也是一個(gè)不斷對(duì)抗原學(xué)習(xí)的過程，最終能選擇產(chǎn)生最適當(dāng)?shù)目贵w與抗原結(jié)合而排除抗原。7.2.3 免疫算法中涉及的術(shù)語簡介免疫記憶：指免疫系統(tǒng)7.2.4 免疫算法的算法思想7.2.4 免疫算法的算法思想7.2.4 免疫算法的算法思想根據(jù)流程圖具體過程為：隨機(jī)產(chǎn)生初始父代種群A1；根據(jù)先驗(yàn)知識(shí)抽取疫苗； 若當(dāng)前群體中包含最佳個(gè)體,則算法停止運(yùn)行并輸出結(jié)果;否則繼續(xù)；對(duì)于目前的第k代父本種群Ak進(jìn)

10、行交叉操作，得到種群Bk； 對(duì)Bk進(jìn)行變異操作，得到種群Ck； 對(duì)Ck進(jìn)行接種疫苗操作，得到種群Dk；對(duì)Dk進(jìn)行免疫選擇操作，得到新一代父本Ak+1,轉(zhuǎn)至。7.2.4 免疫算法的算法思想根據(jù)流程圖具體過程為：7.2.5 免疫算法的收斂性算法的狀態(tài)轉(zhuǎn)移情況：X為搜索空間 n0的群體認(rèn)為是狀態(tài)空間S=Xn0中的一個(gè)點(diǎn) |S|表示S中狀態(tài)的數(shù)量 7.2.5 免疫算法的收斂性算法的狀態(tài)轉(zhuǎn)移情況：7.2.5 免疫算法的收斂性 7.2.5 免疫算法的收斂性7.2.6 免疫算法與免疫系統(tǒng)的對(duì)應(yīng)7.2.6 免疫算法與免疫系統(tǒng)的對(duì)應(yīng)7.2.7 常見免疫算法否定選擇算法具體步驟:定義一個(gè)自體字符串集合，例如，可以

11、是一個(gè)程序，數(shù)據(jù)文件（任何軟件）或一般的行為模式.隨機(jī)產(chǎn)生一個(gè)檢測(cè)器集合，其中每一個(gè)字符串都不能與集合中的字符串相匹配。該算法中的匹配不是完全匹配，而是部分匹配，只要有連續(xù)位相同就稱為匹配，此為一個(gè)可選擇的參數(shù)。通過與集的匹配不斷檢測(cè)的變化，一旦發(fā)生任何匹配，就說明集合發(fā)生了變化，即有外來元素的侵入。7.2.7 常見免疫算法否定選擇算法7.2.7 常見免疫算法肯定選擇算法具體步驟：初始化：產(chǎn)生一個(gè)細(xì)胞候選集合。假設(shè)所有的分子都用長度為l的二進(jìn)制串表示，則可能產(chǎn)生27個(gè)不同的細(xì)胞；親和力計(jì)算：通過集合，計(jì)算中所有元素與自體的親和力；可用集合的產(chǎn)生：如果中某個(gè)元素與中某個(gè)元素的親和力大于或等于一個(gè)

12、給定的閾值，即這個(gè)細(xì)胞能識(shí)別這個(gè)自體，則它肯定被系統(tǒng)選用，放入；否則刪除它。7.2.7 常見免疫算法肯定選擇算法7.2.7 常見免疫算法克隆選擇算法具體步驟：生成候選方案的一個(gè)集合（P）（初始群體），它由記憶細(xì)胞（M）的子集合加上剩余群體（Pr）（PPrM）；選擇n個(gè)具有較高親和力的個(gè)體；克隆這個(gè)最好的個(gè)體，組成一個(gè)臨時(shí)的克隆群體（C）。與抗原親和力越高，個(gè)體在克隆時(shí)的規(guī)模也就越大；把克隆群體提交到高頻變異，根據(jù)親和力的大小決定變異。產(chǎn)生一個(gè)成熟的抗體群體(*)；對(duì)*進(jìn)行再選擇，組成記憶細(xì)胞集合。中的一些成員可以被*中的其它一些改進(jìn)的成員替換掉；生成個(gè)新的抗體取代中個(gè)低親和力的抗體，保持多樣性

13、。7.2.7 常見免疫算法克隆選擇算法7.2.7 常見免疫算法克隆選擇算法在克隆選擇算法表現(xiàn)出的重要特征中，高頻變異(hypermutation)、受體編輯（receptor editing）是其重要的組成部分，它們是實(shí)現(xiàn)多樣性的基本保障。高頻變異機(jī)制的目的是為了使免疫應(yīng)答能夠快速地成熟。整數(shù)形態(tài)空間可以被看成是字母表大小縮小了的海明形態(tài)空間。7.2.7 常見免疫算法克隆選擇算法7.2.8 免疫算子說明多樣化抗體抑制和促進(jìn)抗體抗原編碼方式親和力結(jié)合強(qiáng)度7.2.8 免疫算子說明多樣化7.3 免疫算法與遺傳算法的比較7.3.1 兩者關(guān)系7.3.2 遺傳算法的原理及缺陷7.3.3 免疫算法的原理及優(yōu)

14、勢(shì)7.3 免疫算法與遺傳算法的比較7.3.1 兩者關(guān)系關(guān)聯(lián)：免疫算法也作為一種進(jìn)化算法，所用的遺傳結(jié)構(gòu)與遺傳算法所用的類似，采用重組、變異等算子操作解決抗體優(yōu)化等問題。區(qū)別：免疫算法起源于抗原和抗體之間的內(nèi)部競(jìng)爭，其相互作用的環(huán)境既包括外部也包括內(nèi)部的環(huán)境；而遺傳算法起源于個(gè)體和自私基因之間的外部競(jìng)爭；免疫算法假設(shè)免疫元素互相作用，即每一個(gè)免疫細(xì)胞等個(gè)體可以互相作用，而遺傳算法不考慮個(gè)體之間的作用；免疫算法中，基因可以由個(gè)體自己選擇，而在遺傳算法中基因由環(huán)境選擇；7.3.1 兩者關(guān)系關(guān)聯(lián)：免疫算法也作為一種進(jìn)化算法，所7.3.1 兩者關(guān)系區(qū)別：免疫算法中，基因組合是為了獲得多樣性，一般不用交叉

15、算子，因?yàn)槊庖咚惴ㄖ谢蚴窃谕淮鷤€(gè)體進(jìn)行進(jìn)化，這種情況下，設(shè)交叉（雜交）概率為；而遺傳算法后代個(gè)體基因通常是父代交叉的結(jié)果，交叉用于混合基因。免疫算法選擇和變異階段明顯不同，而遺傳算法中他們是交替進(jìn)行的。7.3.1 兩者關(guān)系區(qū)別：7.3.2 遺傳算法的原理及缺陷原理：利用遺傳算法解決最優(yōu)化問題，首先應(yīng)對(duì)可行域中的點(diǎn)進(jìn)行編碼，然后在可行域中隨機(jī)挑選一些編碼作為進(jìn)化起點(diǎn)的第一代編碼組，并計(jì)算每個(gè)解的目標(biāo)函數(shù)值。缺陷：早熟收斂、隨機(jī)漫游、控制參數(shù)的選擇等7.3.2 遺傳算法的原理及缺陷原理：利用遺傳算法解決最7.3.3 免疫算法的原理及優(yōu)勢(shì)核心思想：在合理提取疫苗的基礎(chǔ)上，通過接種疫苗和免疫選擇兩

16、個(gè)操作步驟來提高群體適應(yīng)度，加速迭代過程并防止群體的退化。優(yōu)勢(shì)：改進(jìn)的疫苗提取算法疫苗的自我識(shí)別分區(qū)域提取疫苗疫苗提取算法疫苗的構(gòu)造7.3.3 免疫算法的原理及優(yōu)勢(shì)核心思想：在合理提取疫苗7.3.3 免疫算法的原理及優(yōu)勢(shì)優(yōu)勢(shì)：改進(jìn)的注射疫苗算法隨機(jī)從疫苗庫中選取一個(gè)疫苗利用該疫苗所含位置信息，尋找疫苗注射的合理位置找到個(gè)體中與將要注射的疫苗相沖突部分，并將沖突部分刪除在找到的注射位注射疫苗7.3.3 免疫算法的原理及優(yōu)勢(shì)優(yōu)勢(shì)：改進(jìn)的免疫算法流程利用濃度概念計(jì)算記憶細(xì)胞和抑制細(xì)胞分化利用期望值計(jì)算抗體產(chǎn)生的促進(jìn)和抑制通過隨機(jī)決定基因產(chǎn)生新抗體，取代在前面被消除的抗體改進(jìn)的免疫算法流程7.4 免疫

17、優(yōu)化算法在VRP中的應(yīng)用7.4.1 裝卸一體化的物流配送VRP描述7.4.2 抗體編碼7.4.3 初始抗體的產(chǎn)生7.4.4 抗體親和力計(jì)算7.4.5 產(chǎn)生記憶/抑制細(xì)胞7.4.6 選擇、交叉、變異7.4 免疫優(yōu)化算法在VRP中的應(yīng)用7.4.1 裝卸一體化的物流配送VRP描述問題描述：有個(gè)結(jié)點(diǎn)需要提供裝貨或卸貨服務(wù)，表示為，可使用車輛數(shù)為（條物流配送路徑），每條路徑都有自己的裝貨點(diǎn)和送貨點(diǎn)。已知：要求在結(jié)點(diǎn)的裝貨量為 ，卸貨量為 。這些任務(wù)由車場(chǎng)發(fā)出的車輛來完成，假設(shè)車輛容量為 ，已知 、 1-2-6-39(0)；路徑2：9(0)-8-5-4-7-0。7.4.2 抗體編碼簡單直觀的自然數(shù)編碼（序

18、數(shù)編碼），用7.4.3 初始抗體的產(chǎn)生按照上述的編碼方式，隨機(jī)產(chǎn)生（先假設(shè)=10）個(gè)編碼長度為l的抗體，l=結(jié)點(diǎn)數(shù)車輛數(shù)-1=8+2-1=9。在第一次迭代時(shí)，抗體通常是在解空間中用隨機(jī)的方法產(chǎn)生的，以下為隨機(jī)產(chǎn)生的10個(gè)抗體：7.4.3 初始抗體的產(chǎn)生按照上述的編碼方式，隨機(jī)產(chǎn)生7.4.4 抗體親和力計(jì)算分別計(jì)算抗體v和抗原間的親和性axv。及抗體和抗體間的親和axv,w。 抗原與抗體之間的親和力axv，由于目標(biāo)函數(shù)為求最小值，因此親和力函數(shù)可以由目標(biāo)函數(shù)的變換得到目標(biāo)函數(shù)的倒數(shù)，即：7.4.4 抗體親和力計(jì)算分別計(jì)算抗體v和抗原間的親和7.4.4 抗體親和力計(jì)算將上述隨機(jī)產(chǎn)生的10個(gè)初始抗體

19、以Ab1，Ab10。分別計(jì)算親和力，按照親和力由大至小按降序排列：Ab2，Ab8 ，Ab9 ，Ab7，Ab3，Ab4，Ab1，Ab10，Ab6，Ab5。可見，在這10個(gè)初始抗體中，抗體Ab2與抗原之間的親和性最大（其親和力等于0。00139860），抗體Ab5與抗原之間的親和性最小（親和力等于0。00103093）。例如：以上述10個(gè)初始抗體為例來說明抗體與抗體之間的親和力計(jì)算。群體規(guī)模是10，抗體基因長度i=，符號(hào)集=，對(duì)于初始群體Ab1，Ab10。計(jì)算出第一個(gè)符號(hào)出現(xiàn)在基因座上的概率計(jì)算這10個(gè)初始抗體信息座j的信息熵j(10)計(jì)算出抗體Ab1，Ab2的平均信息熵H1,2(2)計(jì)算抗體Ab1，Ab2的相似度（親和力） 7.4.4 抗體親和力計(jì)算將上述隨機(jī)產(chǎn)生的10個(gè)初始抗7.4.6 選擇、交叉、變異這一步驟與通常應(yīng)用于車輛路徑優(yōu)化調(diào)度（VRP）的遺傳算法差別不大。對(duì)群體中的抗體按照各自的生存力進(jìn)行選擇，采用的是輪盤賭選擇的方式，按照一定的淘汰率淘汰一部分生存力低的抗體，用隨機(jī)產(chǎn)生的