0遺傳算法的基本原理遺傳算法將問題的求解表示成“染色體”（用編碼表示字符串）。該算法從一群“染色體”串出發(fā)，將它們置于問題的“環(huán)境”中，根據(jù)適者生存的原則，從中選擇出適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，通過交叉、變異兩種基因操作產(chǎn)生出新的一代更適應(yīng)環(huán)境的“染色體”種群。隨著算法的運(yùn)行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個(gè)體。

0遺傳算法的基本原理遺傳算法將問題的求解表示成“染色體1遺傳算法的基本原理1遺傳算法的基本原理2遺傳算法的基本原理2遺傳算法的基本原理3遺傳算法的基本原理常規(guī)的尋優(yōu)方法主要有三種類型：解析法：間接法是通過讓目標(biāo)函數(shù)的梯度為零，進(jìn)而求解一組非線性方程來尋求局部極值。直接法是使梯度信息按最陡的方向逐次運(yùn)動(dòng)來尋求局部極值，它即為通常所稱的爬山法。

枚舉法：可尋找到全局極值，不需要目標(biāo)函數(shù)連續(xù)光滑。

隨機(jī)法：搜索空間中隨機(jī)地漫游并隨時(shí)記錄下所取得的最好結(jié)果。

3遺傳算法的基本原理常規(guī)的尋優(yōu)方法主要有三種類型：4遺傳算法的特點(diǎn)1)遺傳算法是對參數(shù)的編碼進(jìn)行操作，而不是對參數(shù)本身；

2)遺傳算法是從許多初始點(diǎn)開始并行操作，因而可以有效地防止搜索過程收斂于局部最優(yōu)解，而且有較大的可能求得全部最優(yōu)解；

3)遺傳算法通過目標(biāo)函數(shù)來計(jì)算適配度，而不需要其它的推導(dǎo)和附屬信息，從而對問題的依賴性較??；

4)遺傳算法使用概率的轉(zhuǎn)變規(guī)則，而不是確定性的規(guī)則；

5)遺傳算法在解空間內(nèi)不是盲目地窮舉或完全隨機(jī)測試，而是一種啟發(fā)式搜索，其搜索效率往往優(yōu)于其它方法；

6)遺傳算法對于待尋優(yōu)的函數(shù)基本無限制，因而應(yīng)用范圍很廣；

7)遺傳算法更適合大規(guī)模復(fù)雜問題的優(yōu)化。

4遺傳算法的特點(diǎn)1)遺傳算法是對參數(shù)的編碼進(jìn)行操作，而不是對5函數(shù)優(yōu)化組合優(yōu)化生產(chǎn)調(diào)度自動(dòng)控制機(jī)器人學(xué)圖像處理機(jī)器視覺遺傳算法的應(yīng)用5函數(shù)優(yōu)化遺傳算法的應(yīng)用66.2遺傳算法的基本操作與模式理論

設(shè)需要求解的優(yōu)化問題為尋找當(dāng)自變量x在0～31之間取整數(shù)值時(shí)函數(shù)f(x)=x2的最大值。

第一步：準(zhǔn)備工作“染色體”串的編碼采用二進(jìn)制數(shù)來對其進(jìn)行編碼，可用5位數(shù)來表示。例如01010對應(yīng)x=10，11111對應(yīng)x=31。

初始種群的產(chǎn)生

設(shè)種群大小為4，即含有4個(gè)個(gè)體，則需按位隨機(jī)生成4個(gè)5位二進(jìn)制串：

01101、11000、01000、10011

66.2遺傳算法的基本操作與模式理論7復(fù)制操作

復(fù)制(Copy)亦稱再生(Reproduction)或選擇(Selection)，復(fù)制過程是個(gè)體串按照它們的適配度進(jìn)行復(fù)制。本例中目標(biāo)函數(shù)值即可用作適配度。

按照適配度進(jìn)行串復(fù)制的含義是適配度越大的串，在下一代中將有更多的機(jī)會提供一個(gè)或多個(gè)子孫。

遺傳算法的基本操作7復(fù)制操作復(fù)制(Copy)亦稱再生(Reproductio8種群的初始串及對應(yīng)的適配度

序號串X值適配度占整體的百分?jǐn)?shù)%期望的復(fù)制數(shù)實(shí)際得到的復(fù)制數(shù)1011011316914.40.582110002457649.21.973010008645.50.224100111936130.91.23總計(jì)1170100.04.00平均29325.01.00最大值57649.01.97復(fù)制操作

遺傳算法的基本操作8種群的初始串及對應(yīng)的適配度序號串X值適配度占整體的百分9經(jīng)復(fù)制后的新的種群為01101110001100010011串1被復(fù)制了一次串2被復(fù)制了兩次串3被淘汰串4也被復(fù)制了一次復(fù)制操作

遺傳算法的基本操作9經(jīng)復(fù)制后的新的種群為01101復(fù)制操作遺傳算法的基本操作10種群的初始串及對應(yīng)的適配度

序號串X值適配度占整體的百分?jǐn)?shù)%期望的復(fù)制數(shù)實(shí)際得到的復(fù)制數(shù)1011011316914.40.5812110002457649.21.9723010008645.50.2204100111936130.91.231總計(jì)1170100.04.004平均29325.01.001最大值57649.01.97210種群的初始串及對應(yīng)的適配度序號串X值適配度占整體的百11交叉(Crossover)操作可分為兩步：第一步—將新復(fù)制產(chǎn)生的匹配池中的成員隨機(jī)兩兩匹配。第二步—進(jìn)行交叉繁殖。設(shè)串的長度為l，則串的l個(gè)數(shù)字位之間的空隙標(biāo)記為1，2，…，l-１。隨機(jī)地從[1，l-1]中選取一整數(shù)位置k，則將兩個(gè)父母串中從位置k到串末尾的子串互相交換，而形成兩個(gè)新串。交叉操作

遺傳算法的基本操作11交叉(Crossover)操作可分為兩步：交叉操作遺12本例中初始種群的兩個(gè)個(gè)體

假定從１到４間選取隨機(jī)數(shù)，得到k＝４，那么經(jīng)過交叉操作之后將得到如下兩個(gè)新串交叉操作

遺傳算法的基本操作12本例中初始種群的兩個(gè)個(gè)體交叉操作遺傳算法的基本操作13新串號匹配池匹配對象交叉點(diǎn)新種群x值適配度f(x)101101240110012144211000141100125625311000421101127729410011321000016256總計(jì)1754平均439最大值729交叉操作

13新串號匹配池匹配交叉點(diǎn)新種群x值適配度1011012403遺傳算法的實(shí)現(xiàn)與改進(jìn)浮點(diǎn)數(shù)編碼某些子串模式(schemata)在遺傳算法的運(yùn)行中起著關(guān)鍵的作用。按照適配度進(jìn)行串復(fù)制的含義是適配度越大的串，在下一代中將有更多的機(jī)會提供一個(gè)或多個(gè)子孫。1)遺傳算法是對參數(shù)的編碼進(jìn)行操作，而不是對參數(shù)本身；2）新適應(yīng)度最大值F’max是原適應(yīng)度最大值的倍數(shù)；交叉概率為=0.可見，對于高于平均適配度的模式數(shù)量將呈指數(shù)形式增長。隨機(jī)法：搜索空間中隨機(jī)地漫游并隨時(shí)記錄下所取得的最4）確定式采樣選擇3)根據(jù)最佳串給出實(shí)際問題的最優(yōu)解。按照個(gè)體的排序序位k計(jì)算個(gè)體的適配度，計(jì)算公式1）神經(jīng)網(wǎng)絡(luò)控制器的結(jié)構(gòu)設(shè)計(jì)其次數(shù)為4，記為O(H)=4。14變異(Mutation)是以很小的概率隨機(jī)地改變一個(gè)串位的值。變異的概率通常是很小的，一般只有千分之幾。變異操作相對于復(fù)制和交叉操作而言，是處于相對次要的地位，其目的是為了防止丟失一些有用的遺傳因子，變異操作可以起到恢復(fù)串位多樣性的作用。

變異操作

遺傳算法的基本操作3遺傳算法的實(shí)現(xiàn)與改進(jìn)14變異(Mutation)是以很小15

在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。種群的平均適配度從293增至439，最大的適配度從575增至729。可見每經(jīng)過這祥的一次遺傳算法步驟，問題的解便朝著最優(yōu)解方向前進(jìn)了一步。遺傳算法的基本操作15在經(jīng)過一次復(fù)制、交叉和變異操作后，16編碼初始種群生成適應(yīng)度評價(jià)遺傳算子選擇運(yùn)算交叉運(yùn)算變異運(yùn)算基本遺傳算法的運(yùn)行參數(shù)種群大小、進(jìn)化代數(shù)、交叉概率、變異概率遺傳算法的基本操作16編碼遺傳算法的基本操作17遺傳算法的基本操作17遺傳算法的基本操作18遺傳算法的基本操作編碼把一個(gè)問題的解空間轉(zhuǎn)化到遺傳算法的搜索空間的過程就稱為編碼。二進(jìn)制編碼浮點(diǎn)數(shù)編碼符號編碼18遺傳算法的基本操作編碼把一個(gè)問題的解空間轉(zhuǎn)化到遺傳算19編碼遺傳算法的基本操作練習(xí)：175、176的二進(jìn)制編碼19編碼遺傳算法的基本操作練習(xí)：175、176的二進(jìn)制編碼20二進(jìn)制編碼的特點(diǎn)

