遺傳算法詳解課件

5.遺傳算法遺傳算法（geneticalgorithms,簡稱GA）是人工智能的重要分支，是基于達(dá)爾文進(jìn)化論，在微型計算機(jī)上模擬生命進(jìn)化機(jī)制而發(fā)展起來的一門新學(xué)科。它根據(jù)適者生存、優(yōu)勝劣汰等自然進(jìn)化規(guī)則來進(jìn)行搜索計算和問題求解。對許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的非常復(fù)雜問題，特別是最優(yōu)化問題，GA提供了一個行之有效的新途徑。近年來，由于遺傳算法求解復(fù)雜優(yōu)化問題的巨大潛力及其在工業(yè)控制工程領(lǐng)域的成功應(yīng)用，這種算法受到了廣泛的關(guān)注。5.遺傳算法遺傳算法（geneticalg5.1.1基本遺傳學(xué)基礎(chǔ)遺傳算法是根據(jù)生物進(jìn)化的模型提出的一種優(yōu)化算法。自然選擇學(xué)說是進(jìn)化論的中心內(nèi)容，根據(jù)進(jìn)化論，生物的發(fā)展進(jìn)化主要由三個原因，即遺傳、變異和選擇。遺傳是指子代總是和親代相似。遺傳性是一切生物所共有的特性，它使得生物能夠把其特性、性狀傳給后代。遺傳是生物進(jìn)化的基礎(chǔ)。變異是指子代和親代有某些不相似的現(xiàn)象，即子代永遠(yuǎn)不會和親代完全一樣。它是一切生物所具有的共有特性，是生物個體之間相互區(qū)別的基礎(chǔ)。引起變異的原因主要是生活環(huán)境的影響及雜交等。生物的變異性為生物的進(jìn)化和發(fā)展創(chuàng)造了條件。5.1.1基本遺傳學(xué)基礎(chǔ)遺傳算法是根據(jù)生選擇決定生物進(jìn)化的方向。在進(jìn)化過程中，有的要保留，有的要被淘汰。自然選擇是指生物在自然界的生存環(huán)境中適者生存，不適者被淘汰的過程。通過不斷的自然選擇，有利于生存的變異就會遺傳下去，積累起來，使變異越來越大，逐步產(chǎn)生了新的物種。生物就是在遺傳、變異和選擇三種因素的綜合作用過程中，不斷地向前發(fā)展和進(jìn)化。選擇是通過遺傳和變異起作用的，變異為選擇提供資料，遺傳鞏固與積累選擇的資料，而選擇則能控制變異與遺傳的方向，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。遺傳算法正是吸取了自然生物系統(tǒng)“適者生存、優(yōu)勝劣汰”的進(jìn)化原理，從而使它能夠提供一個在復(fù)雜空間中隨機(jī)搜索的方法，為解決許多傳統(tǒng)的優(yōu)化方法難以解決的優(yōu)化問題提供了新的途徑。遺傳算法詳解-課件5.1.2遺傳算法的原理和特點遺傳算法將生物進(jìn)化原理引入待優(yōu)化參數(shù)形成的編碼串群體中，按著一定的適值函數(shù)及一系列遺傳操作對各個體進(jìn)行篩選，從而使適值高的個體被保留下來，組成新的群體，新群體包含上一代的大量信息，并且引入了新的優(yōu)于上一代的個體。這樣周而復(fù)始，群體中各個體適值不斷提高，直至滿足一定的極限條件。此時，群體中適值最高的個體即為待優(yōu)化參數(shù)的最優(yōu)解。正是由于遺傳算法獨具特色的工作原理，使它能夠在復(fù)雜空間進(jìn)行全局優(yōu)化搜索，并且具有較強(qiáng)的魯棒性；另外，遺傳算法對于搜索空間，基本上不需要什么限制性的假設(shè)（如連續(xù)、可微及單峰等）。5.1.2遺傳算法的原理和特點遺傳算法將遺傳算法的特點同常規(guī)優(yōu)化算法相比，遺傳算法有以下特點：①遺傳算法是對參數(shù)的編碼進(jìn)行操作，而非對參數(shù)本身。②遺傳算法是從許多點開始并行操作，并非局限于一點，從而可有效防止搜索過程收斂于局部最優(yōu)解。③遺傳算法通過目標(biāo)函數(shù)計算適值，并不需要其它推導(dǎo)和附加信息，因而對問題的依賴性較小。

遺傳算法的特點同常規(guī)優(yōu)化算法相比，遺傳算法有以下特點：④遺傳算法的尋優(yōu)規(guī)則是由概率決定的，而非確定性的。⑤遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機(jī)搜索。⑥遺傳算法對所求解的優(yōu)化問題沒有太多的數(shù)學(xué)要求。⑦遺傳算法具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度。遺傳算法詳解-課件5.1.3遺傳算法的基本操作一般的遺傳算法都包含三個基本操作：復(fù)制(reproduction)、交叉(crossover)和變異(mutation)。

1.復(fù)制

復(fù)制（又稱繁殖），是從一個舊種群（oldpopulation）中選擇生命力強(qiáng)的字符串（individualstring）產(chǎn)生新種群的過程。或者說，復(fù)制是個體位串根據(jù)其目標(biāo)函數(shù)f（即適值函數(shù)）拷貝自己的過程。直觀地講，可以把目標(biāo)函數(shù)f看作是期望的最大效益的某種量度。根據(jù)位串的適值所進(jìn)行的拷貝，意味著具有較高適值的位串更有可能在下一代中產(chǎn)生一個或多個子孫。顯然，在復(fù)制操作過程中，目標(biāo)函數(shù)(適值)是該位串被復(fù)制或被淘汰的決定因素。

5.1.3遺傳算法的基本操作一般的遺傳算法都包含三個基本復(fù)制操作的初始種群(舊種群)的生成往往是隨機(jī)產(chǎn)生的。例如，通過擲硬幣20次產(chǎn)生維數(shù)n＝4的初始種群如下(正面=1，背面=0)：

01101110000100010011顯然，該初始種群可以看成是一個長度為五位的無符號二進(jìn)制數(shù)，將其編成四個位串，并解碼為十進(jìn)制的數(shù)：位串1：

0110113位串2：

1100024位串3：

010008位串4：

1001119

復(fù)制操作的初始種群(舊種群)的生成往往是隨機(jī)產(chǎn)生的。通過一個5位無符號二進(jìn)制數(shù)，可以得到一個從0到31的數(shù)值x，它可以是系統(tǒng)的某個參數(shù)。計算目標(biāo)函數(shù)或適值f(x)=x2，其結(jié)果如表6-1所示。計算種群中所有個體位串的適值之和，同時，計算種群全體的適值比例，其結(jié)果示于表中。

通過一個5位無符號二進(jìn)制數(shù)，可以得到一個從0到31的轉(zhuǎn)輪法轉(zhuǎn)輪法把種群中所有個體位串適值的總和看作一個輪子的圓周，而每個個體位串按其適值在總和中所占的比例占據(jù)輪子的一個扇區(qū)。按表5-1可繪制如圖的轉(zhuǎn)輪。復(fù)制時，只要簡單地轉(zhuǎn)動這個按權(quán)重劃分的轉(zhuǎn)輪4次，從而產(chǎn)生4個下一代的種群。例如對于表5-1中的位串1，其適值為169，為總適值的14.4%。因此，每旋轉(zhuǎn)一次轉(zhuǎn)輪指向該位串的概率為0.144。每當(dāng)需要下一個后代時，就旋轉(zhuǎn)一下這個按權(quán)重劃分的轉(zhuǎn)輪，產(chǎn)生一個復(fù)制的候選者。這樣位串的適值越高，在其下代中產(chǎn)生的后代就越多。

