遺傳算法詳解ppt課件

5.遺傳算法,遺傳算法（geneticalgorithms,簡稱GA）是人工智能的重要分支，是基于達爾文進化論，在微型計算機上模擬生命進化機制而發(fā)展起來的一門新學(xué)科。它根據(jù)適者生存、優(yōu)勝劣汰等自然進化規(guī)則來進行搜索計算和問題求解。對許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的非常復(fù)雜問題，特別是最優(yōu)化問題，GA提供了一個行之有效的新途徑。近年來，由于遺傳算法求解復(fù)雜優(yōu)化問題的巨大潛力及其在工業(yè)控制工程領(lǐng)域的成功應(yīng)用，這種算法受到了廣泛的關(guān)注。,5.1.1基本遺傳學(xué)基礎(chǔ),遺傳算法是根據(jù)生物進化的模型提出的一種優(yōu)化算法。自然選擇學(xué)說是進化論的中心內(nèi)容，根據(jù)進化論，生物的發(fā)展進化主要由三個原因，即遺傳、變異和選擇。遺傳是指子代總是和親代相似。遺傳性是一切生物所共有的特性，它使得生物能夠把其特性、性狀傳給后代。遺傳是生物進化的基礎(chǔ)。變異是指子代和親代有某些不相似的現(xiàn)象，即子代永遠不會和親代完全一樣。它是一切生物所具有的共有特性，是生物個體之間相互區(qū)別的基礎(chǔ)。引起變異的原因主要是生活環(huán)境的影響及雜交等。生物的變異性為生物的進化和發(fā)展創(chuàng)造了條件。,選擇決定生物進化的方向。在進化過程中，有的要保留，有的要被淘汰。自然選擇是指生物在自然界的生存環(huán)境中適者生存，不適者被淘汰的過程。通過不斷的自然選擇，有利于生存的變異就會遺傳下去，積累起來，使變異越來越大，逐步產(chǎn)生了新的物種。生物就是在遺傳、變異和選擇三種因素的綜合作用過程中，不斷地向前發(fā)展和進化。選擇是通過遺傳和變異起作用的，變異為選擇提供資料，遺傳鞏固與積累選擇的資料，而選擇則能控制變異與遺傳的方向，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。遺傳算法正是吸取了自然生物系統(tǒng)“適者生存、優(yōu)勝劣汰”的進化原理，從而使它能夠提供一個在復(fù)雜空間中隨機搜索的方法，為解決許多傳統(tǒng)的優(yōu)化方法難以解決的優(yōu)化問題提供了新的途徑。,5.1.2遺傳算法的原理和特點,遺傳算法將生物進化原理引入待優(yōu)化參數(shù)形成的編碼串群體中，按著一定的適值函數(shù)及一系列遺傳操作對各個體進行篩選，從而使適值高的個體被保留下來，組成新的群體，新群體包含上一代的大量信息，并且引入了新的優(yōu)于上一代的個體。這樣周而復(fù)始，群體中各個體適值不斷提高，直至滿足一定的極限條件。此時，群體中適值最高的個體即為待優(yōu)化參數(shù)的最優(yōu)解。正是由于遺傳算法獨具特色的工作原理，使它能夠在復(fù)雜空間進行全局優(yōu)化搜索，并且具有較強的魯棒性；另外，遺傳算法對于搜索空間，基本上不需要什么限制性的假設(shè)（如連續(xù)、可微及單峰等）。,遺傳算法的特點,同常規(guī)優(yōu)化算法相比，遺傳算法有以下特點：遺傳算法是對參數(shù)的編碼進行操作，而非對參數(shù)本身。遺傳算法是從許多點開始并行操作，并非局限于一點，從而可有效防止搜索過程收斂于局部最優(yōu)解。遺傳算法通過目標(biāo)函數(shù)計算適值，并不需要其它推導(dǎo)和附加信息，因而對問題的依賴性較小。,遺傳算法的尋優(yōu)規(guī)則是由概率決定的，而非確定性的。遺傳算法在解空間進行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機搜索。遺傳算法對所求解的優(yōu)化問題沒有太多的數(shù)學(xué)要求。遺傳算法具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度。,5.1.3遺傳算法的基本操作,一般的遺傳算法都包含三個基本操作：復(fù)制(reproduction)、交叉(crossover)和變異(mutation)。1.復(fù)制復(fù)制（又稱繁殖），是從一個舊種群（oldpopulation）中選擇生命力強的字符串（individualstring）產(chǎn)生新種群的過程。或者說，復(fù)制是個體位串根據(jù)其目標(biāo)函數(shù)f（即適值函數(shù)）拷貝自己的過程。直觀地講，可以把目標(biāo)函數(shù)f看作是期望的最大效益的某種量度。根據(jù)位串的適值所進行的拷貝，意味著具有較高適值的位串更有可能在下一代中產(chǎn)生一個或多個子孫。顯然，在復(fù)制操作過程中，目標(biāo)函數(shù)(適值)是該位串被復(fù)制或被淘汰的決定因素。,復(fù)制操作的初始種群(舊種群)的生成往往是隨機產(chǎn)生的。例如，通過擲硬幣20次產(chǎn)生維數(shù)n4的初始種群如下(正面=1，背面=0)：01101110000100010011顯然，該初始種群可以看成是一個長度為五位的無符號二進制數(shù)，將其編成四個位串，并解碼為十進制的數(shù)：位串1：0110113位串2：1100024位串3：010008位串4：1001119,通過一個5位無符號二進制數(shù)，可以得到一個從0到31的數(shù)值x，它可以是系統(tǒng)的某個參數(shù)。計算目標(biāo)函數(shù)或適值f(x)=x2，其結(jié)果如表6-1所示。計算種群中所有個體位串的適值之和，同時，計算種群全體的適值比例，其結(jié)果示于表中。,轉(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,當(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)良個體更多繁殖后代的機會，從而使優(yōu)良特性得以遺傳，反之，最差的則被淘汰。,2.交叉簡單的交叉分兩步實現(xiàn)。第一步是將新復(fù)制產(chǎn)生的位串個體隨機兩兩配對；第二步是隨機選擇交叉點，對匹配的位串進行交叉繁殖，產(chǎn)生一對新的位串。具體過程如下：設(shè)位串的字符長度為l，在1，l1的范圍內(nèi)，隨機地選取一個整數(shù)值k作為交叉點。將兩個配對串從第k位右邊部分的所有字符進行交換，從而生成兩個新的位串。例如，在表6-2中，已知位串的字符長度l=5，隨機選取k=4，對兩個初始的位串個體A1和A2進行配對，交叉操作的位置用分隔符“|”表示為：A1=0110|1A2=1100|0交叉操作后產(chǎn)生了兩個新的字符串為：A1=01100A2=11001,一般的交叉操作過程：遺傳算法的有效性主要來自于復(fù)制和交叉操作。復(fù)制雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的個體；交叉模擬生物進化過程中的繁殖現(xiàn)象，通過兩個個體的交換組合，來創(chuàng)造新的優(yōu)良個體。表6-3列出了交叉操作之后的結(jié)果數(shù)據(jù)，從中可以看出交叉操作的具體過程。首先，隨機配對匹配集中的個體，將位串1、2配對，位串3、4配對；然后，隨機選取交叉點，設(shè)位串1、2的交叉點為k=4，二者只交換最后一位，從而生成兩個新的位串，即,圖5-2交叉操作,位串3、4的交叉點為k=2，二者交換后三位，生成兩個新的位串，即,單點交叉與多點交叉,上述例子中交叉的位置是一個，稱單點交叉。即指個體切斷點有一處，由于進行個體間的組合替換生成兩個新個體，位串個體長度為l時，單點交叉可能有l(wèi)1個不同的交叉。多點交叉是允許個體的切斷點有多個，每個切斷點在兩個個體間進行個體的交叉，生成兩個新個體。,3.變異盡管復(fù)制和交叉操作很重要，在遺傳算法中是第一位的，但不能保證不會遺漏一些重要的遺傳信息。在人工遺傳系統(tǒng)中，變異用來防止這種遺漏。在簡單遺傳算法中，變異就是在某個字符串當(dāng)中把某一位的值偶然的（概率很小的）隨機的改變，即在某些特定位置上簡單地把1變?yōu)?，或反之。當(dāng)它有節(jié)制地和交叉一起使用時，它就是一種防止過度成熟而丟失重要概念的保險策略。例如，隨機產(chǎn)生一個種群，如表所示。在該表所列種群中，無論怎樣交叉，在第4位上都不可能得到有1的位串。若優(yōu)化的結(jié)果要求該位是1，顯然僅靠交叉是不夠的，還需要有變異，即特定位置上的0和1之間的轉(zhuǎn)變。,變異在遺傳算法中的作用是第二位的，但卻是必不可少的。變異運算用來模擬生物在自然界的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機改變遺傳基因（即位串個體中某一位）的值。通過變異操作，可確保種群中遺傳基因類型的多樣性，以使搜索能在盡可能大的空間中進行，避免丟失在搜索中有用的遺傳信息而陷入局部解。根據(jù)統(tǒng)計，變異的概率為0.001，即變異的頻率為每千位傳送中只變異一位。在表6-3的種群中共有20個字符（每位串的長度為5個字符）。期望變異的字符串位數(shù)為200.001=0.02（位），所以在此例中無位值的改變。從表6-2和表6-3可以看出，雖然僅進行一代遺傳操作，但種群適值的平均值和最大值卻比初始種群有了很大的提高，平均適值由293變到439，最大值由576變到729。這說明隨著遺傳運算的進行，種群正向著優(yōu)化的方向發(fā)展。,遺傳算法在以下幾個方面不同于傳統(tǒng)優(yōu)化方法,遺傳算法只對參數(shù)集的編碼進行操作，而不是參數(shù)集本身。遺傳算法的搜索始于解的一個種群，而不是單個解，因而可以有效地防止搜索過程收斂于局部最優(yōu)解。遺傳算法只使用適值函數(shù)，而不使用導(dǎo)數(shù)和其它附屬信息，從而對問題的依賴性小。遺傳算法采用概率的、而不是確定的狀態(tài)轉(zhuǎn)移規(guī)則，即具有隨機操作算子。,圖53,遺傳算法的工作原理示意圖,5.2.1目標(biāo)函數(shù)值到適值形式的映射,適值是非負的，任何情況下總希望越大越好；而目標(biāo)函數(shù)有正、有負、甚至可能是復(fù)數(shù)值；且目標(biāo)函數(shù)和適值間的關(guān)系也多種多樣。如求最大值對應(yīng)點時，目標(biāo)函數(shù)和適值變化方向相同；求最小值對應(yīng)點時，變化方向恰好相反；目標(biāo)函數(shù)值越小的點，適值越大。因此，存在目標(biāo)函數(shù)值向適值映射的問題。,5.2遺傳算法應(yīng)用中的一些基本問題,首先應(yīng)保證映射后的適值是非負的，其次目標(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ù)會有所變化。,對最大化問題，一般采用下述方法：(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)位串的多樣性和位串之間的競爭機制?，F(xiàn)將遺傳算法的運行分為開始、中間和結(jié)束三個階段來考慮：在開始階段，若一個規(guī)模不太大的種群內(nèi)有少數(shù)非凡的個體（適值很高的位串），按通常的選擇方法（選擇復(fù)制的概率為fi/fi，期望的復(fù)制數(shù)為fi/），這些個體會被大量地復(fù)制，在種群中占有大的比重，這樣就會減少種群的多樣性，導(dǎo)致過早收斂，從而可能丟失一些有意義的搜索點或最優(yōu)點，而進入局部最優(yōu)；在結(jié)束階段，即使種群內(nèi)保持了很大的多樣性，但若所有或大多數(shù)個體都有很高的適值，從而種群平均適值和最大適值相差無幾，則平均適值附近的個體和具有最高適值的個體，被選中的機會相同，這樣選擇就成了一個近乎隨機的步驟，適值的作用就會消失，從而使搜索性能得不到明顯改進。因此，有必要對種群內(nèi)各位串的適值進行有效調(diào)整，既不能相差太大，又要拉開檔次，強化位串之間的競爭性。,5.2.3編碼原則,遺傳算法參數(shù)編碼原則有兩種：深層意義上的建筑塊原則和最小符號表原則。而后者是一種應(yīng)用廣泛的實用原則。最小符號表原則要求選擇一個使問題得以自然表達的最小符號編碼表。在前面討論中使用的都是二進制符號編碼表0,1，任何一個長度為l的位串都包含在0,1l中。根據(jù)遺傳算法的模式理論，遺傳算法能有效工作的根本原因，在于其能有效的處理種群中的大量模式，尤其是那些定義長度短、確定位數(shù)少、適值高的模式（即建筑塊）。因此，編碼應(yīng)使確定規(guī)模的種群中包含盡可能多的模式。,表6-5給出了一個參數(shù)的二進制編碼和非二進制編碼的對比情況，即將0,31上的二進制整數(shù)一一對應(yīng)地映射到一個有32個字母的符號表中，這個符號表包含26個英文字母（AZ）和6個數(shù)字（16）。在二進制編碼中，通過代碼表中小部分關(guān)鍵代碼可以找到重要的相似性而在非二進制編碼中，只能看到單一代碼的符號表，看不出代碼中的相似性。為了進一步了解二進制編碼的數(shù)學(xué)意義，假設(shè)有一個非二進制的包含k個字母編碼的符號表V及二進制編碼的符號表V，即V=a1,a2,akV=0,1,5.3.1復(fù)制方法的改進,1穩(wěn)態(tài)復(fù)制法該方法保證種群中最優(yōu)秀的個體在進化過程中不被刪除，這在很大程度上減少了有效基因的丟失。在經(jīng)過交叉、變異產(chǎn)生的新種群中，只有一個或兩個優(yōu)秀個體被選進下一代種群，替代原有種群中的最差個體。,2選擇種子法該法也稱最優(yōu)串復(fù)制法，它保證了最優(yōu)的個體被選進下一代進化種群。其執(zhí)行過程如下：隨機初始化種群N(0)，種群大小為n。計算種群中所有個體適值。對以后的種群N(t)進行如下操作，直至滿足條件或達到進化代數(shù)。根據(jù)個體適值大小隨機選出n個個體組成種群N0(t)，并復(fù)制一份為N1(t)，對種群N0(t)實施交叉操作，對種群N1(t)實施基因突變，用以防止有效基因丟失。計算種群N0(t)、N1(t)和N(t)的個體適值，從中選出最好的n個個體構(gòu)成下一代種群N(t1)，轉(zhuǎn)至。,3確定性復(fù)制法在確定性復(fù)制法中，復(fù)制的概率按常規(guī)計算為：Pifi/fi。對個體Ai，其期望的后代數(shù)目ei，計算為：einPi。每一位串個體按ei的整數(shù)部分分配后代數(shù)，種群的其余部分按順序表由高到低來填充。4置換式余數(shù)隨機復(fù)制法這方法開始與上述確定性復(fù)制法一樣，期望的個體數(shù)如前分配為ei的整數(shù)部分；但ei的余數(shù)部分用來計算轉(zhuǎn)輪法中的權(quán)值，以補充種群總數(shù)。5非置換式余數(shù)隨機復(fù)制法這方法開始也與上述確定性復(fù)制法一樣，而ei的余數(shù)部分按概率來處理。換句話說，個體至少復(fù)制一個與ei整數(shù)部分相等的后代，然后以ei的余數(shù)部分為概率來復(fù)制其余的后代，直至種群的總數(shù)達到n。例如一個具有期望復(fù)制值為1.5的個體，它可以復(fù)制產(chǎn)生一個后代，并以0.5概率產(chǎn)生另一個后代。試驗表明，這種方法優(yōu)于其它復(fù)制方法。,5.3.2高級GA算法,為改善SGA的魯棒性，在復(fù)制、交叉和變異運算的基礎(chǔ)上，再考慮兩種類型的基因運算，即為微運算和宏運算。多點交叉微運算是在個體級別上的運算，重組宏運算是在種群級別上的運算。,5.4基于遺傳算法的系統(tǒng)在線辨識,5.4.1遺傳算法在參數(shù)辨識中的應(yīng)用5.4.2遺傳算法參數(shù)辨識仿真示例,5.4.1遺傳算法在參數(shù)辨識中的應(yīng)用,1離散系統(tǒng)參數(shù)估計設(shè)線性離散系統(tǒng)的數(shù)學(xué)模型為：(5-18)式中：d為滯后時間，(k)為零均值的噪聲序列（方差為2），z-1為后移算子。,假定A(z-1)、B(z-1)和C(z-1)未知，則待辨識參數(shù)向量包含na+nb+nc+1個參數(shù)，即(5-19)真參數(shù)為：(5-20)要應(yīng)用遺傳算法對參數(shù)向量進行在線優(yōu)化的參數(shù)辨識，必須解決兩個問題，一個是確定多參數(shù)編碼映射方法，另一個是如何根據(jù)目標(biāo)函數(shù)確定適值。,2.參數(shù)級聯(lián)定點映射編碼,采用多參數(shù)級聯(lián)定點映射編碼原則進行編碼，可根據(jù)辨識精度確定每個參數(shù)的二進制編碼長度。假如每個參數(shù)線性映射在-2l-1,+2l-1范圍內(nèi)，且要求辨識精度2-m，則每個參數(shù)需要m+l位；若已知時滯d2n，則時滯可用n位編碼，則各參數(shù)編碼組成一個整體位串的長為(na+nb+nc)(l+m)+n，這個整體位串就是系統(tǒng)待辨識參數(shù)的一個解。,設(shè)整體位串構(gòu)成的種群數(shù)為N，第p代的第j個（1jN）位串所對應(yīng)的參數(shù)為：(5-21)根據(jù)辨識結(jié)果，有預(yù)測輸出和預(yù)測輸出誤差，它們分別滿足：(5-22)(5-23),3.目標(biāo)函數(shù)到適值形式的映射,為保證映射后的適值是非負的，選擇目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對應(yīng)于適值的增大方向。由式(5-6)的映射關(guān)系，可選擇適值函數(shù)為：(5-24)求和m+1步的意義在于能進一步考察辨識參數(shù)與真參數(shù)的擬合情況。在遺傳算法操作過程中，可能存在這樣的參數(shù)，它離真值很遠，但經(jīng)線性組合后某步預(yù)測輸出與實際輸出相差不大，求和可以避免這樣的參數(shù)集取得高適值以致出現(xiàn)錯誤的收斂。m的值越大，適值函數(shù)的可信度就越高，m的上限可取為k值，cmax值是一足夠大的正數(shù)，它與問題的解有關(guān)。,在計算出種群中每個個體的適值后，需要對它們規(guī)范化，先求出其平均適值為：(5-25)規(guī)范化適值為：(5-26)用種群規(guī)范化適值與平均適值的偏差的平方和來定義收斂域，即(5-27)其中：是一個定義的收斂域，例如若設(shè)0.0001，則可認為種群已經(jīng)收斂，這時種群中適值最大的個體就是當(dāng)前收斂條件下的最優(yōu)者。,5.4.2遺傳算法參數(shù)辨識仿真示例,設(shè)線性離散系統(tǒng)的數(shù)學(xué)模型如式（513）所示，其中d=2采用偽隨機二進制序列（PRBS）輸入，辨識系統(tǒng)參數(shù)為及時滯。設(shè)參數(shù)的范圍是-2,+2，要求辨識精度0.02，則每個參數(shù)需要用8位的位串表示，若時滯d不大于4，則時滯可用2位的位串表示，所以參數(shù)集位串長度為48+2=34位。,取種群規(guī)模N=50，交叉概率Pc=0.90；變異概率Pm=0.001。適值函數(shù)中的cmax值分段選取。在操作初期，主要強調(diào)個體之間的多樣性，可