遺傳算法詳解

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

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

3、和親代相似。遺傳性是一切生物所共有的特性，它使得生物能夠把其特性、性狀傳給后代。共有的特性，它使得生物能夠把其特性、性狀傳給后代。遺傳是生物進(jìn)化的基礎(chǔ)。遺傳是生物進(jìn)化的基礎(chǔ)。 變異是指子代和親代有某些不相似的現(xiàn)象，即子代永變異是指子代和親代有某些不相似的現(xiàn)象，即子代永遠(yuǎn)不會(huì)和親代完全一樣。它是一切生物所具有的共有特性，遠(yuǎn)不會(huì)和親代完全一樣。它是一切生物所具有的共有特性，是生物個(gè)體之間相互區(qū)別的基礎(chǔ)。引起變異的原因主要是是生物個(gè)體之間相互區(qū)別的基礎(chǔ)。引起變異的原因主要是生活環(huán)境的影響及雜交等。生物的變異性為生物的進(jìn)化和生活環(huán)境的影響及雜交等。生物的變異性為生物的進(jìn)化和發(fā)展創(chuàng)造了條件。發(fā)展創(chuàng)造了條

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

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

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

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

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

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

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

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

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

13、其適值在總和中所占的比例占據(jù)輪子周，而每個(gè)個(gè)體位串按其適值在總和中所占的比例占據(jù)輪子的一個(gè)扇區(qū)。按表的一個(gè)扇區(qū)。按表6-1可繪制如圖的轉(zhuǎn)輪?？衫L制如圖的轉(zhuǎn)輪。復(fù)制時(shí)，只要簡(jiǎn)單地轉(zhuǎn)動(dòng)這個(gè)按權(quán)重復(fù)制時(shí)，只要簡(jiǎn)單地轉(zhuǎn)動(dòng)這個(gè)按權(quán)重劃分的轉(zhuǎn)輪劃分的轉(zhuǎn)輪4次，從而產(chǎn)生次，從而產(chǎn)生4個(gè)下一代個(gè)下一代的種群。例如對(duì)于表的種群。例如對(duì)于表6-1中的位串中的位串1，其適值為其適值為169，為總適值的，為總適值的14.4%。因此，每旋轉(zhuǎn)一次轉(zhuǎn)輪指向該位串因此，每旋轉(zhuǎn)一次轉(zhuǎn)輪指向該位串的概率為的概率為0.144。每當(dāng)需要下一個(gè)后。每當(dāng)需要下一個(gè)后代時(shí)，就旋轉(zhuǎn)一下這個(gè)按權(quán)重劃分代時(shí)，就旋轉(zhuǎn)一下這個(gè)按權(quán)重劃分的轉(zhuǎn)輪，產(chǎn)生

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

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

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

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

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

19、稱單點(diǎn)交叉。即指?jìng)€(gè)上述例子中交叉的位置是一個(gè)，稱單點(diǎn)交叉。即指?jìng)€(gè)體切斷點(diǎn)有一處，由于進(jìn)行個(gè)體間的組合替換生成兩個(gè)新體切斷點(diǎn)有一處，由于進(jìn)行個(gè)體間的組合替換生成兩個(gè)新個(gè)體，位串個(gè)體長度為個(gè)體，位串個(gè)體長度為l時(shí)，單點(diǎn)交叉可能有時(shí)，單點(diǎn)交叉可能有l(wèi)1個(gè)不同的個(gè)不同的交叉。交叉。 多點(diǎn)交叉是允許個(gè)體的切斷點(diǎn)有多個(gè)，每個(gè)切斷點(diǎn)在多點(diǎn)交叉是允許個(gè)體的切斷點(diǎn)有多個(gè)，每個(gè)切斷點(diǎn)在兩個(gè)個(gè)體間進(jìn)行個(gè)體的交叉，生成兩個(gè)新個(gè)體。兩個(gè)個(gè)體間進(jìn)行個(gè)體的交叉，生成兩個(gè)新個(gè)體。 3. 變異變異 盡管復(fù)制和交叉操作很重要，在遺傳算法中是第一位的，但不能保證盡管復(fù)制和交叉操作很重要，在遺傳算法中是第一位的，但不能保證不會(huì)遺漏一

