Chapter9 神經網絡與遺傳算法(二)

Chap10神經網絡與遺傳算法(二)遺傳算法目錄(遺傳算法)10.4遺傳算法10.5基于遺傳算法的分類學習系統附:進化神經網絡10.4遺傳算法遺傳算法（GeneticAlgorithms,GA）是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化搜索算法。它模擬了生物的繁殖、交配和變異現象，從初始的種群，產生一群更適應環(huán)境的后代。

1975年美國Michigan大學J.Holland教授提出。美國人De.Jong博士將遺傳算法應用于函數優(yōu)化Goldberg成了遺傳算法的框架。

10.4遺傳算法

遺傳學原理遺傳是作為一種指令碼封裝在每個染色體（個體）中，并以基因（位）的形式包含在染色體（個體）中?；螂s交和基因突變能產生對環(huán)境適應性強的后代，通過優(yōu)勝劣汰的自然選擇，適應值高的基因結構就保存下來。10.4.1遺傳算法基本原理遺傳算法將問題的每個可能的解按某種形式進行編碼，編碼后的解稱作染色體（個體）。隨機選取N個染色體（個體）構成初始種群，再根據預定的評價函數對每個染色體計算適應值，使得性能較好的染色體具有較高的適應值。選擇適應值高的染色體進行復制，通過遺傳算子：選擇、交叉（重組）、變異，來產生一群新的更適應環(huán)境的染色體，形成新的種群。這樣一代一代不斷繁殖、進化，最后收斂到一個最適應環(huán)境的個體上，求得問題的最優(yōu)解。

10.4.1遺傳算法基本原理初始化初始種群（編碼成位串形式）計算每一個染色體（個體）的適應值是否滿足優(yōu)化準則輸出結果YesNo選擇交叉變異產生新一代種群遺傳算子

遺傳算法的處理流程圖遺傳算法基本要素遺傳算法中包含了如下五個基本要素：1）問題編碼2）初始群體的設定3）適應值函數的設計4）遺傳操作設計5）控制參數設定（主要是指群體大小和使用遺傳操作的概率等）這五個要素構成了遺傳算法的核心內容。

（1）問題編碼

如何將問題描述成位串的形式，即問題編碼。一般將問題中各參數用二進制編碼，構成子串，再將子串拼接起來構成“染色體”位串。不同串長和不同的碼制，對問題求解的精度和遺傳算法收斂時間會有很多影響。目前也出現采用其它編碼方式，如用向量、規(guī)則來表示染色體。

（2）初始群體的生成遺傳算法是群體型操作，這樣必須為遺傳操作準備一個由若干初始解組成的初始群體。初始群體的每個個體都是通過隨機方法產生的（3）適應值函數的確定

適應值函數是根據目標函數確定的。適應值總是非負的，任何情況下總是希望越大越好。適應值函數的選取至關重要，它直接影響到算法的收斂速度即最終能否找到最優(yōu)解。函數優(yōu)化問題可直接將目標函數本身作為適應值函數（4）控制參數

參數主要有個體編碼長度、群體大小M、交叉概率Pc、變異概率Pm、終止代數T等這些參數對遺傳算法的運行影響很大，需要認真選擇。10.4.2遺傳算子1、選擇(Selection)算子依據每個染色體的適應值大小，適應值越大，被選中的概率就越大，其子孫在下一代產生的個數就越多。選擇操作是建立在群體中個體的適應值評估基礎上的，目前常用的選擇算子有適應值比例法、最佳個體保存法、期望值方法等。2、交叉(Crossover)算子通過染色體重組來產生新一代染色體。如有兩個用二進制編碼的個體A和B。交叉前后為：A=a1a2a3│a4a5A’=a1a2a3│b4b5B=b1b2b3│b4b5B’=b1b2b3│a4a5(父代) (子代)3、變異(Mutation)算子

變異增加了遺傳算法找到接近最優(yōu)解的能力。變異就是以很小的概率，隨機地改變字符串某個位置上的值。把某一位的內容進行變異。在二進制編碼中，就是將某位0變成1，1變成0。

如：110010的第四位變異成110110（父代）（子代）遺傳算法用于優(yōu)化計算

