人工智能第3章遺傳算法

人工智能ArtificialIntelligence(AI)2023/12/253.4遺傳算法生物群體的生存過程普遍遵照達爾文的物競天擇、適者生存的進化準那么；生物經過個體間的選擇、交叉、變異來順應大自然環(huán)境。2023/12/25遺傳算法是模擬生物遺傳學和自然選擇機理，經過人工方式構造的一類優(yōu)化搜索算法，是對生物進化過程的一個數(shù)學仿真，屬于進化計算中的一類方法。2023/12/25串碼：表示染色體或者個體順應度函數(shù)：表示一個染色體的順應才干，其最大值或者最小值就是最優(yōu)化問題的解2023/12/25一、遺傳算法的根本機理二、遺傳算法的求解步驟三、遺傳算法的收斂性〔略〕2023/12/25一、遺傳算法的根本機理1編碼與解碼2順應度函數(shù)3遺傳操作2023/12/251編碼與解碼在遺傳算法中，為了模擬遺傳學的遺傳規(guī)律，必需對問題的解的構造進展編碼，運轉遺傳算法后，再經過解碼得到問題的解。編碼解碼遺傳算法問題2023/12/25編碼：將問題解的構造轉換成位串方式編碼的過程解碼：將位串方式編碼轉化成問題的解的過程染色體〔個體〕：位串方式編碼2023/12/25編碼與解碼方法：二進制碼方法浮點數(shù)方法符號方法格雷碼方法2023/12/25二進制碼方法編碼方法：將參數(shù)的取值范圍分成等長的2l–1部分，再用l個二進制來編碼每一個等分，共有2l種不同的編碼。2023/12/25假設x[A,B],每一個部分的長度為l＝200A01A+δ10A+2δ11A+3δ=BAB2023/12/25解碼方法：假設某一個體的編碼為：X=xlxl-1…x2x1解碼公式為2023/12/25特點：編碼與解碼簡單碼串比較長搜索空間是有限的，提高解的精度，必需加大碼長求解多個參數(shù)時，將一切的碼拼接起來2023/12/25符號方法：個體編碼中的基因值只取代碼含義的符號集例：TSP問題，按照一個回路中城市的序號進展編碼相互之間不能一樣2023/12/252順應度函數(shù)順應度函數(shù)：度量染色體優(yōu)劣程度的函數(shù)，表達自然進化中的優(yōu)勝劣汰原那么。對于優(yōu)化問題，順應度函數(shù)就是目的函數(shù)。2023/12/25例：對于TSP問題，要求總途徑長度為最小，順應度函數(shù)可以定義為最小化最大化其中，wn+1=w1d(wj,wj+1)：兩個城市之間的間隔2023/12/253遺傳操作三種簡單的遺傳操作：選擇〔Selection〕交叉〔Crossover〕變異〔Mutation〕2023/12/25選擇操作〔復制操作〕：根據(jù)順應度函數(shù)值所度量的個體的優(yōu)劣程度決議此個體在下一代是被淘汰或是被遺。普通情況下，假設是求最大值，順應度函數(shù)值大的個體具有較大的生存時機。2023/12/25交叉操作：選出兩個個體作為父母個體，將兩種的部分碼值進展交換。例：100011101101101110001011110111102023/12/25變異操作：改動數(shù)碼串上的某一個位置的數(shù)碼。例10100110101101102023/12/25二、遺傳算法的求解步驟1遺傳算法的特點經過編碼使得解空間是有限的，一切遺傳算法是一種基于空間搜索的求解技術，經過自然選擇、交叉、變異等操作以及達爾文的適者生存的實際，模擬自然進化過程來尋覓問題的解。2023/12/25如今將遺傳算法看成為一種現(xiàn)代的優(yōu)化技術，但是不一定能找到問題的全局最優(yōu)解。經過一定的手段，可以將誤差控制在允許的范圍內〔以很大的概率找到全局最優(yōu)解〕。最優(yōu)解2023/12/25特點：對參數(shù)集合的編碼進展進化，不是參數(shù)本身進展進化從問題解的編碼組〔群體〕開場，不是從單個解開場搜索只利用順應度函數(shù)〔目的函數(shù)〕，不需求導數(shù)等信息只利用選擇、交叉、變異等操作，不需求利用確定性規(guī)那么進展隨機操作2023/12/252遺傳算法的框圖遺傳算法的根本思想：經過隨機方式產生假設干個個體，構成一個初始種群；利用順應度函數(shù)計算它們的順應度函數(shù)值，淘汰順應度小的個體，選擇順應度高的個體參與遺傳操作；經過遺傳操作后的個體構成下一代種群，再對新的種群進展新的一輪進化。2023/12/25根本思想簡單的遺傳算法根本的遺傳算法復雜的遺傳算法2023/12/25簡單遺傳算法的步驟：初始化種群計算種群中每一個個體的順應度函數(shù)值根據(jù)與順應度相關聯(lián)的規(guī)那么確定進入下一輪的個體2023/12/25按照某一個概率進展交叉操作按照某一個概率進展變異操作假設不滿足終止條件，那么轉到(2)，否那么繼續(xù)將種群中順應度最優(yōu)的個體作為問題的解2023/12/25開場初始化種群計算順應度值選擇操作交叉操作變異操作終止條件？選取順應度最優(yōu)個體作為解終了是2023/12/25算法可定義為一個8元組：C---個體的編碼方法；E---個體順應度評價函數(shù)；P0---初始群體；M---群體大??；Φ---選擇算子；Γ---交叉算子；---變異算子T---遺傳運算終止條件。2023/12/25例用遺傳算法求解優(yōu)化問題其中為整數(shù)。(1)確定初始種群經過隨機的方法來產生染色體的數(shù)字串，并組成初始種群。例如，為得到數(shù)字串的某位——又稱之為基因(genes)，運用計算機在0～1之間產生隨機數(shù)K，并按照數(shù)K的變化區(qū)域來規(guī)定基因代碼如下：

