第四章 用遺傳算法設(shè)計(jì)神經(jīng)網(wǎng)絡(luò)

1、吉林工業(yè)大學(xué)碩士學(xué)位論文 第四章 用遺傳算法設(shè)計(jì)神經(jīng)網(wǎng)絡(luò) 4.1概述自1986年Rumelhart和Parker發(fā)明誤差反向傳播算法（BP算法）以來，人工神經(jīng)網(wǎng)絡(luò)的理論和應(yīng)用研究發(fā)展十分迅速，其中，前饋型網(wǎng)絡(luò)（又稱BP網(wǎng)）因其結(jié)構(gòu)簡單和非線性映射能力而具有廣泛的工程應(yīng)用前景，如模式識別、過程控制、故障診斷等，同時(shí)，BP網(wǎng)在人工智能研究中又被作為機(jī)器學(xué)習(xí)知識獲取的重要工具。Kolmogorov已經(jīng)證明了多層前饋神經(jīng)網(wǎng)絡(luò)能夠解決可以表示成從某個(gè)輸入空間到某個(gè)輸出空間的連續(xù)映射的任意問題。但這只是一個(gè)存在性定理，它沒有給出關(guān)于如何構(gòu)造網(wǎng)絡(luò)的提示，網(wǎng)絡(luò)的構(gòu)造是個(gè)非常重要的問題。如何優(yōu)化BP網(wǎng)絡(luò)的結(jié)構(gòu)目

2、前尚無理論指導(dǎo)，在應(yīng)用過程中往往指定過多的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和層數(shù)，期望通過BP算法自動地裁減多余部分，而實(shí)際情況并非如此。由于BP算法在冗余結(jié)構(gòu)下會產(chǎn)生“過學(xué)習(xí)”現(xiàn)象，使網(wǎng)絡(luò)的訓(xùn)練學(xué)習(xí)了樣本模式的確切特征而不是樣本集的一般特征，缺乏外推能力而難以實(shí)際應(yīng)用18；基于數(shù)值實(shí)驗(yàn)的啟發(fā)式設(shè)計(jì)也很困難，這種啟發(fā)式方法有兩個(gè)主要缺點(diǎn)：第一，可能的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)空間非常大，甚至對小型應(yīng)用問題，其中的大部分結(jié)構(gòu)也仍然沒有探測；第二，構(gòu)成一個(gè)好的結(jié)構(gòu)的因素密切依賴于應(yīng)用，既要考慮需要求解的問題，又要考慮對神經(jīng)網(wǎng)絡(luò)解的限制，但目前還沒有一個(gè)好的技術(shù)或方法做到這一點(diǎn)，網(wǎng)絡(luò)結(jié)構(gòu)空間非常大，探測好的結(jié)構(gòu)十分耗時(shí)。研究神經(jīng)網(wǎng)絡(luò)的

3、最終目的是解決實(shí)際問題，欲實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是至關(guān)重要的，它關(guān)系到實(shí)現(xiàn)的難易程度、網(wǎng)絡(luò)可靠性、穩(wěn)定性、抗干擾性等問題，BP網(wǎng)絡(luò)的結(jié)構(gòu)設(shè)計(jì)取決于具體應(yīng)用，需要一種高效率搜索機(jī)制來探測結(jié)構(gòu)空間。為了進(jìn)一步揭示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與網(wǎng)絡(luò)性能之間的關(guān)系，需要開拓新的研究和分析方法。而遺傳算法正具有這種特性。遺傳算法是一種模擬生物界自然選擇和自然遺傳機(jī)制的高度并行、隨機(jī)、自適應(yīng)最優(yōu)化搜索算法5，具有隱含的并行性和對全局信息的有效利用能力，使它只需搜索少數(shù)結(jié)構(gòu)就能反映搜索空間的大量區(qū)域，利用群體的適應(yīng)值信息，通過簡單的復(fù)制、雜交和變異算子，遺傳算法能以很大的概率找到全局最優(yōu)解，遺傳算法尤其適合于處理傳統(tǒng)

4、搜索方法解決不了的復(fù)雜和非線性問題，并發(fā)展成為一種自組織、自適應(yīng)的綜合技術(shù)57。在一組給定的性能準(zhǔn)則下優(yōu)化神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)是個(gè)復(fù)雜的問題，其中有許多變量，包括離散的和連續(xù)的，并且它們以復(fù)雜的方式相互作用，對一個(gè)給定設(shè)計(jì)的評價(jià)本身也是帶噪聲的，這是由于訓(xùn)練的效能依賴于具有隨機(jī)性的初始條件?？傊?，神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)對遺傳算法而言是個(gè)邏輯應(yīng)用問題。遺傳算法一般可以通過兩種方式應(yīng)用到神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)中，一種方式是利用遺傳算法訓(xùn)練已知結(jié)構(gòu)的網(wǎng)絡(luò)，優(yōu)化網(wǎng)絡(luò)的連接權(quán)；另一種方式是利用遺傳算法找出網(wǎng)絡(luò)的規(guī)模、結(jié)構(gòu)和學(xué)習(xí)參數(shù)。用遺傳算法研究神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)主要有兩個(gè)目標(biāo)。第一個(gè)目標(biāo)是開發(fā)神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)工具，這種工具可以讓設(shè)計(jì)

