遺傳算法的提出理論及應(yīng)用課件

遺傳算法的提出、理論及應(yīng)用遺傳算法簡介基本遺傳算法遺傳算法的理論基礎(chǔ)遺傳算法的改進(jìn)遺傳算法的應(yīng)用遺傳算法的提出、理論及應(yīng)用遺傳算法簡介1遺傳算法簡介1.1.遺傳算法的提出1.2.遺傳算法的基本思想1.3.遺傳算法的基本操作1.4.遺傳算法的應(yīng)用情況遺傳算法簡介1.1.遺傳算法的提出21.1.遺傳算法的提出1.1.1.遺傳算法(GeneticAlgorithm,GA)1975年由Michigan大學(xué)的JohnHoland教授與其同事、學(xué)生一起首先提出。模擬生物進(jìn)化的機(jī)制來構(gòu)造人工的模型。已形成較完整的理論體系。1.1.2.進(jìn)化策略（EvolutionaryStrategy,ES)于60年代由柏林工業(yè)大學(xué)的I.Rechenberg和H.P.Schwefel等人引入。1.1.3.進(jìn)化規(guī)劃（EvolutionaryProgramming,EP)在60年代由L.J.Fogel等人提出。1.1.4.進(jìn)化計算（EvolutionaryComputation)是指包含如下算法的一個“算法組”：遺傳算法(GA)、進(jìn)化策略(GS)、進(jìn)化規(guī)劃(GP)和遺傳程序設(shè)計（GeneticProgramming,GP)。1.1.5.計算智能(ComputationalIntelligence,CI)是一個新的研究方向，它包括：進(jìn)化計算、人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork)和模糊系統(tǒng)理論。1.1.遺傳算法的提出1.1.1.遺傳算法(Geneti31.2.遺傳算法的基本思想1.2.1.遺傳算法的基本思想源于達(dá)爾文的自然選擇（naturalselection）、優(yōu)勝劣汰：遺傳、變異和生存斗爭。1.2.2.遺傳算法的基本思想是基于種群（population)優(yōu)化的,包括：先擇、重組交叉、變異。進(jìn)化成最優(yōu)種群。以下是生物學(xué)的幾個概念：染色體(chromosome)：遺傳物質(zhì)的主要載體，由多個遺傳因子----基因組成。遺傳因子(gene)：也稱基因。是在DNA或RNA長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位。基因座(locus)：遺傳基因（gene)在染色體中所占據(jù)的位置。個體(individual)：指染色體帶有特征的實體。適應(yīng)度(fitness)：度量某個物種對于生存環(huán)境的適應(yīng)程度。選擇(selection)：以一定的概率從種群中選擇若干個個體的操作。復(fù)制(reproduction)：一個個體分裂成兩個個體，其遺傳物質(zhì)不變。交叉(crossover)：有性生殖生物在繁殖下一代時兩個同源染色體之間通過交叉而重組。變異(mutation)：細(xì)胞進(jìn)行復(fù)制時可以很小的概率產(chǎn)生某些復(fù)制差錯，從而使DNA發(fā)生某種變異。1.2.3.遺傳算法的特點：（1）自組織、自適應(yīng)和自學(xué)習(xí)（智能性）；（2）遺傳算法的本質(zhì)并行性；（3）遺傳算法不需要求導(dǎo)或其他輔助知識，而指需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)。1.2.遺傳算法的基本思想1.2.1.遺傳算法的基本思想41.3.遺傳算法的基本操作1.3.1.選擇(selection)1.3.2.交叉或基因重組（crossover/recombination)1.3.3.變異（mutation）1.3.遺傳算法的基本操作1.3.1.選擇(select51.4.遺傳算法的應(yīng)用情況1.4.1.函數(shù)優(yōu)化1.4.2.組和優(yōu)化1.4.3.自動控制。1.4.4.機(jī)器人智能控制1.4.5.圖像處理和模式識別1.4.6.人工生命1.4.7.遺傳程序設(shè)計1.4.8.機(jī)器學(xué)習(xí)1.4.遺傳算法的應(yīng)用情況1.4.1.函數(shù)優(yōu)化62.基本遺傳算法2.1.函數(shù)優(yōu)化的實例2.2.基因和編碼2.3.適應(yīng)度函數(shù)及其尺度變換2.4.遺傳操作2.基本遺傳算法2.1.函數(shù)優(yōu)化的實例72.1.函數(shù)優(yōu)化實例2.1.1.下列一元函數(shù)求最大值的優(yōu)化問題：2.1.2.編碼：從表現(xiàn)型到基因型

二進(jìn)制串：2.1.3.產(chǎn)生初始種群：隨即產(chǎn)生串長為22的二進(jìn)制串組成染色體的基因碼。2.1.4.計算適應(yīng)度函數(shù)：2.1.5.選擇：輪盤賭方法。2.1.6.交叉：隨機(jī)選取交叉點，單點。并按事先選定的小概率進(jìn)行交叉。2.1.7.

隨機(jī)選擇變異位，并按事先選定的小概率進(jìn)行變異。獲得下一代。2.1.8.檢查終止函數(shù)是否滿足，結(jié)束進(jìn)化。2.1.函數(shù)優(yōu)化實例2.1.1.下列一元函數(shù)求最大值的優(yōu)82.2.基因和編碼2.2.1.浮點數(shù)編碼：設(shè)種群個數(shù)為n，表示第t代第i個個體。每個個體的基因位數(shù)L=m，由m個實體構(gòu)成，個體，可以表示m為向量，即可構(gòu)成一實矩陣2.2.2.二進(jìn)制編碼設(shè)種群個數(shù)為n，表示第t代第i個個體。每個個體重的每一位分量均用l維二進(jìn)制表示。2.2.基因和編碼2.2.1.浮點數(shù)編碼：2.2.2.92.3.適應(yīng)度函數(shù)及其尺度變換

2.3.1.適應(yīng)度函數(shù)(fitnessfunction)是由目標(biāo)函數(shù)變換而成的：包括最大化問題和最小化問題等。2.3.2.適應(yīng)度函數(shù)的作用：在進(jìn)化初期，通常會產(chǎn)生一些超常個體；要防止競爭力臺突出，使其控制了選擇過程。在進(jìn)化后期，種群中個體適應(yīng)督差異較小時，易收斂到局部最優(yōu)解。即欺騙問題。2.3.3.適應(yīng)度函數(shù)的設(shè)計：單值、連續(xù)、非負(fù)、最大化；合理、一致性；計算良宵。2.3.4.適應(yīng)度函數(shù)的尺度變換線性變換法：F=a*f+b冪函數(shù)變換法：指數(shù)變換法：2.3.適應(yīng)度函數(shù)及其尺度變換

2.3.1.適應(yīng)度函數(shù)(102.4.遺傳操作2.4.1.選擇：分配方法：(1)按比例的適應(yīng)度分配(proportionalfitnessassignment)

（2）基于排序的適應(yīng)度分配(rank-basedfitnessassignment)選擇方法：(1)輪盤賭方法(roulettewheelselection);(2)隨機(jī)遍歷抽樣法(stochasticuniversalsampling);(3)局部選擇法（localselection)：線性鄰集（整環(huán)形和半環(huán)形）；兩對角鄰集。(4)錦標(biāo)賽選擇法（tournamentselection)：隨機(jī)地選擇最好的個體為父題。2.4.2.交叉/基因重組：二進(jìn)制交叉：單點交叉；多點交叉。實值重組：離散重組；中間重組。2.4.3.

變異：二進(jìn)制變異；實值變異。2.4.遺傳操作2.4.1.選擇：113.遺傳算法的理論基礎(chǔ)

3.1.模式：模式表示基因傳中某些特征為相同的結(jié)構(gòu)3.2.模式階(schemaorder)：模式H中確定位置的個數(shù)稱為模式H的模式階。記為O(H);3.3.定義矩(defininglength)：模式H中的一個確定位置和最一個確定位置之間的距離稱為模式的定義矩，記為3.4.模式定理：在遺傳算子選擇、交叉、變異的