圖5-1轉(zhuǎn)輪法轉(zhuǎn)輪法把種群中所有個體位串適值的總和看作一個輪子的圓圖當(dāng)一個位串被選中時，此位串將被完整地復(fù)制，然后將復(fù)制位串送入匹配集（緩沖區(qū)）中。旋轉(zhuǎn)4次轉(zhuǎn)輪即產(chǎn)生4個位串。這4個位串是上代種群的復(fù)制，有的位串可能被復(fù)制一次或多次，有的可能被淘汰。在本例中，位串3被淘汰，位串4被復(fù)制一次。如表6-2所示，適值最好的有較多的拷貝，即給予適合于生存環(huán)境的優(yōu)良個體更多繁殖后代的機(jī)會，從而使優(yōu)良特性得以遺傳，反之，最差的則被淘汰。當(dāng)一個位串被選中時，此位串將被完整地復(fù)制，然后將復(fù)制

2.交叉

簡單的交叉分兩步實現(xiàn)。第一步是將新復(fù)制產(chǎn)生的位串個體隨機(jī)兩兩配對；第二步是隨機(jī)選擇交叉點，對匹配的位串進(jìn)行交叉繁殖，產(chǎn)生一對新的位串。具體過程如下：設(shè)位串的字符長度為l，在[1，l－1]的范圍內(nèi)，隨機(jī)地選取一個整數(shù)值k作為交叉點。將兩個配對串從第k位右邊部分的所有字符進(jìn)行交換，從而生成兩個新的位串。例如，在表6-2中，已知位串的字符長度l=5，隨機(jī)選取k=4，對兩個初始的位串個體A1和A2進(jìn)行配對，交叉操作的位置用分隔符“|”表示為：A1=0110|1A2=1100|0交叉操作后產(chǎn)生了兩個新的字符串為：

A1’=01100

A2’=11001

2.交叉一般的交叉操作過程：

遺傳算法的有效性主要來自于復(fù)制和交叉操作。復(fù)制雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的個體；交叉模擬生物進(jìn)化過程中的繁殖現(xiàn)象，通過兩個個體的交換組合，來創(chuàng)造新的優(yōu)良個體。表6-3列出了交叉操作之后的結(jié)果數(shù)據(jù)，從中可以看出交叉操作的具體過程。首先，隨機(jī)配對匹配集中的個體，將位串1、2配對，位串3、4配對；然后，隨機(jī)選取交叉點，設(shè)位串1、2的交叉點為k=4，二者只交換最后一位，從而生成兩個新的位串，即

圖5-2交叉操作一般的交叉操作過程：圖5-2交叉操作位串3、4的交叉點為k=2，二者交換后三位，生成兩個新的位串，即

位串3、4的交叉點為k=2，二者交換后三位，生成兩個新的位串單點交叉與多點交叉上述例子中交叉的位置是一個，稱單點交叉。即指個體切斷點有一處，由于進(jìn)行個體間的組合替換生成兩個新個體，位串個體長度為l時，單點交叉可能有l(wèi)－1個不同的交叉。

多點交叉是允許個體的切斷點有多個，每個切斷點在兩個個體間進(jìn)行個體的交叉，生成兩個新個體。

單點交叉與多點交叉3.變異

盡管復(fù)制和交叉操作很重要，在遺傳算法中是第一位的，但不能保證不會遺漏一些重要的遺傳信息。在人工遺傳系統(tǒng)中，變異用來防止這種遺漏。在簡單遺傳算法中，變異就是在某個字符串當(dāng)中把某一位的值偶然的（概率很小的）隨機(jī)的改變，即在某些特定位置上簡單地把1變?yōu)?，或反之。當(dāng)它有節(jié)制地和交叉一起使用時，它就是一種防止過度成熟而丟失重要概念的保險策略。例如，隨機(jī)產(chǎn)生一個種群，如表所示。在該表所列種群中，無論怎樣交叉，在第4位上都不可能得到有1的位串。若優(yōu)化的結(jié)果要求該位是1，顯然僅靠交叉是不夠的，還需要有變異，即特定位置上的0和1之間的轉(zhuǎn)變。

3.變異變異在遺傳算法中的作用是第二位的，但卻是必不可少的。變異運算用來模擬生物在自然界的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)改變遺傳基因（即位串個體中某一位）的值。通過變異操作，可確保種群中遺傳基因類型的多樣性，以使搜索能在盡可能大的空間中進(jìn)行，避免丟失在搜索中有用的遺傳信息而陷入局部解。根據(jù)統(tǒng)計，變異的概率為0.001，即變異的頻率為每千位傳送中只變異一位。在表6-3的種群中共有20個字符（每位串的長度為5個字符）。期望變異的字符串位數(shù)為20×0.001=0.02（位），所以在此例中無位值的改變。從表6-2和表6-3可以看出，雖然僅進(jìn)行一代遺傳操作，但種群適值的平均值和最大值卻比初始種群有了很大的提高，平均適值由293變到439，最大值由576變到729。這說明隨著遺傳運算的進(jìn)行，種群正向著優(yōu)化的方向發(fā)展。

變異在遺傳算法中的作用是第二位的，但卻是必不可少的。遺傳算法在以下幾個方面不同于傳統(tǒng)優(yōu)化方法

①

遺傳算法只對參數(shù)集的編碼進(jìn)行操作，而不是參數(shù)集本身。②

遺傳算法的搜索始于解的一個種群，而不是單個解，因而可以有效地防止搜索過程收斂于局部最優(yōu)解。③

遺傳算法只使用適值函數(shù)，而不使用導(dǎo)數(shù)和其它附屬信息，從而對問題的依賴性小。④

遺傳算法采用概率的、而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則，即具有隨機(jī)操作算子。

遺傳算法在以下幾個方面不同于傳統(tǒng)優(yōu)化方法

①遺傳算法只對

圖5–3

遺傳算法的工作原理示意圖圖5–3遺傳算法的工作原理示意圖5.2.1目標(biāo)函數(shù)值到適值形式的映射適值是非負(fù)的，任何情況下總希望越大越好；而目標(biāo)函數(shù)有正、有負(fù)、甚至可能是復(fù)數(shù)值；且目標(biāo)函數(shù)和適值間的關(guān)系也多種多樣。如求最大值對應(yīng)點時，目標(biāo)函數(shù)和適值變化方向相同；求最小值對應(yīng)點時，變化方向恰好相反；目標(biāo)函數(shù)值越小的點，適值越大。因此，存在目標(biāo)函數(shù)值向適值映射的問題。

5.2遺傳算法應(yīng)用中的一些基本問題

5.2.1目標(biāo)函數(shù)值到適值形式的映射適值是首先應(yīng)保證映射后的適值是非負(fù)的，其次目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對應(yīng)于適值增大的方向。對最小化問題，一般采用如下適值函數(shù)f(x)和目標(biāo)函數(shù)g(x)的映射關(guān)系：

