遺傳算法的提出、理論及應(yīng)用-read

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

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

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

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

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

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

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

8、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.2. 基因和編碼,

9、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.3. 適應(yīng)度函數(shù)及其尺度變換,2.3.1. 適應(yīng)度函數(shù)(fitness function)是由目標(biāo)函數(shù)變換而成的：包括最大化問題和最小

10、化問題等。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.4. 遺傳操作,2.4.

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

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