1）編碼、解碼操作簡單

2）交叉、變異等遺傳操作便于實(shí)現(xiàn)；

3）便于利用模式定理對算法進(jìn)行理論分析

4）對于連續(xù)問題局部搜索能力差遺傳算法的基本操作20二進(jìn)制編碼的特點(diǎn)遺傳算法的基本操作21編碼-格雷碼編碼方法遺傳算法的基本操作假設(shè)有一個(gè)二進(jìn)制編碼為B=bmbm-1…b2b1和其對應(yīng)的格雷碼為G=gmgm-1…g2g1,則由二進(jìn)制編碼轉(zhuǎn)換到格雷碼的公式為：由格雷碼轉(zhuǎn)換到二進(jìn)制編碼的公式為：21編碼-格雷碼編碼方法遺傳算法的基本操作假設(shè)有一個(gè)二進(jìn)制編22編碼-格雷碼編碼方法遺傳算法的基本操作練習(xí)：175、176的格雷碼22編碼-格雷碼編碼方法遺傳算法的基本操作練習(xí)：175、123二進(jìn)制編碼存在的問題

1）連續(xù)空間離散化帶來的誤差；舉例：用二進(jìn)制編碼處理100個(gè)決策變量的優(yōu)化問題，每個(gè)變量的取值范圍為[-100,100],要求精確到小數(shù)點(diǎn)后5位，每個(gè)決策變量需要的二進(jìn)制編碼位數(shù)為？遺傳算法的基本操作200/0.00001=20000000224=16777216225=3355443223二進(jìn)制編碼存在的問題遺傳算法的基本操作200/0.000這里每個(gè)代表一個(gè)二值特性(也稱為基因)。該算法從一群“染色體”串出發(fā)，將它們置于問題的“環(huán)境”中，根據(jù)適者生存的原則，從中選擇出適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，通過交叉、變異兩種基因操作產(chǎn)生出新的一代更適應(yīng)環(huán)境的“染色體”種群。用｛0,1,*}可以構(gòu)造出任意一種模式。引入兩個(gè)模式的屬性定義：模式次數(shù)和定義長度。在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高?？梢?，對于那些高于平均適配度且具有短的定義長度的模式將更多地出現(xiàn)在下一代中。遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)一個(gè)模式H的次數(shù)由O(H)表示，它等于模式中固定串位的個(gè)數(shù)。4遺傳算法在智能控制中的應(yīng)用2遺傳算法的基本操作與模式理論變異操作：將個(gè)體編碼串中的某些基因座上的基因值用該基因座上的其他等位基因來替代，從而形成新的個(gè)體。遺傳算法中的參數(shù)選擇一種是用完全隨機(jī)的方法產(chǎn)生。其中*是通配符，它既可代表“1”，也可代表“0”。24浮點(diǎn)數(shù)編碼個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來表示，個(gè)體的編碼長度等于其決策變量的個(gè)數(shù)。舉例：有一個(gè)5個(gè)決策變量的優(yōu)化問題，一個(gè)基因型為：

X=[5.2，2.6,3.5,6.8,9.0]T遺傳算法的基本操作這里每個(gè)代表一個(gè)二值特性(也稱為基因)。24浮點(diǎn)數(shù)編碼遺25遺傳算法的基本操作符號編碼方法25遺傳算法的基本操作符號編碼方法26初始種群的產(chǎn)生

產(chǎn)生初始種群的方法通常有兩種：一種是用完全隨機(jī)的方法產(chǎn)生。例如用隨機(jī)數(shù)發(fā)生器來產(chǎn)生。設(shè)要操作的二進(jìn)制字串總共p位，設(shè)初始種群取n個(gè)樣本（n<），可在0～之間隨機(jī)地產(chǎn)生n個(gè)數(shù)，則該n個(gè)整數(shù)所對應(yīng)的二進(jìn)制表示即為要求的n個(gè)初始樣本。隨機(jī)產(chǎn)生樣本的方法適于對問題的解無任何先驗(yàn)知識的情況。另一種產(chǎn)生初始種群的方法是，對于具有某些先驗(yàn)知識的情況，可首先將這些先驗(yàn)知識轉(zhuǎn)變?yōu)楸仨殱M足的一組要求，然后在滿足這些要求的解中再隨機(jī)地選取樣本。這樣選擇初始種群可使遺傳算法更快地到達(dá)最優(yōu)解。遺傳算法的基本操作26初始種群的產(chǎn)生產(chǎn)生初始種群的方法通常有兩種：遺傳算法的27適應(yīng)度評價(jià)遺傳算法的基本操作27適應(yīng)度評價(jià)遺傳算法的基本操作28適應(yīng)度評價(jià)遺傳算法的基本操作28適應(yīng)度評價(jià)遺傳算法的基本操作29適應(yīng)度尺度變換遺傳算法的基本操作1）起始階段的早熟問題

2）后期的競爭力喪失問題尺度變換的方法：

1）線性尺度變換

2）乘冪尺度變換

3）指數(shù)尺度變換29適應(yīng)度尺度變換遺傳算法的基本操作1）起始階段的早熟問30線性尺度變換遺傳算法的基本操作條件：

1）新適應(yīng)度平均值與原適應(yīng)度平均值一致；

2）新適應(yīng)度最大值F’max是原適應(yīng)度最大值的倍數(shù)；變換后：優(yōu)良個(gè)體適應(yīng)度降低，較差個(gè)體適應(yīng)度增加。30線性尺度變換遺傳算法的基本操作條件：31乘冪尺度變換遺傳算法的基本操作

F’=Fk指數(shù)尺度變換

F’=exp(-bF)31乘冪尺度變換遺傳算法的基本操作F’=Fk指數(shù)尺度變32遺傳算法的基本操作選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高的個(gè)體將有更多機(jī)會遺傳到下一代。選擇算子就是對種群中的個(gè)體進(jìn)行優(yōu)勝劣汰操作，適應(yīng)度高的個(gè)體被遺傳到下一代的概率大，反之亦然。

1）比例選擇

2）隨機(jī)遍歷抽樣法

3）最優(yōu)保存策略

4）確定式采樣選擇

5）排序選擇

6）隨機(jī)聯(lián)賽選擇32遺傳算法的基本操作選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高33遺傳算法的基本操作比例選擇

輪盤賭圖

適應(yīng)度最大的個(gè)體有可能不被選中。33遺傳算法的基本操作比例選擇輪盤賭圖適應(yīng)度最大的個(gè)3遺傳算法的實(shí)現(xiàn)與改進(jìn)1)遺傳算法是對參數(shù)的編碼進(jìn)行操作，而不是對參數(shù)本身；模型輸出與樣本輸出之間的誤差作為個(gè)體評價(jià)測度。是整個(gè)種群的平均適配度。解的編碼方法采用二進(jìn)制編碼，3個(gè)參數(shù)變量每個(gè)對應(yīng)一個(gè)7位二進(jìn)制串，則每個(gè)參數(shù)變量范圍內(nèi)有128個(gè)可能值；在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。第一步—將新復(fù)制產(chǎn)生的匹配池中的成員隨機(jī)兩兩匹配。均勻交叉：每個(gè)基因座上的個(gè)體都以相同的概率進(jìn)行交換形成新的個(gè)體。模型的輸入激勵(lì)采用單位階躍函數(shù)。一種是用完全隨機(jī)的方法產(chǎn)生。種群的初始串及對應(yīng)的適配度在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。種群的大小為n=50；選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高的個(gè)體將有更多機(jī)會遺傳到下一代。34遺傳算法的基本操作3遺傳算法的實(shí)現(xiàn)與改進(jìn)34遺傳算法的基本操作35遺傳算法的基本操作35遺傳算法的基本操作36隨機(jī)遍歷抽樣法:為需要選擇的個(gè)體數(shù)目等距離的選擇個(gè)體.遺傳算法的基本操作36隨機(jī)遍歷抽樣法:為需要選擇的個(gè)體數(shù)目等距離的選擇個(gè)體.遺37遺傳算法的基本操作最優(yōu)保存策略-穩(wěn)態(tài)復(fù)制目標(biāo)：選擇、變異和交叉操作的隨機(jī)性會破壞種群中最優(yōu)良的個(gè)體，降低適應(yīng)度、運(yùn)行效率和收斂性。因此，應(yīng)用最優(yōu)保存策略進(jìn)化模型進(jìn)行選擇，使優(yōu)良個(gè)體不參加交叉、變異運(yùn)算。操作過程：37遺傳算法的基本操作最優(yōu)保存策略-穩(wěn)態(tài)復(fù)制目標(biāo)：選擇、變異38遺傳算法的基本操作排序選擇著眼于個(gè)體適應(yīng)度的大小關(guān)系，而與正負(fù)無關(guān)。舉例38遺傳算法的基本操作排序選擇著眼于個(gè)體適應(yīng)度的大小關(guān)系，而39遺傳算法的基本操作39遺傳算法的基本操作40遺傳算法的基本操作隨機(jī)聯(lián)賽選擇也是基于個(gè)體適應(yīng)度大小關(guān)系的選擇方式。基本思想：每次選取幾個(gè)個(gè)體對適應(yīng)度進(jìn)行比較，適應(yīng)度最大的個(gè)體遺傳到下一代種群中。進(jìn)行聯(lián)賽的個(gè)體一般每次選擇2個(gè)。重復(fù)進(jìn)行M次，新一代種群就產(chǎn)生。40遺傳算法的基本操作隨機(jī)聯(lián)賽選擇也是基于個(gè)體適應(yīng)度大小41交叉操作：遺傳算法中的交叉運(yùn)算是指兩個(gè)相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉概率的選擇并不是配對后的染色體對一定會交叉。操作時(shí)只有隨機(jī)數(shù)大于交叉概率的個(gè)體才進(jìn)行交叉。交叉概率選擇原則：

