1、1.遺傳算法遺傳算法 遺傳算法（遺傳算法（genetic algorithms,簡稱簡稱GA）是人工智能是人工智能的重要分支，是基于達爾文進化論，在微型計算機上模擬的重要分支，是基于達爾文進化論，在微型計算機上模擬生命進化機制而發展起來的一門新學科。它根據適者生存、生命進化機制而發展起來的一門新學科。它根據適者生存、優勝劣汰等自然進化規則來進行搜索計算和問題求解。對優勝劣汰等自然進化規則來進行搜索計算和問題求解。對許多用傳統數學難以解決或明顯失效的非常復雜問題，特許多用傳統數學難以解決或明顯失效的非常復雜問題，特別是最優化問題，別是最優化問題，GA提供了一個行之有效的新途徑。近提供了一個行之有

2、效的新途徑。近年來，由于遺傳算法求解復雜優化問題的巨大潛力及其在年來，由于遺傳算法求解復雜優化問題的巨大潛力及其在工業控制工程領域的成功應用，這種算法受到了廣泛的關工業控制工程領域的成功應用，這種算法受到了廣泛的關注。注。 1.1.1 基本遺傳學基礎 遺傳算法是根據生物進化的模型提出的一種優化算法。遺傳算法是根據生物進化的模型提出的一種優化算法。自然選擇學說是進化論的中心內容，根據進化論，生物的自然選擇學說是進化論的中心內容，根據進化論，生物的發展進化主要有三個原因，即遺傳、變異和選擇。發展進化主要有三個原因，即遺傳、變異和選擇。 遺傳是指子代總是和親代相似。遺傳性是一切生物所遺傳是指子代總是

3、和親代相似。遺傳性是一切生物所共有的特性，它使得生物能夠把其特性、性狀傳給后代。共有的特性，它使得生物能夠把其特性、性狀傳給后代。遺傳是生物進化的基礎。遺傳是生物進化的基礎。 變異是指子代和親代有某些不相似的現象，即子代永變異是指子代和親代有某些不相似的現象，即子代永遠不會和親代完全一樣。它是一切生物所具有的共有特性，遠不會和親代完全一樣。它是一切生物所具有的共有特性，是生物個體之間相互區別的基礎。引起變異的原因主要是是生物個體之間相互區別的基礎。引起變異的原因主要是生活環境的影響及雜交等。生物的變異性為生物的進化和生活環境的影響及雜交等。生物的變異性為生物的進化和發展創造了條件。發展創造了條

4、件。 選擇決定生物進化的方向。在進化過程中，有的要保選擇決定生物進化的方向。在進化過程中，有的要保留，有的要被淘汰。自然選擇是指生物在自然界的生存環留，有的要被淘汰。自然選擇是指生物在自然界的生存環境中適者生存，不適者被淘汰的過程。通過不斷的自然選境中適者生存，不適者被淘汰的過程。通過不斷的自然選擇，有利于生存的變異就會遺傳下去，積累起來，使變異擇，有利于生存的變異就會遺傳下去，積累起來，使變異越來越大，逐步產生了新的物種。越來越大，逐步產生了新的物種。 生物就是在遺傳、變異和選擇三種因素的綜合作用過生物就是在遺傳、變異和選擇三種因素的綜合作用過程中，不斷地向前發展和進化。選擇是通過遺傳和變異

5、起程中，不斷地向前發展和進化。選擇是通過遺傳和變異起作用的，變異為選擇提供資料，遺傳鞏固與積累選擇的資作用的，變異為選擇提供資料，遺傳鞏固與積累選擇的資料，而選擇則能控制變異與遺傳的方向，使變異和遺傳向料，而選擇則能控制變異與遺傳的方向，使變異和遺傳向著適應環境的方向發展。遺傳算法正是吸取了自然生物系著適應環境的方向發展。遺傳算法正是吸取了自然生物系統統“適者生存、優勝劣汰適者生存、優勝劣汰”的進化原理，從而使它能夠提的進化原理，從而使它能夠提供一個在復雜空間中隨機搜索的方法，為解決許多傳統的供一個在復雜空間中隨機搜索的方法，為解決許多傳統的優化方法難以解決的優化問題提供了新的途徑。優化方法難