0，〔0≤K＜0.5〕1，〔0.5≤K≤1〕G=2023/12/25①參數(shù)編碼將整數(shù)x{0,1,…,31}作為參數(shù)，采用二進制進展編碼：X=0—>00000，……x=31—>11111②隨機生成例如:①01001；②11001；③01000；④10011。2023/12/25(2)選擇根據(jù)“適者生存〞的自然選擇原理,從初始種群中選擇生命力強的個體(適者)產生新的種群①確定順應度函數(shù)順應度函數(shù)取為非負函數(shù),且順應度增大的方向對應于目的函數(shù)的優(yōu)化方向本例取順應度函數(shù)fitness(X)=x2②計算順應度和選擇率將初始種群的個體解碼為X,并計算順應度f(X)及選擇率f/∑,其中∑為順應度之和.2023/12/25選擇順應值大的串作為母本，使在下一代中有更多的時機繁衍其子孫。要在四個種子個體中做選擇，要求依然得到四個染色體，可根據(jù)順應度概率比例制定如下規(guī)那么：低于0.125以下的染色體被淘汰；在0.125～0.375之間的染色體被復制一個；在0.375～0.625之間的染色體被復制兩個；在0.625～0.875之間的染色體被復制三個；在0.875以上的染色體可復制四個。2023/12/252023/12/25③隨機選擇適者個體采用輪盤法，對初始種群進展選擇，使得最優(yōu)秀的個體獲得最多的生存繁衍時機。49.2﹪30.9%14.4%5.5%011011100011000100112023/12/25(3)交叉將選擇出的個體存入交配池中，用隨機方法配對交叉，以產生新一代的個體①隨機選擇配對；②隨機選擇交叉點；③采用單點交叉，產生新的種群2023/12/25(4)變異在交叉過