5、者描述解的問題或問題類，然后自動搜索一個(gè)最優(yōu)的網(wǎng)絡(luò)設(shè)計(jì)；第二個(gè)目標(biāo)是通過發(fā)現(xiàn)更多的依據(jù)來幫助建立神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)的理論。 4.2 遺傳算法的描述自從生物進(jìn)化理論得到人們的接受之后，生物學(xué)家就對進(jìn)化機(jī)制產(chǎn)生了極大的興趣。雖然目前關(guān)于推動這個(gè)進(jìn)化的機(jī)制還沒有完全弄清楚，但它們的某些特征已為人所知。進(jìn)化是發(fā)生在作為生物體結(jié)構(gòu)編碼的染色體上，通過對染色體的譯碼部分地生成生物體，人們現(xiàn)在還不完全清楚染色體的編碼和譯碼過程的細(xì)節(jié)，但下面幾個(gè)關(guān)于進(jìn)化理論的一般特性已廣為人們所接受：（1）進(jìn)化過程是發(fā)生在染色體上，而不是發(fā)生在它們所編碼的生物體上。（2）自然選擇把染色體以及由它們所譯成的結(jié)構(gòu)的表現(xiàn)聯(lián)系在一起，那些

6、適應(yīng)性好的個(gè)體的染色體有更多的繁殖機(jī)會。（3）繁殖過程是進(jìn)化發(fā)生的那一刻，變異可以使生物體子代的染色體不同于它們父代的染色體。通過結(jié)合兩個(gè)父代染色體中的物質(zhì)，重組過程可以在子代中產(chǎn)生有很大差異的染色體。（4）生物進(jìn)化沒有記憶。有關(guān)產(chǎn)生個(gè)體的信息包含在個(gè)體所攜帶的染色體的集合以及染色體編碼的結(jié)構(gòu)之中，這些個(gè)體會很好地適應(yīng)它們的環(huán)境。自然進(jìn)化的這些特征早在60年代就引起了美國學(xué)者John Holland的極大興趣。Holland注意到學(xué)習(xí)不僅可以通過單個(gè)生物體的適應(yīng)而且通過一個(gè)種群的許多代的進(jìn)化適應(yīng)也能發(fā)生。受達(dá)爾文進(jìn)化論適者生存的啟發(fā)，他逐漸認(rèn)識到，在機(jī)器學(xué)習(xí)的研究中，為獲得一個(gè)好的學(xué)習(xí)算法，僅

7、靠單個(gè)策略的建立和改進(jìn)是不夠的，還要依賴于一個(gè)包含許多候選策略的群體的繁殖。他們的研究想法起源于遺傳進(jìn)化，Holland就將這個(gè)研究領(lǐng)域取名為遺傳算法。Holland創(chuàng)建的遺傳算法是一種概率搜索算法，它是利用某種編碼技術(shù)作用于稱為染色體的二進(jìn)制數(shù)串，其基本思想是模擬由這些串組成的群體的進(jìn)化過程。遺傳算法通過有組織地然而是隨機(jī)地信息交換來重新組合那些適應(yīng)性好的串，在每一代中，利用上一代串結(jié)構(gòu)中適應(yīng)性好的位和段來生成一個(gè)新的串的群體；作為額外增添，偶爾也要在串結(jié)構(gòu)中嘗試用新的位和段來代替原來的部分。遺傳算法利用簡單的編碼技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，從而解決非常困難的問題。特別是由于不受搜索空間

8、的限制性假設(shè)的約束，不必要求諸如連續(xù)性、導(dǎo)數(shù)存在和單峰等假設(shè)，以及其固有的并行性，遺傳算法目前已經(jīng)在最優(yōu)化、機(jī)器學(xué)習(xí)和并行處理等領(lǐng)域得到了越來越廣泛的應(yīng)用。遺傳算法的主要步驟如下：（1）隨機(jī)產(chǎn)生一個(gè)由確定長度的特征串組成的初始群體。（2）對串群體迭代地執(zhí)行下面的步（i）和步（ii），直到滿足停止準(zhǔn)則：（i）計(jì)算群體中每個(gè)個(gè)體的適應(yīng)值；（ii）應(yīng)用復(fù)制、雜交和變異算子產(chǎn)生下一代群體。（3）把在任一代中出現(xiàn)的最好的個(gè)體串指定為遺傳算法的執(zhí)行結(jié)果。這個(gè)結(jié)果可以表示問題的一個(gè)解（或近似解）。在準(zhǔn)備應(yīng)用遺傳算法求解問題時(shí)，要完成以下四個(gè)主要步驟：（1）確定表示方案；（2）確定適應(yīng)值度量；（3）確定控制算