6、以解決的優化問題提供了新的途徑。 1.1.2 遺傳算法的原理和特點 遺傳算法將生物進化原理引入待優化參數形成的編碼遺傳算法將生物進化原理引入待優化參數形成的編碼串群體中，按著一定的適值函數及一系列遺傳操作對各個串群體中，按著一定的適值函數及一系列遺傳操作對各個體進行篩選，從而使適值高的個體被保留下來，組成新的體進行篩選，從而使適值高的個體被保留下來，組成新的群體，新群體包含上一代的大量信息，并且引入了新的優群體，新群體包含上一代的大量信息，并且引入了新的優于上一代的個體。這樣周而復始，群體中各個體適值不斷于上一代的個體。這樣周而復始，群體中各個體適值不斷提高，直至滿足一定的極限條件。此時，群體

7、中適值最高提高，直至滿足一定的極限條件。此時，群體中適值最高的個體即為待優化參數的最優解。正是由于遺傳算法獨具的個體即為待優化參數的最優解。正是由于遺傳算法獨具特色的工作原理，使它能夠在復雜空間進行全局優化搜索；特色的工作原理，使它能夠在復雜空間進行全局優化搜索；另外，遺傳算法對于搜索空間，基本上不需要什么限制性另外，遺傳算法對于搜索空間，基本上不需要什么限制性的假設（如連續、可微及單峰等）。的假設（如連續、可微及單峰等）。 遺傳算法的特點遺傳算法的特點同常規優化算法相比，遺傳算法有以下特點：同常規優化算法相比，遺傳算法有以下特點： 遺傳算法是對參數的編碼進行操作，而非對參遺傳算法是對參數的編

8、碼進行操作，而非對參數本身。數本身。 遺傳算法是從許多點開始并行操作，并非局限遺傳算法是從許多點開始并行操作，并非局限于一點，從而可有效防止搜索過程收斂于局部最于一點，從而可有效防止搜索過程收斂于局部最優解。優解。 遺傳算法通過目標函數計算適值，并不需要其遺傳算法通過目標函數計算適值，并不需要其它推導和附加信息，因而對問題的依賴性較小。它推導和附加信息，因而對問題的依賴性較小。 遺傳算法的尋優規則是由概率決定的，而非確遺傳算法的尋優規則是由概率決定的，而非確定性的。定性的。 遺傳算法在解空間進行高效啟發式搜索，而非遺傳算法在解空間進行高效啟發式搜索，而非盲目地窮舉或完全隨機搜索。盲目地窮舉或完

9、全隨機搜索。 遺傳算法對所求解的優化問題沒有太多的數學遺傳算法對所求解的優化問題沒有太多的數學要求。要求。 遺傳算法具有并行計算的特點，因而可通過大遺傳算法具有并行計算的特點，因而可通過大規模并行計算來提高計算速度。規模并行計算來提高計算速度。 1.1.3 遺傳算法的基本操作一般的遺傳算法都包含三個基本操作：復制一般的遺傳算法都包含三個基本操作：復制(reproduction)、交叉交叉(crossover)和變異和變異(mutation)。 1. 復制復制 復制（又稱繁殖），是從一個舊種群（復制（又稱繁殖），是從一個舊種群（old population）中選擇生命力強的字符串（中選擇生命力強

10、的字符串（individual string）產生新種群產生新種群的過程。或者說，復制是個體位串根據其目標函數的過程。或者說，復制是個體位串根據其目標函數f（即即適值函數）拷貝自己的過程。直觀地講，可以把目標函數適值函數）拷貝自己的過程。直觀地講，可以把目標函數f看作是期望的最大效益的某種量度。根據位串的適值所看作是期望的最大效益的某種量度。根據位串的適值所進行的拷貝，意味著具有較高適值的位串更有可能在下一進行的拷貝，意味著具有較高適值的位串更有可能在下一代中產生一個或多個子孫。顯然，在復制操作過程中，目代中產生一個或多個子孫。顯然，在復制操作過程中，目標函數標函數(適值適值)是該位串被復制或

11、被淘汰的決定因素。是該位串被復制或被淘汰的決定因素。 復制操作的初始種群復制操作的初始種群(舊種群舊種群)的生成往往是隨機產生的。的生成往往是隨機產生的。例如，通過擲硬幣例如，通過擲硬幣20次產生維數次產生維數n4的初始種群如下的初始種群如下(正正面面=1，背面，背面=0)： 01101110000100010011 顯然，該初始種群可以看成是一個長度為五位的無符顯然，該初始種群可以看成是一個長度為五位的無符號二進制數，將其編成四個位串，并解碼為十進制的數：號二進制數，將其編成四個位串，并解碼為十進制的數： 位串位串1 1： 01101 13 位串位串2 2： 11000 24 位串位串3 3