1）不要太多破壞個(gè)體編碼串中優(yōu)良性狀個(gè)體模式。

2）能有效產(chǎn)生一些新個(gè)體。

遺傳算法的基本操作41交叉操作：遺傳算法中的交叉運(yùn)算是指兩個(gè)相互配對的染色體按42單點(diǎn)交叉：隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，交換自交叉點(diǎn)到編碼串尾部的染色體。雙點(diǎn)交叉：隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)；交叉兩個(gè)隨機(jī)點(diǎn)之間的部分染色體遺傳算法的基本操作42單點(diǎn)交叉：隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，交換自交叉點(diǎn)到編碼串尾部的43多點(diǎn)交叉遺傳算法的基本操作43多點(diǎn)交叉遺傳算法的基本操作44均勻交叉：每個(gè)基因座上的個(gè)體都以相同的概率進(jìn)行交換形成新的個(gè)體。遺傳算法的基本操作44均勻交叉：每個(gè)基因座上的個(gè)體都以相同的概率進(jìn)行交換形成新其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-1=4。對神經(jīng)網(wǎng)絡(luò)的所有權(quán)值和閾值采用10進(jìn)制編碼，每個(gè)參數(shù)的變化范圍為[-10，10]，種群規(guī)模為n=50，交叉概率為=0.基本位變異：以變異概率Pm隨機(jī)指定某一位或某幾位基因座上的基因值進(jìn)行變異。選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高的個(gè)體將有更多機(jī)會遺傳到下一代。225=33554432例如串11111是個(gè)模式的成員，因?yàn)樗梢耘c每個(gè)串位是1或*的任一模式相匹配。假設(shè)有一個(gè)二進(jìn)制編碼為B=bmbm-1…b2b1和其對應(yīng)的格雷碼為G=gmgm-1…g2g1,則由二進(jìn)制編碼轉(zhuǎn)換到格雷碼的公式為：交叉操作：遺傳算法中的交叉運(yùn)算是指兩個(gè)相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化按照個(gè)體的排序序位k計(jì)算個(gè)體的適配度，計(jì)算公式種群的初始串及對應(yīng)的適配度初始種群的產(chǎn)生設(shè)種群大小為4，即含有4個(gè)個(gè)體，則需按位隨機(jī)生成4個(gè)5位二進(jìn)制串：對于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此總共有種模式。其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-1=4。45算數(shù)交叉：由兩個(gè)個(gè)體線性組合產(chǎn)生新的個(gè)體。遺傳算法的基本操作其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-46變異操作：將個(gè)體編碼串中的某些基因座上的基因值用該基因座上的其他等位基因來替代，從而形成新的個(gè)體。作用：

(1)改善遺傳算法局部搜索能力

(2)維持種群多樣性，防止早熟二進(jìn)制編碼的變異操作（個(gè)體在變異位上的基因值取反）浮點(diǎn)數(shù)編碼的變異操作（隨機(jī)數(shù)替換）符號編碼的變異操作（隨機(jī)字符替換）遺傳算法的基本操作46變異操作：將個(gè)體編碼串中的某些基因座上的基因值用該基因座47基本位變異：以變異概率Pm隨機(jī)指定某一位或某幾位基因座上的基因值進(jìn)行變異。

01001100——選中第4位——01011100

均勻變異：遺傳算法的基本操作47基本位變異：以變異概率Pm隨機(jī)指定某一位或某幾位基因座上48遺傳算法的基本操作48遺傳算法的基本操作49遺傳算法的模式理論

某些子串模式(schemata)在遺傳算法的運(yùn)行中起著關(guān)鍵的作用。比如一個(gè)問題中，樣本串第1位的“1”使得適配度比較大，首位為“1”的子串可以表示成這樣的模式：1****其中*是通配符，它既可代表“1”，也可代表“0”。用｛0,

1,*}可以構(gòu)造出任意一種模式。

49遺傳算法的模式理論某些子串模式(schemata)在遺50稱一個(gè)模式與一個(gè)特定的串相匹配是指：該模式中的1與串中的1相匹配模式中的0與串中的0相匹配模式中的*可以匹配串中的0或1例如模式00*00匹配兩個(gè)串：00100，00000模式*11*0匹配四個(gè)串：01100，01110，11100，11110遺傳算法的模式理論

50稱一個(gè)模式與一個(gè)特定的串相匹配是指：遺傳算法的模式理論51對于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此總共有種模式。對一般的問題，若串的基為k，長度為l，則總共有種模式?？梢娔Ｊ降臄?shù)量要大于串的數(shù)量。

遺傳算法的模式理論

51對于前面例子中的5位字串，由于模式的每一位可取0、1或*52一般地，一個(gè)串中包含種模式。例如串11111是個(gè)模式的成員，因?yàn)樗梢耘c每個(gè)串位是1或*的任一模式相匹配。因此，對于大小為n的種群則包含有到n×種模式。設(shè)一個(gè)7位二進(jìn)制串可以用如下的符號來表示這里每個(gè)代表一個(gè)二值特性(也稱為基因)。

遺傳算法的模式理論

52一般地，一個(gè)串中包含種模式。例如串11111是個(gè)模式53引入兩個(gè)模式的屬性定義：模式次數(shù)和定義長度。一個(gè)模式H的次數(shù)由O(H)表示，它等于模式中固定串位的個(gè)數(shù)。例如模式H＝011*1**，其次數(shù)為4，記為O(H)=4。模式H的長度定義為模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離，用符號(H)表示。例如模式H＝011*1**，其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-1=4。若模式H＝******0，則(H)=0。

遺傳算法的模式理論

53引入兩個(gè)模式的屬性定義：模式次數(shù)和定義長度。遺傳算法的模54復(fù)制對模式的影響在某一世代t，種群A(t)包含有m個(gè)特定模式H，記為m=m(H,t)在復(fù)制過程中，A(t)中的任何一個(gè)串以概率被選中進(jìn)行復(fù)制。因此可以期望在復(fù)制完成后，在t+1世代，特定模式H的數(shù)量將變?yōu)?/p>

或?qū)懗桑ǎ保┢渲衒(H)表示在世代t時(shí)對應(yīng)于模式H

的串的平均適配度。是整個(gè)種群的平均適配度。54復(fù)制對模式的影響在某一世代t，種群A(t)包含有m個(gè)特55為了進(jìn)一步分析高于平均適配度的模式數(shù)量增長，設(shè)

c>0則上面的方程可改寫為如下的差分方程假定c為常數(shù)，可得

(2)

可見，對于高于平均適配度的模式數(shù)量將呈指數(shù)形式增長。

復(fù)制對模式的影響55為了進(jìn)一步分析高于平均適配度的模式數(shù)量增長，設(shè)復(fù)制對模式56交叉過程是串之間的有組織的然而又是隨機(jī)的信息交換，它在創(chuàng)建新結(jié)構(gòu)的同時(shí)，最低限度地破壞復(fù)制過程所選擇的高適配度模式?？疾煲粋€(gè)l＝7的串以及此串所包含的兩個(gè)代表模式。A＝0111000

交叉對模式的影響56交叉過程是串之間的有組織的然而又是隨機(jī)的信息交換，它在創(chuàng)57推廣到一般情況，可以計(jì)算出任何模式的交叉存活概率的下限為中大于號表示當(dāng)交叉點(diǎn)落入定義長度內(nèi)時(shí)也存在模式不被破壞的可能性。

一般情況若設(shè)交叉的概率，則上式變?yōu)?/p>

(3)交叉對模式的影響57推廣到一般情況，可以計(jì)算出任何模式的交叉存活概率的下限為58若綜合考慮復(fù)制和交叉的影響，特定模式在下一代中的數(shù)量可用下式來估計(jì)

(4)可見，對于那些高于平均適配度且具有短的定義長度的模式將更多地出現(xiàn)在下一代中。

交叉對模式的影響58若綜合考慮復(fù)制和交叉的影響，特定模式在下一代中的數(shù)量可用59變異對模式的影響59變異對模式的影響60綜合考慮上述復(fù)制、交叉及變異操作，可得特定模式H的數(shù)量改變?yōu)?/p>

(6)遺傳算法的模式理論

60綜合考慮上述復(fù)制、交叉及變異操作，可得特定模式H的數(shù)量改616.3遺傳算法的實(shí)現(xiàn)與改進(jìn)