9、法的參數(shù)和變量；（4）確定指定結(jié)果的方法和停止運(yùn)行的準(zhǔn)則。在常規(guī)的遺傳算法中，表示方案是把問題的搜索空間中每個(gè)可能的點(diǎn)表示為確定長度的特征串。表示方案的確定需要選擇串長l和字母表規(guī)模k。二進(jìn)制串是遺傳算法中常用的表示方法。選擇一個(gè)便于遺傳算法求解問題的表示方案經(jīng)常需要對問題有深入的了解。適應(yīng)值度量為群體中每個(gè)可能的確定長度的特征串指定一個(gè)適應(yīng)值，它經(jīng)常是問題本身所具有的。適應(yīng)值度量必須有能力計(jì)算搜索空間中每個(gè)確定長度的特征串的適應(yīng)值。控制遺傳算法的主要參數(shù)有群體規(guī)模N和是執(zhí)行的最大代數(shù)目M，次要參數(shù)有復(fù)制概率、雜交概率、變異概率p和代間隙G等參數(shù)。至于指定結(jié)果和停止和停止執(zhí)行算法的方法視具體問

10、題而定。 4.3用遺傳算法設(shè)計(jì)前饋神經(jīng)網(wǎng)絡(luò) 圖4-1給出了遺傳算法用于神經(jīng)網(wǎng)絡(luò)模擬系統(tǒng)構(gòu)成的混合學(xué)習(xí)系統(tǒng)。4.3.1表示方案的確定在遺傳算法的群體中，染色體串編碼前饋多層神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，特別地，它們?yōu)殡[含單元的數(shù)目、布局和控制反向傳播法的三個(gè)參數(shù)（即學(xué)習(xí)率、動量項(xiàng)和初始隨機(jī)連接權(quán)的范圍，均用Gray碼）編碼。在本文討論的前饋神經(jīng)網(wǎng)絡(luò)中，允許至多有兩個(gè)隱含層；在能使網(wǎng)絡(luò)性能提高的條件下，這兩個(gè)隱含層中任何一 遺傳算法 神經(jīng)網(wǎng)絡(luò)通過學(xué)習(xí)后的網(wǎng)絡(luò)性能 網(wǎng)絡(luò)結(jié)構(gòu) 圖4-1 遺傳算法與神經(jīng)網(wǎng)絡(luò)藕合成的混合學(xué)習(xí)系統(tǒng)層在演化中都可以被刪去，在每一個(gè)隱含層中，神經(jīng)元的最大數(shù)目為32。染色體串的編碼形式如下：

11、第一隱含層（第1位=有/無，后5位=單元數(shù)，132） 第二隱含層（第1位=有/無，后5位=單元數(shù)，132）4.3.2適應(yīng)值的確定在遺傳算法中，適應(yīng)值是用來區(qū)分群體中個(gè)體（問題的解）的好壞，適應(yīng)值越大的個(gè)體越好，反之，適應(yīng)值越小的個(gè)體越差。遺傳算法正是基于適應(yīng)值對個(gè)體進(jìn)行選擇，以保證適應(yīng)性好的個(gè)體有機(jī)會在下一代中產(chǎn)生更多的子個(gè)體。此外，象在賭盤選擇中，還要求適應(yīng)值必須是非負(fù)數(shù)。然而在許多問題中，求解目標(biāo)更自然地被表示成某個(gè)代價(jià)函數(shù)f（x）的極小化，而不是某個(gè)利益函數(shù)g（x）的極大化；即使問題被表示成極大化形式，僅僅這一點(diǎn)并不能確保利益函數(shù)g（x）對所有的x都是非負(fù)的。作為這些問題的結(jié)果，常常需要

12、通過一次或多次變換把目標(biāo)函數(shù)轉(zhuǎn)化到適應(yīng)函數(shù)F（x）。對優(yōu)選結(jié)構(gòu)的評價(jià)需要從網(wǎng)絡(luò)的學(xué)習(xí)能力和一般化(外推)能力兩方面綜合考慮。根據(jù)第三章的討論，我們采用自適應(yīng)學(xué)習(xí)率加動量項(xiàng)的改進(jìn)算法，隱層激勵(lì)函數(shù)為Sigmod函數(shù)，輸出層激勵(lì)函數(shù)為線性函數(shù)，采用K重雜交訓(xùn)練方法。我們?nèi)【W(wǎng)絡(luò)性能評價(jià)目標(biāo)函數(shù)為： E= 訓(xùn)練樣本集平均相對誤差 + 測試樣本集平均相對誤差 適應(yīng)值函數(shù)定義為：SyzEXP（min（E）E）式中EXP（）表示以e為底的指數(shù)函數(shù)；min（）表示最小值。這種指數(shù)比例變換使適應(yīng)值范圍在12.718之間，既可限制優(yōu)勢個(gè)體的復(fù)制數(shù)量又可提高相似串之間的竟?fàn)幮浴?.3.3確定選擇方法復(fù)制就是根據(jù)適應(yīng)

13、值從群體中選擇串進(jìn)行拷貝的過程。一旦一個(gè)串被選擇，則將這個(gè)串的拷貝放入在一個(gè)新的暫時(shí)群體交配池中，以便進(jìn)行雜交和變異。當(dāng)完成了N次復(fù)制后，整個(gè)暫時(shí)群體就被填滿了。復(fù)制算子有多種：如賭盤選擇，確定性選擇，有退還和無退還隨機(jī)選擇，有退還和無退還剩余隨機(jī)選擇等。本文采用了確定性選擇方法：對群體中每個(gè)串計(jì)算生存概率,從而得到的期望拷貝數(shù)，仍記為；根據(jù)值的整數(shù)部分，分配給每個(gè)串一個(gè)拷貝數(shù)，并按照值的小數(shù)部分對群體中的串進(jìn)行排序；最后按排列順序從大到小選擇串，直到填滿暫時(shí)群體。4.3.4確定控制算法的參數(shù)和變量（1）群體規(guī)模N群體規(guī)模影響到遺傳算法的最終性能和效率。當(dāng)規(guī)模太小時(shí)，由于群體對大部分超平面只給

