遺傳算法的提出理論及應用課件

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

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

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

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

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

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

變異：二進制變異；實值變異。2.4.遺傳操作2.4.1.選擇：113.遺傳算法的理論基礎

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