12、： 01000 8 位串位串4 4： 10011 19 通過一個通過一個5位無符號二進制數，可以得到一個從位無符號二進制數，可以得到一個從0到到31的數值的數值x，它可以是系統的某個參數。計算目標它可以是系統的某個參數。計算目標函數或適值函數或適值f(x)=x2，其結果如表其結果如表6-1所示。計算種群所示。計算種群中所有個體位串的適值之和，同時，計算種群全體中所有個體位串的適值之和，同時，計算種群全體的適值比例，其結果示于表中。的適值比例，其結果示于表中。 轉輪法轉輪法轉輪法把種群中所有個體位串適值的總和看作一個輪子的圓轉輪法把種群中所有個體位串適值的總和看作一個輪子的圓周，而每個個體位串按

13、其適值在總和中所占的比例占據輪子周，而每個個體位串按其適值在總和中所占的比例占據輪子的一個扇區。按表的一個扇區。按表6-1可繪制如圖的轉輪。可繪制如圖的轉輪。復制時，只要簡單地轉動這個按權重復制時，只要簡單地轉動這個按權重劃分的轉輪劃分的轉輪4次，從而產生次，從而產生4個下一代個下一代的種群。例如對于表的種群。例如對于表6-1中的位串中的位串1，其適值為其適值為169，為總適值的，為總適值的14.4%。因此，每旋轉一次轉輪指向該位串因此，每旋轉一次轉輪指向該位串的概率為的概率為0.144。每當需要下一個后。每當需要下一個后代時，就旋轉一下這個按權重劃分代時，就旋轉一下這個按權重劃分的轉輪，產生

14、一個復制的候選者。的轉輪，產生一個復制的候選者。這樣位串的適值越高，在其下代中這樣位串的適值越高，在其下代中產生的后代就越多。產生的后代就越多。 當一個位串被選中時，此位串將被完整地復當一個位串被選中時，此位串將被完整地復制，然后將復制位串送入匹配集（緩沖區）中。制，然后將復制位串送入匹配集（緩沖區）中。旋轉旋轉4次轉輪即產生次轉輪即產生4個位串。這個位串。這4個位串是上代種個位串是上代種群的復制，有的位串可能被復制一次或多次，有群的復制，有的位串可能被復制一次或多次，有的可能被淘汰。在本例中，位串的可能被淘汰。在本例中，位串3被淘汰，位串被淘汰，位串4被復制一次。如表被復制一次。如表6-2所

15、示，適值最好的有較多的所示，適值最好的有較多的拷貝，即給予適合于生存環境的優良個體更多繁拷貝，即給予適合于生存環境的優良個體更多繁殖后代的機會，從而使優良特性得以遺傳，反之，殖后代的機會，從而使優良特性得以遺傳，反之，最差的則被淘汰。最差的則被淘汰。 2. 交叉 簡單的交叉分兩步實現。第一步是將新復制產生的位串簡單的交叉分兩步實現。第一步是將新復制產生的位串個體隨機兩兩配對；第二步是隨機選擇交叉點，對匹配的位個體隨機兩兩配對；第二步是隨機選擇交叉點，對匹配的位串進行交叉繁殖，產生一對新的位串。具體過程如下：設位串進行交叉繁殖，產生一對新的位串。具體過程如下：設位串的字符長度為串的字符長度為l，

16、在在1，l1的范圍內，隨機地選取一個整的范圍內，隨機地選取一個整數值數值k作為交叉點。將兩個配對串從第作為交叉點。將兩個配對串從第k位右邊部分的所有字位右邊部分的所有字符進行交換，從而生成兩個新的位串。例如，在表符進行交換，從而生成兩個新的位串。例如，在表6-2中，已中，已知位串的字符長度知位串的字符長度l=5，隨機選取隨機選取k=4，對兩個初始的位串個對兩個初始的位串個體體A1和和A2進行配對，交叉操作的位置用分隔符進行配對，交叉操作的位置用分隔符“|”表示為：表示為：A1=0110 | 1A2=1100 | 0交叉操作后產生了兩個新的字符串為：交叉操作后產生了兩個新的字符串為： A1=01

17、100 A2=11001 一般的交叉操作過程：一般的交叉操作過程： 遺傳算法的有效性主要來自于復制和交叉操作。復制雖然能夠從舊種遺傳算法的有效性主要來自于復制和交叉操作。復制雖然能夠從舊種群中選擇出優秀者，但不能創造新的個體；交叉模擬生物進化過程中群中選擇出優秀者，但不能創造新的個體；交叉模擬生物進化過程中的繁殖現象，通過兩個個體的交換組合，來創造新的優良個體。的繁殖現象，通過兩個個體的交換組合，來創造新的優良個體。 表表6-36-3列出了交叉操作之后的結果數據，從中可以看出交叉操作列出了交叉操作之后的結果數據，從中可以看出交叉操作的具體過程。首先，隨機配對匹配集中的個體，將位串的具體過程。首