根據(jù)具體問題特點(diǎn)可采用不同的編碼方式，其中二進(jìn)制編碼是最常用的編碼方式。一般包括以下幾個(gè)步驟：

1)根據(jù)具體問題確定待尋優(yōu)的參數(shù)；

2)對每一個(gè)參數(shù)確定它的變化范圍，并用一個(gè)二進(jìn)制數(shù)來表示。例如若參數(shù)a的變化范圍為，用一位二進(jìn)制數(shù)b來表示，則二者之間滿足3)將所有表示參數(shù)的二進(jìn)制數(shù)串接起來組成一個(gè)長的二進(jìn)制字串。該字串的每一位只有0或1兩種取值。該字串即為遺傳算法可以操作的對象。編碼問題616.3遺傳算法的實(shí)現(xiàn)與改進(jìn)根據(jù)具體問題特62遺傳算法的操作步驟

利用遺傳算法解決一個(gè)具體的優(yōu)化問題，一般分為三個(gè)步驟：1)準(zhǔn)備工作

(1)確定有效且通用的編碼方法，將問題的可能解編碼成有限位的字符串；

(2)定義一個(gè)適應(yīng)度函數(shù)，用以測量和評價(jià)各解的性能；

(3)確定遺傳算法所使用的各參數(shù)的取值，如種群規(guī)模n，交叉概率，變異概率等等。6.3遺傳算法的實(shí)現(xiàn)與改進(jìn)62遺傳算法的操作步驟利用遺傳算法解決一個(gè)具體63遺傳算法的操作步驟2)遺傳算法搜索最佳串

(1)t=0，隨機(jī)產(chǎn)生初始種群A(0)；

(2)計(jì)算各串的適配度，；

(3)根據(jù)對種群進(jìn)行復(fù)制操作，以概率對種群進(jìn)行交叉操作，以概率對種群進(jìn)行變異操作，經(jīng)過三種操作產(chǎn)生新的種群；

(4)t=t+1，計(jì)算各串的適配度；

(5)當(dāng)連續(xù)幾代種群的適配度變化小于某個(gè)事先設(shè)定的值時(shí)，認(rèn)為終止條件滿足，若不滿足返回(3)；

(6)找出最佳串，結(jié)束搜索。

6.3遺傳算法的實(shí)現(xiàn)與改進(jìn)63遺傳算法的操作步驟2)遺傳算法搜索最佳串6.3遺傳64遺傳算法的操作步驟3)根據(jù)最佳串給出實(shí)際問題的最優(yōu)解。

6.3遺傳算法的實(shí)現(xiàn)與改進(jìn)64遺傳算法的操作步驟3)根據(jù)最佳串給出實(shí)際問題的最優(yōu)解。65遺傳算法中的參數(shù)選擇

初始種群的大小n:選擇較大數(shù)目的初始種群可以同時(shí)處理更多的解，因此容易找到全局的最優(yōu)解，其缺點(diǎn)是增加了每次迭代所需要的時(shí)間。交叉概率pc：交叉概率的選擇決定了交叉操作的頻率。頻率越高，可以越快地收斂到最有希望的最優(yōu)解區(qū)域；但是太高的頻率也可能導(dǎo)致收斂于一個(gè)解。變異概率pm：變異概率通常只取較小的數(shù)值，一般為0.001～0.1。若選取高的變異率，一方面可以增加樣本模式的多樣性，另一方面可能引起不穩(wěn)定，但是若選取太小的變異概率，則可能難于找到全局的最優(yōu)解。

6.3遺傳算法的實(shí)現(xiàn)與改進(jìn)65遺傳算法中的參數(shù)選擇初始種群的大小n:66遺傳算法的改進(jìn)

(1)自適應(yīng)變異

:在交叉之前，以海明(Hamming)距離測定雙親基因碼的差異，根據(jù)測定值決定后代的變異概率。若雙親的差異較小，則選取較大的變異概率。

(2)優(yōu)秀個(gè)體保護(hù)法

：對于每代中一定數(shù)量的最優(yōu)個(gè)體，使之直接進(jìn)入下一代。這樣可以防止優(yōu)秀個(gè)體由于選擇、交叉或變異中的偶然因素而被破壞掉。

(3)移民法

：用交叉產(chǎn)生出的個(gè)體替換上一代中適應(yīng)度低的個(gè)體，繼而按移民的比例，引入新的外來個(gè)體來替換新一代中適應(yīng)度低的個(gè)體。

(4)分布式遺傳算法將總的群體分成若干子群，各子群將有略微不同的基因模式，各自的遺傳過程具有相對的獨(dú)立性和封閉性，另一方面，在各子群之間又以一定的比率定期地進(jìn)行優(yōu)良個(gè)體的遷移，使各子群能共享優(yōu)良的基因模式以防止某些子群向局部最優(yōu)方向收斂。

6.3遺傳算法的實(shí)現(xiàn)與改進(jìn)66遺傳算法的改進(jìn)(1)自適應(yīng)變異:在交67遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)

控制系統(tǒng)建模設(shè)定開環(huán)伺服電機(jī)系統(tǒng)模型微分方程式為6.4遺傳算法在智能控制中的應(yīng)用傳遞函數(shù)形式為其中，，其余3個(gè)參數(shù)為待求的優(yōu)化解。

67遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)控制系統(tǒng)建模6.4遺68遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)

6.4遺傳算法在智能控制中的應(yīng)用6.4.2.1控制系統(tǒng)建模

將遺傳算法應(yīng)用于該模型的辨識，方案如下：解的編碼方法采用二進(jìn)制編碼，3個(gè)參數(shù)變量每個(gè)對應(yīng)一個(gè)7位二進(jìn)制串，則每個(gè)參數(shù)變量范圍內(nèi)有128個(gè)可能值；

3個(gè)二進(jìn)制串級聯(lián)成一個(gè)用21位二進(jìn)制數(shù)表示的染色體串；種群的大小為n=50；復(fù)制操作采用排序復(fù)制；交叉概率為=0.6，變異概率為=0.01；模型的輸入激勵(lì)采用單位階躍函數(shù)。

68遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)6.4遺傳算法在智能控3遺傳算法的實(shí)現(xiàn)與改進(jìn)2）后期的競爭力喪失問題一般包括以下幾個(gè)步驟：3遺傳算法的實(shí)現(xiàn)與改進(jìn)遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化復(fù)制操作采用排序復(fù)制；(2)種群大小、進(jìn)化代數(shù)、交叉概率、變異概率單點(diǎn)交叉：隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，交換自交叉點(diǎn)到編碼串尾部的染色體。按照適配度進(jìn)行串復(fù)制的含義是適配度越大的串，在下一代中將有更多的機(jī)會提供一個(gè)或多個(gè)子孫。(3)移民法：用交叉產(chǎn)生出的個(gè)體替換上一代中適應(yīng)度低的個(gè)體，繼而按移民的比例，引入新的外來個(gè)體來替換新一代中適應(yīng)度低的個(gè)體?？梢姡瑢τ诟哂谄骄m配度的模式數(shù)量將呈指數(shù)形式增長。按照個(gè)體的排序序位k計(jì)算個(gè)體的適配度，計(jì)算公式進(jìn)行聯(lián)賽的個(gè)體一般每次選擇2個(gè)。遺傳算法的適配值取倒立擺系統(tǒng)的穩(wěn)定時(shí)間T（系統(tǒng)穩(wěn)定指擺角不超過±15o）。69遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)

6.4.2.1控制系統(tǒng)建模模型輸出與樣本輸出之間的誤差作為個(gè)體評價(jià)測度。

按照個(gè)體的排序序位k計(jì)算個(gè)體的適配度，計(jì)算公式經(jīng)遺傳算法優(yōu)化辨識，獲得最優(yōu)模型辨識參數(shù)為

3遺傳算法的實(shí)現(xiàn)與改進(jìn)69遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)70遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)

控制系統(tǒng)設(shè)計(jì)一種綜合反映系統(tǒng)穩(wěn)態(tài)和暫態(tài)響應(yīng)的簡單誤差函數(shù)為

將遺傳算法應(yīng)用于基于上述直流伺服電機(jī)辨識模型的控制器設(shè)計(jì)，獲得最優(yōu)控制器的傳遞函數(shù)為70遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)控制系統(tǒng)設(shè)計(jì)一種綜合反71遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)

控制系統(tǒng)設(shè)計(jì)經(jīng)遺傳算法優(yōu)化的直流伺服電機(jī)控制系統(tǒng)的階躍響應(yīng)

71遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)控制系統(tǒng)設(shè)計(jì)經(jīng)遺傳算法72遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化

將神經(jīng)網(wǎng)絡(luò)中所有神經(jīng)元的連接權(quán)值編碼成二進(jìn)制碼串或?qū)崝?shù)碼串表示的個(gè)體，隨機(jī)生成這些碼串的初始群體，即可進(jìn)行常規(guī)的遺傳算法優(yōu)化計(jì)算。每進(jìn)行一代計(jì)算后，將碼串解碼為權(quán)值構(gòu)成新的神經(jīng)網(wǎng)絡(luò)，通過對所有訓(xùn)練樣本進(jìn)行計(jì)算得到神經(jīng)網(wǎng)絡(luò)輸出的均方誤差從而確定每個(gè)個(gè)體的適應(yīng)度。經(jīng)過若干代計(jì)算，神經(jīng)網(wǎng)絡(luò)將進(jìn)化到誤差全局最小。6.4遺傳算法在智能控制中的應(yīng)用72遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化將神經(jīng)網(wǎng)73例6.1倒立擺的遺傳神經(jīng)網(wǎng)絡(luò)控制。設(shè)被控對象為圖示的單倒立擺系統(tǒng)遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化