20、些重要的遺傳信息。在人工遺傳系統(tǒng)中，變異用來防止這不會(huì)遺漏一些重要的遺傳信息。在人工遺傳系統(tǒng)中，變異用來防止這種遺漏。在簡(jiǎn)單遺傳算法中，變異就是在某個(gè)字符串當(dāng)中把某一位的種遺漏。在簡(jiǎn)單遺傳算法中，變異就是在某個(gè)字符串當(dāng)中把某一位的值偶然的（概率很小的）隨機(jī)的改變，即在某些特定位置上簡(jiǎn)單地把值偶然的（概率很小的）隨機(jī)的改變，即在某些特定位置上簡(jiǎn)單地把1變?yōu)樽優(yōu)?，或反之。當(dāng)它有節(jié)制地和交叉一起使用時(shí)，它就是一種防止，或反之。當(dāng)它有節(jié)制地和交叉一起使用時(shí)，它就是一種防止過度成熟而丟失重要過度成熟而丟失重要概念的保險(xiǎn)策略。例如，隨概念的保險(xiǎn)策略。例如，隨機(jī)產(chǎn)生一個(gè)種群，如表所示。在機(jī)產(chǎn)生一個(gè)種群，如

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

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

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

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

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

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

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

28、.2 適值的調(diào)整 為了使遺傳算法有效地工作，必須保持種群內(nèi)位串的多樣性和位為了使遺傳算法有效地工作，必須保持種群內(nèi)位串的多樣性和位串之間的競(jìng)爭(zhēng)機(jī)制?，F(xiàn)將遺傳算法的運(yùn)行分為開始、中間和結(jié)束三個(gè)串之間的競(jìng)爭(zhēng)機(jī)制?，F(xiàn)將遺傳算法的運(yùn)行分為開始、中間和結(jié)束三個(gè)階段來考慮：在開始階段，若一個(gè)規(guī)模不太大的種群內(nèi)有少數(shù)非凡的階段來考慮：在開始階段，若一個(gè)規(guī)模不太大的種群內(nèi)有少數(shù)非凡的個(gè)體（適值很高的位串），按通常的選擇方法（選擇復(fù)制的概率為個(gè)體（適值很高的位串），按通常的選擇方法（選擇復(fù)制的概率為fi/fi，期望的復(fù)制數(shù)為期望的復(fù)制數(shù)為fi/），），這些個(gè)體會(huì)被大量地復(fù)制，在種群中占這些個(gè)體會(huì)被大量地復(fù)制，在

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

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

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

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

33、編碼的符號(hào)表，看不出編碼中的相似性。的相似性。為了進(jìn)一步了解二進(jìn)制編碼的為了進(jìn)一步了解二進(jìn)制編碼的數(shù)學(xué)意義，假設(shè)有一個(gè)非二進(jìn)數(shù)學(xué)意義，假設(shè)有一個(gè)非二進(jìn)制的包含制的包含k個(gè)字母編碼的符號(hào)表個(gè)字母編碼的符號(hào)表V及二進(jìn)制編碼的符號(hào)表及二進(jìn)制編碼的符號(hào)表V，即即V=a1,a2,akV=0,11.3.1 復(fù)制方法的改進(jìn)1穩(wěn)態(tài)復(fù)制法穩(wěn)態(tài)復(fù)制法 該方法保證種群中最優(yōu)秀的個(gè)體在進(jìn)化過程該方法保證種群中最優(yōu)秀的個(gè)體在進(jìn)化過程中不被刪除，這在很大程度上減少了有效基因的中不被刪除，這在很大程度上減少了有效基因的丟失。在經(jīng)過交叉、變異產(chǎn)生的新種群中，只有丟失。在經(jīng)過交叉、變異產(chǎn)生的新種群中，只有一個(gè)或兩個(gè)優(yōu)秀個(gè)體被選

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

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

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

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

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

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

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

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

42、 k3. 目標(biāo)函數(shù)到適值形式的映射目標(biāo)函數(shù)到適值形式的映射 為保證映射后的適值是非負(fù)的，選擇目標(biāo)函數(shù)的優(yōu)化方向?yàn)楸ＷC映射后的適值是非負(fù)的，選擇目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對(duì)應(yīng)于適值的增大方向。由式應(yīng)對(duì)應(yīng)于適值的增大方向。由式(1-6)的映射關(guān)系，可選擇的映射關(guān)系，可選擇適值函數(shù)為：適值函數(shù)為： (1-24) 求和求和m+1步的意義在于能進(jìn)一步考察辨識(shí)參數(shù)與真參步的意義在于能進(jìn)一步考察辨識(shí)參數(shù)與真參數(shù)的擬合情況。在遺傳算法操作過程中，可能存在這樣的數(shù)的擬合情況。在遺傳算法操作過程中，可能存在這樣的參數(shù)，它離真值很遠(yuǎn)，但經(jīng)線性組合后某步預(yù)測(cè)輸出與實(shí)參數(shù)，它離真值很遠(yuǎn)，但經(jīng)線性組合后某步預(yù)測(cè)輸出與實(shí)際輸出相

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

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

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