遺傳算法基本概念及其在控制工程中的應(yīng)用-read

1、關(guān)于遺傳算法的一般性介紹,報(bào)告人:楊再躍報(bào)告時(shí)間:2003.1,主要內(nèi)容,1 GA的起源及發(fā)展2 GA的基本思想3 GA的幾個(gè)近親4 SGA的實(shí)現(xiàn)方法5 GA的特點(diǎn)和適用范圍6 需要注意的幾個(gè)問題7 一些改進(jìn)后的算法8 GA在控制工程中的應(yīng)用,1 GA的起源及發(fā)展,1950年，圖靈提出可以通過模擬進(jìn)化和自然選擇過程自動(dòng)生成智能程序。1960s’~1970s’，基于進(jìn)化和自然選擇思想的各種算法的提出和應(yīng)用。1975年，

2、Holland發(fā)表Adaptation in Nature and Artificial Systems，完整描述了GA的原理及實(shí)現(xiàn)步驟。1975年，De Jong提出了5個(gè)評(píng)價(jià)GA效率的測(cè)試函數(shù)。1987年，Goldberg發(fā)表Genetic Algorithms in Search，Optimization and Machine Learning,詳細(xì)介紹了GA在工程上的應(yīng)用。,2 GA的基本思想,GA的思想本源是自然界中的“

3、優(yōu)勝劣汰”現(xiàn)象。各種生物在自然選擇的壓力下，器官和結(jié)構(gòu)不斷演變以適應(yīng)環(huán)境，最終實(shí)現(xiàn)從簡(jiǎn)單到復(fù)雜、從不適應(yīng)到適應(yīng)的進(jìn)化過程。GA中的幾個(gè)術(shù)語。個(gè)體：進(jìn)化的最小單元；種群：個(gè)體的集合；個(gè)體適應(yīng)度：評(píng)價(jià)每個(gè)個(gè)體優(yōu)劣的標(biāo)量值；選擇：從種群中根據(jù)適應(yīng)度選取一定數(shù)量的個(gè)體組成新種群；遺傳操作：包括重組和變異兩種操作；重組：一對(duì)個(gè)體按某種方式結(jié)合生成一對(duì)新個(gè)體；變異：?jiǎn)蝹€(gè)個(gè)體隨機(jī)發(fā)生變化。,2 GA的基本思想,GA是一種模擬自然選擇和進(jìn)化過程來求解

4、問題的計(jì)算模型。GA求解問題的過程：隨機(jī)產(chǎn)生一個(gè)種群，其中的個(gè)體代表問題的可行解；根據(jù)問題確定評(píng)價(jià)個(gè)體適應(yīng)度的方式，并對(duì)個(gè)體賦以適應(yīng)度值；根據(jù)個(gè)體適應(yīng)度選擇一定數(shù)量的個(gè)體參加遺傳操作；被選個(gè)體通過重組或者變異操作生成新個(gè)體；新個(gè)體連同以前的個(gè)體，按照某種方式保存一部分到下一代。重復(fù)前面的步驟，直到滿足終止條件，得到最佳個(gè)體，即問題的近似最優(yōu)解。,3 GA的幾個(gè)近親及其特點(diǎn),遺傳編程（Genetic Programming），個(gè)體為一段

5、程序。演化策略（Evolution Strategies），只有一個(gè)個(gè)體，通過變異不斷進(jìn)化。演化規(guī)劃（Evolutionary Programming），根據(jù)以前的狀態(tài)估計(jì)未來的狀態(tài)，個(gè)體長度不斷增加。硬件演化（Evolvable Hardware），結(jié)合PLD實(shí)現(xiàn)硬件本身自動(dòng)地改變結(jié)構(gòu)以適應(yīng)環(huán)境的變化。,4 SGA的實(shí)現(xiàn)步驟,4.1 編碼4.2 種群設(shè)定4.3 適應(yīng)度函數(shù)4.4 選擇4.5 遺傳操作4.6 個(gè)體保存方式

6、,4.1 編碼,把問題的解轉(zhuǎn)換成GA可以操作的對(duì)象的過程叫做編碼。編碼是一種將解同個(gè)體、將解空間同染色體空間、將表現(xiàn)型同基因型對(duì)應(yīng)起來的映射。在SGA中，一般直接用二進(jìn)制數(shù)表示問題的解；或者用Gray碼表示問題的解。目前在工程上使用最廣泛的是浮點(diǎn)數(shù)直接編碼方式，這是因?yàn)樗诟拍钌细拷饪臻g，同時(shí)也便于使用封閉的算子。,4.2 種群設(shè)定,種群規(guī)模（即所包含的個(gè)體數(shù)目）與問題的搜索空間正相關(guān)，一般選取為20～100之間的一個(gè)常數(shù)。