其動(dòng)力學(xué)方程為73例6.1倒立擺的遺傳神經(jīng)網(wǎng)絡(luò)控制。設(shè)被控對象為圖示的74遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化

6.4遺傳算法在智能控制中的應(yīng)用控制系統(tǒng)采用下圖所示結(jié)構(gòu)，其中NNC為神經(jīng)網(wǎng)絡(luò)控制器，該控制器的輸入為θ、、x、，輸出為控制量u?？刂破鞑捎?層前饋神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)，為了避免陷入局部極小，采用遺傳算法確定網(wǎng)絡(luò)的權(quán)值。

74遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化6.4遺傳算法在智能控751）神經(jīng)網(wǎng)絡(luò)控制器的結(jié)構(gòu)設(shè)計(jì)神經(jīng)網(wǎng)絡(luò)輸入層有4個(gè)節(jié)點(diǎn)，分別對應(yīng)于4個(gè)輸入分量θ、、x、；輸出層設(shè)1個(gè)節(jié)點(diǎn)，對應(yīng)于控制量u；隱層設(shè)10個(gè)節(jié)點(diǎn)。遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化

6.4遺傳算法在智能控制中的應(yīng)用2）遺傳算法訓(xùn)練對神經(jīng)網(wǎng)絡(luò)的所有權(quán)值和閾值采用10進(jìn)制編碼，每個(gè)參數(shù)的變化范圍為[-10，10]，種群規(guī)模為n=50，交叉概率為=0.9，變異概率為=0.03。遺傳算法的適配值取倒立擺系統(tǒng)的穩(wěn)定時(shí)間T（系統(tǒng)穩(wěn)定指擺角不超過±15o）。751）神經(jīng)網(wǎng)絡(luò)控制器的結(jié)構(gòu)設(shè)計(jì)遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)76具體過程如下：(1)采用某種編碼方案對每個(gè)權(quán)值進(jìn)行編碼，隨機(jī)產(chǎn)生一組權(quán)值編碼；(2)計(jì)算神經(jīng)網(wǎng)絡(luò)的誤差函數(shù)，確定其適應(yīng)度的函數(shù)值，誤差值越大，適配值越??；(3)選擇若干適配值大的個(gè)體直接遺傳給下一代，其余按適配值確定的概率遺傳；(4)利用交叉、變異等操作處理當(dāng)前種群，產(chǎn)生下一代種群；(5)重復(fù)(2)～(3)，直到取得滿意解。

遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化

6.4遺傳算法在智能控制中的應(yīng)用76具體過程如下：遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化6.4遺77編碼初始種群生成適應(yīng)度評價(jià)遺傳算子選擇運(yùn)算交叉運(yùn)算變異運(yùn)算基本遺傳算法的運(yùn)行參數(shù)種群大小、進(jìn)化代數(shù)、交叉概率、變異概率遺傳算法的基本操作77編碼遺傳算法的基本操作78編碼-格雷碼編碼方法遺傳算法的基本操作練習(xí)：175、176的格雷碼78編碼-格雷碼編碼方法遺傳算法的基本操作練習(xí)：175、179適應(yīng)度尺度變換遺傳算法的基本操作1）起始階段的早熟問題

2）后期的競爭力喪失問題尺度變換的方法：

1）線性尺度變換

2）乘冪尺度變換

3）指數(shù)尺度變換79適應(yīng)度尺度變換遺傳算法的基本操作1）起始階段的早熟問80遺傳算法的基本操作選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高的個(gè)體將有更多機(jī)會遺傳到下一代。選擇算子就是對種群中的個(gè)體進(jìn)行優(yōu)勝劣汰操作，適應(yīng)度高的個(gè)體被遺傳到下一代的概率大，反之亦然。

1）比例選擇

2）隨機(jī)遍歷抽樣法

3）最優(yōu)保存策略

4）確定式采樣選擇

5）排序選擇

6）隨機(jī)聯(lián)賽選擇80遺傳算法的基本操作選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高81單點(diǎn)交叉：隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，交換自交叉點(diǎn)到編碼串尾部的染色體。雙點(diǎn)交叉：隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)；交叉兩個(gè)隨機(jī)點(diǎn)之間的部分染色體遺傳算法的基本操作81單點(diǎn)交叉：隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，交換自交叉點(diǎn)到編碼串尾部的3）指數(shù)尺度變換4）確定式采樣選擇4遺傳算法在智能控制中的應(yīng)用隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)；經(jīng)過若干代計(jì)算，神經(jīng)網(wǎng)絡(luò)將進(jìn)化到誤差全局最小。種群大小、進(jìn)化代數(shù)、交叉概率、變異概率復(fù)制操作采用排序復(fù)制；(3)移民法：用交叉產(chǎn)生出的個(gè)體替換上一代中適應(yīng)度低的個(gè)體，繼而按移民的比例，引入新的外來個(gè)體來替換新一代中適應(yīng)度低的個(gè)體。單點(diǎn)交叉：隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，交換自交叉點(diǎn)到編碼串尾部的染色體。對于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此總共有種模式。基本遺傳算法的運(yùn)行參數(shù)若選取高的變異率，一方面可以增加樣本模式的多樣性，另一方面可能引起不穩(wěn)定，但是若選取太小的變異概率，則可能難于找到全局的最優(yōu)解。由格雷碼轉(zhuǎn)換到二進(jìn)制編碼的公式為：3）最優(yōu)保存策略其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-1=4。82變異操作：將個(gè)體編碼串中的某些基因座上的基因值用該基因座上的其他等位基因來替代，從而形成新的個(gè)體。作用：

(1)改善遺傳算法局部搜索能力

(2)維持種群多樣性，防止早熟二進(jìn)制編碼的變異操作（個(gè)體在變異位上的基因值取反）浮點(diǎn)數(shù)編碼的變異操作（隨機(jī)數(shù)替換）符號編碼的變異操作（隨機(jī)字符替換）遺傳算法的基本操作3）指數(shù)尺度變換82變異操作：將個(gè)體編碼串中的某些基因座上的83基本位變異：以變異概率Pm隨機(jī)指定某一位或某幾位基因座上的基因值進(jìn)行變異。

01001100——選中第4位——01011100

均勻變異：遺傳算法的基本操作83基本位變異：以變異概率Pm隨機(jī)指定某一位或某幾位基因座上84遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)

控制系統(tǒng)設(shè)計(jì)經(jīng)遺傳算法優(yōu)化的直流伺服電機(jī)控制系統(tǒng)的階躍響應(yīng)

84遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)控制系統(tǒng)設(shè)計(jì)經(jīng)遺傳算法85遺傳算法的基本原理遺傳算法將問題的求解表示成“染色體”（用編碼表示字符串）。該算法從一群“染色體”串出發(fā)，將它們置于問題的“環(huán)境”中，根據(jù)適者生存的原則，從中選擇出適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，通過交叉、變異兩種基因操作產(chǎn)生出新的一代更適應(yīng)環(huán)境的“染色體”種群。隨著算法的運(yùn)行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個(gè)體。

0遺傳算法的基本原理遺傳算法將問題的求解表示成“染色體86遺傳算法的基本原理1遺傳算法的基本原理87遺傳算法的基本原理2遺傳算法的基本原理88遺傳算法的基本原理常規(guī)的尋優(yōu)方法主要有三種類型：解析法：間接法是通過讓目標(biāo)函數(shù)的梯度為零，進(jìn)而求解一組非線性方程來尋求局部極值。直接法是使梯度信息按最陡的方向逐次運(yùn)動(dòng)來尋求局部極值，它即為通常所稱的爬山法。

枚舉法：可尋找到全局極值，不需要目標(biāo)函數(shù)連續(xù)光滑。

隨機(jī)法：搜索空間中隨機(jī)地漫游并隨時(shí)記錄下所取得的最好結(jié)果。

3遺傳算法的基本原理常規(guī)的尋優(yōu)方法主要有三種類型：89遺傳算法的特點(diǎn)1)遺傳算法是對參數(shù)的編碼進(jìn)行操作，而不是對參數(shù)本身；

2)遺傳算法是從許多初始點(diǎn)開始并行操作，因而可以有效地防止搜索過程收斂于局部最優(yōu)解，而且有較大的可能求得全部最優(yōu)解；

3)遺傳算法通過目標(biāo)函數(shù)來計(jì)算適配度，而不需要其它的推導(dǎo)和附屬信息，從而對問題的依賴性較??；

4)遺傳算法使用概率的轉(zhuǎn)變規(guī)則，而不是確定性的規(guī)則；

5)遺傳算法在解空間內(nèi)不是盲目地窮舉或完全隨機(jī)測試，而是一種啟發(fā)式搜索，其搜索效率往往優(yōu)于其它方法；