14、出了不充分的樣本量，所以得到的結(jié)果一般不佳。大的群體更有希望包含出自大量超平面的代表，從而可以阻止過早收斂到局部最優(yōu)解；然而群體規(guī)模越大，每一代需要的計(jì)算量也就越多，這有可能導(dǎo)致一個(gè)無法接受的慢收斂率。在我們的實(shí)驗(yàn)中，由于實(shí)驗(yàn)條件的限制，適應(yīng)值的評價(jià)相當(dāng)費(fèi)時(shí)，群體規(guī)模取為10。（2）雜交率雜交率控制雜交算子應(yīng)用的頻率，在每代新的群體中，有個(gè)串實(shí)行雜交。雜交率越高，群體中串的更新就越快。如果雜交率過高，相對選擇能夠產(chǎn)生的改進(jìn)而言，高性能的串被破壞得要更快。如果雜交率過低，搜索會由于太小的雜交率而可能停滯不前。本實(shí)驗(yàn)選取了0.6作為雜交率。（3）變異率變異是增加群體多樣性的搜索算子，每次選擇和雜交

15、之后，新的群體中的每個(gè)串的每一位以概率等于變異率進(jìn)行隨機(jī)改變，從而每代大約發(fā)生次變異，其中為串長。一個(gè)低水平的變異率足以防止整個(gè)群體中任一給定位保持永遠(yuǎn)收斂到單一的值。高水平的變異率實(shí)質(zhì)上產(chǎn)生的是隨機(jī)搜索。本實(shí)驗(yàn)采用了0.01作為變異率。（4）代間隙G代間隙控制每一代中群體被替換的百分率，即上一代中有個(gè)串被隨機(jī)地選擇保留到下一代中，我們?nèi)?.9。（5）停止準(zhǔn)則迭代停止準(zhǔn)則設(shè)定為規(guī)定的代數(shù)，本實(shí)驗(yàn)定為20。一個(gè)基本的遺傳算法可以用下面的偽碼描述：Procedure Genetic Alogorithm；begin k：=0； 初始P（k）； P（k）為第k代群體 計(jì)算P（k）的適應(yīng)值； whil

16、e (不滿足停止準(zhǔn)則)do k：=k+1； 從P（k-1）中選擇P（k）； 復(fù)制算子 重組P（k）； 雜交和變異算子 在上一代中隨機(jī)選擇個(gè)個(gè)體隨機(jī)替換P（k）中的個(gè)體； 計(jì)算P（k）適應(yīng)值 endend 4.4遺傳算法的改進(jìn)遺傳算法是一種參數(shù)搜索算法。采用適應(yīng)度比例選擇、單點(diǎn)雜交和單點(diǎn)變異的遺傳算法稱為簡單遺傳算法，它的缺陷是收斂速度慢、易陷入局部極小等。在應(yīng)用遺傳算法中，要首先給定一組控制參數(shù)，如群體規(guī)模、雜交率和變異率等，控制參數(shù)的不同選取會對遺傳算法的性能產(chǎn)生很大的影響；各種算法是針對實(shí)際問題的，都有各自的特點(diǎn)，采用不同的選擇、雜交和變異策略，對算法的性能會有很大的影響。針對本項(xiàng)目的具體

17、問題，我們對簡單遺傳算法作了一些改進(jìn)，本文從以下幾個(gè)方面進(jìn)行遺傳算法的改進(jìn)。4.4.1編碼方案的改進(jìn)生成初始染色體群最簡單的方法，就是利用隨機(jī)數(shù)發(fā)生器隨機(jī)地產(chǎn)生一系列方案，然后以此為基礎(chǔ)進(jìn)行迭代。此方法簡單方便，但是產(chǎn)生的初始方案雜亂無章，良莠并存。只有經(jīng)過若干次迭代后，那些生命力強(qiáng)的染色體才會被遺傳或產(chǎn)生出來，進(jìn)而提高染色體的品質(zhì)，得到滿意的解。仔細(xì)分析上述傳統(tǒng)二進(jìn)制結(jié)構(gòu)編碼方案我們發(fā)現(xiàn)存在如下缺點(diǎn)：（1）缺乏全局性和稀疏性。單隱層的網(wǎng)絡(luò)結(jié)構(gòu)多于雙隱層的結(jié)構(gòu)，且單隱層的神經(jīng)元數(shù)相對集中在132中間的一些數(shù)上，有可能重復(fù)；（2）出現(xiàn)無隱層的現(xiàn)象。由于采用二進(jìn)制編碼，雖然比較容易操作，但如果要表

