第六章 遺傳算法工具箱應(yīng)用(共12頁)

1、PAGE PAGE 104第六章 遺傳算法工具箱應(yīng)用(yngyng)本章介紹英國設(shè)菲爾德大學(xué)(dxu)開發(fā)的遺傳算法工具箱的使用方法。這個遺傳算法工具箱已經(jīng)在世界(shji)近30個廣泛的應(yīng)用領(lǐng)域得到了很好的測試，包括：參數(shù)優(yōu)化、多目標(biāo)優(yōu)化、控制器結(jié)構(gòu)選擇、非線性系統(tǒng)論證、形形色色模式的模型制作、神經(jīng)網(wǎng)絡(luò)設(shè)計、實時和自適應(yīng)控制、 并行遺傳算法、故障診斷和天線設(shè)計等。6.1 安裝遺傳算法工具箱的安裝過程可以參照MATLAB的安裝說明進(jìn)行。建議將工具箱中的文件保存在MATLAB或工具箱主目錄下的名為genetic子目錄中。工具箱包含許多可用的示例。例如，示例M文件sga .m是解決數(shù)值優(yōu)化問題的單

2、種群二進(jìn)制編碼的遺傳算法。示例M文件mpga .m是解決動態(tài)控制問題的多種群十進(jìn)制實數(shù)編碼的遺傳算法。這兩個示例M文件在第七章進(jìn)行了詳細(xì)的討論。另外，來自遺傳算法著作的一套測試函數(shù)在一個從遺傳算法工具箱函數(shù)中分離出來的目錄test fns中提供，這些測試函數(shù)的摘要性描述在最后給出。此外，還有，一個文檔描述了這些函數(shù)的實現(xiàn)和使用。 6.2 種群的表示和初始化遺傳算法同時運算在由已編碼的參數(shù)集組成的稱為種群的大量可能答案上。典型的一個種群由30100個個體組成，一些變化的稱為微型的遺傳算法采用很小的10個個體的種群，使用有限制的復(fù)制和代替策略以試圖達(dá)到實時運算。一般情況下，在遺傳算法中大多數(shù)采用單

3、層的二進(jìn)制串染色體表示方法。這里，參數(shù)集中的每一個決策變量被編碼為一個二進(jìn)制串，它串接起來形成一個染色體。這里采用格雷碼，可用來克服傳統(tǒng)二進(jìn)制表示方法的不足。Caruana和Schaffer 的經(jīng)驗證明顯示，表示圖中鄰近值間過大的海明（Hamming）距離使用標(biāo)準(zhǔn)的二進(jìn)制表示情況下，搜索過程易導(dǎo)致欺騙性結(jié)果或不能有效定位于全局最小值。Schmitendorgf 等更進(jìn)一步的方法是在二進(jìn)制編碼的染色體變換到實際的表示值時使用對數(shù)計量。盡管參數(shù)值的精度可能低于希望的范圍，但在問題中，可行參數(shù)的傳播是未知的，一個大的搜索空間中可能掩藏著大量相同的位，與線性映象方案允許的搜索未知搜索空間的計算負(fù)擔(dān)相比

4、，可減少到更易管理的水平。與此同時，二進(jìn)制編碼的遺傳算法更廣泛使用，同時引起更多興趣的可選擇的編碼方案，有整數(shù)和實數(shù)表示。對一些問題域，有一個爭論是二進(jìn)制表示事實上是靠不住的，它掩蓋了搜索的自然性。例如在選擇子集問題中，使用整數(shù)表示法和搜索表提供方便和自然表示方法映射為對問題域的表示。Wright 聲稱(shngchng)使用實值基因的遺傳算法在數(shù)值函數(shù)優(yōu)化上與二進(jìn)制編碼相比有許多的優(yōu)點。在函數(shù)計算前，不需要從染色體到表現(xiàn)值的轉(zhuǎn)換，提高了遺傳算法的效率；計算機內(nèi)部高效的浮點表示可直接使用，以減少內(nèi)存需求；相對于離散的二進(jìn)制或其它值，沒有精度損失；對使用(shyng)不同的遺傳算子非常自由。Mi

