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