人工智能-許建華- 南京師范大學(xué)計(jì)算機(jī)科學(xué)系-4.5遺傳算法

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

部分，再用l

個(gè)二進(jìn)制來(lái)編碼每一個(gè)等分，共有2l

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

xl-1…x2

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

d(wj,wj+1)：兩個(gè)城市之間的距離2023/2/53遺傳操作三種簡(jiǎn)單的遺傳操作：選擇（Selection）交叉（Crossover）變異（Mutation）2023/2/5選擇操作（復(fù)制操作）：根據(jù)適應(yīng)度函數(shù)值所度量的個(gè)體的優(yōu)劣程度決定此個(gè)體在下一代是被淘汰或是被遺。一般情況下，如果是求最大值，適應(yīng)度函數(shù)值大的個(gè)體具有較大的生存機(jī)會(huì)。2023/2/5交叉操作：選出兩個(gè)個(gè)體作為父母?jìng)€(gè)體，將兩種的部分碼值進(jìn)行交換。例：100011101101101110001011110111102023/2/5變異操作：改變數(shù)碼串上的某一個(gè)位置的數(shù)碼。例10100110101101102023/2/54.5.2遺傳算法的求解步驟1遺傳算法的特點(diǎn)通過(guò)編碼使得解空間是有限的，所有遺傳算法是一種基于空間搜索的求解技術(shù)，通過(guò)自然選擇、交叉、變異等操作以及達(dá)爾文的適者生存的理論，模擬自然進(jìn)化過(guò)程來(lái)尋找問(wèn)題的解。2023/2/5現(xiàn)在將遺傳算法看成為一種現(xiàn)代的優(yōu)化技術(shù)，但是不一定能找到問(wèn)題的全局最優(yōu)解。通過(guò)一定的手段，可以將誤差控制在容許的范圍內(nèi)（以很大的概率找到全局最優(yōu)解）。最優(yōu)解2023/2/5特點(diǎn)：對(duì)參數(shù)集合的編碼進(jìn)行進(jìn)化，不是參數(shù)本身進(jìn)行進(jìn)化從問(wèn)題解的編碼組（群體）開(kāi)始，不是從單個(gè)解開(kāi)始搜索只利用適應(yīng)度函數(shù)（目標(biāo)函數(shù)），不需要導(dǎo)數(shù)等信息只利用選擇、交叉、變異等操作，不需要利用確定性規(guī)則進(jìn)行隨機(jī)操作2023/2/52遺傳算法的框圖遺傳算法的基本思想：通過(guò)隨機(jī)方式產(chǎn)生若干個(gè)個(gè)體，形成一個(gè)初始種群；利用適應(yīng)度函數(shù)計(jì)算它們的適應(yīng)度函數(shù)值，淘汰適應(yīng)度小的個(gè)體，選擇適應(yīng)度高的個(gè)體參加遺傳操作；經(jīng)過(guò)遺傳操作后的個(gè)體形成下一代種群，再對(duì)新的種群進(jìn)行新的一輪進(jìn)化。2023/2/5基本思想簡(jiǎn)單的遺傳算法基本的遺傳算法復(fù)雜的遺傳算法2023/2/5簡(jiǎn)單遺傳算法的步驟：初始化種群計(jì)算種群中每一個(gè)個(gè)體的適應(yīng)度函數(shù)值根據(jù)與適應(yīng)度相關(guān)聯(lián)的規(guī)則確定進(jìn)入下一輪的個(gè)體2023/2/5按照某一個(gè)概率進(jìn)行交叉操作按照某一個(gè)概率進(jìn)行變異操作如果不滿(mǎn)足終止條件，則轉(zhuǎn)到(2)，否則繼續(xù)將種群中適應(yīng)度最優(yōu)的個(gè)體作為問(wèn)題的解2023/2/5開(kāi)始初始化種群計(jì)算適應(yīng)度值選擇操作交叉操作變異操作終止條件？選取適應(yīng)度最優(yōu)個(gè)體作為解結(jié)束是2023/2/53遺傳算法例子求最大值2023/2/5主要步驟：編碼：22位二進(jìn)制數(shù)碼串種群初始化適應(yīng)度函數(shù)：函數(shù)本身遺傳操作：選擇、交叉、變異操作算法的若干關(guān)鍵參數(shù)：種群大小、種群代數(shù)、選擇交叉變異概率等2023/2/5結(jié)果：最佳個(gè)體：1111001101000100000101對(duì)于自變量值：1.850773函數(shù)值：2.8502272023/2/54Matlab中的遺傳算法函數(shù)使用方式：函數(shù)形式ga圖形界面形式gatool包含在Matlab7.0版本的GeneticAlgorithmandDirectSearch工具箱中，只能求最小值2023/2/5GA算法的函數(shù)形式：[x,fval,reason]=ga(@fitnessfcn,num,options)其中：fitnessfcn:求目標(biāo)函數(shù)值的Matlab函數(shù)，用戶(hù)自己編寫(xiě)num:變量的個(gè)數(shù)options：算法參數(shù)的設(shè)置(可缺?。?023/2/5函數(shù)fitnessfcn的編寫(xiě)：例：Matlab函數(shù)functiony=simple_fitness(x)y=100*(x(1)^2-x(2))^2+(1-x(1))^2用simple_fitness代替ga中的fitnessfcn2023/2/5Options的內(nèi)容：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參數(shù)設(shè)置函數(shù)：gaoptimset生成參數(shù)結(jié)構(gòu)與設(shè)置參數(shù)值：options=gaoptimset(‘param1’,val1,’param2’,val2,…)改變參數(shù)設(shè)置options=gaoptimset(options,’param1’,val2,….)2023/2/5參數(shù)獲取函數(shù)val=gaoptimget(options,‘param’)2023/2/5返回結(jié)果的含義：[x,fval,reason]最優(yōu)解算法終止的原因最優(yōu)解對(duì)應(yīng)的函數(shù)值2023/2/5終止算法的五個(gè)條件：Generations（代數(shù)，缺省值100）TimeLimit（運(yùn)行時(shí)間，無(wú)窮）FitnessLimit（適應(yīng)度函數(shù)值，負(fù)無(wú)