18、先，隨機配對匹配集中的個體，將位串1 1、2 2配對，位配對，位串串3 3、4 4配對；然后，隨機選取交叉點，設位串配對；然后，隨機選取交叉點，設位串1 1、2 2的交叉點為的交叉點為k k=4=4，二者只交換最后一位，從而生成兩個新的位串，即二者只交換最后一位，從而生成兩個新的位串，即 211001100110010011011021新串新串：串：串位串位串3、4的交叉點為的交叉點為k=2，二者交換后三位，生成兩個新二者交換后三位，生成兩個新的位串，即的位串，即 430000111011110000011143新串新串：串：串單點交叉與多點交叉單點交叉與多點交叉 上述例子中交叉的位置是一個，

19、稱單點交叉。即指個上述例子中交叉的位置是一個，稱單點交叉。即指個體切斷點有一處，由于進行個體間的組合替換生成兩個新體切斷點有一處，由于進行個體間的組合替換生成兩個新個體，位串個體長度為個體，位串個體長度為l時，單點交叉可能有時，單點交叉可能有l1個不同的個不同的交叉。交叉。 多點交叉是允許個體的切斷點有多個，每個切斷點在多點交叉是允許個體的切斷點有多個，每個切斷點在兩個個體間進行個體的交叉，生成兩個新個體。兩個個體間進行個體的交叉，生成兩個新個體。 3. 變異變異 盡管復制和交叉操作很重要，在遺傳算法中是第一位的，但不能保證盡管復制和交叉操作很重要，在遺傳算法中是第一位的，但不能保證不會遺漏一

20、些重要的遺傳信息。在人工遺傳系統中，變異用來防止這不會遺漏一些重要的遺傳信息。在人工遺傳系統中，變異用來防止這種遺漏。在簡單遺傳算法中，變異就是在某個字符串當中把某一位的種遺漏。在簡單遺傳算法中，變異就是在某個字符串當中把某一位的值偶然的（概率很小的）隨機的改變，即在某些特定位置上簡單地把值偶然的（概率很小的）隨機的改變，即在某些特定位置上簡單地把1變為變為0，或反之。當它有節制地和交叉一起使用時，它就是一種防止，或反之。當它有節制地和交叉一起使用時，它就是一種防止過度成熟而丟失重要過度成熟而丟失重要概念的保險策略。例如，隨概念的保險策略。例如，隨機產生一個種群，如表所示。在機產生一個種群，如

21、表所示。在該表所列種群中，無論怎樣交叉，該表所列種群中，無論怎樣交叉，在第在第4位上都不可能得到有位上都不可能得到有1的位串。的位串。若優化的結果要求該位是若優化的結果要求該位是1，顯然僅靠交叉是不夠的，還需要有變顯然僅靠交叉是不夠的，還需要有變異，即特定位置上的異，即特定位置上的0和和1之間的轉變。之間的轉變。 變異在遺傳算法中的作用是第二位的，但卻是必不可變異在遺傳算法中的作用是第二位的，但卻是必不可少的。變異運算用來模擬生物在自然界的遺傳環境中由于少的。變異運算用來模擬生物在自然界的遺傳環境中由于各種偶然因素引起的基因突變，它以很小的概率隨機改變各種偶然因素引起的基因突變，它以很小的概率

22、隨機改變遺傳基因（即位串個體中某一位）的值。通過變異操作，遺傳基因（即位串個體中某一位）的值。通過變異操作，可確保種群中遺傳基因類型的多樣性，以使搜索能在盡可可確保種群中遺傳基因類型的多樣性，以使搜索能在盡可能大的空間中進行，避免丟失在搜索中有用的遺傳信息而能大的空間中進行，避免丟失在搜索中有用的遺傳信息而陷入局部解。根據統計，變異的概率為陷入局部解。根據統計，變異的概率為0.001，即變異的頻，即變異的頻率為每千位傳送中只變異一位。在表率為每千位傳送中只變異一位。在表6-3的種群中共有的種群中共有20個字符（每位串的長度為個字符（每位串的長度為5個字符）。期望變異的字符串個字符）。期望變異的

