李振輝　李凱　姜美雷　孔祥源

摘要：遺傳算法是模擬生物進(jìn)化機(jī)制而發(fā)展起來(lái)的一種并行全局搜索方法。近年來(lái)，遺傳算法作為一種非經(jīng)典的數(shù)學(xué)方法應(yīng)用到越來(lái)越廣泛的領(lǐng)域中，成為了人工智能理論中一個(gè)很活躍的分支學(xué)科。從有限采樣樣本中提取正弦信號(hào)參數(shù)（包括頻率、幅度、相位等）是信號(hào)處理中一類重要的估計(jì)問(wèn)題。綜合介紹了遺傳算法的定義、操作流程和參數(shù)選擇等；重點(diǎn)闡述了在Matlab環(huán)境下，遺傳算法在正弦波信號(hào)參數(shù)提取問(wèn)題中的實(shí)現(xiàn)；對(duì)算法進(jìn)行了測(cè)試。

關(guān)鍵詞：遺傳算法； 正弦波； 參數(shù)提取； Matlab

中圖分類號(hào)：TN911?34 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1004?373X（2013）02?0119?04

0 引 言

正弦信號(hào)是在實(shí)驗(yàn)和實(shí)際的工程問(wèn)題中遇到得非常多的信號(hào)，因而從實(shí)際波形或者有限采樣數(shù)據(jù)中重新提取出正弦波的特征：即周期，初始相位和幅值是一項(xiàng)比較重要的工作。例如，轉(zhuǎn)子的轉(zhuǎn)速信號(hào)可以通過(guò)正弦波信號(hào)的頻率表現(xiàn)出來(lái)，轉(zhuǎn)子旋轉(zhuǎn)時(shí)的振動(dòng)幅值的大小可以通過(guò)正弦波信號(hào)的幅值表現(xiàn)出來(lái)。利用傳統(tǒng)的最小二乘法提取正弦信號(hào)參數(shù)（通常將非線性最小二乘轉(zhuǎn)化為線性問(wèn)題來(lái)處理）存在下列問(wèn)題：

（1）實(shí)踐中能線性化的問(wèn)題只是一小部分；

（2）隨著需要估計(jì)參數(shù)的增加，線性化方法的計(jì)算量成幾何級(jí)數(shù)增長(zhǎng)；

（3）精度低。也可以采用非線性優(yōu)化算法如擬牛頓法、Levenberg?Marquart法等來(lái)估計(jì)正弦信號(hào)參數(shù)，但該類算法具有收斂到局部極小點(diǎn)的缺點(diǎn)。而遺傳算法能很好克服上述缺點(diǎn)（雖然遺傳算法自身也有運(yùn)算效率不高的缺點(diǎn)）。

遺傳算法是完全不同于傳統(tǒng)的優(yōu)化方法，它是模擬生物進(jìn)化機(jī)制而發(fā)展起來(lái)的一種并行全局搜索方法，具有全局優(yōu)化能力。該算法通過(guò)選擇、重組和變異等步驟循環(huán)操作，在全局范圍內(nèi)搜索最優(yōu)個(gè)體，即優(yōu)化找到最佳參數(shù)估計(jì)。

1 遺傳算法綜述

遺傳算法（GA）是借鑒生物界自然選擇和群體進(jìn)化機(jī)制而形成的一種全局尋優(yōu)算法，其本質(zhì)上是一種基于概率的隨機(jī)搜索算法[1]。一般認(rèn)為遺傳算法由五個(gè)基本部分組成（由Michalewicz歸納）[2]：

（1）問(wèn)題的解得遺傳表示；

（2）創(chuàng)建解的初始種群的方法；

（3）根據(jù)個(gè)體適應(yīng)值對(duì)其進(jìn)行優(yōu)劣判定的評(píng)價(jià)函數(shù)；

（4）用來(lái)改變復(fù)制過(guò)程中產(chǎn)生的子個(gè)體遺傳組成的遺傳算子；

（5）遺傳算法的參數(shù)值。