5、chalewicz 在其著作(zhzu)進(jìn)化策略(Evolution Strategies)中描述了使用實值編碼的細(xì)節(jié)。有了確定的表示，簡單遺傳算法的第一步是建立初始種群，使用在希望的范圍內(nèi)均勻分布數(shù)字的隨機數(shù)產(chǎn)生器生成所需數(shù)量的個體。例如，使用有Nind個個體的二進(jìn)制種群，染色體長度為Lind 位，從集0，1中產(chǎn)生Nind Lind 個均勻分布隨機數(shù)。一個變化是Bramlette的擴展隨機的初始步驟，無論如何，大量的隨機初始化(initializations)為每個個體嘗試，它們中性能最好的被選擇為初始種群，另外一些遺傳算法用戶使用初始種群的一些已知為接近全局最小化的個體播種。當(dāng)然，這種接近

6、法僅僅適用于自然問題，是易于事前了解的或遺傳算法用于與基本知識系統(tǒng)相聯(lián)合的。這個遺傳算法工具箱支持二進(jìn)制、整數(shù)和浮點的染色體表示。二進(jìn)制和整數(shù)種群初始化可使用工具箱函數(shù)crtbp創(chuàng)建二進(jìn)制種群。附加函數(shù)crtbase提供向量描述的整數(shù)表示法。實值種群的初始化可使用函數(shù)crtrp完成，程序bs2rv提供二進(jìn)制串和實值之間的轉(zhuǎn)換，它支持使用格雷碼和對數(shù)編碼。6.3 目標(biāo)函數(shù)和適應(yīng)度函數(shù)目標(biāo)函數(shù)將提供一測量手段，測量個體在問題域的完成情況，在一個最小化問題中，最適合的個體對應(yīng)最小的目標(biāo)函數(shù)值。未經(jīng)加工的適應(yīng)度值通常只用在遺傳算法的中期來判斷一個個體的相對性能。另一函數(shù)適應(yīng)度函數(shù)通常用于轉(zhuǎn)換目標(biāo)函數(shù)值

7、為相對適應(yīng)度值。因此，有F(x) = g f (x) 這里f是目標(biāo)函數(shù)，g是將目標(biāo)函數(shù)值轉(zhuǎn)換為非負(fù)值的變換因子，F(xiàn)是所得的相對適應(yīng)度，當(dāng)目標(biāo)函數(shù)是最小化即函數(shù)值越小對應(yīng)適應(yīng)度越好的個體時，這種變換是必須的。許多情況下，適應(yīng)度函數(shù)值對應(yīng)大量子代預(yù)計在下一代中能存在的個體。通常使用這個轉(zhuǎn)換進(jìn)行適應(yīng)度概率分配。個體的適應(yīng)度每一個個體的F(xi)通過個體的未加工的適應(yīng)度f(xi)相對整個種群的適應(yīng)度被計算出來，即 (6.1)式中，NIND是種群大小，xi 是個體i的表現(xiàn)值，與此同時適應(yīng)度分配確保每一個體均有按其相對適應(yīng)度再生的機會，它不能處理負(fù)的目標(biāo)函數(shù)值。 使用水平移位的線性變換是優(yōu)先使用的適應(yīng)度分

8、配方法。 (6.2)如果優(yōu)化方法是最大化，這里是一個正的換算系數(shù)，如果是最小化，則是一個負(fù)的。是一個偏移值，它確保最后的適應(yīng)度值是非負(fù)的。無論如何(w ln r h)，上面給出的線性尺度變換和移位方法易迅速收斂。這個選擇算法選擇個體進(jìn)行再生是基于它們的相對適應(yīng)度。使用線性尺度變換，預(yù)期(yq)的后代將近似與它們性能相稱(成比率)，如果說沒有限制個體在給出代中的性能，則在上代中高適應(yīng)度的個體將決定再生過程引起快速收斂，可能產(chǎn)生局部最優(yōu)解。同樣，如果種群有很少變異，這種變換僅僅向最合適的個體提供小偏移。Baker認(rèn)為通過限制再生范圍，以使個體不產(chǎn)生極端的后代，防止過早收斂。這里個體是根據(jù)它們在種群

