遺傳算法的提出、理論及應用-read

1、遺傳算法的提出、理論及應用,遺傳算法簡介基本遺傳算法遺傳算法的理論基礎遺傳算法的改進遺傳算法的應用,遺傳算法簡介,1.1. 遺傳算法的提出1.2. 遺傳算法的基本思想1.3. 遺傳算法的基本操作1.4. 遺傳算法的應用情況,1.1. 遺傳算法的提出,1.1.1. 遺傳算法(Genetic Algorithm, GA)1975年由Michigan大學的John Holand教授與其同事、學生一起首先提出。模擬生物進化的機制來

2、構造人工的模型。已形成較完整的理論體系。1.1.2. 進化策略（Evolutionary Strategy, ES)于60年代由柏林工業(yè)大學的I. Rechenberg和H.P. Schwefel等人引入。1.1.3. 進化規(guī)劃（Evolutionary Programming, EP)在60年代由L.J. Fogel 等人提出。1.1.4. 進化計算（Evolutionary Computation)是指包含如下算法的一個“算法

3、組”：遺傳算法(GA)、進化策略(GS)、進化規(guī)劃(GP)和遺傳程序設計（Genetic Programming, GP)。1.1.5. 計算智能(Computational Intelligence, CI)是一個新的研究方向，它包括：進化計算、人工神經(jīng)網(wǎng)絡（Artificial Neural Network)和模糊系統(tǒng)理論。,1.2. 遺傳算法的基本思想,1.2.1. 遺傳算法的基本思想源于達爾文的自然選擇（natural sel

4、ection）、優(yōu)勝劣汰：遺傳、變異和生存斗爭。1.2.2. 遺傳算法的基本思想是基于種群（population)優(yōu)化的, 包括：先擇、重組交叉、變異。進化成最優(yōu)種群。以下是生物學的幾個概念：染色體(chromosome)： 遺傳物質的主要載體，由多個遺傳因子----基因組成。遺傳因子(gene)： 也稱基因。是在DNA或RNA長鏈結構中占有一定位置的基本遺傳單位?；蜃?locus)：遺傳基因（gene)在染色體中所占據(jù)的位置

5、。個體(individual)：指染色體帶有特征的實體。適應度(fitness)：度量某個物種對于生存環(huán)境的適應程度。選擇(selection)：以一定的概率從種群中選擇若干個個體的操作。復制(reproduction)：一個個體分裂成兩個個體，其遺傳物質不變。交叉(crossover)：有性生殖生物在繁殖下一代時兩個同源染色體之間通過交叉而重組。變異(mutation)：細胞進行復制時可以很小的概率產(chǎn)生某些復制差錯，從而使

6、DNA發(fā)生某種變異。1.2.3. 遺傳算法的特點： （1）自組織、自適應和自學習（智能性）； （2）遺傳算法的本質并行性； （3）遺傳算法不需要求導或其他輔助知識，而指需要影響搜索方向的目標函數(shù)和相應的適應度函數(shù)。,1.3. 遺傳算法的基本操作,1.3.1. 選擇(selection)1.3.2. 交叉或基因重組（crossover/recombination)1.3.3. 變異（mutation）,

7、1.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. 機器學習,2. 基本遺傳算法,2.1. 函數(shù)優(yōu)化的實例2.2. 基因和編碼2.3. 適應度函數(shù)及其尺度變換2.4. 遺傳操作,2.1. 函數(shù)優(yōu)化實例,2.1.1. 下列一元函數(shù)求最大值的優(yōu)化問題：

8、2.1.2. 編碼：從表現(xiàn)型到基因型 二進制串：2.1.3. 產(chǎn)生初始種群：隨即產(chǎn)生串長為22的二進制串組成染色體的基因碼。2.1.4. 計算適應度函數(shù)：2.1.5. 選擇：輪盤賭方法。2.1.6. 交叉：隨機選取交叉點，單點。并按事先選定的小概率 進行交叉。2.1.7. 隨機選擇變異位，并按事先選定的小概率 進行變異。獲得下一代。2.1.8. 檢查終止函數(shù)是否滿足，結束進化。,2.2. 基因和編碼,

9、2.2.1. 浮點數(shù)編碼：設種群個數(shù)為n， 表示第t代第i 個個體。每個個體的基因位數(shù)L=m，由m個實體構成，個體 ， 可以表示m為向量，即可構成一實矩陣,2.2.2. 二進制編碼設種群個數(shù)為n， 表示第t代第i 個個體。每個個體重的每一位分量均用l維二進制表示。,2.3. 適應度函數(shù)及其尺度變換,2.3.1. 適應度函數(shù)(fitness function)是由目標函數(shù)變換而成的：包括最大化問題和最小

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

11、1. 選擇：分配方法：(1) 按比例的適應度分配(proportional fitness assignment) （2）基于排序的適應度分配(rank-based fitness assignment)選擇方法：(1) 輪盤賭方法(roulette wheel selection);(2) 隨機遍歷抽樣法(stochastic universal sampling);(3)局部選擇法（lo

12、cal selection)：線性鄰集（整環(huán)形和半環(huán)形）；兩對角鄰集。(4) 錦標賽選擇法（tournament selection)：隨機地選擇最好的個體為父題。2.4.2. 交叉/基因重組：二進制交叉：單點交叉；多點交叉。實值重組：離散重組；中間重組。2.4.3. 變異：二進制變異；實值變異。,3. 遺傳算法的理論基礎,3.1. 模式：模式表示基因傳中某些特征為相同的結構3.2. 模式階(schema order)：