智能控制進化算法遺傳算法

智能控制進化算法遺傳算法1第1頁，課件共50頁，創(chuàng)作于2023年2月8.2.1遺傳學習的基本思想8.2.2遺傳學習算法的理論基礎8.2.3遺傳學習算法的改良8.2.4遺傳學習算法的應用8.2遺傳學習原理與算法2第2頁，課件共50頁，創(chuàng)作于2023年2月1.問題的提出美國的J.Holland教授于1975年提出在遺傳學的基礎上利用計算機來模擬生物的進化過程，從而實現(xiàn)復雜問題的優(yōu)化求解。模擬生物染色體的運作（復制、交叉、變異），是一種隨機化搜索算法3第3頁，課件共50頁，創(chuàng)作于2023年2月步驟4第4頁，課件共50頁，創(chuàng)作于2023年2月需要解決的問題編碼機制；選擇機制；控制參數(shù)選擇；二進制字符串的群體構成；適應度函數(shù)的計算遺傳算子（交叉、變異）的定義。5第5頁，課件共50頁，創(chuàng)作于2023年2月2.遺傳學習算法的操作算子編碼機制(Encodingmechanism)適應度函數(shù)(Fitnessfunction)選擇機制(Selectionmechanism)交叉算子(Crossover)變異算子(Mutation)6第6頁，課件共50頁，創(chuàng)作于2023年2月(1)編碼機制二進制編碼每一個位（0或1）－基因字符串－染色體多值編碼方法實數(shù)編碼7第7頁，課件共50頁，創(chuàng)作于2023年2月(2)適應度函數(shù)優(yōu)化問題的目標函數(shù)“適應度值”的計算直接通過將目標函數(shù)經(jīng)一定的線性變換映射到的［0，1］區(qū)間內(nèi)的一個值。8第8頁，課件共50頁，創(chuàng)作于2023年2月(3)選擇機制基本思想取自于自然界進化論的“適者生存”。適應度值越高的個體，生存的數(shù)量也越高。滿足“優(yōu)勝劣汰”自然法則。也可稱為復制機制比例選擇法(Proportionateselectionscheme)轉輪選擇法(RouletteWheelSelectionScheme)：隨機方法9第9頁，課件共50頁，創(chuàng)作于2023年2月(4)交叉算子模擬有性繁殖現(xiàn)象隨機地從父輩集合中選取兩個個體作為雙親。設L表示一個體的字符串（染色體）長度，隨機地產(chǎn)生(0～L)之間的一個數(shù)d，并把此點位置稱為交叉點。交叉運算就是將雙親的基因鏈在交叉點斷裂，且將在交叉點之后的基因根據(jù)交叉率的條件決定是否進行相互交換形成下一代。所謂交叉率pc是根據(jù)優(yōu)化問題預先確定的一個0～1之間的值。通常取0.6～0.9。10第10頁，課件共50頁，創(chuàng)作于2023年2月(5)變異算子模擬基因突變現(xiàn)象所謂變異指的是隨機地選取染色體中的某個基因（也即字符串中的某一位）進行取反運算，即將原有的“1”變?yōu)椤?”和反之。變異率pm取比較小的數(shù)值，一般pm為0.001～0.2。11第11頁，課件共50頁，創(chuàng)作于2023年2月3.遺傳學習算法的設計舉例12第12頁，課件共50頁，創(chuàng)作于2023年2月(1)群體初始化群體規(guī)模N 一般情況下取N=10～200之間為宜。初始群體的構成 隨機選擇13第13頁，課件共50頁，創(chuàng)作于2023年2月舉例群體P1（隨機初始化）染色體適應度值00000111000.210000111110.601101010110.611111110110.914第14頁，課件共50頁，創(chuàng)作于2023年2月以

的比例分配轉輪(2)選擇15第15頁，課件共50頁，創(chuàng)作于2023年2月選擇舉例

群體P2（經(jīng)選擇后）染色體適應度值10000111110.601101010110.611111110110.911111110110.916第16頁，課件共50頁，創(chuàng)作于2023年2月群體P3（交叉運算后）染色體適應度值10000｜110110.501101010110.611111110110.911111｜111111.0(3)交叉本例中隨機選取1和4號個體、2和3號個體分別形成兩對進行交叉運算。當取交叉率pc=0.5時，只有個體1和4這一對雙親進行真正的交叉運算，而另一對個體2和3不進行交叉運算。17第17頁，課件共50頁，創(chuàng)作于2023年2月(4)變異取pm=0.05