(5-6)其中：cmax可以是一個輸入?yún)?shù)，或是理論上的最大值，或是到目前所有代（或最近的k代）之中見到的g(x)的最大值，此時cmax隨著代數(shù)會有所變化。首先應(yīng)保證映射后的適值是非負(fù)的，其次目標(biāo)函數(shù)對最大化問題，一般采用下述方法：(5-7)式中:cmin既可以是輸入值也可以是當(dāng)前最小值或最近的k代中的最小值。對指數(shù)函數(shù)問題，一般采用下述方法：其中：c一般取1.618或2（最大化），0.618（最小化）。這樣，既保證了f(x)≥0又使f(x)的增大方向與優(yōu)化方向一致。對最大化問題，一般采用下述方法：5.2.2適值的調(diào)整為了使遺傳算法有效地工作，必須保持種群內(nèi)位串的多樣性和位串之間的競爭機(jī)制。現(xiàn)將遺傳算法的運行分為開始、中間和結(jié)束三個階段來考慮：在開始階段，若一個規(guī)模不太大的種群內(nèi)有少數(shù)非凡的個體（適值很高的位串），按通常的選擇方法（選擇復(fù)制的概率為fi/Σfi，期望的復(fù)制數(shù)為fi/），這些個體會被大量地復(fù)制，在種群中占有大的比重，這樣就會減少種群的多樣性，導(dǎo)致過早收斂，從而可能丟失一些有意義的搜索點或最優(yōu)點，而進(jìn)入局部最優(yōu)；在結(jié)束階段，即使種群內(nèi)保持了很大的多樣性，但若所有或大多數(shù)個體都有很高的適值，從而種群平均適值和最大適值相差無幾，則平均適值附近的個體和具有最高適值的個體，被選中的機(jī)會相同，這樣選擇就成了一個近乎隨機(jī)的步驟，適值的作用就會消失，從而使搜索性能得不到明顯改進(jìn)。因此，有必要對種群內(nèi)各位串的適值進(jìn)行有效調(diào)整，既不能相差太大，又要拉開檔次，強(qiáng)化位串之間的競爭性。5.2.2適值的調(diào)整5.2.3編碼原則遺傳算法參數(shù)編碼原則有兩種：深層意義上的建筑塊原則和最小符號表原則。而后者是一種應(yīng)用廣泛的實用原則。最小符號表原則要求選擇一個使問題得以自然表達(dá)的最小符號編碼表。在前面討論中使用的都是二進(jìn)制符號編碼表{0,1}，任何一個長度為l的位串都包含在{0,1}l中。根據(jù)遺傳算法的模式理論，遺傳算法能有效工作的根本原因，在于其能有效的處理種群中的大量模式，尤其是那些定義長度短、確定位數(shù)少、適值高的模式（即建筑塊）。因此，編碼應(yīng)使確定規(guī)模的種群中包含盡可能多的模式。5.2.3編碼原則遺傳算法參數(shù)編碼原則有表6-5給出了一個參數(shù)的二進(jìn)制編碼和非二進(jìn)制編碼的對比情況，即將[0,31]上的二進(jìn)制整數(shù)一一對應(yīng)地映射到一個有32個字母的符號表中，這個符號表包含26個英文字母（A～Z）和6個數(shù)字（1～6）。在二進(jìn)制編碼中，通過代碼表中小部分關(guān)鍵代碼可以找到重要的相似性而在非二進(jìn)制編碼中，只能看到單一代碼的符號表，看不出代碼中的相似性。為了進(jìn)一步了解二進(jìn)制編碼的數(shù)學(xué)意義，假設(shè)有一個非二進(jìn)制的包含k個字母編碼的符號表V’及二進(jìn)制編碼的符號表V，即V’={a1,a2,…,ak}V={0,1}表6-5給出了一個參數(shù)的二進(jìn)制編碼和非二進(jìn)制編碼的對比情況，5.3.1復(fù)制方法的改進(jìn)1．穩(wěn)態(tài)復(fù)制法

該方法保證種群中最優(yōu)秀的個體在進(jìn)化過程中不被刪除，這在很大程度上減少了有效基因的丟失。在經(jīng)過交叉、變異產(chǎn)生的新種群中，只有一個或兩個優(yōu)秀個體被選進(jìn)下一代種群，替代原有種群中的最差個體。

5.3.1復(fù)制方法的改進(jìn)1．穩(wěn)態(tài)復(fù)制法

2．選擇種子法該法也稱最優(yōu)串復(fù)制法，它保證了最優(yōu)的個體被選進(jìn)下一代進(jìn)化種群。其執(zhí)行過程如下：①隨機(jī)初始化種群N(0)，種群大小為n。②計算種群中所有個體適值。③對以后的種群N(t)進(jìn)行如下操作，直至滿足條件或達(dá)到進(jìn)化代數(shù)。根據(jù)個體適值大小隨機(jī)選出n個個體組成種群N0(t)，并復(fù)制一份為N1(t)，對種群N0(t)實施交叉操作，對種群N1(t)實施基因突變，用以防止有效基因丟失。④計算種群N0(t)、N1(t)和N(t)的個體適值，從中選出最好的n個個體構(gòu)成下一代種群N(t＋1)，轉(zhuǎn)至③。2．選擇種子法3．確定性復(fù)制法

在確定性復(fù)制法中，復(fù)制的概率按常規(guī)計算為：Pi＝fi/∑fi。對個體Ai，其期望的后代數(shù)目ei，計算為：ei＝nPi。每一位串個體按ei的整數(shù)部分分配后代數(shù)，種群的其余部分按順序表由高到低來填充。4．置換式余數(shù)隨機(jī)復(fù)制法

這方法開始與上述確定性復(fù)制法一樣，期望的個體數(shù)如前分配為ei的整數(shù)部分；但ei的余數(shù)部分用來計算轉(zhuǎn)輪法中的權(quán)值，以補(bǔ)充種群總數(shù)。5．非置換式余數(shù)隨機(jī)復(fù)制法這方法開始也與上述確定性復(fù)制法一樣，而ei的余數(shù)部分按概率來處理。換句話說，個體至少復(fù)制一個與ei整數(shù)部分相等的后代，然后以ei的余數(shù)部分為概率來復(fù)制其余的后代，直至種群的總數(shù)達(dá)到n。例如一個具有期望復(fù)制值為1.5的個體，它可以復(fù)制產(chǎn)生一個后代，并以0.5概率產(chǎn)生另一個后代。試驗表明，這種方法優(yōu)于其它復(fù)制方法。3．確定性復(fù)制法

5.3.2高級GA算法為改善SGA的魯棒性，在復(fù)制、交叉和變異運算的基礎(chǔ)上，再考慮兩種類型的基因運算，即為微運算和宏運算。多點交叉微運算是在個體級別上的運算，重組宏運算是在種群級別上的運算。5.3.2高級GA算法為改善SGA的魯棒性5.4基于遺傳算法的系統(tǒng)在線辨識

5.4.1遺傳算法在參數(shù)辨識中的應(yīng)用

5.4.2遺傳算法參數(shù)辨識仿真示例

5.4基于遺傳算法的系統(tǒng)在線辨識5.4.1遺傳算法在5.4.1遺傳算法在參數(shù)辨識中的應(yīng)用1．離散系統(tǒng)參數(shù)估計

設(shè)線性離散系統(tǒng)的數(shù)學(xué)模型為：

(5-18)式中：d為滯后時間，ξ(k)為零均值的噪聲序列（方差為σ2），z-1為后移算子。5.4.1遺傳算法在參數(shù)辨識中的應(yīng)用1．離散系統(tǒng)參數(shù)估計假定A(z-1)、B(z-1)和C(z-1)未知，則待辨識參數(shù)向量包含na+nb+nc+1個參數(shù)，即(5-19)真參數(shù)為：(5-20)要應(yīng)用遺傳算法對參數(shù)向量θ進(jìn)行在線優(yōu)化的參數(shù)辨識，必須解決兩個問題，一個是確定多參數(shù)編碼映射方法，另一個是如何根據(jù)目標(biāo)函數(shù)確定適值。假定A(z-1)、B(z-1)和C(z-1)未2.參數(shù)級聯(lián)定點映射編碼

采用多參數(shù)級聯(lián)定點映射編碼原則進(jìn)行編碼，可根據(jù)辨識精度確定每個參數(shù)的二進(jìn)制編碼長度。假如每個參數(shù)線性映射在[-2l-1,+2l-1]范圍內(nèi)，且要求辨識精度<2-m，則每個參數(shù)需要m+l位；若已知時滯d≤2n，則時滯可用n位編碼，則各參數(shù)編碼組成一個整體位串的長為(na+nb+nc)×(l+m)+n，這個整體位串就是系統(tǒng)待辨識參數(shù)的一個解。2.參數(shù)級聯(lián)定點映射編碼

采用多參數(shù)級聯(lián)定點映射編碼原則設(shè)整體位串構(gòu)成的種群數(shù)為N，第p代的第j個（1≤j≤N）位串所對應(yīng)的參數(shù)為：(5-21)根據(jù)辨識結(jié)果，有預(yù)測輸出和預(yù)測輸出誤差，它們分別滿足：(5-22)(5-23)設(shè)整體位串構(gòu)成的種群數(shù)為N，第p代的第j個（1≤j≤N）位串3.目標(biāo)函數(shù)到適值形式的映射

為保證映射后的適值是非負(fù)的，選擇目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對應(yīng)于適值的增大方向。由式(5-6)的映射關(guān)系，可選擇適值函數(shù)為：