9、中的排序計算(j sun)適應(yīng)度。一個變量MAX常常用來決定偏移或選擇強度，最適合的個體和其它個體的適應(yīng)度由下面的規(guī)則決定：MIN = 2.0 - MAXINC = 2.0 (MAX -1.0) / N indLOW = INC / 2.0這里MIN是下界，INC是鄰近個體適應(yīng)度的差別，LOW是最小適應(yīng)度個體預(yù)期的試驗值(一定選擇代數(shù))，MAX是在區(qū)間1.1，2.0中典型精選值。因此如果種群大小N ind為40，MAX=1.1，我們將獲得MIN=0.9，INC = 0.05，LOW = 0.025。種群中個體的適應(yīng)度能被直接計算出： (6.3)式中，是個體在有序種群中的位置。盡管工具箱提供大量

10、的M-文件例子用于完成通用的測試功能，但目標(biāo)函數(shù)必須由用戶創(chuàng)建。這些目標(biāo)函數(shù)都有文件名前綴obj，這個工具箱支持線性和非線性兩種評定法，包括一個簡單的線性尺度變換函數(shù)scaling，較為完備。需要注意的是，線性尺度變換函數(shù)不適合于目標(biāo)函數(shù)產(chǎn)生負(fù)的適應(yīng)度值的情況。6.4 選擇選擇是由遺傳代數(shù)或試驗值決定的過程。一個特殊的個體為再生被挑選，確定編碼子代中的一個個體被產(chǎn)生，這種個體的選擇可以看作兩個分離的過程：(1) 決定試驗的代數(shù)和希望接收的個體。(2) 轉(zhuǎn)換預(yù)期的試驗數(shù)為大量離散的子代。第一部分所關(guān)心的是轉(zhuǎn)換原始的適應(yīng)度值為個體再生機率的預(yù)期的實值和處理使用前一小部分的適應(yīng)度計算。第二部分是基于

11、一個個體相對另一個體的適應(yīng)度為再生進(jìn)行的個體概率選擇，有時是由抽樣而已知的。這一小部分的剩余部分將回顧現(xiàn)行使用的更為流行的選擇方法。Baker為選擇算法展現(xiàn)了性能的三種措施偏差（Bias）、個體擴展（Spread）、效率(Efficiency)。Bias被定義為個體的實際值與預(yù)期的選擇概率之間的絕對差值。因此當(dāng)個體的選擇概率等于它的預(yù)期試驗值時，獲得最優(yōu)零偏差。Spread是個體可能達(dá)到的一個可能實驗子代數(shù)的范圍，如果f (i)是個體i收到的實際實驗代數(shù)，則最小個體擴展就是最小的Spread，即理論上允許零偏差。這里(zhl)et(i)是個體(gt)i的預(yù)期實驗(shyn)代數(shù)，表示下限，表示

12、上限。因此，當(dāng)Bias是一個精確的指示時，可選擇方法的個體擴展來測量它的一致性(Consistency)。獲得有效選擇方法的要求是由必須保持遺傳算法全面的時間復(fù)雜度決定的。在一些著作中顯示出遺傳算法的另一些方面(除實際的目標(biāo)函數(shù)評估)是o(L ind*N ind)或更好的時間復(fù)雜度，這里L(fēng)ind是個體長度，Nind是種群的大小。由這個選擇算法而得到零偏差，與此同時保持了最小個體擴展，但對于改進(jìn)這個遺傳算法的時間復(fù)雜度不會有任何作用。下面介紹二種選擇方法。1輪盤賭選擇算法許多選擇技術(shù)采用輪盤賭原理，個體的選擇概率是基于它們的性能進(jìn)行的一些計算。實值范圍總和是所有個體期望的選擇概率的總和或當(dāng)前種群

