【正文】 間，自適應地調(diào)整搜索方向，不需要確定的規(guī)則。 隨后經(jīng)過 20 余年的發(fā)展，取得了豐碩的應用成果和理論研究的進展，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳算法的應用研究顯得格外活躍，不但它的應用領(lǐng)域擴大，而且利用遺傳算法進行優(yōu)化和規(guī)則學習的能力也顯著提高，同時產(chǎn)業(yè)應用方面的研 究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應用研究已從初期的組合優(yōu)化求解擴展到了許多更新、更工程化的應用方面。 近幾年來，遺傳算法主要在復雜優(yōu)化問題求解和工業(yè)工程領(lǐng)域應用方面，取得了一些令人信服的結(jié)果，所以引起了很多人的關(guān)注。在發(fā)展過程中，進化策略、進化規(guī)劃和遺傳算法之間差異越來越小。遺傳算法成功的應用包括：作業(yè)調(diào)度與排序、可靠性設(shè)計、車輛路徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與分配、交通問題、 組合 優(yōu)化、機器學習、信號處理、 自適應控制 和人工生命等 領(lǐng)域 。它是現(xiàn)代有關(guān) 智能計算 中的 關(guān)鍵技術(shù) 。 隨著遺傳算法的不斷發(fā)展， 關(guān)于遺傳算法的國際學術(shù)活動越來越多， 遺傳算法已成為一個多學科、多領(lǐng)域的重要研究方向。 武漢理工大學《數(shù)字信號處理》 4 遺傳算法的概述 遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由 一定數(shù)量的 經(jīng)過 了 基因編碼的個體組成。每個個體實際上是染色體帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn) 為 某種基因組合（即基因型），它決定了個體形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射 ， 即編碼工作。由于仿照基因編碼的工作很 復雜，我們往往 將其 簡化，如二進制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度大小選擇個體，并借助于自然遺傳學的遺傳算子進行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼，可以作為問題近似最優(yōu)解。 遺傳算法的特點 遺傳算法是解決搜索問題的一種通用算法，對于各種通用問題都可以使用。搜索算法的共同特征為： （ 1） 首先組成一組候選解； （ 2） 依據(jù)某些適應性條件測算這些候選解的適應度； （ 3） 根據(jù)適應度保留某些候選解，放棄其他候選解； （ 4） 對保留的候選解進行某些操作，生成新的候選解。 在遺傳算法中，上述幾個特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開來。 遺傳算法還具有以下幾方面的特點： (1)遺傳 算法從問題解的串集開始嫂索，而不是從單個解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的； 武漢理工大學《數(shù)字信號處理》 5 容易誤入局部最優(yōu) 解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。 (2)許多傳統(tǒng)搜索算法都是單點搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時處理群體中的多個個體，即對搜索空間中的多個解進行評估，減少了陷入局部最優(yōu)解的風險，同時算法本身易于實現(xiàn)并行化。 (3)遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應度函數(shù)值來評估個體，在此基礎(chǔ)上進行遺傳操作。適應度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點使得遺傳算法的應用范圍大大擴展。 (4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來 指導他的搜索方向。 (5)具有自組織、自適應和自學習性。遺傳算法利用進化過程獲得的信息自行組織搜索時，硬度大的個體具有較高的生存概率，并獲得更適應環(huán)境的基因結(jié)構(gòu)。 遺傳算法基本流程操作 圖 141 解決實際問題時遺傳算法流程圖 武漢理工大學《數(shù)字信號處理》 6 圖 142 遺傳過程 （ 1） 編碼： 確定用何種碼制 , 然后將問題參數(shù)編碼形成基因碼鏈，每一個碼鏈代表一個個體 , 表示優(yōu)化問題的一個解。 （ 2）初始化： 隨機產(chǎn)生一個規(guī)模為 P 的初始種群 , 其中每個個體為一定長度的碼鏈 , 該群體代表優(yōu)化問題的一些可能解的集合。 （ 3）估計適應度： 計算種群中每個個體的適應度 , 適應度為群體進化時的選擇提供了依據(jù)。一般來說適應度越高 , 解的素質(zhì)越好。適應度函數(shù)可以根據(jù)目標函數(shù)而定。 （ 4）再生 (選擇 )： 根據(jù)每個個體的相對適應度 , 計算每個個體的再生次數(shù) , 并進行再生操作 , 產(chǎn)生新的個體加人下一代群體中 , 一般再生的概率與其適應度成正比。 （ 5）交叉： 從種群中隨機選擇兩個染色體 , 按一定的概率進行基因交換，交換位置的選取是隨機的。 武漢理工大學《數(shù)字信號處理》 7 （ 6） 變異 ： 從種群中隨機地選擇一個染色體 , 按一定的變異概率 P進行基因變異 ,GA的搜索能力主要是由選擇與交 叉賦于的 , 變異算子則保證了算法能搜索到問題空間的每一點 , 從而使算法具有全局最優(yōu)性 , 它進一步增強了 GA的能力 。 （ 7）重復： 若發(fā)現(xiàn)最優(yōu)解 , 則算法停止 , 否則轉(zhuǎn) 3 ,對產(chǎn)生的新一代群體進行重新評價、選擇、交叉、變異操作 , 如此循環(huán)往復 , 使群體中最優(yōu)個體的適應度和平均適應度不斷提高。 武漢理工大學《數(shù)字信號處理》 8 2 數(shù)字濾波器 數(shù)字濾波器的簡介 數(shù)字濾波器一詞出現(xiàn)在 60 年代中期。由于電子計算機技術(shù)和大規(guī)模集成電路的發(fā)展，數(shù)字濾波器已可用計算機軟件實現(xiàn)，也可用大規(guī)模集成數(shù)字硬件實時實現(xiàn)。濾波器是指用來對輸入信號進行濾波的硬件 和軟件。所謂數(shù)字濾波器是一個離散時間系統(tǒng)，按預定的算法，將輸入離散時間信號轉(zhuǎn)換為所要求的輸出離散時間信號的特定功能的裝置。也可以說成是通過一定運算關(guān)系改變輸入信號所含頻率成分的相對比例或者濾除某些頻率成分的器件。 數(shù)字濾波器和模擬濾波器相比，因為信號的形式和實現(xiàn)濾波的方法不同，數(shù)字濾波器具有比模擬濾波器精度高、穩(wěn)定、不要求阻抗匹配等特點。應用數(shù)字濾波器處理模擬信號時，首先須對輸入模擬信號進行限帶、抽樣和模數(shù)轉(zhuǎn)換。數(shù)字濾波器輸入信號的抽樣率應大于被處理信號帶寬的兩倍，其頻率響應具有以抽樣頻率為間隔的周期重復特 性，且以折疊頻率即 1／ 2 抽樣頻率點呈鏡像對稱。為得到模擬信號，數(shù)字濾波器處理的輸出數(shù)字信號須經(jīng)數(shù)模轉(zhuǎn)換、平滑。 一般用兩種方法來實現(xiàn)數(shù)字濾波器：一是采用通用計算機，把濾波器所要完成的運算編程通過計算機來執(zhí)行，也就是采用計算機軟件來實現(xiàn)；二是設(shè)計專用的數(shù)字處理硬件 。 FIR 和 IIR 數(shù)字濾波器的概述 FIR 數(shù)字濾波器 FIR(Finite Impulse Response)濾波器：有限長單位沖激響應濾波器，是數(shù)字信號處理系統(tǒng)中最基本的元件，它可以在保證任意幅頻特性的同時具有嚴格的線性相頻特性 ，同時其單位抽樣響應是有限長的，因而濾波器是穩(wěn)定的系統(tǒng)。因此，F(xiàn)IR 濾波器在通信、圖像處理、模式識別等領(lǐng)域都有著廣泛的應用。 武漢理工大學《數(shù)字信號處理》 9 有限長單位沖激響應（ FIR）濾波器有以下特點： （ 1）系統(tǒng)的單位沖激響應 h (n)在有限個 n 值處不為零； （ 2）系統(tǒng)函數(shù) H(z)在 |z|0 處收斂，極點全部在 z = 0 處（因果系統(tǒng)）； （ 3）結(jié)構(gòu)上主要是非遞歸結(jié)構(gòu)，沒有輸出到輸入的反饋，但有些結(jié)構(gòu)中（例如頻率抽樣結(jié)構(gòu)）也包含有反饋的遞歸部分。 IIR 數(shù)字濾波器 IIR(Infinite Impulse Response)數(shù)字濾波器，又名“無限脈沖響應數(shù)字濾波器”，或“遞歸濾波器”。遞歸濾波器，也就是 IIR 數(shù)字濾波器，顧名思義，具有反饋，一般認為具有無限的脈沖響應。 IIR 濾波器有以下幾個特點： （ 1）封閉函數(shù)： IIR 數(shù)字濾波器的系統(tǒng)函數(shù)可以寫成封閉函數(shù)的形式。 （ 2） IIR 數(shù)字濾波器采用遞歸型結(jié)構(gòu)： IIR 數(shù)字濾波器采用遞歸型結(jié)構(gòu)，即結(jié)構(gòu)上帶有反饋環(huán)路。 IIR 濾波器運算結(jié)構(gòu)通常由延時、乘以系數(shù)和相加等基本運算組成，可以組合成直接型、正準型、級聯(lián)型、并聯(lián)型四種結(jié)構(gòu)形式，都具有反饋回路。由于運算中的舍入處理，使誤差不 斷累積，有時會產(chǎn)生微弱的寄生振蕩。 （ 3）借助成熟的模擬濾波器的成果： IIR 數(shù)字濾波器在設(shè)計上可以借助成熟的模擬濾波器的成果，如巴特沃斯、契比雪夫和橢圓濾波器等，有現(xiàn)成的設(shè)計數(shù)據(jù)或圖表可查，其設(shè)計工作量比較小，對計算工具的要求不高。在設(shè)計一個 IIR數(shù)字濾波器時，我們根據(jù)指標先寫出模擬濾波器的公式，然后通過一定的變換，將模擬濾波器的公式轉(zhuǎn)換成數(shù)字濾波器的公式。 （ 4）需加相位校準網(wǎng)絡： IIR 數(shù)字濾波器的相位特性不好控制，對相位要求較高時，需加相位校準網(wǎng)絡。 武漢理工大學《數(shù)字信號處理》 10 FIR 數(shù)字濾波器與 IIR 數(shù)字濾波器的 區(qū)別 （ 1）單位響應 IIR 數(shù)字濾波器單位響應為無限脈沖序列，而 FIR 數(shù)字濾波器單位響應為有限的； FIR 濾波器，也就是“非遞歸濾波器”，沒有引入反饋。這種濾波器的脈沖響應是有限的。 （ 2）幅頻特性 IIR 數(shù)字濾波器幅頻特性精度很高，不是線性相位的，可以應用于對相位信息不敏感的音頻信號上； FIR 數(shù)字濾波器的幅頻特性精度較之于 IIR 數(shù)字濾波器低，但是線性相位，就是不同頻率分量的信號經(jīng)過 FIR 濾波器后他們的時間差不變，這是很好的性質(zhì)。 （ 3）實時信號處理 FIR 數(shù)字濾波器是有限的單位響應也有利于對數(shù)字 信號的處理，便于編程，用于計算的時延也小，這對實時的信號處理很重要。 武漢理工大學《數(shù)字信號處理》 11 3 數(shù)字濾波器的設(shè)計方法 數(shù)字濾波器的設(shè)計要求 我們通常用的數(shù)字濾波器一般屬于選頻濾波器，數(shù)字濾波器的頻響特性函數(shù)H(ejw)一般為復函數(shù)，所以通常表示為 H(ejw)=|H