智能控制進(jìn)化算法遺傳算法

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

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

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

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

其中：

f(S):

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

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

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

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

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

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

計(jì)算的準(zhǔn)則是希望換算后的適應(yīng)度最大值應(yīng)該是群體平均適應(yīng)度值的某一小的倍數(shù)，通常取1.5或2。σ-截?cái)喾?/p>

其中：群體的平均適應(yīng)度值；

σ：群體適應(yīng)度的標(biāo)準(zhǔn)方差；

c

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

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

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

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