P4給出了第2個個體和第4個個體中分別有一個基因發(fā)生變異后的情況。群體P4(變異運算后)染色體適應度值10000110110.501101110110.711111110110.901111111110.918第18頁，課件共50頁，創(chuàng)作于2023年2月(5)終止準則判斷方法有兩類：19第19頁，課件共50頁，創(chuàng)作于2023年2月8.2.1遺傳學習的基本思想8.2.2遺傳學習算法的理論基礎8.2.3遺傳學習算法的改良8.2.4遺傳學習算法的應用8.2遺傳學習原理與算法20第20頁，課件共50頁，創(chuàng)作于2023年2月8.2.2理論基礎有多種理論分析遺傳算法的收斂性，例如Holland提出的模板理論(Schematheory)Goldberg提出的建筑塊假設(Buildingblockhypothesis)。它們通過計算有用相似性，檢查包含在群體中的各種模板的增長速率來表明遺傳學習的能力。這里主要介紹模板定理21第21頁，課件共50頁，創(chuàng)作于2023年2月1.模板的基本概念模板表示那些在某些基因位置上具有相同性質(zhì)、而在另一些位置上是不影響子集特征的染色體集合。例如：模板**000表示最后三個位置的值必須為“0”的一組染色體構成的子集。在二進制編碼前提下，“*”可以是“0”、也可以是“1”。22第22頁，課件共50頁，創(chuàng)作于2023年2月模板的階o(S)模板的階o(S)模板的定義長度δ(S)模板中含有0或1的個數(shù)。如S=**111，則模板S的階o(S)=3。模板中有確定值數(shù)碼之間的最大距離。如：S=**111，則模板S的長度δ(S)=2。S=1*00*，則模板S的長度δ(S)=3。兩個定義23第23頁，課件共50頁，創(chuàng)作于2023年2月2.模板定理假設一個L長的染色體。如果用二進制編碼，則有2L個模板。對于有N個個體構成的群體總的模板數(shù)NS滿足： 。NS的實際大小取決于群體中染色體的分散性。模板理論可以說明在進化計算中特定字符串在下一代中繁殖的情況。24第24頁，課件共50頁，創(chuàng)作于2023年2月（1）選擇算子假設模板S在t時刻在群體中有n(S,t)個特定字符串（即同一字符串在群體中的占有數(shù)目）。由比例選擇法可知

其中：

f(S):

模板S內(nèi)所有子集的目標函數(shù)平均值； f(P):群體內(nèi)的平均目標函數(shù)值.當f(S)>

f(P)時，該模板的數(shù)目會增加25第25頁，課件共50頁，創(chuàng)作于2023年2月（2）交叉算子交叉算子運算后，模板S中保留特定字符串的概率

選擇、交叉算子運算后，在下一代中模板S的特定字符串數(shù)目滿足：

具有較好的目標函數(shù)和較短定義長度的模板，其字符串的增長率最快。26第26頁，課件共50頁，創(chuàng)作于2023年2月（3）變異算子在變異運算后字符串仍然屬于S模板的概率為

因為，變異率pm通常是非常小27第27頁，課件共50頁，創(chuàng)作于2023年2月定理8-1:模板定理

這一定理表明了隨著遺傳學習的進行，優(yōu)秀品質(zhì)的字符串個體在群體中占有的數(shù)目會越來越多，最終得到平均適應度高、定義長度短和階次小的模板。這種模板又可稱為建筑塊。28第28頁，課件共50頁，創(chuàng)作于2023年2月8.2.1遺傳學習的基本思想8.2.2遺傳學習算法的理論基礎8.2.3遺傳學習算法的改良8.2.4遺傳學習算法的應用8.2遺傳學習原理與算法29第29頁，課件共50頁，創(chuàng)作于2023年2月8.2.3遺傳學習算法的改良目前已經(jīng)提出的改進方案有：編碼機制——灰度編碼和動態(tài)編碼；選擇機制——優(yōu)選策略、基于次序的選擇、穩(wěn)定狀態(tài)選擇及隨機余數(shù)法的比例選擇；交叉機制——兩點或多點交叉、均勻交叉；控制參數(shù)——動態(tài)自適應參數(shù)控制技術；算法策略——分布式遺傳學習算法和并行遺傳學習－算法。30第30頁，課件共50頁，創(chuàng)作于2023年2月1.編碼機制的改進灰度編碼技術保證連續(xù)變量編碼后的相鄰Hamming距離為1。 0000080011110009101121100101111301001101114011012010151110131101610101410017001015000131第31頁，課件共50頁，創(chuàng)作于2023年2月2.選擇機制的改進解決早熟問題。有兩個途徑：一是采用全量程適應度函數(shù)定標；二是采用改進的選擇方案。32第32頁，課件共50頁，創(chuàng)作于2023年2月全量程適應度函數(shù)定標線性變換

