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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、叉定義的交叉點(diǎn)即染色體拆分基因位。均勻交叉更加廣義化，將每個(gè)點(diǎn)都作為潛在的交叉點(diǎn)。一個(gè)交叉掩碼，隨機(jī)產(chǎn)生的與個(gè)體等長(zhǎng)的染色體結(jié)構(gòu)，掩碼中的等價(jià)位表明哪個(gè)父?jìng)€(gè)體向子個(gè)體提供變量值?？紤]如下兩個(gè)父?jìng)€(gè)體，交叉掩碼和最終的子個(gè)體：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)，第一個(gè)子個(gè)體O1產(chǎn)生(chnshng)的位，其掩碼對(duì)應(yīng)(duyng)位為1，則來(lái)自父?jìng)€(gè)體P1；對(duì)應(yīng)位為0，則來(lái)

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

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

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

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

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

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

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

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

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

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

29、行的。例如，在相同的表現(xiàn)型數(shù)據(jù)結(jié)構(gòu)中混有整型、實(shí)型和字母的決策變量是允許的。3目標(biāo)函數(shù)值目標(biāo)函數(shù)常用來(lái)評(píng)估表現(xiàn)型在問(wèn)題域中的性能。目標(biāo)函數(shù)值可能是標(biāo)量或在多目標(biāo)情況下是矢量。值得注意的是，目標(biāo)函數(shù)值不像適應(yīng)度值一樣是必需的。目標(biāo)函數(shù)值被存儲(chǔ)在一大小為的數(shù)字矩陣中，這里是目標(biāo)的數(shù)量。每一行對(duì)應(yīng)一單獨(dú)個(gè)體的目標(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ù)值通過(guò)計(jì)算(j sun)或評(píng)定等級(jí)而得出的。適應(yīng)度是一非負(fù)的標(biāo)量并保存(bocn)在長(zhǎng)度

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

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

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