人工免疫算法培訓(xùn)課件

1、人工免疫算法人工免疫算法主要內(nèi)容 研究背景與現(xiàn)狀； 免疫進(jìn)化算法； 免疫神經(jīng)網(wǎng)絡(luò)；2人工免疫算法主要內(nèi)容 研究背景與現(xiàn)狀；2人工免疫算法研究背景在生物科學(xué)領(lǐng)域，人們對(duì)進(jìn)化、遺傳和免疫等自然 現(xiàn)象已經(jīng)進(jìn)行了廣泛而深入的研究 ；進(jìn)化算法是建立在模仿生物遺傳與自然選擇基礎(chǔ)上的一種并行優(yōu)化算法，其性能優(yōu)異、應(yīng)用廣泛；進(jìn)化算子在為每個(gè)個(gè)體提供了進(jìn)化機(jī)會(huì)的同時(shí)，也無(wú)可避免地產(chǎn)生了退化的可能；大多數(shù)待求問(wèn)題有可以利用的先驗(yàn)知識(shí)或特征信息，故可以利用這些信息來(lái)抑制進(jìn)化過(guò)程中的退化現(xiàn)象；生物免疫理論為改進(jìn)原有算法的性能，建立集進(jìn)化與免疫機(jī)制于一體的新型全局并行算法奠定了基礎(chǔ)。3人工免疫算法研究背景在生物科學(xué)領(lǐng)域

2、，人們對(duì)進(jìn)化、遺傳和免疫等自然 現(xiàn)象已Artificial Immune SystemAIS人工智能信息處理系統(tǒng)的研究腦神經(jīng)系統(tǒng)（神經(jīng)網(wǎng)絡(luò)）；遺傳系統(tǒng)（進(jìn)化計(jì)算）；免疫系統(tǒng)（人工免疫系統(tǒng)）。4人工免疫算法Artificial Immune SystemAIS人工一門(mén)新興的研究領(lǐng)域。AIS的研究歷史Farmer等人在1986年首先在工程領(lǐng)域提出免疫概念；Varela等人受免疫網(wǎng)絡(luò)學(xué)說(shuō)的啟發(fā)，提出并進(jìn)而完善免疫網(wǎng)絡(luò)模型。5人工免疫算法一門(mén)新興的研究領(lǐng)域。AIS的研究歷史Farmer等人在1人工免疫網(wǎng)絡(luò)模型AIS的研究現(xiàn)狀之一獨(dú)特型免疫網(wǎng)絡(luò)（Jerne）；互聯(lián)耦合免疫網(wǎng)絡(luò)（Ishiguro）；免疫反

3、應(yīng)網(wǎng)絡(luò)（Mitsumoto）；對(duì)稱網(wǎng)絡(luò)（Hoffmann）；多值免疫網(wǎng)絡(luò)（Tang）.6人工免疫算法人工免疫網(wǎng)絡(luò)模型AIS的研究現(xiàn)狀之一獨(dú)特型免疫網(wǎng)絡(luò)（Je 免疫學(xué)習(xí)算法AIS的研究現(xiàn)狀之二反面選擇算法（Forrest）；免疫學(xué)習(xí)算法（Hunt&Cooke）；免疫遺傳算法（Chun）；免疫Agent算法（Ishida）；免疫網(wǎng)絡(luò)調(diào)節(jié)算法（Wang&Cao）；免疫進(jìn)化算法（Jiao&Wang）.7人工免疫算法 免疫學(xué)習(xí)算法AIS的研究現(xiàn)狀之二反面選擇算法（Forr 國(guó)際研究AIS的研究現(xiàn)狀之三1996年，日本，基于免疫性系統(tǒng)的國(guó)際專(zhuān)題討論會(huì)，提出并確認(rèn)人工免疫系統(tǒng)（AIS）的概念；1997年，I