(5-24)求和m+1步的意義在于能進(jìn)一步考察辨識參數(shù)與真參數(shù)的擬合情況。在遺傳算法操作過程中，可能存在這樣的參數(shù)，它離真值很遠(yuǎn)，但經(jīng)線性組合后某步預(yù)測輸出與實際輸出相差不大，求和可以避免這樣的參數(shù)集取得高適值以致出現(xiàn)錯誤的收斂。m的值越大，適值函數(shù)的可信度就越高，m的上限可取為k值，cmax值是一足夠大的正數(shù)，它與問題的解有關(guān)。3.目標(biāo)函數(shù)到適值形式的映射

為保證映射后的適值是非負(fù)的在計算出種群中每個個體的適值后，需要對它們規(guī)范化，先求出其平均適值為：(5-25)規(guī)范化適值為：(5-26)用種群規(guī)范化適值與平均適值的偏差的平方和來定義收斂域，即(5-27)其中：δ是一個定義的收斂域，例如若設(shè)δ<0.0001，則可認(rèn)為種群已經(jīng)收斂，這時種群中適值最大的個體就是當(dāng)前收斂條件下的最優(yōu)者。在計算出種群中每個個體的適值后，需要對它們規(guī)范化5.4.2遺傳算法參數(shù)辨識仿真示例設(shè)線性離散系統(tǒng)的數(shù)學(xué)模型如式（5–13）所示，其中d=2采用偽隨機(jī)二進(jìn)制序列（PRBS）輸入，辨識系統(tǒng)參數(shù)為及時滯。設(shè)參數(shù)的范圍是[-2,+2]，要求辨識精度≤0.02，則每個參數(shù)需要用8位的位串表示，若時滯d不大于4，則時滯可用2位的位串表示，所以參數(shù)集位串長度為4×8+2=34位。

5.4.2遺傳算法參數(shù)辨識仿真示例設(shè)線性離散系統(tǒng)的數(shù)學(xué)模取種群規(guī)模N=50，交叉概率Pc=0.90；變異概率Pm=0.001。適值函數(shù)中的cmax值分段選取。在操作初期，主要強(qiáng)調(diào)個體之間的多樣性，可將cmax值稍微取大些，cmax=1.85×m；操作后期，強(qiáng)調(diào)競爭性，cmax值取小些，cmax=1.6×m。兼顧計算速度和適值可信度，取10<m<30。在操作初期，在每一代適值規(guī)范化之后，要保持種群個體中的無子女個體占種群的百分比為一定值，若超過該值，則認(rèn)為是非成熟收斂。一般將這個臨界值定義在20%左右。定義辨識收斂域，δ<0.0001，滿足收斂條件時，種群中適值最高的個體就是當(dāng)前最優(yōu)者。取種群規(guī)模N=50，交叉概率Pc=0.90；變異概率Pm=0遺傳算法參數(shù)辨識運算步驟可歸納如下：①種群初始化，隨機(jī)生成N個參數(shù)集的位串。②采用偽隨機(jī)二進(jìn)制序列（PRBS）作為辨識輸入信號，采樣系統(tǒng)實際輸出y(k)。③按適值函數(shù)評價，并計算整體的平均性能。④參數(shù)辨識是否收斂到指定的精度內(nèi)或仿真步數(shù)是否達(dá)到最大，若是，則仿真結(jié)束。⑤是否過早出現(xiàn)非成熟收斂，若是,則進(jìn)行適值調(diào)整。⑥按規(guī)范適值或適值調(diào)整結(jié)果復(fù)制下一代，并按概率進(jìn)行交叉和變異操作。⑦查看上一代中最優(yōu)秀個體是否保留在本代，若不是，則取代本代中任意一個個體，將優(yōu)秀個體無遺傳保留。⑧轉(zhuǎn)步驟②遺傳算法參數(shù)辨識運算步驟可歸納如下：①種群初始化，隨機(jī)生成圖5–14a顯示了初期種群的系統(tǒng)辨識的平均值和整體收斂情況?？梢钥闯觯瑓?shù)和時滯是同步的，仿真在第150步之后就明顯地向真值收斂。圖5–14b顯示了后期第800步之后的系統(tǒng)辨識的情況，這時，種群平均性能已經(jīng)提高很多，種群的相似性越來越明顯，所以平均參數(shù)和時滯波動較小，仿真在1677步達(dá)到收斂，這時平均m參數(shù)和時滯d為a1=-1.712240,a2=0.727344b0=0.802865,b1=0.802865,d0=2.000圖5-14系統(tǒng)辨識(a)初期系統(tǒng)辨識(b)后期系統(tǒng)辨識

圖5–14a顯示了初期種群的系統(tǒng)辨識的平均值和整體收斂情況。5.3基于遺傳算法的模糊控制一般基于遺傳算法的模糊控制器，考慮最為常用的二維模糊控制的結(jié)構(gòu)，如圖6–15實線部分所示。模糊控制器的輸入量為偏差e(k)和偏差變化ec(k)，輸出為控制變化Δu(k)，其中偏差e(k)=yd(k)－y(k)，ec(k)=e(k)－e(k-1)，yd(k)為期望輸入，y(k)為系統(tǒng)實際輸出。被控對象為工業(yè)中常用的帶有純滯后的對象：（5-28）

其中：K=1，T=50，τ=2。圖6-15

5.3基于遺傳算法的模糊控制一般基于遺傳算法的模糊

模糊系統(tǒng)共有n條if…then形式的規(guī)則，若第i條規(guī)則被描述為：

Ri：ifE

∈

Ai

andEC

∈

BithenΔU

∈

ΔUi

其中：ΔU為控制器增量輸出模糊語言變量；E、EC為控制器輸入模糊語言變量；Ai、Bi和ΔUi為相應(yīng)的模糊子集，其分別在NL（負(fù)大）、NM（負(fù)中）、NS（負(fù)?。E（零）、PS（正小）、PM（正中）和PL（正大）中取值。模糊隸屬函數(shù)從常用的三角形、梯形和高斯函數(shù)形中確定采用等腰三角形，并在尋優(yōu)過程中保持不變。如果存在輸入e=a*，ec=b*，則控制器的增量輸出為：模糊系統(tǒng)共有n條if…then形式的規(guī)則，若第i條控制器的輸出為：其中：，ci是Ui所取的各個模糊值的論域中心元素值。控制規(guī)則的全體構(gòu)成一個M×N維的模糊控制表，M、N為兩個模糊輸入變量E、EC的模糊子集個數(shù)。利用遺傳算法，在固定模糊隸屬函數(shù)的前題下自動調(diào)整模糊控制規(guī)則，其主要操作如下：

⑴

種群大小。在使用遺傳算法時，首先需要解決的是確定種群的大小。若太小，則不能保證種群中個體的多樣性，尋優(yōu)空間小，導(dǎo)致提前收斂；若太大，則會增加計算負(fù)擔(dān)，降低了遺傳算法的效率。因此，一般兼顧二者取種群大小為50。

控制器的輸出為：⑵

參數(shù)編碼。對模糊控制規(guī)則采用自然數(shù)編碼。對M×N維規(guī)則表中的M×N個語言變量值NL、NM、NS、ZE、PS、PM、PL分別用0、1、2、3、4、5、6表示。這樣，在計算機(jī)中每個個體可以用一個M×N行、兩列的數(shù)組表示。

⑶

復(fù)制。研究結(jié)果表明，選擇種子法能保證全局收斂，穩(wěn)態(tài)復(fù)制法適合于非線性較強(qiáng)的問題，代溝法的尋優(yōu)效果一般，一般復(fù)制法效果最差。⑷

交叉和變異。交叉操作是產(chǎn)生新個體增大搜索空間的重要手段，但同時容易造成對有效模式的破壞，針對模糊規(guī)則表采用自然編碼的特點，采用點對點的雙點交換方法如圖5–16所示。

