【文章內(nèi)容簡介】 處理傳統(tǒng)方法難于解決的高度復雜的非線性問題； (2)、 GA在搜索過程中不易陷入局部最優(yōu)，更易找到全局最優(yōu)點； (3)、 GA 隱含并行搜索機制，其在處理較小數(shù)量的位串群體時，所處理的時間復雜度為O(n2)，也就是， GA只花費了正比于群體規(guī)模 n的計算量，但處理的模 3 重慶郵電大學本科畢 業(yè)設計（論文） 式數(shù)量卻正比于群體規(guī)模的三次方。 但遺傳算法 (GA)的不足也是顯而易見的： (1)、 GA的局部搜索能力較弱，致使網(wǎng)絡的訓練精度和效率都不可能太高； (2)、當 GA在搜索時，能迅速到達最優(yōu)解附近，但無法精確確定最優(yōu)解的位置，即 GA在局部搜索空間不具備微調(diào)能力； (3)、如何調(diào)節(jié) GA的參數(shù)才能得到最優(yōu)結(jié)果。一般的處理方法是將 GA和 BP 結(jié)合，按照不同的先后次序輪流迭代運算，這種處理方法主要是易于陷入局部極值點，不能保證收斂到全局最優(yōu)。 本章小結(jié) 本章主要簡單介紹 了遺傳算法的起源，發(fā)展和應用，然后介紹了基于遺傳算法的 BP 神經(jīng)網(wǎng)絡，以及用 GA優(yōu)化 BP神經(jīng)網(wǎng)絡的優(yōu)點。 4 重慶郵電大學本科畢業(yè)設計（論文） 第二章 遺傳算法 遺傳算法基本操作 一般的遺傳算法包括三個基本操作：選擇（ Selection）、交叉 (Crossover Operator)和變異(Mutation Operator)。 選擇 (Selection) 遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被復制到下一代群體中的概率大；反之，適應度低的個體被復制到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體遺傳到下一代群體 [14]。 通?？刹捎孟旅娴膸追N選擇算法。 輪盤賭選擇 各個個體被選擇的概率與適應度大小稱正比。具體操作如下： (1)、計算出群體中每個個體的適應度值 Fi， ， M為群體大?。? (2)、利用比例選擇算子的公式，計算出每個個體被遺傳到下一代群體中的概率； (3)、計算出每個個體的積累概率 pi； (4)、在 [0,1]區(qū)間內(nèi)產(chǎn)生一個均勻分布的 偽隨機數(shù) r； (5)、若 ，則選擇個體 1；否則，選擇個體 k，使得： 成立； (6)、重復 (4)、 (5)共 M次。 由于此方法是基于概率選擇，存在統(tǒng)計誤差。因此結(jié)合最優(yōu)保存策略，來保證當前適應度最好的個體能夠進化到下一代，不被遺傳操作的隨機性破壞掉，保證算法的收斂性。 排序選擇 此方法主要特點是對個體適應度是否取正值或負值以及個體適應度之間的數(shù)值差異程度無特殊要求，但輪盤賭選擇要求適應值一般為非負數(shù)。其基本思想：對群體中的所有個體按其適應度大小進行排序，根據(jù)排序來分配各個個體 被選擇的概率。其具體操作如下： (1)、對群體中的所有個體按其適應度大小進行排序； 5 重慶郵電大學本科畢業(yè)設計（論文） (2)、根據(jù)具體求解問題，設計一個概率分配表，將各個概率值按上述排列次序分配給各個個體。 (3)、基于各個個體的概率值作為遺傳到下一代概率的依據(jù)，按照賦予各個個體的概率再用輪盤賭選擇方法產(chǎn)生下一代群體。 最優(yōu)個體選擇 基本思想：父代群體中的最優(yōu)個體直接進入子代群體中，該方法可保證在遺傳過程中所得到的個體不會被交叉和變異操作所破壞，它是遺傳算法收斂性的一個重要 保證條件。它也容易使得局部最優(yōu)個體不易被淘汰，從而使算法的全局搜索能力變強。 隨機聯(lián)賽選擇 基本思想：每次選擇 N個個體之中適應度最高的個體遺傳到下一代群體中。具體操作如下： (1)、從群體中隨機選取 N 個個體進行適應度大小比較，將其中適應度最高的個體遺傳到下一代群體中去； (2)、將上述過程重復執(zhí)行 M(M為群體大小 )次，就可得到下一代群體。 交叉 (Crossover) 交叉是指對兩個相互交叉的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。它是產(chǎn)生新個體的主要方法，它決 定了 GA的全局搜索能力，在遺傳算法中起關鍵作用。 下面介紹幾種常用的適用于二進制編碼或?qū)崝?shù)編碼方式的交叉算子。 單點交叉 單點交叉是指在個體編碼串中隨機設置一個交叉點，然后在該點相互交換兩個配對個體的部分基因。 兩點交叉 它是指在相互配對的兩個個體編碼串中隨機設置兩個交叉點，并交換兩個交叉點之間的部分基因。 均勻交叉 它是指兩個相互配對個體的每一位基因都以相同的概率進行交換，從而形成兩個新個體。 算術(shù)交叉 它是指由兩個個體的線性組合而產(chǎn)生出新的個體。設在兩個個體 x1， x2 之 間 ?進行算術(shù)交叉，則交叉后的兩個新個體 x1?， x2 為： 6 重慶郵電大學本科畢業(yè)設計（論文） 變異 (Mutation) 變異是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。它是產(chǎn)生新個體的輔助方法。它決定了 GA的局部搜索能力。當交叉算子與變異算子相互配合時，共同完成對搜索空間的全局搜索和局部搜索，從而使得GA以良好的搜索性能完成最優(yōu)化問題 的尋優(yōu)過程。 GA使用變異算子主要有以下兩個目的 : (1)、改善 GA的局部搜索能力； (2)、維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。 下面介紹幾種變異算法。 基本位變異 對個體編碼串以變異概率 p隨機指定某一位或某幾位基因作變異操作。 均勻變異 (一致變異 ) 分別用符合某一范圍內(nèi)均勻分布的隨機數(shù)，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。均勻變異操作特別適合應用于 GA的初期運行階段，它使得搜索點可以在整個搜索空間內(nèi)自由地移動，從而增加群體的多樣性，使算法能夠處理更多的模式。 邊界變異 在進行邊界變異操作時，隨機地取基因座的兩個對應邊界基因值之一去替代原有基因值。當變量的取值范圍特別寬，并且無其他約束條件時，邊界變異會帶來不好的作用，但它特別適合用于最優(yōu)點位于或接近于可行解的邊界時的一類問題。 非均勻變異 均勻變異操作取某一范圍內(nèi)均勻分布的隨機數(shù)來替換原有基因值，可使得個體在搜索空間內(nèi)自由移動，但另一方面，它卻不便于對某一重點區(qū)域進行局部搜索。非均勻變異是對每個基因座都以相同的概率進行變異運算，相當于整個向量在解空間中作了一個輕微的變動。這樣避免了早熟，提高了遺傳 算法地優(yōu)化速度。 高斯變異 在進行變異時用一個均值 u,方差為 的正態(tài)分布的一個隨機數(shù)來替換原有基因值，操作過程和均勻變異類似。 7 重慶郵電大學本科畢業(yè)設計（論文） 遺傳算法基本思想 進化論認為每一物種在不斷的發(fā)展過程中都是越來越適應環(huán)境。物種的每個個體的基本特征被后代所繼承，但后代又不完全同于父代，這些新的變化若適應環(huán)境，則被保留下來。在某一環(huán)境中也是那些更能適應環(huán)境的個體特征能被保留下來，這就是適者生存的原理。 遺傳學說認為遺傳是作為一種指令碼 封裝在每個細胞中，并以基因的形式包含在染色體中，每個基因有特殊的位置并控制某個特殊的性質(zhì)，每個基因產(chǎn)生的個體對環(huán)境都有一定的適應性，基因雜交和基因突變可能產(chǎn)生對環(huán)境適應性更強的后代，通過優(yōu)勝劣汰的自然選擇，適應值高的基因結(jié)構(gòu)就被保存下來。遺傳算法將問題的求解表示成用編碼變異兩種基因操作產(chǎn)生出新一代的更適應環(huán)境的 “染色體 ”種群。隨著算法的運行，優(yōu)良的品質(zhì)被逐漸保留并加以組合，從而不斷產(chǎn)生出更佳的個體。這一過程就如生物進化那樣，好的特征被不斷地繼承下來，壞的特征被逐漸淘汰。新一代個體中包含著上一代個體的大量信息 ，新一代的個體不斷地在總體特性上勝過舊的一代，從而使整個群體向前進化發(fā)展。 下面是遺傳算法的流程： (1)、初始化群體； (2)、計算群體上每個個體的適應度值； (3)、按由個體適應度值所決定的某個規(guī)則選擇將進入下一代的個體； (4)、按交叉概率進行交叉操作； (5)、按變異概率進行變異操作； (6)、沒有滿足某種停止條件，則轉(zhuǎn)第 (2)步，否則進入 (7)； (7)、輸出種群中適應度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。 遺傳算法中的停止條件，一般依據(jù)問題的不同有不同的確定方式。例如，可以 采用以下的準則之一作為判斷條件： (1)、種群中個體的最大適應度超過預先設定值； (2)、種群中個體的平均適應度超過預先設定值； (3)、世代數(shù)超過預先設定值。 8 重慶郵電大學本科畢業(yè)設計（論文） 圖 遺傳算法的運算過程 遺傳算法的特點 常規(guī)的尋優(yōu)算法 常規(guī)的尋優(yōu)方法主要有四種類型：解析法、枚舉法、隨機法。 解析法 解析法尋優(yōu)是研究最多的一種，它一般又可分為間接法和直接法。 (1)、間接法是通過讓目標函數(shù)的梯 度為零，進而求解一組非線性方程來尋求局部極值。 (2)、直接法是使梯度信息按最陡的方向逐次運動來尋求局部極值，通常稱為爬山法。 上述兩種方法的主要缺點：它們只能尋找局部極值而非全局的極值；它們要求目標函數(shù)是連續(xù)光滑的，并且需要導數(shù)信息。這兩個缺點，使得解析尋優(yōu)方法的性能較差。 9 重慶郵電大學本科畢業(yè)設