4、EEE的SMC組織專(zhuān)門(mén)成立了人工免疫系統(tǒng)及應(yīng)用的分會(huì)組織；目前，幾乎所有有關(guān)人工智能領(lǐng)域的學(xué)術(shù)會(huì)議都收錄AIS方面的論文。8人工免疫算法 國(guó)際研究AIS的研究現(xiàn)狀之三1996年，日本，基于免疫免疫進(jìn)化算法的研究9人工免疫算法免疫進(jìn)化算法的研究9人工免疫算法生物免疫的啟示在生物自然界中，免疫現(xiàn)象普遍存在，并對(duì)物種的 生存與繁衍 發(fā)揮著重要的作用；生物的免疫功能主要是由參與免疫反應(yīng)的細(xì)胞或由其構(gòu)成的器官來(lái)完成的；生物免疫主要有兩種類(lèi)型： 特異性免疫（Specific Immunity）， 非特異性免疫反應(yīng)（Nonspecific Immunity）；生物免疫系統(tǒng)是通過(guò)自我識(shí)別、相互刺激與制約而構(gòu)成

5、了一個(gè) 動(dòng)態(tài)平衡的網(wǎng)絡(luò)結(jié)構(gòu) 。 10人工免疫算法生物免疫的啟示在生物自然界中，免疫現(xiàn)象普遍存在，并對(duì)物種的 免疫生物學(xué)的基本概念 抗原是指能夠刺激和誘導(dǎo)機(jī)體的免疫系統(tǒng)使其產(chǎn)生免疫應(yīng)答，并能與相應(yīng)的免疫應(yīng)答產(chǎn)物在體內(nèi)或體外發(fā)生特異性反應(yīng)的物質(zhì)。 抗體是指免疫系統(tǒng)受抗原刺激后，免疫細(xì)胞轉(zhuǎn)化為漿細(xì)胞并產(chǎn)生能與抗原發(fā)生特異性結(jié)合的免疫球蛋白，該免疫球蛋白即為抗體。11人工免疫算法免疫生物學(xué)的基本概念 抗原11人工免疫算法免疫系統(tǒng)的主要功能 免疫防御即機(jī)體防御病原微生物的感染； 免疫（自身）穩(wěn)定即機(jī)體通過(guò)免疫功能經(jīng)常消除那些損傷和衰老的細(xì)胞以維持機(jī)體的生理平衡； 免疫監(jiān)視即機(jī)體通過(guò)免疫功能防止或消除體內(nèi)

6、細(xì)胞在新陳代謝過(guò)程中發(fā)生突變的和異常的細(xì)胞。12人工免疫算法免疫系統(tǒng)的主要功能 免疫防御12人工免疫算法免疫系統(tǒng)的主要特點(diǎn)免疫識(shí)別免疫應(yīng)答免疫耐受免疫記憶免疫調(diào)節(jié)13人工免疫算法免疫系統(tǒng)的主要特點(diǎn)免疫識(shí)別13人工免疫算法算法研究生物學(xué)概念與理論方法：工程計(jì)算方法14人工免疫算法算法研究生物學(xué)概念與理論方法：工程計(jì)算方法14人工免疫算法進(jìn)化免疫傳統(tǒng)進(jìn)化算法是在一定發(fā)生概率的條件下，隨機(jī)地、沒(méi)有指導(dǎo)地迭代搜索，因此它們?cè)跒槿后w中的個(gè)體提供了進(jìn)化機(jī)會(huì)的同時(shí)，也無(wú)可避免地產(chǎn)生了退化的可能。 每一個(gè)待求的實(shí)際問(wèn)題都會(huì)有自身一些基本的、顯而易見(jiàn)的特征信息或知識(shí)。然而進(jìn)化算法中的交叉和變異算子在求解問(wèn)題時(shí)，