13、中所有個體原始適應(yīng)度值的總和。個體采用一對一方式映象到范圍0，SUM的一連續(xù)區(qū)間，每一個體區(qū)間的大小與對應(yīng)個體的適應(yīng)度值相匹配。如圖6.1所示，輪盤賭輪的周長是6個個體適應(yīng)度值的總和，個體5是最大適應(yīng)度個體，它占有最大的區(qū)間，而個體6和4是最小適應(yīng)度個體，相對應(yīng)地在輪盤上占有小的區(qū)間。選擇一個個體，用在0，Sum間產(chǎn)生隨機數(shù)，看此隨機數(shù)處在哪個個體的區(qū)間上，則此個體被選中。重復(fù)此過程，直到所需數(shù)量個體被選中為止。圖6.1 輪盤賭輪選擇這個基本的輪盤賭選擇方法是可代替的隨機抽樣(SSR)。在這里片段大小和選擇概率在整個選擇階段保持相同，個體的選擇根據(jù)上面的步驟完成。SSR給出了零偏差但可能是無限

14、的個體擴展，段長大于零的任意個體完全可能填入下一種群。局部替換的隨機抽樣(SSPR)是在SSR上擴充而來的，如果一個個體被選擇，重新建立它的段大小。個體被選擇一次，其段長被減小1，如果段長變?yōu)樨?fù)，則設(shè)為零。這里提供一個體擴展上界，無論如何低界為零，偏差(Bias)都是大于SSR的。剩余抽樣法解決了兩個不同的方面。1）在整數(shù)方面，個體的選擇決定于期望試驗的整數(shù)部分，剩余個體的選擇概率來自于個體期望值的小數(shù)部分。替換的剩余隨機抽樣(RSSR)采用輪盤賭選擇，對抽樣的個體并不重新賦值。2）在輪盤賭選擇期間，個體的小數(shù)部分保持不變，隨后在“Spins”間競爭選擇。RSSR提供零偏差和具有下界的個體擴展

15、，上界被指定代的參與分配樣本部分和一個個體的整數(shù)部分大小限定。例如，任何一個小數(shù)部分大于零的個體將在分級(小數(shù))階段的所有抽樣中取勝。如果一個體在小數(shù)階段被抽樣，沒有替換的剩余隨機抽樣(RSSWR)設(shè)置它的期望值的小數(shù)部分為零。雖然這個選擇方法偏向于有小的小數(shù)，這里給出的RSSWR具有最小的個體擴展。2隨機(su j)遍歷抽樣隨機遍歷抽樣(SUS)是具有零偏差和最小個體擴展的單狀態(tài)(single_phase)抽樣算法。替代用于輪盤賭方法的單個選擇指針，SUS使用N個相等距離的指針，這里N是要求選擇的個數(shù)。種群被隨機排列，在0，Sum/N范圍內(nèi)產(chǎn)生一隨機數(shù)作為(zuwi)指針ptr，N個個體由相

16、隔一個距離的N個指針ptr，ptr+1，ptr+2，ptr+N-1選擇，選取(xunq)適應(yīng)度范圍在指針位置的個體。一個個體確保被選擇的最少次數(shù)et(i)和不超過et(i)，因此獲得最小的個體擴展，另外個體完全按它們在種群中的地位選擇，SUS具有零偏差。輪盤賭選擇算法總可按O(N log N)執(zhí)行，而SUS是更簡單的算法且具有O(N)的時間復(fù)雜度。這個工具箱提供隨機遍歷抽樣函數(shù)sus和具有替換的隨機抽樣算法rws。6.5 交叉在遺傳算法中產(chǎn)生新染色體的基本操作是染色體的交叉(也稱為基因重組)。與自然進(jìn)化一樣，交叉產(chǎn)生的新個體具有父母雙方的一部分遺傳物質(zhì)。最簡單的交叉是單點交叉。下面討論幾種交叉

17、方法，并比較它們各自的優(yōu)點。1多點交叉對多點交叉有m個交叉位（特別當(dāng)m=1時為單點交叉），ki 1，2，l-1，這里ki是交叉點，l是染色體的長度，這m個交叉位是通過隨機數(shù)選擇的沒有重復(fù)的按升序排列的。父母染色體中在兩個相連的交叉位間的基因進(jìn)行交換產(chǎn)生兩個新的子代。個體第一個基因到第一個交叉點之間的位并不進(jìn)行交換。這個過程如圖6.2 所示。圖6.2 多點交叉（m=5）多點交叉的思想和事實交叉上的許多變異源于控制個體特定行為的染色體表示信息的部分，無須包含于鄰近的子串中。進(jìn)一步，多點交叉的破壞性可以促進(jìn)解空間的搜索而不至于在搜索中因高適應(yīng)度個體過早收斂，使搜索更加健壯。2均勻交叉單點交叉和多點交