7、確定種群規(guī)模后，隨機(jī)初始化種群，即隨機(jī)產(chǎn)生指定數(shù)量的可行個(gè)體?？梢酝ㄟ^選擇代溝（generation gap）確定選取多少個(gè)體參加遺傳操作，代溝通常為0.7～0.9之間的常數(shù)。,4.3 適應(yīng)度函數(shù),適應(yīng)度函數(shù)用于根據(jù)問題（目標(biāo)函數(shù)）賦給個(gè)體相應(yīng)的適應(yīng)度值。常見的幾種適應(yīng)度函數(shù)類型：線性定標(biāo)形式；冪乘形式；排序賦值等。其中以排序賦值使用最為廣泛。,4.4 選擇,從群體中根據(jù)個(gè)體適應(yīng)度依概率選取一部分個(gè)體參加遺傳操作的過程叫做選擇。選

8、擇的個(gè)體數(shù)量等于種群規(guī)模與代溝的乘積。常用的選擇方法有：輪盤賭選擇法，期望值法，最優(yōu)個(gè)體選擇法，排序選擇法，部分放回隨機(jī)選擇法，隨機(jī)均勻選擇法，聯(lián)賽選擇法，排擠法等。,4.5 遺傳操作,遺傳操作是按概率執(zhí)行的，它包括重組和變異兩部分，可以根據(jù)實(shí)際情況選擇執(zhí)行兩種操作或者其中的某一種操作。如何確定遺傳操作一直是學(xué)術(shù)界爭(zhēng)論的焦點(diǎn)，或者說由于GA針對(duì)性太強(qiáng)而無法給出普適性的結(jié)論。總的說來，重組操作趨向于在深度方向進(jìn)行搜索，變異操作趨向于

9、在廣度方向進(jìn)行搜索。,4.5 遺傳操作,重組操作是指將個(gè)體兩兩配對(duì)，重新組合生成新個(gè)體的過程。重組操作的設(shè)計(jì)需要結(jié)合編碼方式來考慮。例如針對(duì)二進(jìn)制形式的編碼，通常是將兩個(gè)體對(duì)應(yīng)位相互交換而生成新個(gè)體，如001和010 → 011和000。習(xí)慣上稱這種重組方式為交叉，交叉又可以細(xì)分為單點(diǎn)交叉、兩點(diǎn)交叉和多點(diǎn)交叉。而對(duì)于浮點(diǎn)數(shù)編碼，重組操作通常是將兩個(gè)個(gè)體分別乘以系數(shù)后相加，如3.14和4.13 → 3.14× α +4.13&

10、#215; β和3.14× β+4.13× α，通常α＋β＝1。,4.5 遺傳操作,變異操作是指依概率從參加遺傳操作的種群中指定一定數(shù)量的個(gè)體，然后隨機(jī)改變這些個(gè)體的某些位的過程。變異操作通常也需要結(jié)合編碼方式來考慮。針對(duì)二進(jìn)制編碼，可通過將某位取非來實(shí)現(xiàn)變異，如01→11；而對(duì)于浮點(diǎn)數(shù)編碼，則可以通過增加或者減去指定幅度（步長）以內(nèi)的一個(gè)隨機(jī)數(shù)來實(shí)現(xiàn)變異，如3.14 → 3.14+0.01×θ，其中0.

11、01為步長， －1 ≤ θ ≤ 1，且服從某種概率分布 。,4.6 個(gè)體保留,為了維持種群規(guī)模恒定（也有少數(shù)GA種群規(guī)模是變化的），只能新個(gè)體和老個(gè)體中間的一部分保留到下一代，因此需要按照某種適當(dāng)?shù)姆绞綄?shí)現(xiàn)個(gè)體保留過程。由于個(gè)體保留同選擇過程在操作基本相同，因此可以沿用選擇操作。,5 GA的特點(diǎn)和適用范圍,GA是一種迭代自適應(yīng)概率性搜索算法。它無需了解問題的數(shù)學(xué)模型，不依賴于梯度信息。因此，它適合解決傳統(tǒng)搜索方法不能很好處理的問題，例

12、如系統(tǒng)具有嚴(yán)重的非線性，或者難以建模分析等；反之，則GA并不適宜。GA是一種實(shí)驗(yàn)性較強(qiáng)的算法，并沒有完備的數(shù)學(xué)理論作為基礎(chǔ)，因此GA的設(shè)計(jì)更針對(duì)具體問題，而沒有一種普適性的設(shè)計(jì)方案。一般說來，在目前的計(jì)算能力下，GA運(yùn)算相對(duì)時(shí)間較長，難以進(jìn)行在線求解。,6 需要注意的幾個(gè)問題,編碼應(yīng)該遵循以下原則：基因型與表現(xiàn)型應(yīng)是一一映射，并且應(yīng)該確保二者的變化是一致的。這是為了避免在編碼——譯碼過程中出現(xiàn)誤解。二進(jìn)制數(shù)編碼存在“海明懸崖”問題，