7、操作的可變程度較小。15人工免疫算法進(jìn)化免疫傳統(tǒng)進(jìn)化算法是在一定發(fā)生概率的條件下，隨機(jī)地、基本概念染色體表示待求問(wèn)題的解的形式的一種數(shù)據(jù)結(jié)構(gòu)?；驑?gòu)成染色體的最基本的數(shù)據(jù)單位。個(gè)體具有某類(lèi)染色體結(jié)構(gòu)的一種特例。16人工免疫算法基本概念染色體16人工免疫算法基本概念抗原 所有可能錯(cuò)誤的基因，即非最佳個(gè)體的基因。疫苗根據(jù)進(jìn)化環(huán)境或待求問(wèn)題的先驗(yàn)知識(shí)，所得到的對(duì)最佳個(gè)體基因的估計(jì)。抗體根據(jù)疫苗修正某個(gè)個(gè)體的基因所得到的新個(gè)體。17人工免疫算法基本概念抗原17人工免疫算法免疫算子有兩種類(lèi)型：全免疫 非特異性免疫目標(biāo)免疫 特異性免疫免疫思想的實(shí)現(xiàn) 免疫算子即：群體中的每個(gè)個(gè)體在進(jìn)化算子作用后，對(duì)其每一環(huán)

8、節(jié)都進(jìn)行一次免疫操作的免疫類(lèi)型；即：在進(jìn)行了進(jìn)化操作后，經(jīng)過(guò)一定的判斷，個(gè)體僅在作用點(diǎn)處發(fā)生免疫反應(yīng)的一種類(lèi)型。18人工免疫算法免疫算子有兩種類(lèi)型：免疫思想的實(shí)現(xiàn) 免疫算子即：群體中的每免疫操作的基本過(guò)程首先，對(duì)待求求問(wèn)題進(jìn)行具體分析，從中提取出 最基本的特征信息； 其次，對(duì)此特征信息進(jìn)行處理，以將其轉(zhuǎn)化為求解問(wèn)題的一種方案；最后，將此方案以適當(dāng)?shù)男问睫D(zhuǎn)化成 免疫算子 以實(shí)施具體的操作。19人工免疫算法免疫操作的基本過(guò)程首先，對(duì)待求求問(wèn)題進(jìn)行具體分析，從中提免疫算子 算法中的免疫思想主要是在合理提取疫苗的基礎(chǔ)上，通過(guò)免疫算子來(lái)實(shí)現(xiàn)的；免疫算子由 接種疫苗 和 免疫選擇 兩個(gè)操作完成的。The

9、Immune operator為了防止群體的退化。為了提高個(gè)體的適應(yīng)度。20人工免疫算法免疫算子 算法中的免疫思想主要是在合理提取疫苗的基礎(chǔ)上，設(shè)個(gè)體x，給其接種疫苗是指按照先驗(yàn)知識(shí)來(lái)修改x的某些基因位上的基因或其分量，使所得個(gè)體以較大的概率具有更高的適應(yīng)度。疫苗 是從先驗(yàn)知識(shí)中提煉出來(lái)的，它所含的信息量及其準(zhǔn)確性對(duì)算法性能的發(fā)揮起著重要的作用。免疫算子接種疫苗之21人工免疫算法設(shè)個(gè)體x，給其接種疫苗是指按照先驗(yàn)知識(shí)來(lái)修改x的某些基因位上這一操作一般分兩步完成：第一步是 免疫檢測(cè) ，即對(duì)接種了疫苗的個(gè)體進(jìn)行檢測(cè)，若其適應(yīng)度仍不如父代，則該個(gè)體將被父代中所對(duì)應(yīng)的個(gè)體所取代；第二步是 退火選擇 ，

10、即在目前的子代群體中以右邊所示概率免疫算子免疫檢測(cè)之選擇個(gè)體進(jìn)入新的父代群體。在免疫策略中，僅有免疫檢測(cè)而沒(méi)有退火選擇。22人工免疫算法這一操作一般分兩步完成：第一步是 免疫檢測(cè) ，即對(duì)接種了疫苗體系結(jié)構(gòu)免疫算法免疫規(guī)劃免疫策略 23人工免疫算法體系結(jié)構(gòu)免疫算法23人工免疫算法免疫算法隨機(jī)產(chǎn)生初始父代種群A1 ，根據(jù)先驗(yàn)知識(shí)抽取疫苗；若當(dāng)前群體中包含最佳個(gè)體，則算法停止運(yùn)行并輸出結(jié)果；否則，繼續(xù)；對(duì)當(dāng)前第k代父本種群Ak進(jìn)行交叉操作，得到種群Bk；對(duì)Bk進(jìn)行變異操作，得到種群Ck；對(duì)Ck進(jìn)行接種疫苗操作，得到種群Dk；對(duì)Dk進(jìn)行免疫選擇操作，得到新一代父本Ak+1，轉(zhuǎn)至第二步。Immune A