18、叉定義的交叉點即染色體拆分基因位。均勻交叉更加廣義化，將每個點都作為潛在的交叉點。一個交叉掩碼，隨機產(chǎn)生的與個體等長的染色體結(jié)構(gòu)，掩碼中的等價位表明哪個父個體向子個體提供變量值。考慮如下兩個父個體，交叉掩碼和最終的子個體：P 1 = 1 0 1 1 0 0 0 1 1 1P 2 = 0 0 0 1 1 1 1 0 0 0Mask = 0 0 1 1 0 0 1 1 0 0O 1 = 0 0 1 1 1 1 0 1 0 0O 2 = 1 0 0 1 0 0 1 0 1 1這里(zhl)，第一個子個體O1產(chǎn)生(chnshng)的位，其掩碼對應(yīng)(duyng)位為1，則來自父個體P1；對應(yīng)位為0，則來

19、自父個體P2。而第二個個體的產(chǎn)生則相反，即將上面的P1和P2交換。均勻交叉類似于多點交叉，可以減少二進(jìn)制編碼長度與給定參數(shù)特殊編碼之間的偏差，并有助于克服單點交叉中對短子串的偏差而不用精確了解染色體表示信息的個體位的重要性(意義)。Spears和De Jong已經(jīng)證明均勻交叉通過應(yīng)用概率交換位怎樣參數(shù)化。額外的參數(shù)常用來控制重組期間的破壞總量，不用引進(jìn)表現(xiàn)信息長度用的偏差。當(dāng)均勻交叉用于實值形時，它常作為離散重組參考。3中間重組給定一實值編碼的染色體結(jié)構(gòu)，中間重組是產(chǎn)生新表現(xiàn)型范圍的方法，這個范圍處于父表現(xiàn)型值之間。子個體按照下列公式產(chǎn)生： (6.4)這里，是一區(qū)間的均勻隨機數(shù)，是換算系數(shù)，典

20、型區(qū)間為-0.25，1.25；P1和P2是父染色體，子代的每一個變量的值由父變量的值和對每一對父基因產(chǎn)生的一新的值按上面的公式產(chǎn)生。用幾何圖形描述，中間重組能產(chǎn)生新的變量在比其父代定義的稍大的立體中，并受限制，顯示如圖6.3所示。圖6.3 中間重組的幾何效果4線性重組線性重組與中間重組比較相似，只是在重組中使用一個值。圖6.4顯示了線性重組怎樣由父個體在擾動范圍的線上任意點產(chǎn)生，用于兩個參數(shù)的重組。圖6.4 線性重組的幾何效果 5其它一些交叉算子一相關(guān)的交叉算法(sun f)是洗牌交叉。一個交叉點被選擇，但此位前的哪些位交換，這些位在父母之間進(jìn)行隨機洗牌。重組后，子代中的這些位不進(jìn)行洗牌，當(dāng)這

21、些位在每次交叉執(zhí)行時被隨機分配，將減少位置偏差。在任何可能的地方(dfng)，縮小代理算子、強制交叉(jioch)總是產(chǎn)生新的個體群。通常它作為限制交叉點位置的工具，以便使交叉點只發(fā)生在那些基因值不同的地方。6.6 變異在自然進(jìn)化中，變異是一隨機過程，是基因上的一個等位基因被另一個代替而產(chǎn)生一新的遺傳結(jié)構(gòu)。在遺傳算法中，變異采用了一任意的小概率，典型值是在0.0010.1之間，并改變?nèi)旧w的元素。通常認(rèn)為它是后臺算子，變異的作用被認(rèn)為是：搜索任意給定串的可能性永不為零，為保證通過選擇和交叉操作恢復(fù)可能丟失的好的遺傳物質(zhì)提供安全網(wǎng)絡(luò)。圖6.5說明了在一個二進(jìn)制串上的變異效果。二進(jìn)制串是用10位二