計算的準則是希望換算后的適應度最大值應該是群體平均適應度值的某一小的倍數(shù)，通常取1.5或2。σ-截斷法

其中：群體的平均適應度值；

σ：群體適應度的標準方差；

c

：一個小的常數(shù)，通常取1～3。33第33頁，課件共50頁，創(chuàng)作于2023年2月選擇方法的改進基于次序的選擇法競爭選擇隨機余數(shù)技術優(yōu)選策略局部替代法穩(wěn)定狀態(tài)法選擇育種法34第34頁，課件共50頁，創(chuàng)作于2023年2月3.交叉機制的改進兩點交叉或多點交叉均勻交叉（是否交叉由概率決定）父輩字符串分別為A、B：

A=10110011011101B=11011000010101交叉后的子代為：

A'=11110011010101B'=1001100001110135第35頁，課件共50頁，創(chuàng)作于2023年2月倒置變換對于字長為10的字符串個體A=100｜1101｜010 隨機選取兩點4和8。將4與8之間的字符串進行倒置，即第7位變換到第4位、第6位變換到第5位...，生成新的個體A'

A'=100｜1011｜01036第36頁，課件共50頁，創(chuàng)作于2023年2月4.控制參數(shù) 經(jīng)驗性結論增大群體規(guī)模會增加群體中個體的發(fā)散性，減少GA算法過早收斂于局部最優(yōu)的可能性。但也增加了算法的計算時間。小規(guī)模群體的GA搜索問題可以選擇相對較大的交叉率和變異率，而群體規(guī)模比較大時，可以選擇較小的交叉率和變異率。37第37頁，課件共50頁，創(chuàng)作于2023年2月5.算法策略動態(tài)自適應策略 根據(jù)性能指標和搜索的階段，自適應調(diào)整控制參數(shù)，對于遺傳算法的收斂，尤其對高精度最優(yōu)解的搜索有著重要的作用。分布式GA算法和并行GA算法策略分布式GA算法是一個群整體分解為幾個弱相關的子體分別進行進化計算，并行GA算法是對傳統(tǒng)的串行計算方法用并行計算手段來實現(xiàn)。38第38頁，課件共50頁，創(chuàng)作于2023年2月GA的優(yōu)點GA算法的突出優(yōu)點在于能夠根據(jù)交互的環(huán)境中的相應情況和進化算子在沒有任何最優(yōu)解先驗知識條件下尋找到最優(yōu)解。它不同于梯度下降法那樣只對一點進行優(yōu)化計算而是通過對群體中的所有個體進行遺傳操作達到優(yōu)化的目的，因此避免了單點優(yōu)化算法可能出現(xiàn)的局部最優(yōu)問題。從而使得GA算法可以處理復雜的、高維的、多目標的優(yōu)化問題。這些都是傳統(tǒng)優(yōu)化方法無法比擬的。39第39頁，課件共50頁，創(chuàng)作于2023年2月8.2.1遺傳學習的基本思想8.2.2遺傳學習算法的理論基礎8.2.3遺傳學習算法的改良8.2.4遺傳學習算法的應用8.2遺傳學習原理與算法40第40頁，課件共50頁，創(chuàng)作于2023年2月8.2.4遺傳學習算法的應用遺傳學習算法能夠解決許多傳統(tǒng)的優(yōu)化方法難以解決的眾多問題，已經(jīng)在工程優(yōu)化設計、機器學習、自適應控制、魯棒控制器設計、PID控制、模糊邏輯控制器優(yōu)化、最優(yōu)控制、系統(tǒng)辨識、故障診斷、神經(jīng)網(wǎng)絡控制等領域得到應用和發(fā)展。41第41頁，課件共50頁，創(chuàng)作于2023年2月1.非線性系統(tǒng)的神經(jīng)網(wǎng)絡辨識42第42頁，課件共50頁，創(chuàng)作于2023年2月舉例考慮非線性系統(tǒng)選擇神經(jīng)網(wǎng)絡結構為輸入矢量為[y(k),y(k-1),u(k)]輸出矢量為y(k+1)。43第43頁，課件共50頁，創(chuàng)作于2023年2月GA設計用一個16位字長的編碼來表示一個權系數(shù)，神經(jīng)網(wǎng)絡結構共需要16×[(1+3)×6+(6+1)×1]=496 位長的字符串。群體規(guī)模N=60，pc=0.7,pm=0.01。44第44頁，課件共50頁，創(chuàng)作于2023年2