6)遺傳算法對于待尋優(yōu)的函數(shù)基本無限制，因而應(yīng)用范圍很廣；

7)遺傳算法更適合大規(guī)模復(fù)雜問題的優(yōu)化。

4遺傳算法的特點(diǎn)1)遺傳算法是對參數(shù)的編碼進(jìn)行操作，而不是對90函數(shù)優(yōu)化組合優(yōu)化生產(chǎn)調(diào)度自動(dòng)控制機(jī)器人學(xué)圖像處理機(jī)器視覺遺傳算法的應(yīng)用5函數(shù)優(yōu)化遺傳算法的應(yīng)用916.2遺傳算法的基本操作與模式理論

設(shè)需要求解的優(yōu)化問題為尋找當(dāng)自變量x在0～31之間取整數(shù)值時(shí)函數(shù)f(x)=x2的最大值。

第一步：準(zhǔn)備工作“染色體”串的編碼采用二進(jìn)制數(shù)來對其進(jìn)行編碼，可用5位數(shù)來表示。例如01010對應(yīng)x=10，11111對應(yīng)x=31。

初始種群的產(chǎn)生

設(shè)種群大小為4，即含有4個(gè)個(gè)體，則需按位隨機(jī)生成4個(gè)5位二進(jìn)制串：

01101、11000、01000、10011

66.2遺傳算法的基本操作與模式理論92復(fù)制操作

復(fù)制(Copy)亦稱再生(Reproduction)或選擇(Selection)，復(fù)制過程是個(gè)體串按照它們的適配度進(jìn)行復(fù)制。本例中目標(biāo)函數(shù)值即可用作適配度。

按照適配度進(jìn)行串復(fù)制的含義是適配度越大的串，在下一代中將有更多的機(jī)會提供一個(gè)或多個(gè)子孫。

遺傳算法的基本操作7復(fù)制操作復(fù)制(Copy)亦稱再生(Reproductio93種群的初始串及對應(yīng)的適配度

序號串X值適配度占整體的百分?jǐn)?shù)%期望的復(fù)制數(shù)實(shí)際得到的復(fù)制數(shù)1011011316914.40.582110002457649.21.973010008645.50.224100111936130.91.23總計(jì)1170100.04.00平均29325.01.00最大值57649.01.97復(fù)制操作

遺傳算法的基本操作8種群的初始串及對應(yīng)的適配度序號串X值適配度占整體的百分94經(jīng)復(fù)制后的新的種群為01101110001100010011串1被復(fù)制了一次串2被復(fù)制了兩次串3被淘汰串4也被復(fù)制了一次復(fù)制操作

遺傳算法的基本操作9經(jīng)復(fù)制后的新的種群為01101復(fù)制操作遺傳算法的基本操作95種群的初始串及對應(yīng)的適配度

序號串X值適配度占整體的百分?jǐn)?shù)%期望的復(fù)制數(shù)實(shí)際得到的復(fù)制數(shù)1011011316914.40.5812110002457649.21.9723010008645.50.2204100111936130.91.231總計(jì)1170100.04.004平均29325.01.001最大值57649.01.97210種群的初始串及對應(yīng)的適配度序號串X值適配度占整體的百96交叉(Crossover)操作可分為兩步：第一步—將新復(fù)制產(chǎn)生的匹配池中的成員隨機(jī)兩兩匹配。第二步—進(jìn)行交叉繁殖。設(shè)串的長度為l，則串的l個(gè)數(shù)字位之間的空隙標(biāo)記為1，2，…，l-１。隨機(jī)地從[1，l-1]中選取一整數(shù)位置k，則將兩個(gè)父母串中從位置k到串末尾的子串互相交換，而形成兩個(gè)新串。交叉操作

遺傳算法的基本操作11交叉(Crossover)操作可分為兩步：交叉操作遺97本例中初始種群的兩個(gè)個(gè)體

假定從１到４間選取隨機(jī)數(shù)，得到k＝４，那么經(jīng)過交叉操作之后將得到如下兩個(gè)新串交叉操作

遺傳算法的基本操作12本例中初始種群的兩個(gè)個(gè)體交叉操作遺傳算法的基本操作98新串號匹配池匹配對象交叉點(diǎn)新種群x值適配度f(x)101101240110012144211000141100125625311000421101127729410011321000016256總計(jì)1754平均439最大值729交叉操作

13新串號匹配池匹配交叉點(diǎn)新種群x值適配度1011012403遺傳算法的實(shí)現(xiàn)與改進(jìn)浮點(diǎn)數(shù)編碼某些子串模式(schemata)在遺傳算法的運(yùn)行中起著關(guān)鍵的作用。按照適配度進(jìn)行串復(fù)制的含義是適配度越大的串，在下一代中將有更多的機(jī)會提供一個(gè)或多個(gè)子孫。1)遺傳算法是對參數(shù)的編碼進(jìn)行操作，而不是對參數(shù)本身；2）新適應(yīng)度最大值F’max是原適應(yīng)度最大值的倍數(shù)；交叉概率為=0.可見，對于高于平均適配度的模式數(shù)量將呈指數(shù)形式增長。隨機(jī)法：搜索空間中隨機(jī)地漫游并隨時(shí)記錄下所取得的最4）確定式采樣選擇3)根據(jù)最佳串給出實(shí)際問題的最優(yōu)解。按照個(gè)體的排序序位k計(jì)算個(gè)體的適配度，計(jì)算公式1）神經(jīng)網(wǎng)絡(luò)控制器的結(jié)構(gòu)設(shè)計(jì)其次數(shù)為4，記為O(H)=4。99變異(Mutation)是以很小的概率隨機(jī)地改變一個(gè)串位的值。變異的概率通常是很小的，一般只有千分之幾。變異操作相對于復(fù)制和交叉操作而言，是處于相對次要的地位，其目的是為了防止丟失一些有用的遺傳因子，變異操作可以起到恢復(fù)串位多樣性的作用。

變異操作

遺傳算法的基本操作3遺傳算法的實(shí)現(xiàn)與改進(jìn)14變異(Mutation)是以很小100

在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。種群的平均適配度從293增至439，最大的適配度從575增至729。可見每經(jīng)過這祥的一次遺傳算法步驟，問題的解便朝著最優(yōu)解方向前進(jìn)了一步。遺傳算法的基本操作15在經(jīng)過一次復(fù)制、交叉和變異操作后，101編碼初始種群生成適應(yīng)度評價(jià)遺傳算子選擇運(yùn)算交叉運(yùn)算變異運(yùn)算基本遺傳算法的運(yùn)行參數(shù)種群大小、進(jìn)化代數(shù)、交叉概率、變異概率遺傳算法的基本操作16編碼遺傳算法的基本操作102遺傳算法的基本操作17遺傳算法的基本操作103遺傳算法的基本操作編碼把一個(gè)問題的解空間轉(zhuǎn)化到遺傳算法的搜索空間的過程就稱為編碼。二進(jìn)制編碼浮點(diǎn)數(shù)編碼符號編碼18遺傳算法的基本操作編碼把一個(gè)問題的解空間轉(zhuǎn)化到遺傳算104編碼遺傳算法的基本操作練習(xí)：175、176的二進(jìn)制編碼19編碼遺傳算法的基本操作練習(xí)：175、176的二進(jìn)制編碼105二進(jìn)制編碼的特點(diǎn)

1）編碼、解碼操作簡單

2）交叉、變異等遺傳操作便于實(shí)現(xiàn)；

3）便于利用模式定理對算法進(jìn)行理論分析

4）對于連續(xù)問題局部搜索能力差遺傳算法的基本操作20二進(jìn)制編碼的特點(diǎn)遺傳算法的基本操作106編碼-格雷碼編碼方法遺傳算法的基本操作假設(shè)有一個(gè)二進(jìn)制編碼為B=bmbm-1…b2b1和其對應(yīng)的格雷碼為G=gmgm-1…g2g1,則由二進(jìn)制編碼轉(zhuǎn)換到格雷碼的公式為：由格雷碼轉(zhuǎn)換到二進(jìn)制編碼的公式為：21編碼-格雷碼編碼方法遺傳算法的基本操作假設(shè)有一個(gè)二進(jìn)制編107編碼-格雷碼編碼方法遺傳算法的基本操作練習(xí)：175、176的格雷碼22編碼-格雷碼編碼方法遺傳算法的基本操作練習(xí)：175、1108二進(jìn)制編碼存在的問題