18、示較大的范圍，則串的長度比較大。從理論上已經(jīng)證明：具有短定義長度、低階并且適應(yīng)值高于群體平均值的模式，在遺傳算法迭代中將按指數(shù)率增長，對群體中N個(gè)串的處理實(shí)際上隱含地并行處理了大約O(N3)個(gè)模式5。由于實(shí)驗(yàn)條件有限，盡管遺傳算法本身具有隱含并行性，但對于適應(yīng)值的計(jì)算并行性有待于研究，而對于我們這個(gè)混合學(xué)習(xí)系統(tǒng)，適應(yīng)值的評價(jià)是非常費(fèi)時(shí)的，因此我們設(shè)置的群體數(shù)量較少，而且迭代次數(shù)也不可能太多，還不能真正實(shí)現(xiàn)全局范圍內(nèi)的優(yōu)化。對于單隱層的網(wǎng)絡(luò)，隱含節(jié)點(diǎn)數(shù)在30以上的網(wǎng)絡(luò)很難得到評價(jià)。對于這一點(diǎn)，除了采用全新的編碼方案如浮點(diǎn)編碼方案以外，我們也可以對上述的編碼方案作如表4-1的改進(jìn)。這種編碼方案，不

19、僅位串少了一位，而且表示的范圍較傳統(tǒng)的編碼范圍大，表示的模式也較多，保證了遺傳算法搜索的全局性和稀疏性，同時(shí)也避免了出現(xiàn)無隱層的現(xiàn)象。 表4-1 染色體串編碼結(jié)構(gòu)序號域名稱位數(shù) 取值說明1學(xué)習(xí)速率20.5，0.25，0.125，0.06252沖量因子20.9，0.8，0.7，0.63初始權(quán)值范圍2±1，±0.5，±0.25，±0.1254多層結(jié)構(gòu)10表示單隱層，神經(jīng)元數(shù)為序號5、6之和：264；1表示兩隱層5第1隱層節(jié)點(diǎn)數(shù)51326第2隱層節(jié)點(diǎn)數(shù)51324.4.2適應(yīng)值的比例變換適應(yīng)值的度量問題是一個(gè)很重要的問題。在簡單遺傳算法中我們采用的是指數(shù)比例變換

20、： E= 訓(xùn)練樣本集批平均相對誤差 + 測試樣本集平均相對誤差 適應(yīng)值函數(shù)定義為：SyzEXP（min（E）E）這樣使適應(yīng)值范圍在 12.718 之間，這種指數(shù)比例變換在搜索初期可限制優(yōu)勢個(gè)體的復(fù)制數(shù)量，防止算法早熟收斂，但到搜索后期對于提高相似串之間的竟?fàn)幮圆焕驗(yàn)榈剿阉骱笃诎创耸接?jì)算出的適應(yīng)值差別很小。為此我們對此式加以修改，將指數(shù)比例變換為下面的關(guān)系式： Syz=EXP（min（E）/E） （4-1）這種類型比例方法的基本思想出自于模擬退火過程。下面應(yīng)用指數(shù)比例方法處理兩組典型的數(shù)據(jù)。例1 群體中有6個(gè)串，其中一個(gè)傳遞適應(yīng)值非常大：原適應(yīng)值 1 0.04 0.035 0.03 0.02

21、5 0.02比例適應(yīng)值（=1） 2.718 1.041 1.036 1.030 1.025 1.020 例2 群體中有6個(gè)串,它們的適應(yīng)值都比較接近：原適應(yīng)值 0.9 0.8 0.7 0.6 0.5 0.4比例適應(yīng)值（=5） 90 55 33 20 12 7從上面可以看到，指數(shù)比例既可以讓非常好的串保持多的復(fù)制機(jī)會，同時(shí)又限制了其復(fù)制數(shù)目以免其很快控制整個(gè)群體；這種方法也提高了相近串的競爭性。系數(shù)的值很重要，它決定選擇的強(qiáng)制性，越大，選擇強(qiáng)制就越趨向于那些具有最高適應(yīng)值的串。對于如何確定值，本文提出了一種新的自適應(yīng)的調(diào)整方法： （4-2）式中avg（）表示取平均值；max（）取最大值。并且對做