22、進(jìn)制染色體表示的一個在區(qū)間0，10之間的實值編碼，使用標(biāo)準(zhǔn)二進(jìn)制和格雷碼兩種編碼，二進(jìn)制串中的變異位是第3位。這里，二進(jìn)制變異是對選擇變異位的值進(jìn)行翻轉(zhuǎn)。給定的變異通常一致應(yīng)用于整個種群串，一個給定的二進(jìn)制串變異的可能不止一位。變異位 二進(jìn)制 格雷碼原始串 0 0 0 1 1 0 0 0 1 0 0.9659 0.6634變異后的串 0 0 1 1 1 0 0 0 1 0 2.2146 1.8439圖6.5 二進(jìn)制變異對于非二進(jìn)制表示，變異完成的是擾亂基因值和隨機選擇一允許范圍內(nèi)的新值。Wright、Janikow和Michalewicz已經(jīng)證明，實值編碼在高變異率中比二進(jìn)制編碼好，它提高了對

23、搜索空間的搜索能力，而不會對收斂特征產(chǎn)生不利影響。的確，Tate和Smith論證了為什么比二進(jìn)制復(fù)雜的編碼，高變異率是適合的和必須的，示范了為什么復(fù)雜組合最優(yōu)化問題、高變異率和非二進(jìn)制編碼領(lǐng)域解法大大好于通用方法。還有許多變異的變異算子，例如，具有低適應(yīng)度的、帶偏差的變異能提高搜索能力、而不會丟失來自高適應(yīng)度個體的信息或帶參數(shù)的變異的變異概率降低不影響種群收斂。Mhlenbein介紹了一種實值編碼遺傳算法的變異算子，對變異范圍分布用非線性項應(yīng)用于基因值。已經(jīng)證明使用偏差變異使基因值有較小的變化，變異常常用于與重組連接作為搜索過程的前期工作。另一些變異包括傳統(tǒng)變異如何在染色體中分配個體基因，習(xí)慣

24、上對弱條件直接變異和重新安排變異，即交換位的位置或提高在決定變量空間基因的差異。遺傳算法工具箱提供的二進(jìn)制和整型變異函數(shù)mut，實值變異適合使用函數(shù)mutbga；變異算子的高級接口函數(shù)是mutate。6.7 重插入(ch r)一旦一個新的種群通過(tnggu)對舊種群的個體進(jìn)行選擇和重組而產(chǎn)生，新種群中個體的適應(yīng)度被確定了，如果通過重組產(chǎn)生的種群個體數(shù)少于原始種群的大小，新種群和舊種群大小的差異被稱為代溝。在這種情況下，每一代產(chǎn)生的新個體數(shù)較少，這時的遺傳算法稱之為穩(wěn)態(tài)或增量的。如果一個或多個最適合個體(gt)被連續(xù)代繁殖，則遺傳算法被稱為得到精英策略。為了保持原始種群的大小，一些新的個體不得

25、不被重新插入舊種群中。同樣地，如果在每一代并非所有新個體被使用或生產(chǎn)的子代大小超過舊種群，則一個恢復(fù)計劃用來決定那些個體存在于新種群中。如前所述，穩(wěn)態(tài)遺傳算法(steady-state GA)最引人注目的一個重要的特征是在每一代中不創(chuàng)建比現(xiàn)存種群多的后代，計算次數(shù)被減少，并且產(chǎn)生后代時由于有少的新個體存儲，內(nèi)存要求也小。當(dāng)選擇老種群中哪些成員被替代時最常用的策略是替換確定的最小適應(yīng)度成員。Fogarty 在研究中已經(jīng)證明，對選擇的個體進(jìn)行替代使用逆比率選擇或最小適應(yīng)度，其收斂特性沒有顯著差異。當(dāng)最大適應(yīng)度成員將具有機會連續(xù)生存時，他進(jìn)一步斷言替代最小適應(yīng)成員是一有效的優(yōu)選策略工具。的確，大多數(shù)