11、lgorithm-IA24人工免疫算法免疫算法隨機(jī)產(chǎn)生初始父代種群A1 ，根據(jù)先驗(yàn)知識(shí)抽取疫苗；I免疫算法的收斂性狀態(tài)轉(zhuǎn)移過(guò)程示意圖：定 理：免疫算法是收斂的。定 義：如果對(duì)于任意的初始分布均有則稱算法收斂。25人工免疫算法免疫算法的收斂性狀態(tài)轉(zhuǎn)移過(guò)程示意圖：定 理：免疫算法是收人工免疫算法培訓(xùn)課件免疫規(guī)劃的收斂性狀態(tài)轉(zhuǎn)移過(guò)程示意圖：定 理：免疫規(guī)劃是收斂的。定 義：如果對(duì)于任意的初始分布均有則稱算法收斂。27人工免疫算法免疫規(guī)劃的收斂性狀態(tài)轉(zhuǎn)移過(guò)程示意圖：定 理：免疫規(guī)劃是收免疫策略根據(jù)要求確定解的精度，再根據(jù)先驗(yàn)知識(shí)抽取疫苗H；隨機(jī)產(chǎn)生個(gè)個(gè)體作為初始的父本群體；交叉：產(chǎn)生由父代和子代構(gòu)成的

12、規(guī)模為2的中間群體；變異：對(duì)每一個(gè)個(gè)體進(jìn)行變異將得到一個(gè)新的個(gè)體；免疫：首先按照對(duì)問(wèn)題的先驗(yàn)知識(shí)修改個(gè)體(x,)的某些分量；然后對(duì)群體中注射了疫苗的個(gè)體進(jìn)行檢測(cè)；選擇：從規(guī)模為2的群體中按適應(yīng)度的大小取出前個(gè)個(gè)體作為新一代父本的群體；停機(jī)條件檢測(cè)。Immune Strategy-IS28人工免疫算法免疫策略根據(jù)要求確定解的精度，再根據(jù)先驗(yàn)知識(shí)抽取疫苗H；Im免疫策略的收斂性狀態(tài)轉(zhuǎn)移過(guò)程示意圖：定 理：免疫策略是收斂的。定 義：如果對(duì)于任意的初始分布均有則稱算法收斂。29人工免疫算法免疫策略的收斂性狀態(tài)轉(zhuǎn)移過(guò)程示意圖：定 理：免疫策略是收免疫算子的機(jī)理在免疫選擇作用下，若疫苗使抗體適應(yīng)度得到提高

13、，且高于當(dāng)前群體的平均適應(yīng)度，則疫苗所對(duì)應(yīng)的模式將在群體中呈指數(shù)級(jí)擴(kuò)散；否則，它將被遏制或呈指數(shù)級(jí)衰減。定 理：30人工免疫算法免疫算子的機(jī)理在免疫選擇作用下，若疫苗使抗體適應(yīng)度得到提高，Begin:抽取疫苗： 分析待求問(wèn)題，搜集特征信息； 依據(jù)特征信息估計(jì)特定基因位上的模式: ；k = 0 and j = 0；while (Conditions = True) if PV=True, then j = j +1； i = 0； for (in) 接種疫苗： ； 免疫檢驗(yàn)：if , then ; else ； i = i +1； 退火選擇： ； k = k+1；End免疫算子的執(zhí)行算法31人工