22、如下限制：如果大于4，則=4；如果小于1，則=1。這樣在搜索初期，avg(E)<(max(E)-avg(E)，也就是說進(jìn)化群體在解空間中較分散時(shí)，則給予較小的值，限制性能好的群體的復(fù)制數(shù)目，以免其很快控制整個(gè)群體；當(dāng)avg(E)>(max(E)-avg(E)，也就是說在搜索后期，整個(gè)群體的性能值都比較接近的情況下，我們采用較大的比例系數(shù)，提高相似串間的競爭性。4.4.3自適應(yīng)雜交率和變異率的設(shè)計(jì)在簡單遺傳算法(SGA)或標(biāo)準(zhǔn)遺傳算法(CGA)中，變異率是個(gè)常數(shù)。通常，對于變異率是一常量的情況，經(jīng)過多次迭代后，群體的素質(zhì)會趨于一致，這樣就形成了“近親繁殖 ”，近親繁殖對后代的質(zhì)量不利

23、。同樣，如果雙親的基因碼鏈非常接近，雜交以后其后代對于雙親，素質(zhì)提高也極少。因此，群體基因的多樣性變差不僅會減慢進(jìn)化歷程，而且可能導(dǎo)致進(jìn)化停滯，過早收斂于非最優(yōu)解。目前許多學(xué)者都認(rèn)識到變異率需要隨著遺傳進(jìn)程而自適應(yīng)變化，這種有組織性能的遺傳算法具有更高的魯棒性、全局最優(yōu)性和效率。文獻(xiàn)47提出一種雜交率Pc和變異率Pm隨基因操作的在線性能自適應(yīng)變化的有效方法，性能提高則Pc增加，反之則Pm增加；文獻(xiàn)46研究了Pm隨迭代次數(shù)變化的效果，實(shí)例證明Pm隨指數(shù)下降有較好性能；文獻(xiàn)48提出一種自適應(yīng)變異方式，Pm與1對父串間的海明距離成反比，結(jié)果顯示能有效保持基因的多樣性；文獻(xiàn)49提出一種Pc和Pm隨父串

24、的適合度自適應(yīng)變化的新方法，進(jìn)行了詳細(xì)的理論分析和廣泛的實(shí)驗(yàn)研究，結(jié)果顯示該方法在非線性和多模型問題的優(yōu)化中性能優(yōu)異?？梢姡诮窈蟮难芯恐?，遺傳算法結(jié)構(gòu)、基因操作和參數(shù)都會向自組織的形式發(fā)展并將進(jìn)行系統(tǒng)的綜合。本文借鑒上述文獻(xiàn)的思想，提出如下新的自適應(yīng)雜交和變異概率，具體公式設(shè)計(jì)如下： （4-3） （4-4）其中：雜交概率；：變異概率；：每代中個(gè)體適應(yīng)值最高值；每代平均適應(yīng)值。且對變異率作如下的重新定義：每代中個(gè)體發(fā)生變異的概率，也就是每代中有N個(gè)個(gè)體發(fā)生變異。文獻(xiàn)25提出對于變異個(gè)體每位發(fā)生變異的概率為： （4-5）我們通過實(shí)驗(yàn)發(fā)現(xiàn)，這種方法能夠保證在迭代初期，對劣質(zhì)個(gè)體賦予較大的變異率，以

25、造成足夠的擾動，擴(kuò)大解空間，對于優(yōu)良個(gè)體發(fā)生變異的位數(shù)較少。但是到了后期，個(gè)體適應(yīng)值比較接近時(shí)，就沒有變異發(fā)生；而且即使在迭代初期也沒有必要對劣質(zhì)個(gè)體發(fā)生較大變異，這也不符合自然進(jìn)化規(guī)律。我們采用恒定的變異率，每個(gè)變異個(gè)體2或3位發(fā)生變異即可。這種方法在群體中各個(gè)個(gè)體過分趨于一致時(shí)，會使變異的可能性增加，從而提高群體的多樣性，增強(qiáng)算法維持搜索的能力；而當(dāng)進(jìn)化群體在解空間中較分散時(shí)，則給予較大的雜交概率，使其盡快找到最優(yōu)解。4.4.4 選擇和變異的結(jié)合變異算子雖然增加了種群的多樣性，但卻是以降低算法的離線和在線性能為代價(jià)的。為什么會如此？我們對此作了分析，主要是因?yàn)殡S機(jī)變異所致。傳統(tǒng)的遺傳算法是

26、在雜交后實(shí)施變異操作，“優(yōu)良”個(gè)體和“劣質(zhì)”個(gè)體經(jīng)受相同的雜交和變異概率，這樣很難保證丟失基因的恢復(fù)，即使是恢復(fù)了，有效基因的個(gè)體的適應(yīng)值也不一定高，經(jīng)過選擇操作后又會造成有效基因的丟失。對于傳統(tǒng)算法的步驟我們加以改進(jìn)：我們先進(jìn)行選擇和變異，最后再進(jìn)行雜交。我們把傳統(tǒng)的確定性選擇算法與變異結(jié)合起來，本文采用了確定性選擇方法：對群體中每個(gè)串計(jì)算生存概率，從而得到的期望拷貝數(shù)，仍記為；根據(jù)值的整數(shù)部分，分配給每個(gè)串一個(gè)拷貝數(shù)，并按照值的小數(shù)部分對群體中的串進(jìn)行排序；最后按排列順序從大到小選擇串，直到填滿（N-N）暫時(shí)群體，余下的N個(gè)串從中選擇適應(yīng)值較低的串進(jìn)行變異，并放入交配池中，這樣就避免了隨機(jī)

27、變異所造成的有效基因的丟失，從而避免了算法性能的下降。4.4.5雜交算子的改進(jìn)傳統(tǒng)遺傳算法是建立在隨機(jī)模型的基礎(chǔ)上，因而即使在搜索尋優(yōu)計(jì)算前期樣本模式較多，在執(zhí)行雜交操作時(shí)也經(jīng)常會遇到雜交的兩個(gè)位串極其相似的情況；特別在搜索后期，樣本個(gè)體趨于一致時(shí)，由于其相似性，雜交后很難得到新個(gè)體，不僅影響搜索尋優(yōu)進(jìn)度，而且影響到搜索結(jié)果的有效性。這就是所謂的近親雜交問題。根據(jù)Holland提出的遺傳算法的模式理論，一個(gè)模式就是一個(gè)描述種群中在位串的某些確定位置上具有相似性的位串子集的相似模板。為了描述一個(gè)模式，在用以表示位串的二個(gè)字符的字母表0，1中加入一個(gè)通配符*，構(gòu)成一個(gè)表示模式用的三個(gè)字母表0,1,

28、*。一個(gè)模式就象一個(gè)模式匹配裝置。模式理論中有兩個(gè)重要概念，對于模式H，定義：（1）模式位數(shù)（H）：H中有定義的非*位的個(gè)數(shù)；（2）定義長度（H）：H中最兩端的有定義位置之間的距離。由于基于隨機(jī)模型的雜交算子在實(shí)際使用中經(jīng)常會出現(xiàn)近親雜交問題，為解決此問題可以定義一位串間的相似性程度值近親值S（取值0，1，0表示完全不同，1表示完全相同），表示位串和之間的近親值，且。定義由位串和的相同位組成的位串位模式，則的大小與的大小成正比，又因?yàn)榇蟮哪Ｊ狡潆s交后個(gè)體發(fā)生變化的機(jī)率亦大，綜合二者的影響，定義如下近親值計(jì)算式： （4-6）（其中L為位串長度，為加權(quán)系數(shù),且）。 位串：1 0 1 1 0 位串：

