【正文】 Q1： Q2： 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 58/79 遺傳算法 遺傳算法的基本原理 3. 遺傳操作 變異操作的簡(jiǎn)單方式是改變數(shù)碼串的某個(gè)位置上的數(shù)碼。 交叉：按概率 Pc進(jìn)行 變異：按概率 Pm進(jìn)行 終止條件： ① 完成了預(yù)先給定的進(jìn)化代數(shù) ② 種群中的最優(yōu)個(gè)體在連續(xù)若干代 沒(méi)有改進(jìn)或平均適應(yīng)度在連續(xù)若 干代基本沒(méi)有改進(jìn) 開(kāi)始 初始化種群 選擇操作 終止條件 否 適應(yīng)度最有優(yōu)個(gè)體 計(jì)算適應(yīng)度值 交叉操作 變異操作 結(jié)束 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 61/79 遺傳算法 遺傳算法的性能 遺傳算法求得的解是一滿(mǎn)意解。 例 : 設(shè)有函數(shù) f(x)=x2, 請(qǐng)用遺傳算法求其自變量 x在區(qū)間 [0，31] 取整數(shù)值時(shí)的最大值 ， 并說(shuō)明此函數(shù)的優(yōu)化問(wèn)題 。 要在四個(gè)種子個(gè)體中做選擇，要求仍然得到四個(gè)染色體，可依據(jù)適應(yīng)度概率比例制定如下規(guī)則： 低于 ； 在 ～ ； 在 ～ ； 在 ～ ； 在 。 遺傳算法 合肥工業(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)行交換而得。 特點(diǎn)：每經(jīng)一次進(jìn)化計(jì)算步驟 ,問(wèn)題解答便向著最優(yōu)方向前進(jìn)了一步 。 模擬退火算法：由初始解 i和控制參數(shù)初值 t開(kāi)始，對(duì)當(dāng)前解重復(fù)進(jìn)行“產(chǎn)生新解 → 計(jì)算目標(biāo)函數(shù)差 → 接受或舍棄”的迭代，并逐步衰減 t值，算法終止時(shí)的當(dāng)前解為所得近似最優(yōu)解。 自然免疫系統(tǒng)：一個(gè)復(fù)雜的自適應(yīng)系統(tǒng)，通過(guò)一套復(fù)雜的機(jī)制來(lái)重組基因，以產(chǎn)生相應(yīng)入侵抗原的抗體；同時(shí)還具有學(xué)習(xí)和記憶功能，可以區(qū)分自身細(xì)胞和抗原細(xì)胞，并最終消滅抗原細(xì)胞。 疫苗（ vanccine）：在免疫算法中疫苗指根據(jù)已有的先驗(yàn)知識(shí)得到的關(guān)于對(duì)最佳個(gè)體的一個(gè)估計(jì)值；在免疫學(xué)中，疫苗是一類(lèi)能引起免疫應(yīng)答反應(yīng)的生物制劑，通常為蛋白質(zhì)。 識(shí)別的有限性：一個(gè)免疫細(xì)胞（抗體）不一定能夠與所有的抗原匹配。 排斥力：描述兩個(gè)抗體之間的相異程度。通常是在解空間中隨機(jī)產(chǎn)生 n個(gè)候選解作為初始抗體， n為抗體群眾抗體的數(shù)目。通過(guò)免疫算子產(chǎn)生新的抗體，并計(jì)算新抗體的親和力及其之間的排斥力。若新抗體中有與抗原相匹配的抗體，或以滿(mǎn)足預(yù)定的停機(jī)條件則停機(jī)。在選擇時(shí)，給那些親和力大的抗體賦予較大的選擇概率。 （ 7）利用免疫算子產(chǎn)生新的抗體群。將與抗原親和力高的抗體加入到記憶單元中，并淘汰與其排斥力最高的原有抗體。分別計(jì)算每個(gè)抗體的親和力以及各抗體之間排斥力。輸入問(wèn)題的目標(biāo)函數(shù)和各種約束條件，作為免疫算法的抗原。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 78/79 免疫系統(tǒng)進(jìn)化的目標(biāo)：以最少的抗體數(shù)量覆蓋幾乎整個(gè)抗原空間。 免疫算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 77/79 免疫算法 當(dāng)病原體入侵時(shí)，免疫系統(tǒng)首先要識(shí)別這一抗原，然后產(chǎn)生相應(yīng)的抗體來(lái)消滅它。 免疫算法 合肥工業(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é)功能和生成不同抗體的功能。 模擬退火算法 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 75/79 生物機(jī)體系統(tǒng)：腦神經(jīng)系統(tǒng)、遺傳系統(tǒng)、自然免疫系統(tǒng)和內(nèi)分泌系統(tǒng)。 遺傳算法 合肥工業(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)能減為最小。 在上例中，種群的平均適應(yīng)值從 293增至 。對(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ī)兩兩匹配 ,稱(chēng)其為雙親染色體 ；②再把 雙親染色體 進(jìn)行交叉繁殖。例如，為得到數(shù)字串的某位 —— 又稱(chēng)之為基因 (genes)，使用計(jì)算機(jī)在 0～ 1之間產(chǎn)生隨機(jī)數(shù) K，并按照數(shù) K的變化區(qū)域來(lái)規(guī)定基因代碼如下： 0， （ 0≤K＜ ） 1， （ ≤K≤1） 遺傳算法 G = 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 64/79 于是 隨機(jī)生成 4個(gè) 染色體的數(shù)字符串為： 01101 11000 01000 10011 從而構(gòu)造了初始種群，完成了遺傳算法的準(zhǔn)備。 （ 1） 確定適當(dāng)?shù)木幋a方案：將 x編碼表示為染色體的數(shù)字符號(hào)串。 隨機(jī)產(chǎn)生一個(gè) 1~8之間的數(shù) k，假設(shè) k=5，對(duì)從右往左第 5位變異操作。 簡(jiǎn)單遺傳算法采用賭輪選擇機(jī)制，令 ∑fi表示群體的適應(yīng)度值之總和， fi表示種群中第 i個(gè)染色體的適應(yīng)度值，它產(chǎn)生后代的能力正好為其適應(yīng)度值所占份額 fi /∑fi。適應(yīng)度函數(shù)的取值大小與求解問(wèn)題對(duì)象的意義有很大的關(guān)系。它其實(shí)是 1， …… ， n的一個(gè)循環(huán)排列。把位串形式編碼表示叫染色體，有時(shí)也叫個(gè)體。現(xiàn)以此作為討論主要對(duì)象，加上適應(yīng)的改進(jìn)，來(lái)分析遺傳算法的結(jié)構(gòu)和機(jī)理。直到二十世紀(jì) 80年代中期 ,隨著計(jì)算機(jī)技術(shù)日新月異高速發(fā)展與進(jìn)步 ,遺傳算法首先成功地應(yīng)用于 AI機(jī)器學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)方面 。從此，進(jìn)化計(jì)算逐漸成為人們用來(lái)解決高度復(fù)雜問(wèn)題的新思路和新方法。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 49/79 遺傳算法 遺傳算法提出： 于 20世紀(jì) 60年代由密歇根 (Michigan)大學(xué)Hollstien, Bagleyh和 Rosenberg等人在其博士論文中首先加以研究； 1975年，美國(guó) “ Adaptation in Natural and Artificial Systems” 中系統(tǒng)地闡述了遺傳算法，給出了遺傳算法的基本定理和大量的數(shù)學(xué)理論證明。因此采用αβ剪枝技術(shù)通常都要使用某種深度優(yōu)先的搜索方法。 （ 2） MIN節(jié)點(diǎn)（包括起始節(jié)點(diǎn)）的 β值永不增加。這一過(guò)程稱(chēng)為 α剪枝。 存儲(chǔ)受限問(wèn)題：先生成一定深度的博弈樹(shù)，進(jìn)行極小極大分析，找出當(dāng)前的最好的行動(dòng)方案。此時(shí)估算出來(lái)的得分稱(chēng)為的靜態(tài)估值。其主要描述思想和算法： （ 1）設(shè)博弈的一方為 MAX方，其目標(biāo)是盡可能使自己得到最高分；另一方為 MIN方 , 其目標(biāo)是盡可能給 MAX方送出最低分。 如果自己一方擴(kuò)展的節(jié)點(diǎn)之間是“或”關(guān)系，則對(duì)方擴(kuò)展的節(jié)點(diǎn)之間是“與”關(guān)系。 假如 MAX方的目標(biāo)： 盡可能使自己達(dá)到最大（或最高）的分?jǐn)?shù)分枝節(jié)點(diǎn)， 可用 “或” 關(guān)系來(lái)描述，稱(chēng)之為 MAX方 節(jié)點(diǎn)； 而當(dāng)輪到 MIN方行動(dòng)時(shí)， MIN方的目標(biāo)： 盡可能使 MIN方獲得最?。ɑ蜃畹停┑姆?jǐn)?shù)分枝節(jié)點(diǎn)， 這對(duì) MIN方來(lái)說(shuō)，這些行動(dòng)方案或分?jǐn)?shù)分枝節(jié)點(diǎn)之間，可以用 “與” 關(guān)系來(lái)描述，是由MIN方 自主進(jìn)行控制的，故又稱(chēng)之為 MIN節(jié)點(diǎn)。 （ 2）全信息： 在對(duì)壘過(guò)程中，任何一方都了解當(dāng)前格局及過(guò)去的歷史。當(dāng) h=0時(shí)， A*算法就變?yōu)橛行蛩阉魉惴ā０?h叫做啟發(fā)函數(shù)。 對(duì)于 g(n)：一個(gè)明顯的選擇就是搜索樹(shù)中從 S到 n這段路徑的代價(jià)，這一代價(jià)可以由從 n到 S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來(lái)給出 (這條路徑就是到目前為止用搜索算法找到的從 S到 n的最小代價(jià)路徑 )。 h*(n)：表示整個(gè)目標(biāo)節(jié)點(diǎn)集合｛ ti｝上所有 k(n,ti)中最小的一個(gè)，因此， h*(n)就是從 n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)，而且從 n到目標(biāo)節(jié)點(diǎn)能夠獲得 h*(n)的任一路徑就是一條從 n到某個(gè)目標(biāo)節(jié)點(diǎn)的最佳路徑 (對(duì)于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn) n，函數(shù) h*沒(méi)有定