【正文】 搜索算法。 在 遺傳算法 中， 雖 然也用到了隨機思想 ,但與 上述的隨機搜索 方式不同。 與其它尋優(yōu)算法相比 ,遺傳算法的主要特點歸納 為 下面幾點 : 1)對可行解表 示的廣泛性。許多傳統(tǒng)的搜索方式 都是單點搜索 ,而單點搜索一般 提供的信息 量 不多 ,搜索效率 也 不高 ,對于 那些 多峰分布的搜索空間 ，該方法往往會陷入局部的某個極值點 ， 使 得 搜索過程停滯不前 。 遺傳算法 用概率的變遷規(guī)則 指導它的搜索方向 , 而非 采用確定性規(guī)則 。 遺傳算法評估基因個體 僅需要適應(yīng)度函數(shù)的 函數(shù)值就可以了 ,并 且 遺傳操作 也是 在此基礎(chǔ)上 完成的。 5) 遺傳算法具備獨特的并行性和并行計算機制。在進行參數(shù)編碼時，應(yīng)根據(jù)具體問題選擇編碼的方式，因為編碼的好壞會直接影響到選擇、交叉、變異等遺傳操作。傳統(tǒng)的二進 制編碼是 0、 1字符構(gòu)成的固定長度串。由于遺傳 算法應(yīng)用的廣泛性 ，迄今 為止人 們已經(jīng)提出了許多 不同的編碼方法，總的來說，可以分為三大類：二進制編碼方法、 浮點數(shù)編碼方法以及 符號編碼方法。 二進 制編碼的優(yōu)點有四點：一是編 碼、 解碼操作簡單 易行；二是交 叉、 變異 等遺傳操作 便于實現(xiàn)；三是符合最 小字符集 編 碼原則；四是便于利 用模式定 理對算法進行理 論分析，因為模式定 理是以二進 制編碼為寄出的。 2）格雷 碼編碼 二進 制編碼不便于 反映所求問題 的結(jié)構(gòu)特征 ，對于一些 連續(xù)函數(shù) 的優(yōu)化問題 等，也由于遺傳 運算的隨機 特性而使得 其局部搜素 能力較差。 格雷 碼編碼的主要 優(yōu)點有四點 :一是 便于提高遺傳 算法的局 部搜索能力；二是 交叉、變異等遺傳操作 便于實現(xiàn)； 三是符合最小字 符集編碼原則；四是便于利 用模式定 理 對算法進 行理論分析。所謂浮點數(shù)編碼方法，是指個體的每個個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)。 c) 便于較大 空間的遺傳搜索。 g) 便于處理復(fù)雜 的決策變量約束條件。 c) 非冗余性（ Non redundancy） :染色體和 候選解一一對應(yīng)。 遺傳算法的任務(wù) 就 是 仿效 生物 進化的過程 對種 群 進行優(yōu)勝劣汰 , 最后選出符合 優(yōu)化要求的種 群和個體 。 （ 3）確定 適應(yīng)度函數(shù) 20 度量個體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)（ Fitness Function）， 遺傳算法中 定義一個 適應(yīng)性函 數(shù) 是評估個體優(yōu) 劣的手段，評估 的 標 準 隨 所研究 的問題 的不同而 不同，它往往是由 目標函數(shù)轉(zhuǎn)化 而來，要求和目 標函數(shù)有一樣 的極值點和可行解域，并且 值域 為非負，這樣就 能夠?qū)⒛繕撕? 數(shù)極小值問題，轉(zhuǎn) 變?yōu)榍筮m應(yīng) 度函數(shù)極大值問 題，易于 遺傳操作。 2）對于求最小值的問題，做下列轉(zhuǎn)換： m a x m a x( ) ( )( ( ) ) 0c f x f x cF it f t ???? ?? 其 他 （ 54） 式中， maxc 為一個適當?shù)南鄬Ρ容^大的數(shù)，是 ()fx的最大值估計，可以是一個合適的輸入值。這種方法 與第二種方法類似。遺傳算法使用選擇算子（又稱為復(fù)制算子， Reprodu ction Operator）來對群體中 的個體進行優(yōu)勝劣汰操 作；根據(jù)每個個體的適應(yīng)度值大小選擇，適 應(yīng)度較高的個體被遺傳到下一代群體中的概率較大；適應(yīng)度較高的個體被遺傳到下一代群體中的概率較小。選擇算子確定的好壞，直接影響到遺傳算法的計算結(jié)果。下面介紹幾種常用的選擇算子。每個個體就像圓盤中的一個扇形部分，扇面的角度和個體的適應(yīng)度值成正比，隨機撥動圓盤，當圓盤停止轉(zhuǎn)動時指針所在扇面對應(yīng)的個體被選中，輪盤賭式的選擇方法由此得名。在隨機競爭選擇中，每次按輪盤賭選擇機制選取一對個體，然后讓這兩個個體進行競爭，適應(yīng)度高的被選中，如此反復(fù)，直到選滿為止。而這卻不是我們所希望發(fā)生的，因為它會降低群體的平均適應(yīng)度，并且對遺傳算法的運行效 率、收斂性都有不利的影響，所以，我們希望適應(yīng)度最好的個體要盡量保留到下一代群體中。該策略使得實施可保證迄今為止所得到的的最優(yōu)個體不會被交叉、變異等遺傳運算所破壞，它是遺傳算法收斂性的一個重要保證條件。從而產(chǎn)生出新的的個體或物種。交叉運算產(chǎn)生子代，子代繼承了父代的基本特征。 遺傳算法中個，在交叉運算之前必須對群體中的個體進行配對。下面介紹幾種適合于二進制編碼個體或浮點數(shù)編碼個體的交叉算子。 39。圖 9 所示為兩點交叉運算示意圖。多點交叉是指在個體編碼中隨機設(shè)置多個交叉 點，然后進行基因交換。 算術(shù)交叉 (Arithmetic Crossover)是指由兩個個體的線性組合而產(chǎn)生出兩個新的個體。 遺傳算法的收斂性主要取決于其核心操作交叉算子的收斂性。變異（ Mutation）是以較小的概率對個體編碼串上的某個或某些位值進行改變。交叉運算是產(chǎn)生新個體的主要方法，它決定了遺傳算法的全局搜索能力；而變異運算只是產(chǎn)生新個體的輔助方法，但它也是必不可少的一個步驟，因為它決定了遺 25 傳算法的局部搜索能力。 均勻變異（ Uniform Mutation）操作是指分別用符合某一范圍內(nèi)均勻分布的隨機數(shù)，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。以改進這個性能，以擾動后的結(jié)果作為變異后的新基因值。所謂高斯變異操作，是指進行變異操作時用符合均值為 P ，方差為 2P 的正態(tài)分布的一個隨機數(shù)來替換原有的基因值。二是 種群具有多樣性 。 遺傳算法 的基本 運算 步驟如下 : 1) 初始化 。 3) 選擇操作。 5) 變異操作。如果達到預(yù)設(shè)的最大代數(shù)則輸出最優(yōu)個體，終止運算，否則返回步驟 2）繼續(xù)繁殖進化。 遺傳 算法可以從三個方面對 BP 網(wǎng)絡(luò)進行優(yōu)化 :一是優(yōu)化 神經(jīng) 網(wǎng)絡(luò)的拓撲結(jié)構(gòu) 。 目前 。下面對這三種優(yōu)化方式逐一進行介紹。 遺傳算法優(yōu)化 BP 神經(jīng)網(wǎng)絡(luò) BP 神經(jīng)網(wǎng)絡(luò)是目前使用最廣泛的一種神經(jīng)網(wǎng)絡(luò)，但其具有學習 收斂 速度慢、易陷入局部最小值等缺點，因此許多研究者們努力尋求解決 BP 神經(jīng)網(wǎng)絡(luò)的這些缺點的方法。經(jīng)過 選擇 、 交叉 、變異操作 后 便可得到一個適應(yīng)度更高的新 種群 。 4) 交叉操作。 2) 評價每個 個體 的適應(yīng)度。四是不同個 26 體間適應(yīng)環(huán)境 能力 不同 ,適應(yīng)能力強 的個體繁殖能力強 ,適應(yīng)能力弱的繁殖能力弱。高斯變異的具體操作過程與均勻變異類似。這種變異 操作方法就稱為非均勻變異（ Non Uniform Mutation）。均勻變異操作特別適合應(yīng)用于遺傳算法的初級運行階段，它使得搜索點可以在整個搜索空間內(nèi)自由地移動，從而可以增加群體的多樣性，使算法處理更多的模式。 下面介紹幾種變異操作方法，它們適合于二進制編碼的個體和浮點數(shù)編碼的個體。遺傳算法中所謂的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替代，從而形成一個新的個體。 3) 變異 在生物的遺傳和自 然進化過程中，其細胞分裂復(fù)制環(huán)節(jié)有可能因為某些偶然因素的影響而產(chǎn)生一些復(fù)制差錯，這樣會導致生物的某些基因發(fā)聲某種變異，從而產(chǎn)生出新的染色體，表現(xiàn)出新的生物性狀。 假設(shè)在兩個個體 taX 、 tbX 之間進行交叉算術(shù)交叉，則交叉運算后所產(chǎn)生的新個體為 11(1 )(1 )t t ta b at t tb a bX X XX X X????? ? ? ?? ? ? ?? （ 58） 其中， ? 可以是一個常數(shù)（此時所進行的交叉運算稱為均勻算術(shù)交叉）， ? 可以是一個由進化代數(shù)所決定的變量（此時所進行的交叉運算稱為非均勻算術(shù)交叉）。需要說明的是，一般情況下 24 不使用多點交叉算子，因為它有可能破壞好的模式。1 2 3 4 5 6 1 2 3 4 5 639。1 2 3 4 5 6 1 2 3 4 5 6A = [ ] [ ][ ] [ ]ABB? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ???? ? ?父 代 交 叉 子 代 圖 8 單點 交叉示意圖 兩點交叉 (Twopoint Crossover)是指在個體編碼串中隨機設(shè)置了兩個交叉點，然后再進行部分基因交換。單點交叉的具體操作過程為：首先對每一對相互配對的個體，隨機設(shè)置某一基因座之后的位置為交叉點，若染色體的長度為 N ，則共有 1N? 個可能的交叉點位置，然后對每一對相互配對的個體，依設(shè)定的交叉概率在其交叉點出相互交換兩個個體的部分染色體，從而產(chǎn)生新的個體。交叉操作是在這些配對個體組中的兩個個體之間進行的。遺傳算法中所謂的交叉運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。模仿這個環(huán)節(jié)，遺傳算法中使用交叉算子來產(chǎn)生新的個體。所以，該方法一般要與其他一些選擇操作方法配合起來使用，方可有良好的結(jié)果。 最優(yōu)保存策略進化模型的具體操作過程是：首先，找出當前群體中適應(yīng)度最高的個體和適應(yīng)度最低的個體；其次，若當前群體中最佳個體的適應(yīng)度比總的迄今為止的最好個體的適應(yīng)度還要高，則以當前群體中的最佳個體作為新的迄今為止的最好個體；最后，用迄今為止 的最好個體替換掉當前群體中的最差個體。雖然隨著群體的進化過程會產(chǎn)生越來越多的優(yōu)良個體。圖 7所示為輪盤賭選擇示意圖。所有選擇是從當前種群中根據(jù)個體的適應(yīng)度值，按某種準則挑選出好的個體進入下一代種群。遺傳算法中選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下一代群體中的一種遺傳運算 ，用來確定重組或交叉?zhèn)€體，以及被選個體將產(chǎn)生多少個子代個體。選擇操作建立在對個體的適應(yīng)度進行評價的基礎(chǔ)之上。這部分同時 也是 遺傳算法的主體 部分。 這種方法是第一種方法的改進， 可以 稱為“ 界限構(gòu)造法 ”，但 這種方法有時存 在界限值預(yù) 先估計困難、不可能精確的問題。總的來說，適應(yīng)函數(shù)為種群進化的擇優(yōu) 提供了依據(jù)。 種群 規(guī)模取得越大， 可供選擇 的面 就 越寬 , 就 越 容易得到更好的 結(jié)果 ， 但是 , 如果 種群 規(guī)模選 取過大 ,優(yōu)化 速度就 會減慢 。在有些場合， 允許生成致死基因 的編碼，必然會導致 冗余的搜索，但總的 計算量可能反而 減小，從而可以 更有效地找出最優(yōu)解。評估編碼策略常用的三個規(guī)范為： a) 完備性（ Completeness）：問題空間中的所有點（候選解）都能作 為遺傳算法空間中的點（染色體）表現(xiàn)。 e) 便于遺傳 算法與經(jīng)典優(yōu)化 方法的混合使用。 浮點數(shù)編碼方法的優(yōu)點有 一下幾點： a) 適合于在遺傳 算法中表示范 圍較大的數(shù)。人們在一些經(jīng)典算法的研究中所總結(jié)出的一些寶貴經(jīng)驗也就無法在這里加以利用，也不便于處理非平凡約束條件。 格雷碼是這樣 一種編碼方法， 其連續(xù)的兩個整數(shù) 所對應(yīng)的編碼之間 僅僅只有一個碼位 是不同的，其余 碼位都完全 相同。個體編碼串的長度較短時，可能達不到精度的要求，而個體編碼串的長度較大時，雖然能提高編碼精度，但卻會 使遺傳 算法的搜 索空間 急劇擴大。 1）二進制編碼方法 二進制編碼方法是遺傳算法中最主要的一種編碼方法，它使用的編碼符號集是由二進制符號 0和 1所組成的二值符號集 {0,1}，它所構(gòu)成的個體基因型是一個二進制編碼符號串 。 為解決這個問題而提出的格雷碼（ Gray Code），在相鄰整數(shù)之間漢明距離都為 1，然而漢明距離在整數(shù)之間的差并 非單調(diào)增加，引入另一層 次 的隱懸崖。反之，從遺傳算法的解空間 向問題的解空間的轉(zhuǎn)換被稱為解碼（又稱譯碼， Decoding）。 遺傳算法的實現(xiàn) 基本遺傳操作 遺傳算法的基本遺傳操作主要由參數(shù)的編碼、種群初始化、適應(yīng) 度函數(shù)設(shè)計、遺傳算子操作構(gòu)成，下面將一一詳細地進行介紹。遺傳算法 對適應(yīng)度函數(shù)的唯一 的要求 是編碼必須與可行解 的 空間對應(yīng) ,而 不能出現(xiàn)死碼 。 4) 遺傳算法直接把目標函數(shù)值用作 搜索信息 。 3) 遺傳算法使 用啟發(fā)式 概率 搜索技術(shù) 。遺傳算法的這種 對參數(shù)進 17 行 編碼的操作方法 ,可以借鑒 生物的遺傳進化過程 ,也可以 應(yīng)用遺傳操作算子 ,這使得遺傳算法可以應(yīng)用到廣泛的 領(lǐng)域 中去。所以 ,隨機 搜索并不一定 就意味著是無序 搜索 。所以，隨機法的最終結(jié)果往往 不是最優(yōu)值 。即使 著名的動態(tài)規(guī)劃方法 (其本質(zhì)上 屬于枚舉法 )也常 遇到指數(shù)爆炸的問題 。二是它們 要求目標函數(shù) 必須 是連續(xù)光滑的 ,并 需要導數(shù)的信息 。 （ 1） 解析法 解析法是三種算法中研究的最多的一種方法 ,它又 可 以 分為直接法和間接法 。 隨著 選擇、交叉、變異的循環(huán)進行 ,適應(yīng)性強的染色體會被一代一代選出 并加以組合 ,進而 不斷 地 產(chǎn)生出更好的個體 。 物種 中 的每 一個個體的基本特征為 后代所繼承 ,但 是 后代又不會 完全與父代相同 ,與父代的有差異特征如果能有利于后代 適應(yīng)環(huán)境 ,就被留存下來。 遺傳算法 的引入 為 人工神經(jīng)網(wǎng)絡(luò)的設(shè)計與 訓練提供了 一條 新的途徑 。 （ 6） BP 網(wǎng)絡(luò)故障診斷系統(tǒng)的輔助設(shè)計 為使本設(shè)計的故障診斷系統(tǒng)的更為完善，本