14、免疫算法Begin:免疫算子的執(zhí)行算法31人工免疫算法具體分析待求問(wèn)題，搜集特征信息。免疫疫苗的選取方法通用方法之一以TSP問(wèn)題為例，通過(guò)具體分析可以得出相鄰兩兩城市之間的最短路徑即為求解該問(wèn)題時(shí)可以利用的一種疫苗。32人工免疫算法具體分析待求問(wèn)題，搜集特征信息。免疫疫苗的選取方法通用方法之TSP問(wèn)題的描述TSP問(wèn)題是旅行商問(wèn)題的簡(jiǎn)稱。即一個(gè)商人從某一城市出發(fā)，要遍歷所有目標(biāo)城市，其中每個(gè)城市必須而且只須訪問(wèn)一次。所要研究的問(wèn)題是在所有可能的路徑中尋找一條路程最短的路線。該問(wèn)題是一個(gè)典型的NP問(wèn)題，即隨著規(guī)模的增加，可行解的數(shù)目將做指數(shù)級(jí)增長(zhǎng)。33人工免疫算法TSP問(wèn)題的描述TSP問(wèn)題是旅行商

15、問(wèn)題的簡(jiǎn)稱。即一個(gè)商人從某TSP問(wèn)題的分析設(shè)所有與城市Ai距離最近的城市為Aj,進(jìn)行一次如虛線所示的調(diào)整后,多數(shù)情況下， l3較aj-1 + aj的減少量要大于l1 + l2較ai的增加量。故：34人工免疫算法TSP問(wèn)題的分析設(shè)所有與城市Ai距離最近的城市為Aj,進(jìn)行一Begin:while (Conditions = True) 統(tǒng)計(jì)父代群體，確定最佳個(gè)體：; 分解最佳個(gè)體，抽取免疫基因：; 執(zhí)行遺傳和免疫算子操作;end免疫疫苗的選取方法自適應(yīng)方法之二35人工免疫算法Begin:免疫疫苗的選取方法自適應(yīng)方法之二35人工免疫算法Begin:鄰近城市序列初始化：Neighbor(i) = ra

16、ndom(1, n) , i =1, , n;最短子路徑的初始化：Sub_path(i) i =1, n;while (Conditions = True) for i = 1 to n 變異： Neighbor(i) = Floor(Gauss(Neighbor(i), 1 ) ) ; 選擇：if Distance(City_ i, Neighbor(i) Min_distance(i) then Sub_path(i) = Neighbor(i); Min_distance(i) = Distance(City_ i, Neighbor(i); end endend免疫疫苗的選取方法進(jìn)化規(guī)

17、劃方法之三36人工免疫算法Begin:免疫疫苗的選取方法進(jìn)化規(guī)劃方法之三36人工免疫算仿真實(shí)驗(yàn)基于IA的TSP求解之一a. 免疫抗體b. 最優(yōu)化路徑75城市的TSP問(wèn)題免疫優(yōu)化仿真示意圖37人工免疫算法仿真實(shí)驗(yàn)基于IA的TSP求解之一a. 免疫抗體b. 子代適應(yīng)度值隨進(jìn)化過(guò)程的變化曲線a 通用遺傳算法計(jì)算曲線b 免疫算法計(jì)算曲線38人工免疫算法子代適應(yīng)度值隨進(jìn)化過(guò)程的變化曲線a 通用遺傳算法計(jì)算曲線仿真實(shí)驗(yàn)基于IS的TSP求解之二a. 免疫疫苗示意圖 b. 最優(yōu)路徑示意圖442城市的TSP問(wèn)題免疫優(yōu)化仿真示意圖39人工免疫算法仿真實(shí)驗(yàn)基于IS的TSP求解之二a. 免疫疫苗示意圖 子代適應(yīng)度值隨進(jìn)化過(guò)程的變化曲線a (,2 )-ES計(jì)算曲線 b ( ,2 )-IS 計(jì)算曲線40人工免疫算法子代適應(yīng)度值隨進(jìn)化過(guò)程的變化曲線a (,2 )-ES計(jì)仿真實(shí)驗(yàn)基于IE的函數(shù)優(yōu)化之三問(wèn)題: 在(0,1)內(nèi)尋找 xmax使下式成立:41人工免疫算法仿真實(shí)驗(yàn)基于IE的函