在遺傳算法中，首先將需要解決問(wèn)題中的決策變量通過(guò)一定的編碼表示成遺傳空間的一個(gè)個(gè)體，它是一個(gè)基因型串結(jié)構(gòu)數(shù)據(jù)，然后將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度值，用來(lái)評(píng)價(jià)每個(gè)個(gè)體的優(yōu)劣，并將其作為遺傳操作的依據(jù)。初始產(chǎn)生的一系列個(gè)體構(gòu)成初始的種群。

遺傳操作包括三個(gè)算子：選擇、雜交和變異。選擇是從當(dāng)前群體中選擇適應(yīng)值高的個(gè)體以生成交配池的過(guò)程，交配池是當(dāng)前代與下一代之間的中間群體。選擇算子的作用是用來(lái)提高群體的平均適應(yīng)度值。雜交算子先從交配池中的個(gè)體隨機(jī)配對(duì)，然后將兩兩配對(duì)的個(gè)體按一定方式相互交換部分基因，其作用是將原有的優(yōu)良基因遺傳給下一代個(gè)體，并生成包含更復(fù)雜基因的新個(gè)體。變異算子是通過(guò)模擬自然界的基因突變現(xiàn)象對(duì)個(gè)體的某一個(gè)或幾位按某一較小的概率進(jìn)行反轉(zhuǎn)其二進(jìn)制字符而形成新的個(gè)體。新產(chǎn)生的個(gè)體（稱為后代）也通過(guò)適應(yīng)度值被評(píng)價(jià)優(yōu)劣。新產(chǎn)生的個(gè)體中比較優(yōu)秀的個(gè)體構(gòu)成下一代的種群（即子代種群）。在若干代以后算法收斂到一個(gè)最優(yōu)個(gè)體，該個(gè)體很有可能就是問(wèn)題的最優(yōu)或者次優(yōu)解。

將問(wèn)題的解進(jìn)行遺傳表示，也即染色體的編碼有多種方法，包括：二進(jìn)制編碼，實(shí)數(shù)編碼，證書(shū)或字母排列編碼，一般數(shù)據(jù)編碼等。各種方法各有利弊，但都必須滿足以下原則：不冗余、合法性、完備性、Lamarckian性質(zhì)和因果性。

選擇算子的選擇也有多種：輪盤(pán)賭選擇、[μ+λ]選擇、競(jìng)爭(zhēng)選擇、穩(wěn)態(tài)復(fù)制、排序與比例變換、共享等方法都有各自的優(yōu)點(diǎn)和適應(yīng)的問(wèn)題。

同理，雜交算子和變異算子也有多種。經(jīng)常使用的雜交算子有：算術(shù)雜交、混合雜交、單峰正態(tài)分布雜交、邊界算子和基于方向的雜交。使用的較多的變異算子是：非均勻變異、有向變異何高斯變異。

在使用遺傳算法時(shí)，除需要選定各個(gè)算子外，還必須確定一些運(yùn)行參數(shù)，比如：編碼串長(zhǎng)度、選擇壓力、雜交和變異概率、種群規(guī)模等等。編碼串長(zhǎng)度由問(wèn)題的所要求的精度來(lái)決定，長(zhǎng)的編碼能得到較精確的解，但可能導(dǎo)致過(guò)長(zhǎng)的求解時(shí)間。選擇壓力用來(lái)限制搜索空間的大小，較小的選擇壓力可以在更大的空間上進(jìn)行廣度搜索，但可能保留較多的不可行解（實(shí)際上，保持適量的不可行解是必要的，因?yàn)檫@其中的某一些個(gè)體可能提供關(guān)于最優(yōu)解的有用信息，即某些優(yōu)良基因）。雜交概率控制著雜交操作的頻率，雜交操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法，所以雜交概率通常應(yīng)取較大值，但如果雜交概率太大的話又可能反過(guò)來(lái)會(huì)破壞群體的優(yōu)良模式，反而增加迭代代數(shù)。變異概率也是影響新個(gè)體產(chǎn)生的一個(gè)因素，如果變異概率太小，則產(chǎn)生新個(gè)體較少；如果變異概率太大，則又會(huì)使遺傳算法變成隨機(jī)搜索，通常取變異概率取較小，以保證種群發(fā)展的穩(wěn)定性。至于種群規(guī)模的選擇，種群規(guī)模太大時(shí)，計(jì)算量會(huì)很大，使遺傳算法的運(yùn)行效率降低，運(yùn)行時(shí)間增加，但種群規(guī)模太小時(shí)，卻降低了種群的多樣性，有可能找不出最優(yōu)解。