13、例如：兩個(gè)解為7、8，對(duì)應(yīng)的4位二進(jìn)制數(shù)為0111、1000，即表現(xiàn)型與基因型之間變化并不一致。評(píng)價(jià)選擇機(jī)制優(yōu)劣應(yīng)遵循Baker提出的三條準(zhǔn)則：偏差、延伸度和復(fù)雜度。偏差是指?jìng)€(gè)體實(shí)際被選擇的概率與期望概率之差的絕對(duì)值；延伸度是指?jìng)€(gè)體在演化中可能經(jīng)歷的代數(shù)；復(fù)雜度是指選擇算法的復(fù)雜程度。那么，優(yōu)越的選擇機(jī)制應(yīng)該是：零偏差，小延伸度，低復(fù)雜度。隨機(jī)均勻選擇較為理想。,6 需要注意的幾個(gè)問題,GA的搜索過程是一個(gè)動(dòng)態(tài)過程，在不同階段對(duì)搜索的

14、方向和力度有不同的要求，可以使用動(dòng)態(tài)參數(shù)提高搜索效率；但另一方面，這勢(shì)必會(huì)增加算法的復(fù)雜度。,7 一些改進(jìn)后的算法,1.7.1 多種群GA1.7.2 自適應(yīng)GA1.7.3 GA的二級(jí)參數(shù)控制1.7.4 各種混合GA,7.1 多種群GA,將種群劃分成多個(gè)子種群，每個(gè)種群獨(dú)立進(jìn)化，然后按照一定的方式交換子種群中的個(gè)體（遺傳信息）；周而復(fù)始直到算法終止。該模型來源于這樣的思想：近親結(jié)合產(chǎn)生的后代常常有缺陷，而混血兒通常更為優(yōu)秀。該模

15、型比較適合在并行系統(tǒng)上運(yùn)行，可以求解運(yùn)算量較大的問題。同時(shí)也比較適合解決多峰問題，有助于逃離局部最優(yōu)解，求得全局最優(yōu)解。,7.2 自適應(yīng)GA,為了迎合GA搜索過程中的內(nèi)在動(dòng)態(tài)特性，因此根據(jù)搜索狀態(tài)自動(dòng)修正各個(gè)參數(shù)值。GA在各個(gè)階段對(duì)搜索的方向和力度有不同的要求?？偟恼f來，在初始階段應(yīng)在較廣的范圍內(nèi)進(jìn)行較粗的搜索，而在搜索后期，則應(yīng)該集中于某一較小區(qū)域進(jìn)行較細(xì)致的搜索。主要使用自適應(yīng)參數(shù)的是選擇和變異操作。,7.3 GA的二級(jí)參數(shù)控

16、制,基本思想是用一個(gè)GA去優(yōu)化另一個(gè)GA的各個(gè)參數(shù)。由于GA的各個(gè)參數(shù)相互關(guān)聯(lián)，而且參數(shù)對(duì)搜索進(jìn)程的影響并不十分明朗，即：GA的參數(shù)設(shè)置本身就是一個(gè)復(fù)雜的、人們不太了解的問題，而求解這類問題正是GA所擅長的。顯然，這種參數(shù)設(shè)計(jì)方式會(huì)很耗時(shí)間。同時(shí)，這種方法并沒有從根本上解決GA參數(shù)設(shè)計(jì)難題。,7.4 各種混合GA,將GA同其它算法結(jié)合起來，揚(yáng)長避短，以尋求更高的搜索效率。針對(duì)性較強(qiáng)，不具有普遍意義。,8 遺傳算法在控制工程中的應(yīng)用

17、,8.1 控制器設(shè)計(jì)8.2 系統(tǒng)辨識(shí)8.3 其他,8.1 控制器設(shè)計(jì),基于GA的控制器設(shè)計(jì)主要是指控制器的參數(shù)優(yōu)化（也有利用GA設(shè)計(jì)控制器的結(jié)構(gòu)）。對(duì)于復(fù)雜的控制系統(tǒng)，通常難以在控制器參數(shù)與控制性能指標(biāo)之間建立準(zhǔn)確的數(shù)學(xué)聯(lián)系，這也就為GA提供了施展本領(lǐng)的舞臺(tái)，即：以某些性能指標(biāo)為目標(biāo)函數(shù)（單目標(biāo)或多目標(biāo)），利用GA搜索最佳的參數(shù)組合。但是由于GA求解時(shí)間較長，限制了這種方法的在線應(yīng)用。,8.2 系統(tǒng)辨識(shí),在系統(tǒng)辨識(shí)中，GA可以用