⑵參數(shù)編碼。對模糊控制規(guī)則采用自然數(shù)編碼。對M×N維規(guī)則表變異能克服由于交叉、復(fù)制操作造成的有效基因的丟失，使搜索在盡可能大的尋優(yōu)空間中進(jìn)行。在進(jìn)化早期，隨機(jī)選擇突變次數(shù)（1~3）次，在串中隨機(jī)選擇一個突變位置，進(jìn)行6步距突變，即把突變位置上的表示規(guī)則的自然數(shù)b加上0~6的隨機(jī)數(shù)s，然后將和除以7，取余數(shù)即突變操作的結(jié)果a，即a=(b+s)%7。在進(jìn)化后期，為防止6步突變造成個體性能惡化，采用2步距突變，例如對規(guī)則ZE將有可能突變成NS或PS或NM或PM，而對規(guī)則NL將有可能變成NM或NS。另外，根據(jù)模糊控制器設(shè)計的一般常識對如下3條規(guī)則不作突變操作。ifE

∈

NL

andEC

∈

NL

thenΔU

∈PLifE

∈

ZE

andEC

∈

ZE

thenΔU

∈ZEifE

∈

PL

andEC

∈

PL

thenΔU

∈NL

圖5-16

圖5-16⑸

適值調(diào)整。為防止種群進(jìn)化過程中提前收斂以及提高進(jìn)化后期的收斂速度，擴(kuò)大尋優(yōu)空間和提高尋優(yōu)精度，采用窗口法和函數(shù)歸一法進(jìn)行適值調(diào)整。

⑹

個體目標(biāo)函數(shù)估計。個體是模糊控制器參數(shù)的編碼，個體目標(biāo)函數(shù)用來估價該控制器的性能，本控制器采用的個體目標(biāo)函數(shù)如下：（5-31）其中：ts是控制器作用于對象的持續(xù)時間，au、ay、ae為式（5-31）中相應(yīng)項的加權(quán)系數(shù)，它們分別決定了∣u(k)－u(k-1)∣、∣e(k)∣、∣ec(k)∣項在個體目標(biāo)函數(shù)中所占的比重，其值越大對該項的重視程度越高，其中ae∣ec(k)∣項的引入主要是防止輸出響應(yīng)超調(diào)量過大。進(jìn)而，得到個體適值為：

(5-32)其中，N為種群大小，Jj為第j個個體的目標(biāo)函數(shù)值。

⑸適值調(diào)整。為防止種群進(jìn)化過程中提前收斂以及提高進(jìn)化后期的⑺

尋優(yōu)過程中期望輸入的選擇。令期望輸入yd=1，式（5-31）中ts=100s，利用遺傳算法尋優(yōu)，將得到的模糊控制器用于系統(tǒng)控制，其響應(yīng)曲線如圖5–17所示，顯而易見，當(dāng)t>135s時，控制效果變差。其主要原因是由于在尋優(yōu)過程中，種群個體沒有對系統(tǒng)輸出在不同區(qū)域、不同變化速率的情況都進(jìn)行目標(biāo)函數(shù)估價。采用變期望輸入的方法使控制器在尋優(yōu)過程中能夠?qū)ο到y(tǒng)絕大部分狀態(tài)變化做出響應(yīng)。此時，期望輸入按下式選?。?/p>

(5-33)圖5-18圖5-17⑺尋優(yōu)過程中期望輸入的選擇。令期望輸入yd=1，式（5-35.遺傳算法遺傳算法（geneticalgorithms,簡稱GA）是人工智能的重要分支，是基于達(dá)爾文進(jìn)化論，在微型計算機(jī)上模擬生命進(jìn)化機(jī)制而發(fā)展起來的一門新學(xué)科。它根據(jù)適者生存、優(yōu)勝劣汰等自然進(jìn)化規(guī)則來進(jìn)行搜索計算和問題求解。對許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的非常復(fù)雜問題，特別是最優(yōu)化問題，GA提供了一個行之有效的新途徑。近年來，由于遺傳算法求解復(fù)雜優(yōu)化問題的巨大潛力及其在工業(yè)控制工程領(lǐng)域的成功應(yīng)用，這種算法受到了廣泛的關(guān)注。5.遺傳算法遺傳算法（geneticalg5.1.1基本遺傳學(xué)基礎(chǔ)遺傳算法是根據(jù)生物進(jìn)化的模型提出的一種優(yōu)化算法。自然選擇學(xué)說是進(jìn)化論的中心內(nèi)容，根據(jù)進(jìn)化論，生物的發(fā)展進(jìn)化主要由三個原因，即遺傳、變異和選擇。遺傳是指子代總是和親代相似。遺傳性是一切生物所共有的特性，它使得生物能夠把其特性、性狀傳給后代。遺傳是生物進(jìn)化的基礎(chǔ)。變異是指子代和親代有某些不相似的現(xiàn)象，即子代永遠(yuǎn)不會和親代完全一樣。它是一切生物所具有的共有特性，是生物個體之間相互區(qū)別的基礎(chǔ)。引起變異的原因主要是生活環(huán)境的影響及雜交等。生物的變異性為生物的進(jìn)化和發(fā)展創(chuàng)造了條件。5.1.1基本遺傳學(xué)基礎(chǔ)遺傳算法是根據(jù)生選擇決定生物進(jìn)化的方向。在進(jìn)化過程中，有的要保留，有的要被淘汰。自然選擇是指生物在自然界的生存環(huán)境中適者生存，不適者被淘汰的過程。通過不斷的自然選擇，有利于生存的變異就會遺傳下去，積累起來，使變異越來越大，逐步產(chǎn)生了新的物種。生物就是在遺傳、變異和選擇三種因素的綜合作用過程中，不斷地向前發(fā)展和進(jìn)化。選擇是通過遺傳和變異起作用的，變異為選擇提供資料，遺傳鞏固與積累選擇的資料，而選擇則能控制變異與遺傳的方向，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。遺傳算法正是吸取了自然生物系統(tǒng)“適者生存、優(yōu)勝劣汰”的進(jìn)化原理，從而使它能夠提供一個在復(fù)雜空間中隨機(jī)搜索的方法，為解決許多傳統(tǒng)的優(yōu)化方法難以解決的優(yōu)化問題提供了新的途徑。遺傳算法詳解-課件5.1.2遺傳算法的原理和特點遺傳算法將生物進(jìn)化原理引入待優(yōu)化參數(shù)形成的編碼串群體中，按著一定的適值函數(shù)及一系列遺傳操作對各個體進(jìn)行篩選，從而使適值高的個體被保留下來，組成新的群體，新群體包含上一代的大量信息，并且引入了新的優(yōu)于上一代的個體。這樣周而復(fù)始，群體中各個體適值不斷提高，直至滿足一定的極限條件。此時，群體中適值最高的個體即為待優(yōu)化參數(shù)的最優(yōu)解。正是由于遺傳算法獨具特色的工作原理，使它能夠在復(fù)雜空間進(jìn)行全局優(yōu)化搜索，并且具有較強(qiáng)的魯棒性；另外，遺傳算法對于搜索空間，基本上不需要什么限制性的假設(shè)（如連續(xù)、可微及單峰等）。5.1.2遺傳算法的原理和特點遺傳算法將遺傳算法的特點同常規(guī)優(yōu)化算法相比，遺傳算法有以下特點：①遺傳算法是對參數(shù)的編碼進(jìn)行操作，而非對參數(shù)本身。②遺傳算法是從許多點開始并行操作，并非局限于一點，從而可有效防止搜索過程收斂于局部最優(yōu)解。③遺傳算法通過目標(biāo)函數(shù)計算適值，并不需要其它推導(dǎo)和附加信息，因而對問題的依賴性較小。

遺傳算法的特點同常規(guī)優(yōu)化算法相比，遺傳算法有以下特點：④遺傳算法的尋優(yōu)規(guī)則是由概率決定的，而非確定性的。⑤遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機(jī)搜索。⑥遺傳算法對所求解的優(yōu)化問題沒有太多的數(shù)學(xué)要求。⑦遺傳算法具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度。遺傳算法詳解-課件5.1.3遺傳算法的基本操作一般的遺傳算法都包含三個基本操作：復(fù)制(reproduction)、交叉(crossover)和變異(mutation)。