23、字符串位數為位數為200.001=0.02（位），所以在此例中無位值的改（位），所以在此例中無位值的改變。從表變。從表6-2和表和表6-3可以看出，雖然僅進行一代遺傳操作，可以看出，雖然僅進行一代遺傳操作，但種群適值的平均值和最大值卻比初始種群有了很大的提但種群適值的平均值和最大值卻比初始種群有了很大的提高，平均適值由高，平均適值由293變到變到439，最大值由，最大值由576變到變到729。這說。這說明隨著遺傳運算的進行，種群正向著優化的方向發展。明隨著遺傳運算的進行，種群正向著優化的方向發展。 遺傳算法在以下幾個方面不同于傳統優化遺傳算法在以下幾個方面不同于傳統優化方法方法 遺傳算法只對參

24、數集的編碼進行操作，而不是遺傳算法只對參數集的編碼進行操作，而不是參數集本身。參數集本身。 遺傳算法的搜索始于解的一個種群，而不是單遺傳算法的搜索始于解的一個種群，而不是單個解，因而可以有效地防止搜索過程收斂于局部個解，因而可以有效地防止搜索過程收斂于局部最優解。最優解。 遺傳算法只使用適值函數，而不使用導數和其遺傳算法只使用適值函數，而不使用導數和其它附屬信息，從而對問題的依賴性小。它附屬信息，從而對問題的依賴性小。 遺傳算法采用概率的、而不是確定的狀態轉移遺傳算法采用概率的、而不是確定的狀態轉移規則，即具有隨機操作算子。規則，即具有隨機操作算子。 遺傳算法的工作原理示意圖遺傳算法的工作原理

25、示意圖1.2.1 目標函數值到適值形式的映射 適值是非負的，任何情況下總希望越大越好；而目標適值是非負的，任何情況下總希望越大越好；而目標函數有正、有負、甚至可能是復數值；且目標函數和適值函數有正、有負、甚至可能是復數值；且目標函數和適值間的關系也多種多樣。如求最大值對應點時，目標函數和間的關系也多種多樣。如求最大值對應點時，目標函數和適值變化方向相同；求最小值對應點時，變化方向恰好相適值變化方向相同；求最小值對應點時，變化方向恰好相反；目標函數值越小的點，適值越大。因此，存在目標函反；目標函數值越小的點，適值越大。因此，存在目標函數值向適值映射的問題。數值向適值映射的問題。 1.2 遺傳算法