1）連續(xù)空間離散化帶來的誤差；舉例：用二進(jìn)制編碼處理100個(gè)決策變量的優(yōu)化問題，每個(gè)變量的取值范圍為[-100,100],要求精確到小數(shù)點(diǎn)后5位，每個(gè)決策變量需要的二進(jìn)制編碼位數(shù)為？遺傳算法的基本操作200/0.00001=20000000224=16777216225=3355443223二進(jìn)制編碼存在的問題遺傳算法的基本操作200/0.000這里每個(gè)代表一個(gè)二值特性(也稱為基因)。該算法從一群“染色體”串出發(fā)，將它們置于問題的“環(huán)境”中，根據(jù)適者生存的原則，從中選擇出適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，通過交叉、變異兩種基因操作產(chǎn)生出新的一代更適應(yīng)環(huán)境的“染色體”種群。用｛0,1,*}可以構(gòu)造出任意一種模式。引入兩個(gè)模式的屬性定義：模式次數(shù)和定義長度。在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高?？梢姡瑢τ谀切└哂谄骄m配度且具有短的定義長度的模式將更多地出現(xiàn)在下一代中。遺傳算法用于控制系統(tǒng)建模與設(shè)計(jì)一個(gè)模式H的次數(shù)由O(H)表示，它等于模式中固定串位的個(gè)數(shù)。4遺傳算法在智能控制中的應(yīng)用2遺傳算法的基本操作與模式理論變異操作：將個(gè)體編碼串中的某些基因座上的基因值用該基因座上的其他等位基因來替代，從而形成新的個(gè)體。遺傳算法中的參數(shù)選擇一種是用完全隨機(jī)的方法產(chǎn)生。其中*是通配符，它既可代表“1”，也可代表“0”。109浮點(diǎn)數(shù)編碼個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來表示，個(gè)體的編碼長度等于其決策變量的個(gè)數(shù)。舉例：有一個(gè)5個(gè)決策變量的優(yōu)化問題，一個(gè)基因型為：

X=[5.2，2.6,3.5,6.8,9.0]T遺傳算法的基本操作這里每個(gè)代表一個(gè)二值特性(也稱為基因)。24浮點(diǎn)數(shù)編碼遺110遺傳算法的基本操作符號編碼方法25遺傳算法的基本操作符號編碼方法111初始種群的產(chǎn)生

產(chǎn)生初始種群的方法通常有兩種：一種是用完全隨機(jī)的方法產(chǎn)生。例如用隨機(jī)數(shù)發(fā)生器來產(chǎn)生。設(shè)要操作的二進(jìn)制字串總共p位，設(shè)初始種群取n個(gè)樣本（n<），可在0～之間隨機(jī)地產(chǎn)生n個(gè)數(shù)，則該n個(gè)整數(shù)所對應(yīng)的二進(jìn)制表示即為要求的n個(gè)初始樣本。隨機(jī)產(chǎn)生樣本的方法適于對問題的解無任何先驗(yàn)知識的情況。另一種產(chǎn)生初始種群的方法是，對于具有某些先驗(yàn)知識的情況，可首先將這些先驗(yàn)知識轉(zhuǎn)變?yōu)楸仨殱M足的一組要求，然后在滿足這些要求的解中再隨機(jī)地選取樣本。這樣選擇初始種群可使遺傳算法更快地到達(dá)最優(yōu)解。遺傳算法的基本操作26初始種群的產(chǎn)生產(chǎn)生初始種群的方法通常有兩種：遺傳算法的112適應(yīng)度評價(jià)遺傳算法的基本操作27適應(yīng)度評價(jià)遺傳算法的基本操作113適應(yīng)度評價(jià)遺傳算法的基本操作28適應(yīng)度評價(jià)遺傳算法的基本操作114適應(yīng)度尺度變換遺傳算法的基本操作1）起始階段的早熟問題

2）后期的競爭力喪失問題尺度變換的方法：

1）線性尺度變換

2）乘冪尺度變換

3）指數(shù)尺度變換29適應(yīng)度尺度變換遺傳算法的基本操作1）起始階段的早熟問115線性尺度變換遺傳算法的基本操作條件：

1）新適應(yīng)度平均值與原適應(yīng)度平均值一致；

2）新適應(yīng)度最大值F’max是原適應(yīng)度最大值的倍數(shù)；變換后：優(yōu)良個(gè)體適應(yīng)度降低，較差個(gè)體適應(yīng)度增加。30線性尺度變換遺傳算法的基本操作條件：116乘冪尺度變換遺傳算法的基本操作

F’=Fk指數(shù)尺度變換

F’=exp(-bF)31乘冪尺度變換遺傳算法的基本操作F’=Fk指數(shù)尺度變117遺傳算法的基本操作選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高的個(gè)體將有更多機(jī)會遺傳到下一代。選擇算子就是對種群中的個(gè)體進(jìn)行優(yōu)勝劣汰操作，適應(yīng)度高的個(gè)體被遺傳到下一代的概率大，反之亦然。

1）比例選擇

2）隨機(jī)遍歷抽樣法

3）最優(yōu)保存策略

4）確定式采樣選擇

5）排序選擇

6）隨機(jī)聯(lián)賽選擇32遺傳算法的基本操作選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高118遺傳算法的基本操作比例選擇

輪盤賭圖

適應(yīng)度最大的個(gè)體有可能不被選中。33遺傳算法的基本操作比例選擇輪盤賭圖適應(yīng)度最大的個(gè)3遺傳算法的實(shí)現(xiàn)與改進(jìn)1)遺傳算法是對參數(shù)的編碼進(jìn)行操作，而不是對參數(shù)本身；模型輸出與樣本輸出之間的誤差作為個(gè)體評價(jià)測度。是整個(gè)種群的平均適配度。解的編碼方法采用二進(jìn)制編碼，3個(gè)參數(shù)變量每個(gè)對應(yīng)一個(gè)7位二進(jìn)制串，則每個(gè)參數(shù)變量范圍內(nèi)有128個(gè)可能值；在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。第一步—將新復(fù)制產(chǎn)生的匹配池中的成員隨機(jī)兩兩匹配。均勻交叉：每個(gè)基因座上的個(gè)體都以相同的概率進(jìn)行交換形成新的個(gè)體。模型的輸入激勵(lì)采用單位階躍函數(shù)。一種是用完全隨機(jī)的方法產(chǎn)生。種群的初始串及對應(yīng)的適配度在經(jīng)過一次復(fù)制、交叉和變異操作后，最優(yōu)的和平均的目標(biāo)函數(shù)值均有所提高。種群的大小為n=50；選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高的個(gè)體將有更多機(jī)會遺傳到下一代。119遺傳算法的基本操作3遺傳算法的實(shí)現(xiàn)與改進(jìn)34遺傳算法的基本操作120遺傳算法的基本操作35遺傳算法的基本操作121隨機(jī)遍歷抽樣法:為需要選擇的個(gè)體數(shù)目等距離的選擇個(gè)體.遺傳算法的基本操作36隨機(jī)遍歷抽樣法:為需要選擇的個(gè)體數(shù)目等距離的選擇個(gè)體.遺122遺傳算法的基本操作最優(yōu)保存策略-穩(wěn)態(tài)復(fù)制目標(biāo)：選擇、變異和交叉操作的隨機(jī)性會破壞種群中最優(yōu)良的個(gè)體，降低適應(yīng)度、運(yùn)行效率和收斂性。因此，應(yīng)用最優(yōu)保存策略進(jìn)化模型進(jìn)行選擇，使優(yōu)良個(gè)體不參加交叉、變異運(yùn)算。操作過程：37遺傳算法的基本操作最優(yōu)保存策略-穩(wěn)態(tài)復(fù)制目標(biāo)：選擇、變異123遺傳算法的基本操作排序選擇著眼于個(gè)體適應(yīng)度的大小關(guān)系，而與正負(fù)無關(guān)。舉例38遺傳算法的基本操作排序選擇著眼于個(gè)體適應(yīng)度的大小關(guān)系，而124遺傳算法的基本操作39遺傳算法的基本操作125遺傳算法的基本操作隨機(jī)聯(lián)賽選擇也是基于個(gè)體適應(yīng)度大小關(guān)系的選擇方式?；舅枷耄好看芜x取幾個(gè)個(gè)體對適應(yīng)度進(jìn)行比較，適應(yīng)度最大的個(gè)體遺傳到下一代種群中。進(jìn)行聯(lián)賽的個(gè)體一般每次選擇2個(gè)。重復(fù)進(jìn)行M次，新一代種群就產(chǎn)生。40遺傳算法的基本操作隨機(jī)聯(lián)賽選擇也是基于個(gè)體適應(yīng)度大小126交叉操作：遺傳算法中的交叉運(yùn)算是指兩個(gè)相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉概率的選擇并不是配對后的染色體對一定會交叉。操作時(shí)只有隨機(jī)數(shù)大于交叉概率的個(gè)體才進(jìn)行交叉。交叉概率選擇原則：

1）不要太多破壞個(gè)體編碼串中優(yōu)良性狀個(gè)體模式。

2）能有效產(chǎn)生一些新個(gè)體。