1.復(fù)制

復(fù)制（又稱繁殖），是從一個舊種群（oldpopulation）中選擇生命力強(qiáng)的字符串（individualstring）產(chǎn)生新種群的過程?；蛘哒f，復(fù)制是個體位串根據(jù)其目標(biāo)函數(shù)f（即適值函數(shù)）拷貝自己的過程。直觀地講，可以把目標(biāo)函數(shù)f看作是期望的最大效益的某種量度。根據(jù)位串的適值所進(jìn)行的拷貝，意味著具有較高適值的位串更有可能在下一代中產(chǎn)生一個或多個子孫。顯然，在復(fù)制操作過程中，目標(biāo)函數(shù)(適值)是該位串被復(fù)制或被淘汰的決定因素。

5.1.3遺傳算法的基本操作一般的遺傳算法都包含三個基本復(fù)制操作的初始種群(舊種群)的生成往往是隨機(jī)產(chǎn)生的。例如，通過擲硬幣20次產(chǎn)生維數(shù)n＝4的初始種群如下(正面=1，背面=0)：

01101110000100010011顯然，該初始種群可以看成是一個長度為五位的無符號二進(jìn)制數(shù)，將其編成四個位串，并解碼為十進(jìn)制的數(shù)：位串1：

0110113位串2：

1100024位串3：

010008位串4：

1001119

復(fù)制操作的初始種群(舊種群)的生成往往是隨機(jī)產(chǎn)生的。通過一個5位無符號二進(jìn)制數(shù)，可以得到一個從0到31的數(shù)值x，它可以是系統(tǒng)的某個參數(shù)。計算目標(biāo)函數(shù)或適值f(x)=x2，其結(jié)果如表6-1所示。計算種群中所有個體位串的適值之和，同時，計算種群全體的適值比例，其結(jié)果示于表中。

通過一個5位無符號二進(jìn)制數(shù)，可以得到一個從0到31的轉(zhuǎn)輪法轉(zhuǎn)輪法把種群中所有個體位串適值的總和看作一個輪子的圓周，而每個個體位串按其適值在總和中所占的比例占據(jù)輪子的一個扇區(qū)。按表5-1可繪制如圖的轉(zhuǎn)輪。復(fù)制時，只要簡單地轉(zhuǎn)動這個按權(quán)重劃分的轉(zhuǎn)輪4次，從而產(chǎn)生4個下一代的種群。例如對于表5-1中的位串1，其適值為169，為總適值的14.4%。因此，每旋轉(zhuǎn)一次轉(zhuǎn)輪指向該位串的概率為0.144。每當(dāng)需要下一個后代時，就旋轉(zhuǎn)一下這個按權(quán)重劃分的轉(zhuǎn)輪，產(chǎn)生一個復(fù)制的候選者。這樣位串的適值越高，在其下代中產(chǎn)生的后代就越多。

圖5-1轉(zhuǎn)輪法轉(zhuǎn)輪法把種群中所有個體位串適值的總和看作一個輪子的圓圖當(dāng)一個位串被選中時，此位串將被完整地復(fù)制，然后將復(fù)制位串送入匹配集（緩沖區(qū)）中。旋轉(zhuǎn)4次轉(zhuǎn)輪即產(chǎn)生4個位串。這4個位串是上代種群的復(fù)制，有的位串可能被復(fù)制一次或多次，有的可能被淘汰。在本例中，位串3被淘汰，位串4被復(fù)制一次。如表6-2所示，適值最好的有較多的拷貝，即給予適合于生存環(huán)境的優(yōu)良個體更多繁殖后代的機(jī)會，從而使優(yōu)良特性得以遺傳，反之，最差的則被淘汰。當(dāng)一個位串被選中時，此位串將被完整地復(fù)制，然后將復(fù)制

2.交叉

簡單的交叉分兩步實現(xiàn)。第一步是將新復(fù)制產(chǎn)生的位串個體隨機(jī)兩兩配對；第二步是隨機(jī)選擇交叉點，對匹配的位串進(jìn)行交叉繁殖，產(chǎn)生一對新的位串。具體過程如下：設(shè)位串的字符長度為l，在[1，l－1]的范圍內(nèi)，隨機(jī)地選取一個整數(shù)值k作為交叉點。將兩個配對串從第k位右邊部分的所有字符進(jìn)行交換，從而生成兩個新的位串。例如，在表6-2中，已知位串的字符長度l=5，隨機(jī)選取k=4，對兩個初始的位串個體A1和A2進(jìn)行配對，交叉操作的位置用分隔符“|”表示為：A1=0110|1A2=1100|0交叉操作后產(chǎn)生了兩個新的字符串為：

A1’=01100

A2’=11001

2.交叉一般的交叉操作過程：

遺傳算法的有效性主要來自于復(fù)制和交叉操作。復(fù)制雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的個體；交叉模擬生物進(jìn)化過程中的繁殖現(xiàn)象，通過兩個個體的交換組合，來創(chuàng)造新的優(yōu)良個體。表6-3列出了交叉操作之后的結(jié)果數(shù)據(jù)，從中可以看出交叉操作的具體過程。首先，隨機(jī)配對匹配集中的個體，將位串1、2配對，位串3、4配對；然后，隨機(jī)選取交叉點，設(shè)位串1、2的交叉點為k=4，二者只交換最后一位，從而生成兩個新的位串，即

圖5-2交叉操作一般的交叉操作過程：圖5-2交叉操作位串3、4的交叉點為k=2，二者交換后三位，生成兩個新的位串，即

位串3、4的交叉點為k=2，二者交換后三位，生成兩個新的位串單點交叉與多點交叉上述例子中交叉的位置是一個，稱單點交叉。即指個體切斷點有一處，由于進(jìn)行個體間的組合替換生成兩個新個體，位串個體長度為l時，單點交叉可能有l(wèi)－1個不同的交叉。

多點交叉是允許個體的切斷點有多個，每個切斷點在兩個個體間進(jìn)行個體的交叉，生成兩個新個體。

單點交叉與多點交叉3.變異

盡管復(fù)制和交叉操作很重要，在遺傳算法中是第一位的，但不能保證不會遺漏一些重要的遺傳信息。在人工遺傳系統(tǒng)中，變異用來防止這種遺漏。在簡單遺傳算法中，變異就是在某個字符串當(dāng)中把某一位的值偶然的（概率很小的）隨機(jī)的改變，即在某些特定位置上簡單地把1變?yōu)?，或反之。當(dāng)它有節(jié)制地和交叉一起使用時，它就是一種防止過度成熟而丟失重要概念的保險策略。例如，隨機(jī)產(chǎn)生一個種群，如表所示。在該表所列種群中，無論怎樣交叉，在第4位上都不可能得到有1的位串。若優(yōu)化的結(jié)果要求該位是1，顯然僅靠交叉是不夠的，還需要有變異，即特定位置上的0和1之間的轉(zhuǎn)變。

3.變異變異在遺傳算法中的作用是第二位的，但卻是必不可少的。變異運算用來模擬生物在自然界的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)改變遺傳基因（即位串個體中某一位）的值。通過變異操作，可確保種群中遺傳基因類型的多樣性，以使搜索能在盡可能大的空間中進(jìn)行，避免丟失在搜索中有用的遺傳信息而陷入局部解。根據(jù)統(tǒng)計，變異的概率為0.001，即變異的頻率為每千位傳送中只變異一位。在表6-3的種群中共有20個字符（每位串的長度為5個字符）。期望變異的字符串位數(shù)為20×0.001=0.02（位），所以在此例中無位值的改變。從表6-2和表6-3可以看出，雖然僅進(jìn)行一代遺傳操作，但種群適值的平均值和最大值卻比初始種群有了很大的提高，平均適值由293變到439，最大值由576變到729。這說明隨著遺傳運算的進(jìn)行，種群正向著優(yōu)化的方向發(fā)展。

