GA 遺傳算法簡介概述課件

遺傳算法GeneticAlgorithm遺傳算法GeneticAlgorithm主要內容一、遺傳算法概述二、遺傳算法的基本操作三、遺傳算法原理四、遺傳算法的應用主要內容一、遺傳算法概述現(xiàn)代智能優(yōu)化算法遺傳算法禁忌算法蟻群算法粒子群算法細菌算法混沌算法TSGAACOPSOBCCOA自由搜索算法FS現(xiàn)代智能優(yōu)化算法遺禁蟻粒細混TSGAACOPSOBCCOA自1、遺傳算法起源

遺傳算法(GeneticAlgorithm,GA)是由美國的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。GA來源于達爾文的進化論、魏茨曼的物種選擇學說和孟德爾的群體遺傳學說。其基本思想是模擬自然界遺傳機制和生物進化論而形成的一種過程搜索全局最優(yōu)解的算法。一、遺傳算法概述1、遺傳算法起源遺傳算法(Gene2、生物進化理論和遺傳學基本知識

一、遺傳算法概述(1)達爾文的自然選擇說遺傳（heredity）：

子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性變異（variation）：

子代與父代,子代不同個體之間總有差異，是生命多樣性的根源生存斗爭和適者生存：

具有適應性變異的個體被保留，不具適應性變異的個體被淘汰2、生物進化理論和遺傳學基本知識一、遺傳算法概述(1)達一、遺傳算法概述2、生物進化理論和遺傳學基本知識

(2)遺傳學基本概念和術語基因(gene)：染色體的一個片段染色體(Chromosome)：問題中個體的某種字符串形式的編碼表示種群(Population)：個體的集合,該集合內的個體數(shù)稱為種群的大小基因型(genetype)：基因組合的模型，染色體的內部表現(xiàn)表現(xiàn)型(phenotype)：染色體決定性狀的外部表現(xiàn)111

1

111

111

0

111個體染色體9----1001一、遺傳算法概述2、生物進化理論和遺傳學基本知識(2)遺一、遺傳算法概述2、生物進化理論和遺傳學基本知識

(2)遺傳學基本概念和術語進化(evolution)：個體逐漸適應生存環(huán)境，不斷改良品質的過程適應度(fitness)：反映個體性能的一個數(shù)量值編碼(coding)：從表現(xiàn)型到基因型的映射解碼(decoding)：從基因型到表現(xiàn)性的映射適應度函數(shù)(fitnessfunction):

問題中的全體個體與其適應度之間的一個對應關系,一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導搜索的評價函數(shù)。一、遺傳算法概述2、生物進化理論和遺傳學基本知識(2)遺1選擇-復制(selection-reproduction)二、遺傳算法的基本操作選擇-復制指的就是以一定的概率從種群中選擇若干個體并進行復制的操作輪盤賭選擇（roulettewheelselection）隨機遍歷抽樣（stochasticuniversalselection）局部選擇（localselection）截斷選擇（truncationselection）錦標賽選擇（tournamentselection）

選擇概率P(xi)的計算公式為:常用選擇-復制方法：按比例的適應度分配方法1選擇-復制(selection-reproduction1選擇-復制(selection-reproduction)二、遺傳算法的基本操作例：輪盤賭選擇

解(1)計算選擇概率和累計概率

個體染色體適應度選擇概率累計概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.0000001選擇-復制(selection-reproduction1選擇-復制(selection-reproduction)二、遺傳算法的基本操作個體染色體適應度選擇概率累計概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.000000復制操作能從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體！(2)在0-1之間產(chǎn)生一個隨機數(shù)

0.50789360.07022110.54592980.78456790.44693060.29119850.71634080.27190140.37143560.85464110淘汰1選擇-復制(selection-reproduction2交叉(crossover)——基因重組二、遺傳算法的基本操作

交叉就是互換兩個染色體某些位上的基因

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體

例：設染色體s1=01001011,s2=10010101,交換其后4位基因,即單點交叉2交叉(crossover)——基因重組二、遺傳算法的基本2交叉(crossover)——基因重組二、遺傳算法的基本操作

其它常用的交叉方法：

多點交叉（multiple-pointcrossover）均勻交叉（uniformcrossover）部分匹配交叉（PartiallyMatchedCrossover）順序交叉（OrderedCrossover）循環(huán)交叉（CycleCrossover）交叉模擬了生物進化過程中的繁殖現(xiàn)象，通過兩個染色體的交換組合，來產(chǎn)生新的優(yōu)良品種！2交叉(crossover)——基因重組二、遺傳算法的基本3變異(mutation)變異就是改變染色體某個(些)位上的基因例如，設染色體s=11001101，將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體變異運算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變.若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進行搜索，使進化過程在早期就陷入局部解而進入終止過程，從而影響解的質量!二、遺傳算法的基本操作3變異(mutation)變異就是改變染色體某個(些)位上三、遺傳算法的原理標準遺傳算法流程框圖遺傳算子適者生存種群繁殖關鍵三、遺傳算法的原理標準遺傳算法流程框圖遺傳算子適者生存種群繁三、遺傳算法的原理算法中的一些控制參數(shù)：

種群規(guī)模：最大換代數(shù)：交叉率(crossoverrate)：參加交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例，記為Pc取值范圍一般為0.4～0.99

變異率(mutationrate)：發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm

取值范圍一般為0.0001～0.1三、遺傳算法的原理算法中的一些控制參數(shù)：三、遺傳算法的原理標準遺傳算法(Standardgeneticalgorithm,SGA)Step1

在搜索空間U上定義一個適應度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；Step2

隨機產(chǎn)生U中的N個個體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計數(shù)器t=1；Step3

計算S中每個個體的適應度f(x)；

Step4若終止條件滿足，則取S中適應度最大的個體作為所求結果，算法結束。否則，轉Step5；三、遺傳算法的原理標準遺傳算法(StandardgenetStep5

按選擇概率P(xi)所決定的選中機會，每次從S中隨機選定1個個體并將其復制，共做N次，然后將復制所得的N個染色體組成群體S1；Step6

按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機確定c個染色體，配對進行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；Step7按變異率Pm所決定的變異次數(shù)m，從S2中隨機確定m個染色體，分別進行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；Step8

將群體S3作為新一代種群，即用S3代替S，t=t+1，轉步Step3；三、遺傳算法的原理標準遺傳算法(Standardgeneticalgorithm,SGA)Step5按選擇概率P(xi)所決定的選中機會，每次從S四、遺傳算法的應用1、遺傳算法的應用領域（1）組合優(yōu)化（2）函數(shù)優(yōu)化（3）自動控制（4）生產(chǎn)調度（5）圖像處理（6）機器學習（7）人工生命（8）數(shù)據(jù)挖掘四、遺傳算法的應用1、遺傳算法的應用領域（1）組合優(yōu)化2、遺傳算法的應用舉例四、遺傳算法的應用例：求下列一元函數(shù)的最大值：

x∈[-1,2]，求解結果精確到6位小數(shù)。2、遺傳算法的應用舉例四、遺傳算法的應用例：求下列一元函數(shù)的四、遺傳算法的應用用微分法求解：即：

解有無窮多個

(i=1,2,…及i=-1,-2,…)是一個接近于0的實數(shù)遞減序列當i為奇數(shù)時xi對應局部極大值點，i為偶數(shù)時xi對應局部極小值x19即為區(qū)間[-1,2]內的最大值點此時，函數(shù)最大值f(x19）比f(1.85)=3.85稍大四、遺傳算法的應用用微分法求解：即：解有無窮多個四、遺傳算法的應用用遺傳算法求解：

分析：由于區(qū)間長度為3，求解結果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因為221<3×106<222，所以本例的二進制編碼長度至少需要22位，編碼過程實質上是將區(qū)間[-1，2]內對應的實數(shù)值轉化為一個二進制串（b21b20…b0）。求解過程：(1)編碼表現(xiàn)型：x基因型：二進制編碼，串長22位四、遺傳算法的應用用遺傳算法求解：分析：由于區(qū)間長度為幾個術語基因型：1000101110110101000111表現(xiàn)型：0.637197編碼解碼個體（染色體）基因幾個術語基因型：100010111011010100011四、遺傳算法的應用(2)生成初始種群用遺傳算法求解：方式：隨機生成長度為22的二進制制串數(shù)量：種群的大小(規(guī)模)，如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……四、遺傳算法的應用(2)生成初始種群用遺傳算法求解：方式：隨四、遺傳算法的應用(3)計算適應度用遺傳算法求解：不同的問題有不同的適應度計算方法，本例直接用目標函數(shù)作為適應度函數(shù)②計算x的函數(shù)值(適應度)：①將某個個體轉化為[-1,2]區(qū)間的實數(shù)：s=<1000101110110101000111>x=0.637197(4)遺傳操作選擇：輪盤賭選擇法交叉：單點交叉變異：小概率變異四、遺傳算法的應用(3)計算適應度用遺傳算法求解：四、遺傳算法的應用用遺傳算法求解：(5)模擬結果設置的參數(shù)：種群大小50,交叉概率0.75變異概率0.05,最大代數(shù)200

得到的最佳個體：smax=<1111001100111011111100>xmax=1.8506f(xmax)=3.8503世代數(shù)自變量適應度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503四、遺傳算法的應用用遺傳算法求解：(5)模擬結果設置的參數(shù)：遺傳算法的本質遺傳算法本質上是對染色體模式所進行的一系列運算，即通過選擇算子將當前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進行模式重組，利用變異算子進行模式突變。通過這些遺傳操作，模式逐步向較好的方向進化，最終得到問題的最優(yōu)解。遺傳算法的本質遺傳算法本質上是對染小結1、遺傳算法優(yōu)點：搜索過程不直接作用在變量上，而是對參數(shù)集進行了編碼的個體上搜索過程是迭代的過程，具有并行性利用概率轉移規(guī)則，可在一個不確定的空間上尋優(yōu)不是從一點出發(fā)沿一條線搜索，而是在整個空間上搜索，從而找到全局最優(yōu)解對搜索空間無任何特殊要求(連通，凸性)容錯能力強2、遺傳算法存在的問題：

編碼問題：編碼選擇不當使GA很難收斂到最優(yōu)解早熟收斂：群體過早失去多樣性而收斂到局部最優(yōu)解進化時間長：進化過程中產(chǎn)生大量數(shù)據(jù)，計算大、時間長參數(shù)選擇問題：目前參數(shù)選擇是根據(jù)經(jīng)驗來確定，缺乏理論依據(jù)小結1、遺傳算法優(yōu)點：搜索過程不直接作用在變量上，而是對改變GA的組成成分（編碼、適應度函數(shù)）采用動態(tài)自適應技術（交叉率和變異率）——自適應GA采用非標準的遺傳操作算子——CHC結合其他技術，生成混合GA并行GA、小生境遺傳算法等小結3、遺傳算法改進方法：改變GA的組成成分（編碼、適應度函數(shù)）小結3、遺傳算法改進Thankyou！Thankyou！遺傳算法GeneticAlgorithm遺傳算法GeneticAlgorithm主要內容一、遺傳算法概述二、遺傳算法的基本操作三、遺傳算法原理四、遺傳算法的應用主要內容一、遺傳算法概述現(xiàn)代智能優(yōu)化算法遺傳算法禁忌算法蟻群算法粒子群算法細菌算法混沌算法TSGAACOPSOBCCOA自由搜索算法FS現(xiàn)代智能優(yōu)化算法遺禁蟻粒細混TSGAACOPSOBCCOA自1、遺傳算法起源

遺傳算法(GeneticAlgorithm,GA)是由美國的J.Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應性》中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。GA來源于達爾文的進化論、魏茨曼的物種選擇學說和孟德爾的群體遺傳學說。其基本思想是模擬自然界遺傳機制和生物進化論而形成的一種過程搜索全局最優(yōu)解的算法。一、遺傳算法概述1、遺傳算法起源遺傳算法(Gene2、生物進化理論和遺傳學基本知識

一、遺傳算法概述(1)達爾文的自然選擇說遺傳（heredity）：

子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性變異（variation）：

子代與父代,子代不同個體之間總有差異，是生命多樣性的根源生存斗爭和適者生存：

具有適應性變異的個體被保留，不具適應性變異的個體被淘汰2、生物進化理論和遺傳學基本知識一、遺傳算法概述(1)達一、遺傳算法概述2、生物進化理論和遺傳學基本知識

(2)遺傳學基本概念和術語基因(gene)：染色體的一個片段染色體(Chromosome)：問題中個體的某種字符串形式的編碼表示種群(Population)：個體的集合,該集合內的個體數(shù)稱為種群的大小基因型(genetype)：基因組合的模型，染色體的內部表現(xiàn)表現(xiàn)型(phenotype)：染色體決定性狀的外部表現(xiàn)111

1

111

111

0

111個體染色體9----1001一、遺傳算法概述2、生物進化理論和遺傳學基本知識(2)遺一、遺傳算法概述2、生物進化理論和遺傳學基本知識

(2)遺傳學基本概念和術語進化(evolution)：個體逐漸適應生存環(huán)境，不斷改良品質的過程適應度(fitness)：反映個體性能的一個數(shù)量值編碼(coding)：從表現(xiàn)型到基因型的映射解碼(decoding)：從基因型到表現(xiàn)性的映射適應度函數(shù)(fitnessfunction):

問題中的全體個體與其適應度之間的一個對應關系,一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導搜索的評價函數(shù)。一、遺傳算法概述2、生物進化理論和遺傳學基本知識(2)遺1選擇-復制(selection-reproduction)二、遺傳算法的基本操作選擇-復制指的就是以一定的概率從種群中選擇若干個體并進行復制的操作輪盤賭選擇（roulettewheelselection）隨機遍歷抽樣（stochasticuniversalselection）局部選擇（localselection）截斷選擇（truncationselection）錦標賽選擇（tournamentselection）

選擇概率P(xi)的計算公式為:常用選擇-復制方法：按比例的適應度分配方法1選擇-復制(selection-reproduction1選擇-復制(selection-reproduction)二、遺傳算法的基本操作例：輪盤賭選擇

解(1)計算選擇概率和累計概率

個體染色體適應度選擇概率累計概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.0000001選擇-復制(selection-reproduction1選擇-復制(selection-reproduction)二、遺傳算法的基本操作個體染色體適應度選擇概率累計概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.000000復制操作能從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體！(2)在0-1之間產(chǎn)生一個隨機數(shù)

0.50789360.07022110.54592980.78456790.44693060.29119850.71634080.27190140.37143560.85464110淘汰1選擇-復制(selection-reproduction2交叉(crossover)——基因重組二、遺傳算法的基本操作

交叉就是互換兩個染色體某些位上的基因

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體

例：設染色體s1=01001011,s2=10010101,交換其后4位基因,即單點交叉2交叉(crossover)——基因重組二、遺傳算法的基本2交叉(crossover)——基因重組二、遺傳算法的基本操作

其它常用的交叉方法：

多點交叉（multiple-pointcrossover）均勻交叉（uniformcrossover）部分匹配交叉（PartiallyMatchedCrossover）順序交叉（OrderedCrossover）循環(huán)交叉（CycleCrossover）交叉模擬了生物進化過程中的繁殖現(xiàn)象，通過兩個染色體的交換組合，來產(chǎn)生新的優(yōu)良品種！2交叉(crossover)——基因重組二、遺傳算法的基本3變異(mutation)變異就是改變染色體某個(些)位上的基因例如，設染色體s=11001101，將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體變異運算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變.若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進行搜索，使進化過程在早期就陷入局部解而進入終止過程，從而影響解的質量!二、遺傳算法的基本操作3變異(mutation)變異就是改變染色體某個(些)位上三、遺傳算法的原理標準遺傳算法流程框圖遺傳算子適者生存種群繁殖關鍵三、遺傳算法的原理標準遺傳算法流程框圖遺傳算子適者生存種群繁三、遺傳算法的原理算法中的一些控制參數(shù)：

種群規(guī)模：最大換代數(shù)：交叉率(crossoverrate)：參加交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例，記為Pc取值范圍一般為0.4～0.99

變異率(mutationrate)：發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm

取值范圍一般為0.0001～0.1三、遺傳算法的原理算法中的一些控制參數(shù)：三、遺傳算法的原理標準遺傳算法(Standardgeneticalgorithm,SGA)Step1

在搜索空間U上定義一個適應度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；Step2

隨機產(chǎn)生U中的N個個體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計數(shù)器t=1；Step3

計算S中每個個體的適應度f(x)；

Step4若終止條件滿足，則取S中適應度最大的個體作為所求結果，算法結束。否則，轉Step5；三、遺傳算法的原理標準遺傳算法(StandardgenetStep5

按選擇概率P(xi)所決定的選中機會，每次從S中隨機選定1個個體并將其復制，共做N次，然后將復制所得的N個染色體組成群體S1；Step6

按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機確定c個染色體，配對進行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；Step7按變異率Pm所決定的變異次數(shù)m，從S2中隨機確定m個染色體，分別進行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；Step8

將群體S3作為新一代種群，即用S3代替S，t=t+1，轉步Step3；三、遺傳算法的原理標準遺傳算法(Standardgeneticalgorithm,SGA)Step5按選擇概率P(xi)所決定的選中機會，每次從S四、遺傳算法的應用1、遺傳算法的應用領域（1）組合優(yōu)化（2）函數(shù)優(yōu)化（3）自動控制（4）生產(chǎn)調度（5）圖像處理（6）機器學習（7）人工生命（8）數(shù)據(jù)挖掘四、遺傳算法的應用1、遺傳算法的應用領域（1）組合優(yōu)化2、遺傳算法的應用舉例四、遺傳算法的應用例：求下列一元函數(shù)的最大值：

x∈[-1,2]，求解結果精確到6位小數(shù)。2、遺傳算法的應用舉例四、遺傳算法的應用例：求下列一元函數(shù)的四、遺傳算法的應用用微分法求解：即：

解有無窮多個

(i=1,2,…及i=-1,-2,…)是一個接近于0的實數(shù)遞減序列當i為奇數(shù)時xi對應局部極大值點，i為偶數(shù)時xi對應局部極小值x19即為區(qū)間[-1,2]內的最大值點此時，函數(shù)最大值f(x19）比f(1.85)=3.85稍大四、遺傳算法的應用用微分法求解：即：解有無窮多個四、遺傳算法的應用用遺傳算法求解：

分析：由于區(qū)間長度為3，求解結果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因為221<3×106<222，所以本例的二進制編碼長度至少需要22位，編碼過程實質上是將區(qū)間[-1，2]內對應的實數(shù)值轉化為一個二進制串（b21b20…b0）。求解過程：(1)編碼表現(xiàn)型：x基因型：二進制編碼，串長22位四、遺傳算法的應用用遺傳算法求解：分析：由于區(qū)間長度為幾個術語基因型：1000101110110101000111表現(xiàn)型：0.637197編碼解碼個體（染色體）基因幾個術語基因型：100010111011010100011四、遺傳算法的應用(2)生成初始種群用遺傳算法求解：方式：隨機生成長度為22的二進制制串數(shù)量：種群的大小(規(guī)模)，如30，50，…11110100111000010110001100110011101010101110