遺傳算法的基本操作41交叉操作：遺傳算法中的交叉運(yùn)算是指兩個(gè)相互配對的染色體按127單點(diǎn)交叉：隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，交換自交叉點(diǎn)到編碼串尾部的染色體。雙點(diǎn)交叉：隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)；交叉兩個(gè)隨機(jī)點(diǎn)之間的部分染色體遺傳算法的基本操作42單點(diǎn)交叉：隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，交換自交叉點(diǎn)到編碼串尾部的128多點(diǎn)交叉遺傳算法的基本操作43多點(diǎn)交叉遺傳算法的基本操作129均勻交叉：每個(gè)基因座上的個(gè)體都以相同的概率進(jìn)行交換形成新的個(gè)體。遺傳算法的基本操作44均勻交叉：每個(gè)基因座上的個(gè)體都以相同的概率進(jìn)行交換形成新其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-1=4。對神經(jīng)網(wǎng)絡(luò)的所有權(quán)值和閾值采用10進(jìn)制編碼，每個(gè)參數(shù)的變化范圍為[-10，10]，種群規(guī)模為n=50，交叉概率為=0.基本位變異：以變異概率Pm隨機(jī)指定某一位或某幾位基因座上的基因值進(jìn)行變異。選擇操作進(jìn)化過程中對環(huán)境適應(yīng)度較高的個(gè)體將有更多機(jī)會遺傳到下一代。225=33554432例如串11111是個(gè)模式的成員，因?yàn)樗梢耘c每個(gè)串位是1或*的任一模式相匹配。假設(shè)有一個(gè)二進(jìn)制編碼為B=bmbm-1…b2b1和其對應(yīng)的格雷碼為G=gmgm-1…g2g1,則由二進(jìn)制編碼轉(zhuǎn)換到格雷碼的公式為：交叉操作：遺傳算法中的交叉運(yùn)算是指兩個(gè)相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。遺傳算法用于神經(jīng)網(wǎng)絡(luò)的權(quán)值優(yōu)化按照個(gè)體的排序序位k計(jì)算個(gè)體的適配度，計(jì)算公式種群的初始串及對應(yīng)的適配度初始種群的產(chǎn)生設(shè)種群大小為4，即含有4個(gè)個(gè)體，則需按位隨機(jī)生成4個(gè)5位二進(jìn)制串：對于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此總共有種模式。其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-1=4。130算數(shù)交叉：由兩個(gè)個(gè)體線性組合產(chǎn)生新的個(gè)體。遺傳算法的基本操作其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-131變異操作：將個(gè)體編碼串中的某些基因座上的基因值用該基因座上的其他等位基因來替代，從而形成新的個(gè)體。作用：

(1)改善遺傳算法局部搜索能力

(2)維持種群多樣性，防止早熟二進(jìn)制編碼的變異操作（個(gè)體在變異位上的基因值取反）浮點(diǎn)數(shù)編碼的變異操作（隨機(jī)數(shù)替換）符號編碼的變異操作（隨機(jī)字符替換）遺傳算法的基本操作46變異操作：將個(gè)體編碼串中的某些基因座上的基因值用該基因座132基本位變異：以變異概率Pm隨機(jī)指定某一位或某幾位基因座上的基因值進(jìn)行變異。

01001100——選中第4位——01011100

均勻變異：遺傳算法的基本操作47基本位變異：以變異概率Pm隨機(jī)指定某一位或某幾位基因座上133遺傳算法的基本操作48遺傳算法的基本操作134遺傳算法的模式理論

某些子串模式(schemata)在遺傳算法的運(yùn)行中起著關(guān)鍵的作用。比如一個(gè)問題中，樣本串第1位的“1”使得適配度比較大，首位為“1”的子串可以表示成這樣的模式：1****其中*是通配符，它既可代表“1”，也可代表“0”。用｛0,

1,*}可以構(gòu)造出任意一種模式。

49遺傳算法的模式理論某些子串模式(schemata)在遺135稱一個(gè)模式與一個(gè)特定的串相匹配是指：該模式中的1與串中的1相匹配模式中的0與串中的0相匹配模式中的*可以匹配串中的0或1例如模式00*00匹配兩個(gè)串：00100，00000模式*11*0匹配四個(gè)串：01100，01110，11100，11110遺傳算法的模式理論

50稱一個(gè)模式與一個(gè)特定的串相匹配是指：遺傳算法的模式理論136對于前面例子中的5位字串，由于模式的每一位可取0、1或*，因此總共有種模式。對一般的問題，若串的基為k，長度為l，則總共有種模式?？梢娔Ｊ降臄?shù)量要大于串的數(shù)量。

遺傳算法的模式理論

51對于前面例子中的5位字串，由于模式的每一位可取0、1或*137一般地，一個(gè)串中包含種模式。例如串11111是個(gè)模式的成員，因?yàn)樗梢耘c每個(gè)串位是1或*的任一模式相匹配。因此，對于大小為n的種群則包含有到n×種模式。設(shè)一個(gè)7位二進(jìn)制串可以用如下的符號來表示這里每個(gè)代表一個(gè)二值特性(也稱為基因)。

遺傳算法的模式理論

52一般地，一個(gè)串中包含種模式。例如串11111是個(gè)模式138引入兩個(gè)模式的屬性定義：模式次數(shù)和定義長度。一個(gè)模式H的次數(shù)由O(H)表示，它等于模式中固定串位的個(gè)數(shù)。例如模式H＝011*1**，其次數(shù)為4，記為O(H)=4。模式H的長度定義為模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離，用符號(H)表示。例如模式H＝011*1**，其中第一個(gè)確定位置是1，最后一個(gè)位置是5，所以(H)=5-1=4。若模式H＝******0，則(H)=0。

遺傳算法的模式理論

53引入兩個(gè)模式的屬性定義：模式次數(shù)和定義長度。遺傳算法的模139復(fù)制對模式的影響在某一世代t，種群A(t)包含有m個(gè)特定模式H，記為m=m(H,t)在復(fù)制過程中，A(t)中的任何一個(gè)串以概率被選中進(jìn)行復(fù)制。因此可以期望在復(fù)制完成后，在t+1世代，特定模式H的數(shù)量將變?yōu)?/p>

或?qū)懗桑ǎ保┢渲衒(H)表示在世代t時(shí)對應(yīng)于模式H

的串的平均適配度。是整個(gè)種群的平均適配度。54復(fù)制對模式的影響在某一世代t，種群A(t)包含有m個(gè)特140為了進(jìn)一步分析高于平均適配度的模式數(shù)量增長，設(shè)

c>0則上面的方程可改寫為如下的差分方程假定c為常數(shù)，可得

(2)

可見，對于高于平均適配度的模式數(shù)量將呈指數(shù)形式增長。

復(fù)制對模式的影響55為了進(jìn)一步分析高于平均適配度的模式數(shù)量增長，設(shè)復(fù)制對模式141交叉過程是串之間的有組織的然而又是隨機(jī)的信息交換，它在創(chuàng)建新結(jié)構(gòu)的同時(shí)，最低限度地破壞復(fù)制過程所選擇的高適配度模式?？疾煲粋€(gè)l＝7的串以及此串所包含的兩個(gè)代表模式。A＝0111000

交叉對模式的影響56交叉過程是串之間的有組織的然而又是隨機(jī)的信息交換，它在創(chuàng)142推廣到一般情況，可以計(jì)算出任何模式的交叉存活概率的下限為中大于號表示當(dāng)交叉點(diǎn)落入定義長度內(nèi)時(shí)也存在模式不被破壞的可能性。

一般情況若設(shè)交叉的概率，則上式變?yōu)?/p>

(3)交叉對模式的影響57推廣到一般情況，可以計(jì)算出任何模式的交叉存活概率的下限為143若綜合考慮復(fù)制和交叉的影響，特定模式在下一代中的數(shù)量可用下式來估計(jì)

(4)可見，對于那些高于平均適配度且具有短的定義長度的模式將更多地出現(xiàn)在下一代中。

交叉對模式的影響58若綜合考慮復(fù)制和交叉的影響，特定模式在下一代中的數(shù)量可用144變異對模式的影響59變異對模式的影響145綜合考慮上述復(fù)制、交叉及變異操作，可得特定模式H的數(shù)量改變?yōu)?/p>

(6)遺傳算法的模式理論

60綜合考慮上述復(fù)制、交叉及變異操作，可得特定模式H的數(shù)量改1466.3遺傳算法的實(shí)現(xiàn)與改進(jìn)

根據(jù)具體問題特點(diǎn)可采用不同的編碼方式，其中二進(jìn)制編碼是最常用的編碼方式。一般包括以下幾個(gè)步驟：

1)根據(jù)具體問題確定待尋優(yōu)的參數(shù)；

2)對每一個(gè)參數(shù)確定它的變化范圍，并用一個(gè)二進(jìn)制數(shù)來表示。例如若參數(shù)a的變化范圍為，用一位二進(jìn)制數(shù)b來表示，則二者之間滿足3)將所有表示參數(shù)的二進(jìn)制數(shù)串接起來組成一個(gè)長的二進(jìn)制字串。該字串的每一位只有0或1兩種取值。該字串即為遺傳算法可以操作的對象。編碼問題616.3遺傳算法的實(shí)現(xiàn)與改進(jìn)根據(jù)具體問題特147遺傳算法的操作步驟

利用遺傳算法解決一個(gè)具體的優(yōu)化問題，一般分為三個(gè)步驟：1)準(zhǔn)備工作

(1)確定有效且通用的編碼方法，將問題的可能解編碼成有限位的字符串；

(2)定義一個(gè)適應(yīng)度函數(shù)，用以測量和評價(jià)各解的性能；

(3)確定遺傳算法所使用的各參數(shù)的取值，如種群規(guī)模n，交叉概率，變異概率等等。6.3遺傳算法的實(shí)現(xiàn)與改進(jìn)62遺傳算法的操作步驟利用遺傳算法解決一個(gè)具體148遺傳算法的操作步驟2)遺傳算法搜索最佳串

(1)t=0，隨機(jī)產(chǎn)生初始種