變異在遺傳算法中的作用是第二位的，但卻是必不可少的。遺傳算法在以下幾個方面不同于傳統(tǒng)優(yōu)化方法

①

遺傳算法只對參數(shù)集的編碼進(jìn)行操作，而不是參數(shù)集本身。②

遺傳算法的搜索始于解的一個種群，而不是單個解，因而可以有效地防止搜索過程收斂于局部最優(yōu)解。③

遺傳算法只使用適值函數(shù)，而不使用導(dǎo)數(shù)和其它附屬信息，從而對問題的依賴性小。④

遺傳算法采用概率的、而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則，即具有隨機(jī)操作算子。

遺傳算法在以下幾個方面不同于傳統(tǒng)優(yōu)化方法

①遺傳算法只對

圖5–3

遺傳算法的工作原理示意圖圖5–3遺傳算法的工作原理示意圖5.2.1目標(biāo)函數(shù)值到適值形式的映射適值是非負(fù)的，任何情況下總希望越大越好；而目標(biāo)函數(shù)有正、有負(fù)、甚至可能是復(fù)數(shù)值；且目標(biāo)函數(shù)和適值間的關(guān)系也多種多樣。如求最大值對應(yīng)點時，目標(biāo)函數(shù)和適值變化方向相同；求最小值對應(yīng)點時，變化方向恰好相反；目標(biāo)函數(shù)值越小的點，適值越大。因此，存在目標(biāo)函數(shù)值向適值映射的問題。

5.2遺傳算法應(yīng)用中的一些基本問題

5.2.1目標(biāo)函數(shù)值到適值形式的映射適值是首先應(yīng)保證映射后的適值是非負(fù)的，其次目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對應(yīng)于適值增大的方向。對最小化問題，一般采用如下適值函數(shù)f(x)和目標(biāo)函數(shù)g(x)的映射關(guān)系：

(5-6)其中：cmax可以是一個輸入?yún)?shù)，或是理論上的最大值，或是到目前所有代（或最近的k代）之中見到的g(x)的最大值，此時cmax隨著代數(shù)會有所變化。首先應(yīng)保證映射后的適值是非負(fù)的，其次目標(biāo)函數(shù)對最大化問題，一般采用下述方法：(5-7)式中:cmin既可以是輸入值也可以是當(dāng)前最小值或最近的k代中的最小值。對指數(shù)函數(shù)問題，一般采用下述方法：其中：c一般取1.618或2（最大化），0.618（最小化）。這樣，既保證了f(x)≥0又使f(x)的增大方向與優(yōu)化方向一致。對最大化問題，一般采用下述方法：5.2.2適值的調(diào)整為了使遺傳算法有效地工作，必須保持種群內(nèi)位串的多樣性和位串之間的競爭機(jī)制?，F(xiàn)將遺傳算法的運行分為開始、中間和結(jié)束三個階段來考慮：在開始階段，若一個規(guī)模不太大的種群內(nèi)有少數(shù)非凡的個體（適值很高的位串），按通常的選擇方法（選擇復(fù)制的概率為fi/Σfi，期望的復(fù)制數(shù)為fi/），這些個體會被大量地復(fù)制，在種群中占有大的比重，這樣就會減少種群的多樣性，導(dǎo)致過早收斂，從而可能丟失一些有意義的搜索點或最優(yōu)點，而進(jìn)入局部最優(yōu)；在結(jié)束階段，即使種群內(nèi)保持了很大的多樣性，但若所有或大多數(shù)個體都有很高的適值，從而種群平均適值和最大適值相差無幾，則平均適值附近的個體和具有最高適值的個體，被選中的機(jī)會相同，這樣選擇就成了一個近乎隨機(jī)的步驟，適值的作用就會消失，從而使搜索性能得不到明顯改進(jìn)。因此，有必要對種群內(nèi)各位串的適值進(jìn)行有效調(diào)整，既不能相差太大，又要拉開檔次，強(qiáng)化位串之間的競爭性。5.2.2適值的調(diào)整5.2.3編碼原則遺傳算法參數(shù)編碼原則有兩種：深層意義上的建筑塊原則和最小符號表原則。而后者是一種應(yīng)用廣泛的實用原則。最小符號表原則要求選擇一個使問題得以自然表達(dá)的最小符號編碼表。在前面討論中使用的都是二進(jìn)制符號編碼表{0,1}，任何一個長度為l的位串都包含在{0,1}l中。根據(jù)遺傳算法的模式理論，遺傳算法能有效工作的根本原因，在于其能有效的處理種群中的大量模式，尤其是那些定義長度短、確定位數(shù)少、適值高的模式（即建筑塊）。因此，編碼應(yīng)使確定規(guī)模的種群中包含盡可能多的模式。5.2.3編碼原則遺傳算法參數(shù)編碼原則有表6-5給出了一個參數(shù)的二進(jìn)制編碼和非二進(jìn)制編碼的對比情況，即將[0,31]上的二進(jìn)制整數(shù)一一對應(yīng)地映射到一個有32個字母的符號表中，這個符號表包含26個英文字母（A～Z）和6個數(shù)字（1～6）。在二進(jìn)制編碼中，通過代碼表中小部分關(guān)鍵代碼可以找到重要的相似性而在非二進(jìn)制編碼中，只能看到單一代碼的符號表，看不出代碼中的相似性。為了進(jìn)一步了解二進(jìn)制編碼的數(shù)學(xué)意義，假設(shè)有一個非二進(jìn)制的包含k個字母編碼的符號表V’及二進(jìn)制編碼的符號表V，即V’={a1,a2,…,ak}V={0,1}表6-5給出了一個參數(shù)的二進(jìn)制編碼和非二進(jìn)制編碼的對比情況，5.3.1復(fù)制方法的改進(jìn)1．穩(wěn)態(tài)復(fù)制法

該方法保證種群中最優(yōu)秀的個體在進(jìn)化過程中不被刪除，這在很大程度上減少了有效基因的丟失。在經(jīng)過交叉、變異產(chǎn)生的新種群中，只有一個或兩個優(yōu)秀個體被選進(jìn)下一代種群，替代原有種群中的最差個體。

5.3.1復(fù)制方法的改進(jìn)1．穩(wěn)態(tài)復(fù)制法

2．選擇種子法該法也稱最優(yōu)串復(fù)制法，它保證了最優(yōu)的個體被選進(jìn)下一代進(jìn)化種群。其執(zhí)行過程如下：①隨機(jī)初始化種群N(0)，種群大小為n。②計算種群中所有個體適值。③對以后的種群N(t)進(jìn)行如下操作，直至滿足條件或達(dá)到進(jìn)化代數(shù)。根據(jù)個體適值大小隨機(jī)選出n個個體組成種群N0(t)，并復(fù)制一份為N1(t)，對種群N0(t)實施交叉操作，對種群N1(t)實施基因突變，用以防止有效基因丟失。④計算種群N0(t)、N1(t)和N(t)的個體適值，從中選出最好的n個個體構(gòu)成下一代種群N(t＋1)，轉(zhuǎn)至③。2．選擇種子法3．確定性復(fù)制法

在確定性復(fù)制法中，復(fù)制的概率按常規(guī)計算為：Pi＝fi/∑fi。對個體Ai，其期望的后代數(shù)目ei，計算為：ei＝nPi。每一位串個體按ei的整數(shù)部分分配后代數(shù)，種群的其余部分按順序表由高到低來填充。4．置換式余數(shù)隨機(jī)復(fù)制法

這方法開始與上述確定性復(fù)制法一樣，期望的個體數(shù)如前分配為ei的整數(shù)部分；但ei的余數(shù)部分用來計算轉(zhuǎn)輪法中的權(quán)值，以補(bǔ)充種群總數(shù)。5．非置換式余數(shù)隨機(jī)復(fù)制法這方法開始也與上述確定性復(fù)制法一樣，而ei的余數(shù)部分按概率來處理。換句話說，個體至少復(fù)制一個與ei整數(shù)部分相等的后代，然后以ei的余數(shù)部分為概率來復(fù)制其余的后代，直至種群的總數(shù)達(dá)到n。例如一個具有期望復(fù)制值為1.5的個體，它可以復(fù)制產(chǎn)生一個后代，并以0.5概率產(chǎn)生另一個后代。試驗表明，這種方法優(yōu)于其它復(fù)制方法。3．確定性復(fù)制法