26、成功的選擇方案是選擇種群中最老的成員進(jìn)行替代。這里指出多數(shù)與代的再生一致，在某一時刻，種群中的每一個成員都將被替代。因此為使一個個體能連續(xù)存在，它必須有足夠適應(yīng)度以確保繁殖到下一代。遺傳算法工具箱提供一函數(shù)reins使個體可在重組后重插入種群中。任選輸入?yún)?shù)允許使用一致隨機或基于適應(yīng)度的重插入。另外，這個程序能選擇重插入比重組產(chǎn)生少的子代。6.8 遺傳算法的終止因為遺傳算法是隨機搜索算法，找到一個正式的、明確的收斂性判別標(biāo)準(zhǔn)是困難的。若在找到最優(yōu)個體以前的許多代的種群適應(yīng)度可能保持不變，應(yīng)用程序的常規(guī)終止條件將成為有問題的。常用方法是遺傳算法終止采用達(dá)到預(yù)先設(shè)定的代數(shù)和根據(jù)問題定義測試種群中最

27、優(yōu)個體的性能。如果沒有可接受的解答，遺傳算法重新啟動或用新的搜索初始條件。6.9 數(shù)據(jù)結(jié)構(gòu)MATLAB本質(zhì)上只支持實值或復(fù)數(shù)值矩陣一種數(shù)據(jù)類型。遺傳算法工具箱的主要數(shù)據(jù)結(jié)構(gòu)是：染色體、表現(xiàn)型、目標(biāo)函數(shù)值和適應(yīng)度值。1染色體染色體數(shù)據(jù)結(jié)構(gòu)用大小的單矩陣存儲整個種群，這里是種群中個體的個數(shù)，是個體基因表現(xiàn)型的長度，每一行對應(yīng)一個個體的基因，由個基數(shù)組成，典型的是二進(jìn)制值。染色體數(shù)據(jù)結(jié)構(gòu)(sh j ji u)舉例如下：這種數(shù)據(jù)表示并不是染色體結(jié)構(gòu)的強制結(jié)構(gòu)，只要求所有(suyu)染色體具有(jyu)相同的長度。因此，結(jié)構(gòu)化種群或具有可變基因基礎(chǔ)的種群可用于遺傳算法工具箱提供的合適編碼函數(shù)、映射染色體

28、的表現(xiàn)型。2表現(xiàn)型遺傳算法中的決策變量或表現(xiàn)型通過在決策變量空間對染色體表現(xiàn)形式進(jìn)行映射獲得。這里，包含在染色體結(jié)構(gòu)中的每一個串根據(jù)在搜索空間中的維度值和對應(yīng)的決策變量向量值編碼為一行向量，這個決策變量被存儲在一大小為的數(shù)字矩陣中，每一行對應(yīng)一特定個體的表現(xiàn)型。下面給出了表現(xiàn)型數(shù)據(jù)結(jié)構(gòu)的例子，遺傳算法工具箱的DECODDE常用于表示一泛函數(shù)，映射基因到表現(xiàn)型。Phen= DECODE ( Chrom ); % 將基因型變換為顯型(Map Genotype to Phenotype) 在染色體表示和表現(xiàn)型值之間的實際映射依賴于函數(shù)DECODE的應(yīng)用。應(yīng)用這種表達(dá)得到不同類型決策變量的向量是完全可

29、行的。例如，在相同的表現(xiàn)型數(shù)據(jù)結(jié)構(gòu)中混有整型、實型和字母的決策變量是允許的。3目標(biāo)函數(shù)值目標(biāo)函數(shù)常用來評估表現(xiàn)型在問題域中的性能。目標(biāo)函數(shù)值可能是標(biāo)量或在多目標(biāo)情況下是矢量。值得注意的是，目標(biāo)函數(shù)值不像適應(yīng)度值一樣是必需的。目標(biāo)函數(shù)值被存儲在一大小為的數(shù)字矩陣中，這里是目標(biāo)的數(shù)量。每一行對應(yīng)一單獨個體的目標(biāo)矢量。目標(biāo)函數(shù)值數(shù)據(jù)結(jié)構(gòu)例子在下面給出，用OBJFUN表示一任意的目標(biāo)函數(shù)。ObjV = OBJFUN (Phen); % 目標(biāo)函數(shù)（Objective Function） 4適應(yīng)度值適應(yīng)度值是由目標(biāo)函數(shù)值通過計算(j sun)或評定等級而得出的。適應(yīng)度是一非負(fù)的標(biāo)量并保存(bocn)在長度