10.4.3遺傳算法實例問題：求發(fā)f(x)=x2在[0，31]上的最大值。一、初始種群1.編碼：用五位二進制表示x，有x=0→00000x=31→111112.初始種群隨機產生4個個體：13，24，8，193.適應值fi直接用目標函數作為適應值：fi=xi2非負;(2)逐步增大4.選擇率ps和期望值選擇率：ps=fi/∑fi平均適應值：f=∑fi/n期望值：fi/f5.實選值期望值取整數

編號初始種群位串參數值x值目標適應值f(x)=x2選擇率fi/∑fi期望值fi/f實選值123401101110000100010011132489169576643610.140.490.060.310.581.970.221.231201總和∑平均值最大值11702935761.000.250.494.001.001.974.01.02.0初始種群參數計算二、遺傳選擇后的交配池（下劃線部分交叉）交叉對象（隨機選擇）交叉位置（隨機選擇）新的種群xf(x)=x2011011100011000

10011214344220110011001110111000012252716144625729256總和∑平均值最大值1754439729說明：1.選擇（繁殖）在種群眾，實選值（期望值）高者多繁殖；實選值（期望值）低者少繁殖或不繁殖。繁殖（復制）的個體放入交配池中。2.交叉隨機選擇交配對象（相同個體不交配），如個體1和2，3和4。隨機選擇交叉點進行交叉。3.變異取變異概率pe=0.01，表示每100個體中有一個個體的一位發(fā)生變異。（暫不變異）新的種群，其平均值和最大值都有很大提高。均值：293→439

最大值：576→729新種群中四個個體，有2個變好：25，25；2個變壞：12，16。三、再遺傳一代編號初始種群位串參數值x值目標適應值f(x)=x2選擇率fi/∑fi期望值fi/f實選值123401100110011101110000122527161446257292560.080.360.420.150.331.421.660.580121總和∑平均值最大000.250.424.001.001.664.01.02.0選擇后的交配池（下劃線部分交叉）交叉對象（隨機選擇）交叉位置（隨機選擇）新的種群xf(x)=x2110011101111011

1000021431133110111100111000

1001127252419729625576361總和∑平均值最大值2291572729單純用交叉而沒有用變異，則遺傳多少代得不到最優(yōu)解31(11111)。主要是第三位所有個體都是0，這樣只能得到27（11011）次優(yōu)解。

說明：10.4.4遺傳算法的特點

遺傳算法是進行群體的搜索。它對多個個體進行群體搜索，構成一個不斷進化的群體序列，它能找到全局最優(yōu)解（優(yōu)于爬山法）遺傳算法是一種隨機搜索方法，三個算子都是隨機操作，利用概率轉移規(guī)則。遺傳算法的處理對象是問題參變量進行編碼的個體，而不是參變量自身。參變量編碼成位串個體，通過遺傳算子進行操作。不是對參數變量進行直接操作。遺傳算法利用適應值信息，而不需要導數或其它輔助信息。遺傳算法用適應值評估個體，用遺傳算子產生更優(yōu)后代，不需要像神經網絡中用梯度公式引導。隱含并行性：遺傳算法是對N個位串個體進行運算，它隱含了大量的模式（用通配符#包含的個體）遺傳機器學習10.5基于遺傳算法的分類學習系統我們研制的遺傳分類學習系統GCLS是一種字符串規(guī)則（分類器）的學習系統。它將規(guī)則“條件condition”和“結論action”合并成消息個體，也稱分類器。適應值設計成分類器（規(guī)則）覆蓋消息的個數，覆蓋消息個數越多，規(guī)則的有效性愈大。GCLS系統由五個部件組成

①檢測器②消息表③分類器④測試表⑤作用器分類器系統的詳細結構框圖如下：檢測器消息表信任分配算法工作分類器遺傳算法測試表作用器客觀環(huán)境增生操作精煉分類器系統的工作流程1.初始化所有預置參數。2.將環(huán)境信息放入消息表中。3.對初始種群調用信任分配算法，修改其中規(guī)則的適應值。4.對種群進行合并操作，合并后的種群設為種群M。系統的工作流程5.假如種群M已經收斂，則復制該種群