5.3.2高級GA算法為改善SGA的魯棒性，在復(fù)制、交叉和變異運算的基礎(chǔ)上，再考慮兩種類型的基因運算，即為微運算和宏運算。多點交叉微運算是在個體級別上的運算，重組宏運算是在種群級別上的運算。5.3.2高級GA算法為改善SGA的魯棒性5.4基于遺傳算法的系統(tǒng)在線辨識

5.4.1遺傳算法在參數(shù)辨識中的應(yīng)用

5.4.2遺傳算法參數(shù)辨識仿真示例

5.4基于遺傳算法的系統(tǒng)在線辨識5.4.1遺傳算法在5.4.1遺傳算法在參數(shù)辨識中的應(yīng)用1．離散系統(tǒng)參數(shù)估計

設(shè)線性離散系統(tǒng)的數(shù)學(xué)模型為：

(5-18)式中：d為滯后時間，ξ(k)為零均值的噪聲序列（方差為σ2），z-1為后移算子。5.4.1遺傳算法在參數(shù)辨識中的應(yīng)用1．離散系統(tǒng)參數(shù)估計假定A(z-1)、B(z-1)和C(z-1)未知，則待辨識參數(shù)向量包含na+nb+nc+1個參數(shù)，即(5-19)真參數(shù)為：(5-20)要應(yīng)用遺傳算法對參數(shù)向量θ進(jìn)行在線優(yōu)化的參數(shù)辨識，必須解決兩個問題，一個是確定多參數(shù)編碼映射方法，另一個是如何根據(jù)目標(biāo)函數(shù)確定適值。假定A(z-1)、B(z-1)和C(z-1)未2.參數(shù)級聯(lián)定點映射編碼

采用多參數(shù)級聯(lián)定點映射編碼原則進(jìn)行編碼，可根據(jù)辨識精度確定每個參數(shù)的二進(jìn)制編碼長度。假如每個參數(shù)線性映射在[-2l-1,+2l-1]范圍內(nèi)，且要求辨識精度<2-m，則每個參數(shù)需要m+l位；若已知時滯d≤2n，則時滯可用n位編碼，則各參數(shù)編碼組成一個整體位串的長為(na+nb+nc)×(l+m)+n，這個整體位串就是系統(tǒng)待辨識參數(shù)的一個解。2.參數(shù)級聯(lián)定點映射編碼

采用多參數(shù)級聯(lián)定點映射編碼原則設(shè)整體位串構(gòu)成的種群數(shù)為N，第p代的第j個（1≤j≤N）位串所對應(yīng)的參數(shù)為：(5-21)根據(jù)辨識結(jié)果，有預(yù)測輸出和預(yù)測輸出誤差，它們分別滿足：(5-22)(5-23)設(shè)整體位串構(gòu)成的種群數(shù)為N，第p代的第j個（1≤j≤N）位串3.目標(biāo)函數(shù)到適值形式的映射

為保證映射后的適值是非負(fù)的，選擇目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對應(yīng)于適值的增大方向。由式(5-6)的映射關(guān)系，可選擇適值函數(shù)為：

(5-24)求和m+1步的意義在于能進(jìn)一步考察辨識參數(shù)與真參數(shù)的擬合情況。在遺傳算法操作過程中，可能存在這樣的參數(shù)，它離真值很遠(yuǎn)，但經(jīng)線性組合后某步預(yù)測輸出與實際輸出相差不大，求和可以避免這樣的參數(shù)集取得高適值以致出現(xiàn)錯誤的收斂。m的值越大，適值函數(shù)的可信度就越高，m的上限可取為k值，cmax值是一足夠大的正數(shù)，它與問題的解有關(guān)。3.目標(biāo)函數(shù)到適值形式的映射

為保證映射后的適值是非負(fù)的在計算出種群中每個個體的適值后，需要對它們規(guī)范化，先求出其平均適值為：(5-25)規(guī)范化適值為：(5-26)用種群規(guī)范化適值與平均適值的偏差的平方和來定義收斂域，即(5-27)其中：δ是一個定義的收斂域，例如若設(shè)δ<0.0001，則可認(rèn)為種群已經(jīng)收斂，這時種群中適值最大的個體就是當(dāng)前收斂條件下的最優(yōu)者。在計算出種群中每個個體的適值后，需要對它們規(guī)范化5.4.2遺傳算法參數(shù)辨識仿真示例設(shè)線性離散系統(tǒng)的數(shù)學(xué)模型如式（5–13）所示，其中d=2采用偽隨機(jī)二進(jìn)制序列（PRBS）輸入，辨識系統(tǒng)參數(shù)為及時滯。設(shè)參數(shù)的范圍是[-2,+2]，要求辨識精度≤0.02，則每個參數(shù)需要用8位的位串表示，若時滯d不大于4，則時滯可用2位的位串表示，所以參數(shù)集位串長度為4×8+2=34位。

5.4.2遺傳算法參數(shù)辨識仿真示例設(shè)線性離散系統(tǒng)的數(shù)學(xué)模取種群規(guī)模N=50，交叉概率Pc=0.90；變異概率Pm=0.001。適值函數(shù)中的cmax值分段選取。在操作初期，主要強(qiáng)調(diào)個體之間的多樣性，可將cmax值稍微取大些，cmax=1.85×m；操作后期，強(qiáng)調(diào)競爭性，cmax值取小些，cmax=1.6×m。兼顧計算速度和適值可信度，取10<m<30。在操作初期，在每一代適值規(guī)范化之后，要保持種群個體中的無子女個體占種群的百分比為一定值，若超過該值，則認(rèn)為是非成熟收斂。一般將這個臨界值定義在20%左右。定義辨識收斂域，δ<0.0001，滿足收斂條件時，種群中適值最高的個體就是當(dāng)前最優(yōu)者。取種群規(guī)模N=50，交叉概率Pc=0.90；變異概率Pm=0遺傳算法參數(shù)辨識運算步驟可歸納如下：①種群初始化，隨機(jī)生成N個參數(shù)集的位串。②采用偽隨機(jī)二進(jìn)制序列（PRBS）作為辨識輸入信號，采樣系統(tǒng)實際輸出y(k)。③按適值函數(shù)評價，并計算整體的平均性能。④參數(shù)辨識是否收斂到指定的精度內(nèi)或仿真步數(shù)是否達(dá)到最大，若是，則仿真結(jié)束。⑤是否過早出現(xiàn)非成熟收斂，若是,則進(jìn)行適值調(diào)整。⑥按規(guī)范適值或適值調(diào)整結(jié)果復(fù)制下一代，并按概率進(jìn)行交叉和變異操作。⑦查看上一代中最優(yōu)秀個體是否保留在本代，若不是，則取代本代中任意一個個體，將優(yōu)秀個體無遺傳保留。⑧轉(zhuǎn)步驟②遺傳算法參數(shù)辨識運算步驟可歸納如下：①種群初始化，隨機(jī)生成圖5–14a顯示了初期種群的系統(tǒng)辨識的平均值和整體收斂情況?？梢钥闯?，參數(shù)和時滯是同步的，仿真在第150步之后就明顯地向真值收斂。圖5–14b顯示了后期第800步之后的系統(tǒng)辨識的情況，這時，種群平均性能已經(jīng)提高很多，種群的相似性越來越明顯，所以平均參數(shù)和時滯波動較小，仿真在1677步達(dá)到收斂，這時平均m參數(shù)和時滯d為a1=-1.712240,a2=0.727344b0=0.802865,b1=0.802865,d0=2.000圖5-14系統(tǒng)辨識(a)初期系統(tǒng)辨識(b)后期系統(tǒng)辨識

圖5–14a顯示了初期種群的系統(tǒng)辨識的平均值和