【正文】 總計(jì) ∑ （ 初始種群值 ） 1170 % 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 66/79 （ 3）復(fù)制 (選擇 ): 選擇適應(yīng)值大的串作為母本，使在下一代中有更多的機(jī)會(huì)繁殖其子孫。 要在四個(gè)種子個(gè)體中做選擇，要求仍然得到四個(gè)染色體，可依據(jù)適應(yīng)度概率比例制定如下規(guī)則： 低于 ； 在 ～ ； 在 ～ ； 在 ～ ； 在 。 遺傳算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 67/79 對(duì)應(yīng)于上例，按照適應(yīng)度的計(jì)算，經(jīng)復(fù)制操作后，得到新的染色體種群為 01101 11000 11000 10011 遺傳算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 68/79 某個(gè)染色體是否被復(fù)制 ,可以通過(guò)概率決策法、適應(yīng)度比例法或“輪盤(pán)賭”的隨機(jī)方法來(lái)斷定。對(duì)應(yīng)輪盤(pán)賭轉(zhuǎn)盤(pán)的隨機(jī)方法 ,根據(jù)表 ，繪制出的輪盤(pán)賭轉(zhuǎn)盤(pán) ,如圖所示 : 進(jìn)化計(jì)算 —— 基本 遺傳算法原理 ﹪ % % % ? 01101 ? 11000 ? 11000 ? 10011 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 69/79 遺傳算法 初始種群 x 值 適應(yīng)度 選擇概率 期望值 實(shí)際復(fù)制數(shù) 編號(hào) （ 隨機(jī)產(chǎn)生 ） （ 無(wú)符號(hào)整數(shù) ） f (x) = x2 Pc f(xi)/fA （ 或轉(zhuǎn)輪法 ） 1 01101 13 169 1 2 11000 24 576 2 3 01000 8 64 0 4 10011 19 361 1 ∑ 1170 平均 (A) 293 MAX 576 初始種群染色體準(zhǔn)備復(fù)制操作的各項(xiàng)計(jì)算數(shù)據(jù) 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 70/79 （ 4） 交叉 : 交叉具體分兩步：①將新復(fù)制產(chǎn)生的 染色體 隨機(jī)兩兩匹配 ,稱其為雙親染色體 ；②再把 雙親染色體 進(jìn)行交叉繁殖。 交叉的實(shí)現(xiàn) : 設(shè)染色體數(shù)字串長(zhǎng)度為 L，把 L個(gè)數(shù)字位間空隙分別標(biāo)記為： 1， 2， ? ， L－ 1 隨機(jī)從 [1， L－ 1]中選取某一整數(shù)位置 k， 0kL 交換雙親染色體交換點(diǎn)位置 k右邊的部分，就形成了兩個(gè)新的數(shù)字符串（也可以只交換其中的第 k基因），得到了兩個(gè)新的染色體，又稱之為下一代染色體。 遺傳算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 71/79 例如，將上例初始種群的兩個(gè)體 A1=01┇ 10┇ 1 A2=11┇ 00┇ 0 假定從 1到 4間選取兩個(gè)隨機(jī)數(shù) ， 得到 к1=2， к2=4， 那么經(jīng)過(guò)交叉操作之后將得到如下兩組新的數(shù)字符串 A1=01000 A2=11101 遺傳算法 ?A3=01100 ?A4=11001 ?前一組數(shù)字串是使用 к1=2,即將第 2位后的 3～ 5位交換得到； ?后一組數(shù)字串是使用 к2=4，即僅將第 5位 因子 進(jìn)行交換而得。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 72/79 遺傳算法 編號(hào) 復(fù)制操作后的區(qū)配池 匹配號(hào) (隨機(jī)選取 ) 交叉空隙位 ( 隨機(jī)選取 ) 交叉后新種群 新種群x值 適應(yīng)度 f(x) = x2 1 01101 2 2 01000 8 64 2 11000 1 2 11101 29 841 3 11000 4 4 11001 25 625 4 10011 3 4 10000 16 256 總計(jì) （ ∑ ） 1786 平均 (A) 最大值 (MAX) 841 復(fù)制、交叉操作的各項(xiàng)數(shù)據(jù) 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 73/79 （ 5）變異 : 設(shè)變異概率取為 ,則對(duì)于種群總共有 20個(gè)基因位 . 期望的變異串位數(shù)計(jì)算 :20 =(位 ), 故一般來(lái)說(shuō) ,該例中無(wú)基因位數(shù)值的改變 .從表 112和 113可以看出 ,每經(jīng)過(guò)一次復(fù)制、交叉和變異操作后 ,目標(biāo)函數(shù)的最優(yōu)值和平均值就會(huì)有所提高。 在上例中，種群的平均適應(yīng)值從 293增至 。最大的適應(yīng)度數(shù)值從 576增至 841。 特點(diǎn)：每經(jīng)一次進(jìn)化計(jì)算步驟 ,問(wèn)題解答便向著最優(yōu)方向前進(jìn)了一步 。若該過(guò)程一直進(jìn)行下去 ,就將最終走向全局的最優(yōu)解 .可見(jiàn)進(jìn)化計(jì)算的每一步操作簡(jiǎn)單 ,并且系統(tǒng)的求解過(guò)程是依照計(jì)算方法與規(guī)律來(lái)決定 ,與本源問(wèn)題自身的特性很少相關(guān)。 遺傳算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 74/79 固體退火原理：固體內(nèi)部粒子隨著溫度升高而變?yōu)闊o(wú)序，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。 Metropolis準(zhǔn)則： 粒子在溫度 T時(shí)趨于平衡的概率 =e△ E/(kT) 其中， E為固體在溫度 T時(shí)的內(nèi)能， △ E為內(nèi)能的改變量， k為波爾茲曼（ Boltzmann）常數(shù)。 模擬退火算法：由初始解 i和控制參數(shù)初值 t開(kāi)始，對(duì)當(dāng)前解重復(fù)進(jìn)行“產(chǎn)生新解 → 計(jì)算目標(biāo)函數(shù)差 → 接受或舍棄”的迭代，并逐步衰減 t值，算法終止時(shí)的當(dāng)前解為所得近似最優(yōu)解。退火過(guò)程由冷卻進(jìn)度表控制，包括控制參數(shù)的初值 t及其衰減因子 △ t、每個(gè) t值時(shí)的迭代次數(shù) L和停止條件 S。 模擬退火算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 75/79 生物機(jī)體系統(tǒng)：腦神經(jīng)系統(tǒng)、遺傳系統(tǒng)、自然免疫系統(tǒng)和內(nèi)分泌系統(tǒng)。 免疫計(jì)算：模仿自然免疫系統(tǒng)而產(chǎn)生的一種新的計(jì)算理論和方法。 自然免疫系統(tǒng)：一個(gè)復(fù)雜的自適應(yīng)系統(tǒng)，通過(guò)一套復(fù)雜的機(jī)制來(lái)重組基因，以產(chǎn)生相應(yīng)入侵抗原的抗體；同時(shí)還具有學(xué)習(xí)和記憶功能，可以區(qū)分自身細(xì)胞和抗原細(xì)胞，并最終消滅抗原細(xì)胞。 人工免疫系統(tǒng)的研究： 20世紀(jì) 90年代，解決網(wǎng)絡(luò)適應(yīng)性問(wèn)題、傳感器網(wǎng)絡(luò)故障診斷、病毒檢測(cè)、機(jī)器學(xué)習(xí)。 免疫算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 76/79 免疫算法（ immunealgorithm）：在模仿生物免疫機(jī)制的基礎(chǔ)上，綜合基因進(jìn)化機(jī)理，人工地構(gòu)造的一類(lèi)優(yōu)化算法，它實(shí)現(xiàn)了類(lèi)似于免疫系統(tǒng)自我調(diào)節(jié)功能和生成不同抗體的功能。 抗原（ antigen）：在免疫算法中抗原指非最佳個(gè)體的基因，或者可能錯(cuò)誤地基因；在免疫學(xué)中，抗原指有一種能夠刺激機(jī)體產(chǎn)生相應(yīng)抗體的物質(zhì)。 疫苗（ vanccine）：在免疫算法中疫苗指根據(jù)已有的先驗(yàn)知識(shí)得到的關(guān)于對(duì)最佳個(gè)體的一個(gè)估計(jì)值；在免疫學(xué)中，疫苗是一類(lèi)能引起免疫應(yīng)答反應(yīng)的生物制劑，通常為蛋白質(zhì)。 抗體（ antibody）：在免疫算法中抗體是指根據(jù)疫苗修正某個(gè)個(gè)體基因所得到的新個(gè)體（新基因）；在免疫學(xué)中，抗體是一種具有免疫功能的球蛋白，是人體抵抗力最重要的組成部分。 免疫算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 77/79 免疫算法 當(dāng)病原體入侵時(shí)，免疫系統(tǒng)首先要識(shí)別這一抗原，然后產(chǎn)生相應(yīng)的抗體來(lái)消滅它。識(shí)別的過(guò)程實(shí)際上就是免疫細(xì)胞與抗原匹配并結(jié)合的過(guò)程，如果一個(gè)系統(tǒng)中所有抗原都被抗體識(shí)別（隨后被消滅）了，那么這個(gè)系統(tǒng)就達(dá)到了最佳狀態(tài)。 識(shí)別的有限性：一個(gè)免疫細(xì)胞（抗體）不一定能夠與所有的抗原匹配。 識(shí)別的多樣性：一個(gè)免疫細(xì)胞可以識(shí)別多種不同的抗原。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 78/79 免疫系統(tǒng)進(jìn)化的目標(biāo)：以最少的抗體數(shù)量覆蓋幾乎整個(gè)抗原空間。 親和力：描述抗體和抗原之間的匹配程度（覆蓋能力）。 排斥力：描述兩個(gè)抗體之間的相異程度。 算法步驟： （ 1）識(shí)別抗原。輸入問(wèn)題的目標(biāo)函數(shù)和各種約束條件，作為免疫算法的抗原。 （ 2）產(chǎn)生初始抗體群。通常是在解空間中隨機(jī)產(chǎn)生 n個(gè)候選解作為初始抗體， n為抗體群眾抗體的數(shù)目。 （ 3）計(jì)算親和力和排斥力。分別計(jì)算每個(gè)抗體的親和力以及各抗體之間排斥力。 免疫算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 79/79 （ 4）產(chǎn)生新的抗體。通過(guò)免疫算子產(chǎn)生新的抗體，并計(jì)算新抗體的親和力及其之間的排斥力。 （ 5）更新記憶能力。將與抗原親和力高的抗體加入到記憶單元中，并淘汰與其排斥力最高的原有抗體。 （ 6）判斷是否滿足停止條件。若新抗體中有與抗原相匹配的抗體，或以滿足預(yù)定的停機(jī)條件則停機(jī)。否則轉(zhuǎn)（ 7）。 （ 7）利用免疫算子產(chǎn)生新的抗體群。免疫算子包括選擇、交叉和變異等操作。在選擇時(shí)，給那些親和力大的抗體賦予較大的選擇概率。 （ 8）轉(zhuǎn)（ 3） 免疫算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 80/79 演講完畢，謝謝觀看！