人工智能ArtificialIntelligence(AI)許建華xujianhua@南京師范大學計算機科學系2006年9-12月2023/2/54.5遺傳算法生物群體的生存過程普遍遵循達爾文的物競天擇、適者生存的進化準則；生物通過個體間的選擇、交叉、變異來適應大自然環境。2023/2/5遺傳算法是模仿生物遺傳學和自然選擇機理，通過人工方式構造的一類優化搜索算法，是對生物進化過程的一個數學仿真，屬于進化計算中的一類方法。2023/2/5串碼：表示染色體或者個體適應度函數：表示一個染色體的適應能力，其最大值或者最小值就是最優化問題的解2023/2/54.5.1遺傳算法的基本機理4.5.2遺傳算法的求解步驟4.5.3遺傳算法的收斂性（略）2023/2/54.5.1遺傳算法的基本機理1編碼與解碼2適應度函數3遺傳操作2023/2/51編碼與解碼在遺傳算法中，為了模仿遺傳學的遺傳規律，必須對問題的解的結構進行編碼，運行遺傳算法后，再通過解碼得到問題的解。編碼解碼遺傳算法問題2023/2/5編碼：將問題解的結構轉換成位串形式編碼的過程解碼：將位串形式編碼轉化成問題的解的過程染色體（個體）：位串形式編碼2023/2/5編碼與解碼方法：二進制碼方法浮點數方法符號方法格雷碼方法2023/2/5二進制碼方法編碼方法：將參數的取值范圍分成等長的2l–1

部分，再用l

個二進制來編碼每一個等分，共有2l

種不同的編碼。2023/2/5假設x[A,B],每一個部分的長度為l＝200A01A+δ10A+2δ11A+3δ=BAB2023/2/5解碼方法：如果某一個體的編碼為：X=xl

xl-1…x2

x1解碼公式為2023/2/5特點：編碼與解碼簡單碼串比較長搜索空間是有限的，提高解的精度，必須加大碼長求解多個參數時，將所有的碼拼接起來2023/2/5符號方法：個體編碼中的基因值只取代碼含義的符號集例：TSP問題，按照一個回路中城市的序號進行編碼相互之間不能相同2023/2/52適應度函數適應度函數：度量染色體優劣程度的函數，體現自然進化中的優勝劣汰原則。對于優化問題，適應度函數就是目標函數。2023/2/5例：對于TSP問題，要求總路徑長度為最小，適應度函數可以定義為最小化最大化其中，wn+1=w1

d(wj,wj+1)：兩個城市之間的距離2023/2/53遺傳操作三種簡單的遺傳操作：選擇（Selection）交叉（Crossover）變異（Mutation）2023/2/5選擇操作（復制操作）：根據適應度函數值所度量的個體的優劣程度決定此個體在下一代是被淘汰或是被遺。一般情況下，如果是求最大值，適應度函數值大的個體具有較大的生存機會。2023/2/5交叉操作：選出兩個個體作為父母個體，將兩種的部分碼值進行交換。例：100011101101101110001011110111102023/2/5變異操作：改變數碼串上的某一個位置的數碼。例10100110101101102023/2/54.5.2遺傳算法的求解步驟1遺傳算法的特點通過編碼使得解空間是有限的，所有遺傳算法是一種基于空間搜索的求解技術，通過自然選擇、交叉、變異等操作以及達爾文的適者生存的理論，模擬自然進化過程來尋找問題的解。2023/2/5現在將遺傳算法看成為一種現代的優化技術，但是不一定能找到問題的全局最優解。通過一定的手段，可以將誤差控制在容許的范圍內（以很大的概率找到全局最優解）。最優解2023/2/5特點：對參數集合的編碼進行進化，不是參數本身進行進化從問題解的編碼組（群體）開始，不是從單個解開始搜索只利用適應度函數（目標函數），不需要導數等信息只利用選擇、交叉、變異等操作，不需要利用確定性規則進行隨機操作2023/2/52遺傳算法的框圖遺傳算法的基本思想：通過隨機方式產生若干個個體，形成一個初始種群；利用適應度函數計算它們的適應度函數值，淘汰適應度小的個體，選擇適應度高的個體參加遺傳操作；經過遺傳操作后的個體形成下一代種群，再對新的種群進行新的一輪進化。2023/2/5基本思想簡單的遺傳算法基本的遺傳算法復雜的遺傳算法2023/2/5簡單遺傳算法的步驟：初始化種群計算種群中每一個個體的適應度函數值根據與適應度相關聯的規則確定進入下一輪的個體2023/2/5按照某一個概率進行交叉操作按照某一個概率進行變異操作如果不滿足終止條件，則轉到(2)，否則繼續將種群中適應度最優的個體作為問題的解2023/2/5開始初始化種群計算適應度值選擇操作交叉操作變異操作終止條件？選取適應度最優個體作為解結束是2023/2/53遺傳算法例子求最大值2023/2/5主要步驟：編碼：22位二進制數碼串種群初始化適應度函數：函數本身遺傳操作：選擇、交叉、變異操作算法的若干關鍵參數：種群大小、種群代數、選擇交叉變異概率等2023/2/5結果：最佳個體：1111001101000100000101對于自變量值：1.850773函數值：2.8502272023/2/54Matlab中的遺傳算法函數使用方式：函數形式ga圖形界面形式gatool包含在Matlab7.0版本的GeneticAlgorithmandDirectSearch工具箱中，只能求最小值2023/2/5GA算法的函數形式：[x,fval,reason]=ga(@fitnessfcn,num,options)其中：fitnessfcn:求目標函數值的Matlab函數，用戶自己編寫num:變量的個數options：算法參數的設置(可缺省）2023/2/5函數fitnessfcn的編寫：例：Matlab函數functiony=simple_fitness(x)y=100*(x(1)^2-x(2))^2+(1-x(1))^2用simple_fitness代替ga中的fitnessfcn2023/2/5Options的內容：PopulationType:'doubleVector'PopInitRange:[2x1double]PopulationSize:20EliteCount:2CrossoverFraction:0.8000MigrationDirection:'forward'MigrationInterval:20MigrationFraction:0.2000Generations:100TimeLimit:InfFitnessLimit:-InfStallLimitG:50StallLimitS:20InitialPopulation:[]InitialScores:[]PlotInterval:1CreationFcn:@gacreationuniformFitnessScalingFcn:@fitscalingrankSelectionFcn:@selectionstochunifCrossoverFcn:@crossoverscatteredMutationFcn:@mutationgaussianHybridFcn:[]Display:'final'PlotFcns:[]OutputFcns:[]Vectorized:'off’2023/2/5參數設置函數：gaoptimset生成參數結構與設置參數值：options=gaoptimset(‘param1’,val1,’param2’,val2,…)改變參數設置options=gaoptimset(options,’param1’,val2,….)2023/2/5參數獲取函數val=gaoptimget(options,‘param’)2023/2/5返回結果的含義：[x,fval,reason]最優解算法終止的原因最優解對應的函數值2023/2/5終止算法的五個條件：Generations（代數，缺省值100）TimeLimit（運行時間，無窮）FitnessLimit（適應度函數值，負無