26、應用中的一些基本問題 首先應保證映射后的適值是非負的，其次目標函首先應保證映射后的適值是非負的，其次目標函數的優化方向應對應于適值增大的方向。數的優化方向應對應于適值增大的方向。 對最小化問題，一般采用如下適值函數對最小化問題，一般采用如下適值函數f(x)和目標和目標函數函數g(x)的映射關系：的映射關系： (1-6)其中：其中：cmax可以是一個輸入參數，或是理論上的最可以是一個輸入參數，或是理論上的最大值，或是到目前所有代（或最近的大值，或是到目前所有代（或最近的k代）之中見代）之中見到的到的g(x)的最大值，此時的最大值，此時cmax隨著代數會有所變化。隨著代數會有所變化。其它, 0)(

27、),()(maxmaxcxgxgcxf對最大化問題，一般采用下述方法：對最大化問題，一般采用下述方法： (1-7)式中式中: cmin既可以是輸入值也可以是當前最小值或既可以是輸入值也可以是當前最小值或最近的最近的k代中的最小值。代中的最小值。對指數函數問題，一般采用下述方法：對指數函數問題，一般采用下述方法：其中：其中：c一般取一般取1.618或或2（最大化），（最大化），0.618（最小（最小化）。這樣，既保證了化）。這樣，既保證了f(x)0又使又使f(x)的增大方向的增大方向與優化方向一致。與優化方向一致。其它, 0)(,)()(minmincxgcxgxfycxf)()(xgy 1.2

28、.2 適值的調整 為了使遺傳算法有效地工作，必須保持種群內位串的多樣性和位為了使遺傳算法有效地工作，必須保持種群內位串的多樣性和位串之間的競爭機制。現將遺傳算法的運行分為開始、中間和結束三個串之間的競爭機制。現將遺傳算法的運行分為開始、中間和結束三個階段來考慮：在開始階段，若一個規模不太大的種群內有少數非凡的階段來考慮：在開始階段，若一個規模不太大的種群內有少數非凡的個體（適值很高的位串），按通常的選擇方法（選擇復制的概率為個體（適值很高的位串），按通常的選擇方法（選擇復制的概率為fi/fi，期望的復制數為期望的復制數為fi/），），這些個體會被大量地復制，在種群中占這些個體會被大量地復制，在

29、種群中占有大的比重，這樣就會減少種群的多樣性，導致過早收斂，從而可能有大的比重，這樣就會減少種群的多樣性，導致過早收斂，從而可能丟失一些有意義的搜索點或最優點，而進入局部最優；在結束階段，丟失一些有意義的搜索點或最優點，而進入局部最優；在結束階段，即使種群內保持了很大的多樣性，但若所有或大多數個體都有很高的即使種群內保持了很大的多樣性，但若所有或大多數個體都有很高的適值，從而種群平均適值和最大適值相差無幾，則平均適值附近的個適值，從而種群平均適值和最大適值相差無幾，則平均適值附近的個體和具有最高適值的個體，被選中的機會相同，這樣選擇就成了一個體和具有最高適值的個體，被選中的機會相同，這樣選擇就

30、成了一個近乎隨機的步驟，適值的作用就會消失，從而使搜索性能得不到明顯近乎隨機的步驟，適值的作用就會消失，從而使搜索性能得不到明顯改進。因此，有必要對種群內各位串的適值進行有效調整，既不能相改進。因此，有必要對種群內各位串的適值進行有效調整，既不能相差太大，又要拉開檔次，強化位串之間的競爭性。差太大，又要拉開檔次，強化位串之間的競爭性。1.2.3 編碼原則 遺傳算法參數編碼原則有兩種：深層意義上的建筑塊遺傳算法參數編碼原則有兩種：深層意義上的建筑塊原則和最小符號表原則。而后者是一種應用廣泛的實用原原則和最小符號表原則。而后者是一種應用廣泛的實用原則。則。 最小符號表原則要求選擇一個使問題得以自然

31、表達的最小符號表原則要求選擇一個使問題得以自然表達的最小符號編碼表。在前面討論中使用的都是二進制符號編最小符號編碼表。在前面討論中使用的都是二進制符號編碼表碼表0, 1，任何一個長度為，任何一個長度為l的位串都包含在的位串都包含在0,1l中。根中。根據遺傳算法的模式理論，遺傳算法能有效工作的根本原因，據遺傳算法的模式理論，遺傳算法能有效工作的根本原因，在于其能有效的處理種群中的大量模式，尤其是那些定義在于其能有效的處理種群中的大量模式，尤其是那些定義長度短、確定位數少、適值高的模式（即建筑塊）。因此，長度短、確定位數少、適值高的模式（即建筑塊）。因此，編碼應使確定規模的種群中包含盡可能多的模式

32、。編碼應使確定規模的種群中包含盡可能多的模式。 表表6-5給出了一個參數的二進制給出了一個參數的二進制編碼和非二進制編碼的對比情編碼和非二進制編碼的對比情況，即將況，即將0,31上的二進制整數上的二進制整數一一對應地映射到一個有一一對應地映射到一個有32個字個字母的符號表中，這個符號表包母的符號表中，這個符號表包含含26個英文字母（個英文字母（AZ）和和6個個數字（數字（16）。在二進制編碼中，）。在二進制編碼中，通過編碼表中小部分關鍵編碼通過編碼表中小部分關鍵編碼可以找到重要的相似性而在非可以找到重要的相似性而在非二進制編碼中，只能看到單一二進制編碼中，只能看到單一編碼的符號表，看不出編碼中

33、編碼的符號表，看不出編碼中的相似性。的相似性。為了進一步了解二進制編碼的為了進一步了解二進制編碼的數學意義，假設有一個非二進數學意義，假設有一個非二進制的包含制的包含k個字母編碼的符號表個字母編碼的符號表V及二進制編碼的符號表及二進制編碼的符號表V，即即V=a1,a2,akV=0,11.3.1 復制方法的改進1穩態復制法穩態復制法 該方法保證種群中最優秀的個體在進化過程該方法保證種群中最優秀的個體在進化過程中不被刪除，這在很大程度上減少了有效基因的中不被刪除，這在很大程度上減少了有效基因的丟失。在經過交叉、變異產生的新種群中，只有丟失。在經過交叉、變異產生的新種群中，只有一個或兩個優秀個體被選

34、進下一代種群，替代原一個或兩個優秀個體被選進下一代種群，替代原有種群中的最差個體。有種群中的最差個體。 2選擇種子法選擇種子法 該法也稱最優串復制法，它保證了最優的個該法也稱最優串復制法，它保證了最優的個體被選進下一代進化種群。其執行過程如下：體被選進下一代進化種群。其執行過程如下： 隨機初始化種群隨機初始化種群N(0)，種群大小為種群大小為n。 計算種群中所有個體適值。計算種群中所有個體適值。 對以后的種群對以后的種群N(t)進行如下操作，直至滿足條進行如下操作，直至滿足條件或達到進化代數。根據個體適值大小隨機選出件或達到進化代數。根據個體適值大小隨機選出n個個體組成種群個個體組成種群N0(

35、t)，并復制一份為并復制一份為N1(t)，對種對種群群N0(t)實施交叉操作，對種群實施交叉操作，對種群N1(t)實施基因突變，實施基因突變，用以防止有效基因丟失。用以防止有效基因丟失。 計算種群計算種群N0(t)、N1(t)和和N(t)的個體適值，從中的個體適值，從中選出最好的選出最好的n個個體構成下一代種群個個體構成下一代種群N (t1)，轉轉至。至。 3確定性復制法確定性復制法 在確定性復制法中，復制的概率按常規計算為：在確定性復制法中，復制的概率按常規計算為：Pifi/fi。對個體對個體Ai，其期望的后代數目其期望的后代數目ei，計算為：計算為：einPi。每一位串個體按每一位串個體按

36、ei的整數部分分配后代數，種群的其余部的整數部分分配后代數，種群的其余部分按順序表由高到低來填充。分按順序表由高到低來填充。 4置換式余數隨機復制法置換式余數隨機復制法 這方法開始與上述確定性復制法一樣，期望的個體數這方法開始與上述確定性復制法一樣，期望的個體數如前分配為如前分配為ei的整數部分；但的整數部分；但ei的余數部分用來計算轉輪法的余數部分用來計算轉輪法中的權值，以補充種群總數。中的權值，以補充種群總數。5非置換式余數隨機復制法非置換式余數隨機復制法 這方法開始也與上述確定性復制法一樣，而這方法開始也與上述確定性復制法一樣，而ei的余數的余數部分按概率來處理。換句話說，個體至少復制一

37、個與部分按概率來處理。換句話說，個體至少復制一個與ei整整數部分相等的后代，然后以數部分相等的后代，然后以ei的余數部分為概率來復制其的余數部分為概率來復制其余的后代，直至種群的總數達到余的后代，直至種群的總數達到n。例如一個具有期望復例如一個具有期望復制值為制值為1.5的個體，它可以復制產生一個后代，并以的個體，它可以復制產生一個后代，并以0.5概概率產生另一個后代。試驗表明，這種方法優于其它復制方率產生另一個后代。試驗表明，這種方法優于其它復制方法。法。1.3.2 高級GA算法 為改善為改善GA的遺傳性，在復制、交叉和變異運算的基礎的遺傳性，在復制、交叉和變異運算的基礎上，再考慮兩種類型的

38、基因運算，即為微運算和宏運算。上，再考慮兩種類型的基因運算，即為微運算和宏運算。多點交叉微運算是在個體級別上的運算，重組宏運算是在多點交叉微運算是在個體級別上的運算，重組宏運算是在種群級別上的運算。種群級別上的運算。 1.4 基于遺傳算法的系統在線辨識 1.4.1 遺傳算法在參數辨識中的應用 1.4.2 遺傳算法參數辨識仿真示例 1.4.1 遺傳算法在參數辨識中的應用1離散系統參數估計離散系統參數估計 設線性離散系統的數學模型為：設線性離散系統的數學模型為： (1-18)式中：式中：d為滯后時間，為滯后時間，(k)為零均值的噪聲序列（方差為為零均值的噪聲序列（方差為2），），z-1為后移算子。

39、為后移算子。 )()()()()()(111kzCdkuzBkyzAiniizazAa111)(iniizbzBb01)(iniizczCc111)( 假定假定A(z-1)、B(z-1)和和C(z-1)未知，則待辨識參數未知，則待辨識參數向量包含向量包含na+ nb+ nc+1個參數，即個參數，即 (1-19)真參數為：真參數為： (1-20) 要應用遺傳算法對參數向量要應用遺傳算法對參數向量進行在線優化的進行在線優化的參數辨識，必須解決兩個問題，一個是確定多參參數辨識，必須解決兩個問題，一個是確定多參數編碼映射方法，另一個是如何根據目標函數確數編碼映射方法，另一個是如何根據目標函數確定適值。

40、定適值。 Tnnncbacccbbbaaa,211021Tnnncbacccbbbaaa,2110212. 參數級聯定點映射編碼參數級聯定點映射編碼 采用多參數級聯定點映射編碼原則進行編碼，可采用多參數級聯定點映射編碼原則進行編碼，可根據辨識精度確定每個參數的二進制編碼長度。根據辨識精度確定每個參數的二進制編碼長度。假如每個參數線性映射在假如每個參數線性映射在-2l-1,+2l-1范圍內，且要范圍內，且要求辨識精度求辨識精度2-m，則每個參數需要則每個參數需要m+l位；若已知位；若已知時滯時滯d2n，則時滯可用則時滯可用n位編碼，則各參數編碼組位編碼，則各參數編碼組成一個整體位串的長為成一個整

41、體位串的長為(na+ nb+ nc)(l+m)+n，這這個整體位串就是系統待辨識參數的一個解。個整體位串就是系統待辨識參數的一個解。 設整體位串構成的種群數為設整體位串構成的種群數為N，第第p代的第代的第j個個（1jN）位串所對應的參數為：位串所對應的參數為： (1-21) 根據辨識結果，有預測輸出和預測輸出誤差，它根據辨識結果，有預測輸出和預測輸出誤差，它們分別滿足：們分別滿足： (1-22) (1-23)Tpjnpjipjnpjpjnpjpjdccbbaacba,=,0, 1111()( )() ()() ( )ppppjjjjAzykBzu kdCzk( )( )( )ppjjekyky

42、 k3. 目標函數到適值形式的映射目標函數到適值形式的映射 為保證映射后的適值是非負的，選擇目標函數的優化方向為保證映射后的適值是非負的，選擇目標函數的優化方向應對應于適值的增大方向。由式應對應于適值的增大方向。由式(1-6)的映射關系，可選擇的映射關系，可選擇適值函數為：適值函數為： (1-24) 求和求和m+1步的意義在于能進一步考察辨識參數與真參步的意義在于能進一步考察辨識參數與真參數的擬合情況。在遺傳算法操作過程中，可能存在這樣的數的擬合情況。在遺傳算法操作過程中，可能存在這樣的參數，它離真值很遠，但經線性組合后某步預測輸出與實參數，它離真值很遠，但經線性組合后某步預測輸出與實際輸出相

43、差不大，求和可以避免這樣的參數集取得高適值際輸出相差不大，求和可以避免這樣的參數集取得高適值以致出現錯誤的收斂。以致出現錯誤的收斂。m的值越大，適值函數的可信度就的值越大，適值函數的可信度就越高，越高，m的上限可取為的上限可取為k值，值，cmax值是一足夠大的正數，它值是一足夠大的正數，它與問題的解有關。與問題的解有關。 其它, 0)(,)()(max0202maxcikeikecfmipjmipjpj 在計算出種群中每個個體的適值后，需要對它們規范在計算出種群中每個個體的適值后，需要對它們規范化，先求出其平均適值為：化，先求出其平均適值為： (1-25)規范化適值為：規范化適值為： (1-2

44、6) 用種群規范化適值與平均適值的偏差的平方和來定義用種群規范化適值與平均適值的偏差的平方和來定義收斂域，即收斂域，即 (1-27)其中：其中：是一個定義的收斂域，例如若設是一個定義的收斂域，例如若設0.0001，則可則可認為種群已經收斂，這時種群中適值最大的個體就是當前認為種群已經收斂，這時種群中適值最大的個體就是當前收斂條件下的最優者。收斂條件下的最優者。 NjpjpNf1/ )()(averfit)(averfit/ )()(norfitppjpjfNjppj12)(averfit)(norfit1.4.2 遺傳算法參數辨識仿真示例設線性離散系統的數學模型如式（設線性離散系統的數學模型如

45、式（113）所示，其中）所示，其中 d=2采用偽隨機二進制序列（采用偽隨機二進制序列（PRBS）輸入，辨識系統參數為輸入，辨識系統參數為 及時滯。設參數的范圍是及時滯。設參數的范圍是-2,+2，要求辨，要求辨識精度識精度0.02，則每個參數需要用，則每個參數需要用8位的位串表示，若時滯位的位串表示，若時滯d不大于不大于4，則時滯可用，則時滯可用2位的位串表示，所以參數集位串長位的位串表示，所以參數集位串長度為度為48+2=34位。位。 21174. 072. 11)(zzzA118 . 09 . 0)(zzBTbbaa,1021取種群規模取種群規模N=50，交叉概率交叉概率Pc=0.90；變異概率變異概率Pm=0.001。 適值函數中的適值函數中的cmax值分段選取。在操作初期，主要值分段選取。在操作