30、為的列向量(xingling)中。下面給出一個例子。FITNESS是一任意的適應(yīng)度函數(shù)。Fitn = FITNESS (ObjV); % 適應(yīng)度函數(shù)（Fitness Function）注意，對多目標(biāo)函數(shù)，一個特定個體的適應(yīng)度是目標(biāo)函數(shù)值向量的一個函數(shù)。多目標(biāo)問題一般沒有一個簡單的惟一解，但可由具有不同值的決策變量的一組相同合適解描述。因此通過采用一些措施確保種群能夠解出一組Pareto最優(yōu)解，例如，通過在選擇方法中使用適應(yīng)度共享。盡管在本版本的遺傳算法工具箱中不支持，計劃在后續(xù)版本中補充多目標(biāo)搜索。6.10 多種群支持遺傳算法工具箱通過使用高級遺傳算子函數(shù)和例程在子種群中交換個體而支持多子種群

31、。在一些文獻(xiàn)中，使用多子種群表明，在大多數(shù)情況下，相比于單種群遺傳算法，它改善了所獲得結(jié)果的性能。遺傳算法工具箱支持通過修改所用的數(shù)據(jù)結(jié)構(gòu)將所用單種群分割成許多子種群或同類群，以便使用一個簡單矩陣將子種群保存在一連續(xù)塊中。例如，染色體結(jié)構(gòu)Chrom由每個長度為N的SUBPOP個子種群組成而保存。著名的是遷移(Migration)或孤島 (Island) 模型，每一個子種群通過傳統(tǒng)的遺傳算法和個體時，隨時從一個子種群遷移到另一個子種群而發(fā)展成下一代。遷移的個體數(shù)量和遷移的模式?jīng)Q定有多大的遺傳差異發(fā)生。 為了允許工具箱例程在子種群上獨立操作，遺傳算法工具箱提供了大量的高級接口程序，接受一任選變量來

32、確定在數(shù)據(jù)結(jié)構(gòu)中獲得的子種群的數(shù)量。低級例程被依次獨立調(diào)用，對每個子種群完成選擇、交叉和重插入等功能。表6.1中列出子種群支持的函數(shù)，這是一些高級函數(shù)。表6.1 子種群支持的函數(shù)函 數(shù)說 明mutate變異算子recombin交叉和重組算子reins均勻隨機和基于適應(yīng)度的重插入select獨立子種群選擇注意：對當(dāng)前工具，所有子種群必須是相同大小的。個體在兩個子種群之間的遷移是由函數(shù)migrate實現(xiàn)的，一個單一的標(biāo)量決定遷移個體的總量。因此，給出的一個種群包括大量的子種群，它從另一個子種群接收數(shù)量相同的個體，這個函數(shù)的第二個參數(shù)控制使用均勻選擇或者按照適應(yīng)度兩種方式之一選擇哪個個體參加遷移。均勻選擇為遷移選取個體并且在子種群中使用隨機方式用遷移個體替代本子種群中的個體，基于適應(yīng)度遷移選擇個體是按照它們的適應(yīng)度水平進(jìn)行的，最適應(yīng)個體將被選擇作為遷移，子種群被替代的個體是按均勻隨機選擇的。子群1 子群2 子群3 子群6 子群5 子群4 圖6.7 相鄰遷移拓?fù)渥尤? 子群2 子群3 子群6 子群5 子群4 圖6.6 循環(huán)遷移拓?fù)湎旅?xi mian)，更進(jìn)一步用參數(shù)說明在不同(b tn)種群拓?fù)浣Y(jié)構(gòu)中遷移的發(fā)生(fshng)過程。圖6.6顯示循環(huán)遷移在函數(shù)migrate中執(zhí)行的大多數(shù)基本遷移路徑。這里個體的遷移是在直接相鄰的子種群中，例如來自子種群6的遷移個體只遷移到子種