從理論上講，不存在一組適用于所有問(wèn)題的最佳參數(shù)值和最佳算子，隨著具體問(wèn)題的不同，有效參數(shù)和高效遺傳算子選擇的差異往往是十分顯著的。在此處所用到Matlab下的遺傳算法工具箱具有強(qiáng)大的功能，可以讓用戶自己選擇具體使用何種遺傳算子，也允許用戶在規(guī)定范圍內(nèi)自己選擇各組參數(shù)值，甚至還包括結(jié)束搜索的方式和結(jié)果的輸出方式等都可以自由選擇。

5 結(jié) 語(yǔ)

從實(shí)驗(yàn)結(jié)果來(lái)看，遺傳算法在正弦波信號(hào)參數(shù)提取中的應(yīng)用比較很成功，能夠比較好的得到優(yōu)化參數(shù)，尤其是在算法參數(shù)的選擇比較恰當(dāng)和待尋優(yōu)參數(shù)的范圍能限定到比較小的范圍，同時(shí)，噪聲干擾較小時(shí)能更好的工作。

當(dāng)然，即使存在一定的白噪聲對(duì)結(jié)果的影響也是非常小的。另外，遺傳算法過(guò)于耗時(shí)的毛病在本問(wèn)題中也幾乎沒(méi)有體現(xiàn)出來(lái)，算法運(yùn)行用時(shí)很短。當(dāng)然“耗時(shí)長(zhǎng)短”這一點(diǎn)還與給定的采樣數(shù)據(jù)量，也就是計(jì)算量由一定的關(guān)系。

總之，在Matlab環(huán)境下基于遺傳算法的正弦波信號(hào)參數(shù)提取能很好的實(shí)現(xiàn)。實(shí)際應(yīng)用上也有較好的前景，在實(shí)驗(yàn)室或者工程項(xiàng)目中都可以由本算法和一些前期的采樣裝置較好較快的得到結(jié)果。

參考文獻(xiàn)

[1] 玄光男，程潤(rùn)偉.遺傳算法與工程優(yōu)化[M].北京：清華大學(xué)出版社，2004.

[2] 梁科.Matlab環(huán)境下的遺傳算法程序設(shè)計(jì)及優(yōu)化問(wèn)題求解[J]. 開(kāi)發(fā)研究與設(shè)計(jì)技術(shù)，2006（4）：1049?1051.

[3] 席裕庚，柴天佑，惲為民.遺傳算法綜述[J]. 控制理論與應(yīng)用，1996（6）：69?70.

[4] 李少遠(yuǎn)，蔡文劍.工業(yè)過(guò)程辨識(shí)與控制[M].北京：化學(xué)工業(yè)出版社，2005.

[5] 殷銘，張興華，戴先中.基于Matlab的遺傳算法實(shí)現(xiàn)[J]. 電子技術(shù)應(yīng)用，2000（1）：8?10.

[6] 曹志松.基于混合遺傳算法的航空發(fā)動(dòng)機(jī)PID控制參數(shù)尋優(yōu)[J].航空動(dòng)力學(xué)報(bào)，2003（9）：1588?1592.

[7] 陳秋靈，徐江峰.用遺傳算法搜索一維光子晶體帶隙[J].中國(guó)計(jì)量學(xué)院學(xué)報(bào)，2007（1）：97?101.

[8] 周雄偉，熊慶國(guó)，況海龍，等.基于遺傳算法的組合邏輯電路設(shè)計(jì)的FPGA實(shí)現(xiàn)[J].電子設(shè)計(jì)工程，2012（1）：148?150.