29、0 0 1 0 0位串（10110）和（00100）的模式為（*01*0），并且L=5。假設(shè)某一種群有n個(gè)位串，則各位串之間的近親值可以用如下所示矩陣表示： 為獲得最佳的雜交對，可以對上面的近親值矩陣執(zhí)行如下操作：(1) 搜索近親矩陣上三角矩陣的S值，得到一最小值的雜交對；(2) 保存此雜交對；(3) 將矩陣在的行和列刪除，得到一新矩陣；(4) 重復(fù)上三步至所要求的雜交對數(shù)。文獻(xiàn)26提出：在搜索尋優(yōu)后期，如果繼續(xù)使用遠(yuǎn)親有先策略，會使一個(gè)種群喪失其優(yōu)良特性。這在生物界，也同樣體現(xiàn)在同種相配或近種相配，以使種族得以延續(xù)。為了避免產(chǎn)生劣等品種，在搜索后期，應(yīng)對異種雜交進(jìn)行限制。定義一位串間的相異性

30、程度值遠(yuǎn)親值D，則位串和的遠(yuǎn)親值為，取值。利用構(gòu)造遠(yuǎn)親值矩陣，用上述同樣方法求解最小的最佳雜交配對。而我們根據(jù)實(shí)驗(yàn)發(fā)現(xiàn)，到搜索后期，樣本趨于一致時(shí)，更應(yīng)采用遠(yuǎn)親交配方法，這樣有利于產(chǎn)生新的個(gè)體，當(dāng)然這也導(dǎo)致算法在線性能的下降，我們將會采取補(bǔ)救措施。對于新雜交算子的實(shí)現(xiàn)描述如下： Procedure New_Crossover Begin 計(jì)算各位串之間的近親值； 構(gòu)造近親值矩陣； 利用上述方法對矩陣求解最佳雜交對； 執(zhí)行隨機(jī)位選的雜交操作；End采用上述選擇和變異結(jié)合，在此基礎(chǔ)上再采用遠(yuǎn)親交配策略，就不會出現(xiàn)大量重復(fù)迭代相同的個(gè)體，保證了變異和雜交所出現(xiàn)的種群多樣性的效果。最后為了彌補(bǔ)雜交和變

31、異算子對算法性能造成的影響，對簡單遺傳算法中的代間隙也加以重新定義：從上一代中選擇（1-G）個(gè)適應(yīng)值最好的個(gè)體保存到下一代中，這里G取0.8。綜合改進(jìn)遺傳算法敘述如下：Procedure Genetic Algorithm；begin 初始化P（k）； for k=1:T T為規(guī)定迭代的代數(shù) 計(jì)算P（k）各個(gè)體的訓(xùn)練誤差和測試誤差； if (滿足停止準(zhǔn)則) break; end 自適應(yīng)指數(shù)比例系數(shù)計(jì)算； 適應(yīng)值計(jì)算； 自適應(yīng)雜交率和變異率的計(jì)算； 從P（k-1）中選擇N-N個(gè)染色體放入交配池中； 復(fù)制算子 從P（k-1）中選擇N個(gè)適應(yīng)值較差的染色體，進(jìn)行變異并放入交配池中 ； 新的雜交算子；

32、從上一代中選擇個(gè)適應(yīng)值最好的串隨機(jī)替換交配池中的 個(gè)個(gè)體； end end 改進(jìn)的遺傳算法避免了重復(fù)迭代相同的個(gè)體；采用變異劣質(zhì)個(gè)體的方法，避免了隨機(jī)變異而造成對優(yōu)良個(gè)體的破壞；我們把每代中兩個(gè)最優(yōu)個(gè)體保留到下一代的前提下，采用較高的變異率和雜交率，不但增加了種群的多樣性，而且也保證了算法的離線性能，當(dāng)然在線性能有所影響。 4.5 算法性能分析和試驗(yàn)結(jié)果遺傳算法的性能分析一直是都是遺傳算法研究領(lǐng)域中最重要的主題之一。在遺傳算法中，群體規(guī)模、雜交和變異算子的概率等控制參數(shù)的選取是非常困難的。而對于算法性能的評價(jià)也是個(gè)復(fù)雜的問題，同樣也存在收斂速度和收斂精度的矛盾。特別是通過BP算法評價(jià)結(jié)構(gòu)又帶有

