【文章內(nèi)容簡(jiǎn)介】 遺傳算法基本思想 進(jìn)化論認(rèn)為每一物種在不斷的發(fā)展過程中都是越來越適應(yīng)環(huán)境 。 物種的每個(gè)個(gè)體的基本特征被后代所繼承，但后代又不完全同于父代，這些新的變化若適應(yīng)環(huán)境，則被保留下來 。 在某一環(huán)境中也是那些更能適應(yīng)環(huán)境的個(gè)體特征能被保留下來，這就是適者生存的原理 。 遺傳學(xué)說認(rèn)為遺傳是作為一種指令碼封裝在每個(gè)細(xì)胞中，并以基因的形式包含在染色體中，每個(gè)基因有特殊的位置并控制某個(gè)特殊的性質(zhì)，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境都有一定的適應(yīng)性，基因雜交和基因突變可能產(chǎn)生對(duì)環(huán)境適應(yīng)性更強(qiáng)的后代，通過優(yōu)勝劣汰的自然選擇，適應(yīng) 值高的基因結(jié)構(gòu)就被保存下來 。 遺傳算法將問題的求解表示成用編碼變異兩種基因操作產(chǎn)生出新一代的更適應(yīng)環(huán)境的“染色體”種群 。 隨著算法的運(yùn)行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個(gè)體 。 這一過程就如生物進(jìn)化那樣，好的特征被不斷地繼承下來，壞的特征被逐漸淘汰 。 新一代個(gè)體中包含著上一代個(gè)體的大量信息，新一代的個(gè)體不斷地在總體特性上勝過舊的一代，從而使整個(gè)群體向前進(jìn)化發(fā)展 。 下面是遺傳算法的流程： (1)、初始化群體； (2)、計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值； (3)、按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn) 入下一代的個(gè)體； (4)、按交叉概率進(jìn)行交叉操作； (5)、按變異概率進(jìn)行變異操作； (6)、沒有滿足某種停止條件，則轉(zhuǎn)第 (2)步，否則進(jìn)入 (7)； (7)、輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解 。 遺傳算法中的停止條件，一般依據(jù)問題的不同有不同的確定方式 。 例如，可以采用以下的準(zhǔn)則之一作為判斷條件： (1)、種群中個(gè)體的最大適應(yīng)度超過預(yù)先設(shè)定值； (2)、種群中個(gè)體的平均適應(yīng)度超過預(yù)先設(shè)定值； (3)、世代數(shù)超過預(yù)先設(shè)定值 。 重慶郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 9 圖 遺傳算法的運(yùn)算過程 遺傳算法的特點(diǎn) 常規(guī)的尋優(yōu)算法 常規(guī)的尋優(yōu)方法主要有四種類型：解析法、枚舉法、隨機(jī)法 。 解析法 解析法尋優(yōu)是研究最多的一種，它一般又可分為間接法和直接法 。 (1)、間接法是通過讓目標(biāo)函數(shù)的梯度為零，進(jìn)而求解一組非線性方程來尋求局部極值 。 (2)、直接法是使梯度信息按最陡的方向逐次運(yùn)動(dòng)來尋求局部極值，通常稱為爬山法 。 上述兩種方法的主要缺點(diǎn)：它們只能尋找局部極值而非全局的極值；它們要求目標(biāo)函數(shù)是連續(xù)光滑的，并且需 要導(dǎo)數(shù)信息 。 這兩個(gè)缺點(diǎn)，使得解析尋優(yōu)方法的性能較差 。 相互確定 解碼 編碼 Y N 輸出 X* 選擇、交叉、變異 目標(biāo)函數(shù) 初始種群體 p(t) 搜索空間 解空間 適應(yīng)度評(píng)價(jià) 生成新的群體 p(t+1) 符合 輸出 C* 重慶郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 10 枚舉法 枚舉法可以克服上述解析法的兩個(gè)缺點(diǎn)，即它可以尋找到全局的極值，而且也不需要目標(biāo)函數(shù)是連續(xù)光滑的 。 主要缺點(diǎn)：計(jì)算效率太低，對(duì)于一個(gè)實(shí)際問題，常常由于太大的搜索空間而不可能將所有的情況都搜索到，對(duì)于中等規(guī)模和適度復(fù)雜性的問題，它也常常無能為力 。 隨機(jī)法 隨機(jī)法通過在搜索空間中隨機(jī)地漫游并隨時(shí)記錄下所取得的最好結(jié)果 。 出于效率的考慮，搜索到一定程度便終止 。 然而所得結(jié)果一般尚不是最優(yōu)值 。 本質(zhì)上隨機(jī)法仍然是一種枚舉法 。 遺傳算法與常 規(guī)尋優(yōu)算法的比較 遺傳算法相對(duì)于常規(guī) 尋優(yōu) 算法有如下的特點(diǎn) 。 (1)、遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象 。 傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身來進(jìn)行優(yōu)化計(jì)算，而遺傳算法處理決策變量的 某種編碼形式，使得我們可以借鑒生物學(xué)中的染色體和基因的概念， 模仿自然界生物的遺傳和進(jìn)化機(jī)理，也使得我們能夠方便的應(yīng)用遺傳操作算子 。 特別是對(duì)一些無數(shù)值或很難有數(shù)值 而只有代碼概念的優(yōu)化問題，編碼處理方式更顯示出了其獨(dú)特的優(yōu)越性 。 (2)、遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息 。 傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，而且往 往需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息才能確定搜索方向 。 而遺傳算法僅使用由目標(biāo)函數(shù)值變換來的適應(yīng)度函數(shù)值，就可確定進(jìn)一步的搜索方向和搜索范圍，無需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其它輔助信息 。 (3)、遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息，具有隱含并行性 。 很多傳統(tǒng)的優(yōu)化算法往往是從解空間中的一個(gè)初始點(diǎn)開始最優(yōu)解的迭代搜索過程 。 單個(gè)搜索點(diǎn)所提供的搜索信息畢竟不多，所以搜索效率不高，有時(shí)甚至使搜索過程陷于局部最優(yōu)解而停滯不前 。 遺傳算法是 由很多個(gè)個(gè)體所組成的一個(gè)初始群體開始最優(yōu)解的搜索過程 。 對(duì)這個(gè)群體進(jìn)行遺傳操作，產(chǎn)生出新 一代群體，這個(gè)過程包括了很多群體信息 。 這些信息可以避免搜索一些不必搜索的點(diǎn)，所以實(shí)際上相當(dāng)于搜索了更多的點(diǎn)，這是遺傳算法所特有的一種隱含并行性 。 (4)、遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則 。 很多傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法，這種確定性可能使得重慶郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 11 搜索永遠(yuǎn)達(dá)不到最優(yōu)點(diǎn)，因而也限制了算法的應(yīng)用范圍 。 而遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性 。 (5)、遺傳算法有極強(qiáng)的容錯(cuò)能力 。 遺傳算法的初始串集本身就帶有大量與最優(yōu) 解甚遠(yuǎn)的信息，通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串，這是一個(gè)強(qiáng)烈的濾波過程，并且是一個(gè)并行濾波機(jī)制 。 故而，遺傳算法有很高的容錯(cuò)能力 。 本章小結(jié) 本章詳細(xì)闡述了遺傳算法的基本操作和特點(diǎn)，通過對(duì)上面知識(shí)的了解，把它與常規(guī)的尋優(yōu)方法作出比較，得出遺傳算法并不是一種單純的優(yōu)化算法，而是一種以進(jìn)化思想為基礎(chǔ)的全新的一般方法論，它是解決復(fù)雜問題的有力工具 。 遺傳算法的發(fā)展過程也是不斷進(jìn)化的過程 。 重慶郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 12 第三章 神經(jīng)網(wǎng)絡(luò) 人工神經(jīng)網(wǎng)絡(luò)發(fā)展 1958 年美國(guó)計(jì)算機(jī)學(xué)家羅森布拉特 (Frank Rosenblatt)提出了一種具有三層網(wǎng)絡(luò)特性的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，稱為“ 感知機(jī)” (Perception),這或許是世界上第一個(gè)真正優(yōu)秀的人工神經(jīng)網(wǎng)絡(luò) [7]。 1969 年， 美國(guó)著名人工智能學(xué)者 Minsk 和 Papery寫了一本評(píng)論人工神經(jīng)網(wǎng)絡(luò)的書《感知機(jī)》 (Perception)。稱感知機(jī)不能解決“閾值”這一問題，這本書引起了人們對(duì) 60 年代后期神經(jīng)網(wǎng)絡(luò)發(fā)展面臨過熱現(xiàn)象的爭(zhēng)議。這使神經(jīng)網(wǎng)絡(luò)的研究進(jìn)入低潮時(shí)期。 70 年代后期，由于傳統(tǒng)模型距離人類自身的真實(shí)模型較遠(yuǎn)，表現(xiàn)出了極大的局限性。即對(duì)于那些還找不 到有效計(jì)算方法和明確的計(jì)算方法的問題，例如：在人工智能、模糊識(shí)別、動(dòng)力學(xué)過程模擬等方面，就碰到了有限時(shí)間和空間的障礙，對(duì)于人腦所具有的直覺感知、創(chuàng)造性思維、聯(lián)想功能等，這些迫使人工智能和計(jì)算機(jī)科學(xué)家必須另外尋找發(fā)展智能計(jì)算機(jī)的途徑，并把注意力重新轉(zhuǎn)向人腦的信息處理模式。 人工神經(jīng)網(wǎng)絡(luò)在 80 年代中期得到了飛速的發(fā)展。 1982 年， Hopfield 將人工神經(jīng)網(wǎng)絡(luò)成功地應(yīng)用在組合優(yōu)化問題，提出了 HNN 模型，從而有力地推動(dòng)了神經(jīng)網(wǎng)絡(luò)的研究。他引入了“計(jì)算能量函數(shù)”的概念，給出了網(wǎng)絡(luò)穩(wěn)定性判據(jù)。它的電子電路的實(shí)現(xiàn)為神經(jīng) 計(jì)算機(jī)的研究奠定了基礎(chǔ)，同時(shí)開拓了神經(jīng)網(wǎng)絡(luò)用于聯(lián)想記憶和優(yōu)化計(jì)算的新途徑。 人工神經(jīng)網(wǎng)絡(luò)模型發(fā)展到今日已有百余種模型，建造的方法也是多種多樣，有出自于熱力學(xué)的，數(shù)學(xué)方法的，模糊以及混沌方法。由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的規(guī)則性，限制了系統(tǒng)的自由性和無序運(yùn)動(dòng)，因而可以采用非效力學(xué)的其他方法，如對(duì)于前饋拓?fù)浣Y(jié)構(gòu)的人工神經(jīng)網(wǎng)絡(luò)，可使用感知器算法、誤差反傳遞算法、競(jìng)爭(zhēng)學(xué)習(xí)算法等。 神經(jīng)網(wǎng)絡(luò)基本原理 神經(jīng)元模型 重慶郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 13 神經(jīng)網(wǎng)絡(luò)的基本處理單元是神經(jīng)元，大量神經(jīng)元的并行工作造就了生物神經(jīng)系統(tǒng)驚人的識(shí)別能力 [13]。對(duì)生物神經(jīng)系統(tǒng)的模擬首先是對(duì)神經(jīng)元的模擬。通過對(duì)神經(jīng)元細(xì)胞的研究，人們得出一系列的數(shù)學(xué)特性并提出一些基本的假設(shè) [9]： (1)、神經(jīng)元是一個(gè)多輸入，多輸出的系統(tǒng)； (2)、輸入端有興奮和抑制兩種狀態(tài)； (3)、神經(jīng)元有閾值特性，當(dāng)所有輸入的總和超過閾值時(shí)，才輸出； (4)、輸入、輸出之間有時(shí)間總和、空間總和與不應(yīng)期等特性； (5)、神經(jīng)元是非時(shí)變的。 人們利用數(shù)學(xué)語(yǔ)言，近似地描述出神經(jīng)元的結(jié)構(gòu)特征，它有 5 個(gè)基本要素： (1)、輸入信號(hào)：是神經(jīng)元的 N維輸入，可以用一個(gè) N維的列向量來表示 12[ , , , ]TnX x x x? ??? () (2)、網(wǎng)絡(luò)權(quán)值和閾值： W是神經(jīng)元的權(quán)值，即輸入與神經(jīng)元之間的連接強(qiáng)度，權(quán)值為正表示激活，為負(fù)表示抑制； ? 是神經(jīng)元的閾值，當(dāng)輸入信號(hào)加權(quán)和超過 ?時(shí)，則神經(jīng)元被激活。 (3)、求和單元：用于求取 輸入信號(hào)的加權(quán)和 (線性組合 )，即 1pi kii X W ????? () (4)、非線性激活函數(shù)：它是神經(jīng)元 輸入和輸出之間的變換函數(shù)，起到一個(gè)非線性映射的作用，并將神經(jīng)元輸出幅度限制在一定范圍內(nèi) (一般限制在 (0,1) 或( 1, 1)?? 之間 )。在神經(jīng)元獲得網(wǎng)絡(luò)輸入信號(hào)，經(jīng)過激活函數(shù)就可以得到網(wǎng)絡(luò)輸出信號(hào)。 (5)、輸出信號(hào)：輸入信號(hào)神經(jīng)元加權(quán)求和及傳遞 (激活 )函數(shù)作用后，最后得到終端的輸出。表示為 ()y ?? () 其結(jié)構(gòu)示意圖 所示。圖中， 12{ , , , }inX x x x? ???為神經(jīng)元輸入信號(hào)， iS 為平移信號(hào)， i? 為神經(jīng)元閾值， ijW 為 j? 到 i? 連接的權(quán)值。對(duì)圖示神經(jīng)元，其輸入可表示為： i ij j i ij w x s ?? ? ?? () 輸出為： ()iiy f ? () 重慶郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 14 其中， f是神經(jīng)元激活函數(shù)。 圖 神經(jīng)元結(jié)構(gòu)圖 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)及工作方式 下面介紹神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和工作方式： 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu) 神經(jīng)網(wǎng)絡(luò)的基本結(jié)構(gòu)可以描述為具有下列性質(zhì)的有向圖 : (1)、每個(gè)節(jié)點(diǎn)有一個(gè)狀態(tài)向量 jx ； (2)、節(jié)點(diǎn) i 到節(jié)點(diǎn) j 有一個(gè)連接權(quán)系數(shù) jiW ； (3)、每個(gè)節(jié)點(diǎn)有一個(gè)閾值 j? ； (4)、每個(gè)節(jié)點(diǎn)定義一個(gè)變換函數(shù) , , ( )i jif x W i j??????，最基本形式為 ()ji i jif W x ??? 神經(jīng)網(wǎng)絡(luò)的工作方式 神經(jīng)網(wǎng)絡(luò)的工作過程主要分為兩個(gè)階段： (1)、學(xué)習(xí)期 此時(shí)各計(jì)算單元狀態(tài)不變，各連線上的權(quán)值可通過學(xué)習(xí)來修改； (2)、工作期 此時(shí)各連接 權(quán)固定，計(jì)算單元狀態(tài)變化，以達(dá)到某種穩(wěn)定狀態(tài)。 1iW 2iW iS 1x 2x nx inW iu i? iy 重慶郵電大學(xué)本科畢業(yè)設(shè)計(jì)（論文） 15 神經(jīng)網(wǎng)絡(luò)原理概要 神經(jīng)網(wǎng)絡(luò)是由若干個(gè)處理單元 (神經(jīng)元 )相互連接所組成的系統(tǒng)，第一個(gè)數(shù)學(xué)模型是 MP 模型，它的基本思想是：伸進(jìn)細(xì)胞的工作方式是或者興奮，或者擬制。由于神經(jīng)元之間的信號(hào)連接強(qiáng)度取決于突觸狀態(tài)，因此在 MP 模型中，神經(jīng)元的每個(gè)突觸 的活動(dòng)強(qiáng)度用權(quán)值模擬。于是每個(gè)神經(jīng)元模型都可以從數(shù)十個(gè)甚至數(shù)百個(gè)其他神經(jīng)元接受信息，產(chǎn)生神經(jīng)興奮和沖動(dòng)；單個(gè) MP 神經(jīng)元模型可以實(shí)現(xiàn)與、或、與非、或非等二值邏輯運(yùn)算，但不能實(shí)現(xiàn)異或運(yùn)算，并且由于它是一種靜態(tài)神經(jīng)元，即固定結(jié)構(gòu)，權(quán)值無法調(diào)節(jié)，因此缺乏學(xué)習(xí)能力。 BP 神經(jīng)網(wǎng)絡(luò) BP 神經(jīng)網(wǎng)絡(luò) (Backpropagation Neutral Network)通常是指基于誤差反向傳播算法 (BP 算法 )的多層前饋神經(jīng)網(wǎng)絡(luò)，采用監(jiān)督學(xué)習(xí) (需要外界存在一個(gè)“教師”，它可對(duì)一組給定輸入提供應(yīng)有的輸出結(jié)果 (正確答案 )的訓(xùn)練方式 [4]。 BP算法基本思想 學(xué)習(xí)過程由信號(hào)的正向傳播與誤差的反向傳播兩個(gè)過程組成。正向傳播時(shí)，輸入樣本從輸入層傳入，經(jīng)各隱層逐層處理后，傳向輸出層。若輸出層的實(shí)際輸出與期望的輸 出 (監(jiān)督信號(hào) )不符，則轉(zhuǎn)入誤差的反向傳播階段。誤差反傳是將輸出誤差以某種形式通過隱層向輸入層逐層反傳并將誤差分?jǐn)偨o各層的所有單元，從而獲得各層單元的誤差信號(hào)，此誤差信號(hào)即作為修正各單元權(quán)值的依據(jù)。 如圖 所示。 BP 網(wǎng)絡(luò)分為輸入層 (Input layer)、隱含層 (Hidden layer)、輸出層 (Output layer)。層與層間多采用全互聯(lián)方式，而同層單元間無連接。 BP在正向傳播過程中，輸入信息從輸入層經(jīng)隱含層逐層處理，并傳向輸出層。每一層神經(jīng)元的狀態(tài)值影響下一層神經(jīng)元的狀態(tài)。如果輸出層得不到 期望的輸出，則轉(zhuǎn)入反向傳播，將誤差信號(hào)沿原來的連接通道返回，通過修改各層神經(jīng)元