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