33、一定的隨機(jī)性，因?yàn)榫W(wǎng)絡(luò)的訓(xùn)練效能依賴于隨機(jī)的初始化條件；如果定義停止準(zhǔn)則為某代個(gè)體的最優(yōu)性能達(dá)到規(guī)定的要求或兩代之間最好性能值之差為某個(gè)值，由于初始群體的隨機(jī)性，以算法的收斂速度去評價(jià)性能就失去意義。為了能夠綜合評價(jià)算法的性能，我們定義停止準(zhǔn)則為規(guī)定的代數(shù)，除了比較算法的離線性能和在線性能，我們對最后的收斂結(jié)果也加以分析和比較。下面定義兩個(gè)性能度量，一個(gè)是度量算法的收斂性能，另一個(gè)是度量算法的進(jìn)行性能，分別稱為離線性能和在線性能。定義 在f的響應(yīng)面上，搜索算法a的在線性能定義為 （4-7）其中是在時(shí)間內(nèi)所得到的性能值。在線性能表示算法在直到當(dāng)前為止的時(shí)間內(nèi)得到的所有性能值的平均值。定義 在f的

34、響應(yīng)面上，搜索算法a的離線性能定義為 （4-8）其中是在時(shí)間0，內(nèi)所得到的最優(yōu)性能值。離線性能表示算法在執(zhí)行中得到的最優(yōu)性能值的平均值。簡單遺傳算法與綜合改進(jìn)遺傳算法的性能比較如圖4-2、4-3所示。對于簡單遺傳算法我們也采用改進(jìn)的編碼結(jié)構(gòu)，簡單遺傳算法的雜交率為0.6，變異率為0.02。我們也給出了傳統(tǒng)編碼方案的簡單遺傳算法（雜交率為0.6，變異率為0.01）離線性能和優(yōu)化結(jié)果，而在線性能由于單隱層多于雙隱層，且有無隱層的現(xiàn)象，雖然呈下降趨勢，但總體性能比較差，我們沒有畫出。由圖4-2、4-3可看出：改進(jìn)遺傳算法的離線性能明顯好于簡單遺傳算法。由于對于網(wǎng)絡(luò)結(jié)構(gòu)性能的評價(jià)非常費(fèi)時(shí)，對于上述算法

35、我們都運(yùn)行了大約同樣的時(shí)間，而沒有迭代到規(guī)定的代數(shù)。采用新編碼的簡單算法和改進(jìn)遺傳算法迭代了18次，而傳統(tǒng)編碼的簡單遺傳算法才迭代了7次，這是由于簡單遺傳算法中，初始群體缺乏多樣性，初始參數(shù)值都比較低，網(wǎng)絡(luò)訓(xùn)練速度慢。從實(shí)驗(yàn)結(jié)果可以看出如果變異率較小，簡單遺傳算法也存在局部最優(yōu)解問題，也就是早熟收斂問題。簡單遺傳算法更加趨于自然進(jìn)化規(guī)律，而改進(jìn)遺傳算法就好比由于科學(xué)的進(jìn)步，人們由掌握規(guī)律到充分地利用規(guī)律，利用現(xiàn)代科技手段使自然向更好的方向進(jìn)化和發(fā)展。我們對網(wǎng)絡(luò)性能的評價(jià)，只考慮了收斂精度，而對于網(wǎng)絡(luò)的收斂速度卻未進(jìn)行評價(jià)。由上一章我們知道單隱層網(wǎng)絡(luò)收斂速度快于雙隱層結(jié)構(gòu)的網(wǎng)絡(luò)。因此，通過遺傳算

36、法的優(yōu)化實(shí)驗(yàn)我們可以得出如下結(jié)論：在設(shè)計(jì)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)時(shí)，盡量采用單隱層的結(jié)構(gòu)，盡管單隱層結(jié)構(gòu)的隱層單元數(shù)多于兩個(gè)隱層，但收斂速度仍快于雙隱層結(jié)構(gòu)；如果需要兩個(gè)隱層時(shí)，把神經(jīng)元盡量放在第一隱層。0246810121416185101520253035404550 新編碼簡單GA 改進(jìn)GA 圖4-2 簡單GA 與綜合改進(jìn)GA在線性能比較0246810121416180.450.50.550.60.650.70.750.8 簡單GA 新編碼簡單GA 改進(jìn)GA 圖4-3 簡單GA 與綜合改進(jìn)算法離線性能比較對于簡單遺傳算法與改進(jìn)遺傳算法優(yōu)化結(jié)果分別如表4-2、4-3、4-4所示。盡管我們對傳統(tǒng)的網(wǎng)絡(luò)結(jié)構(gòu)編碼進(jìn)行了改進(jìn)，但對于單隱層的網(wǎng)絡(luò)，由于隱層的神經(jīng)元數(shù)對網(wǎng)絡(luò)的性能影響很大，如果不合適就會被淘汰，而只能靠變異來恢復(fù)，即