李振輝 李凱 姜美雷 孔祥源
摘要:遺傳算法是模擬生物進化機制而發(fā)展起來的一種并行全局搜索方法。近年來,遺傳算法作為一種非經(jīng)典的數(shù)學(xué)方法應(yīng)用到越來越廣泛的領(lǐng)域中,成為了人工智能理論中一個很活躍的分支學(xué)科。從有限采樣樣本中提取正弦信號參數(shù)(包括頻率、幅度、相位等)是信號處理中一類重要的估計問題。綜合介紹了遺傳算法的定義、操作流程和參數(shù)選擇等;重點闡述了在Matlab環(huán)境下,遺傳算法在正弦波信號參數(shù)提取問題中的實現(xiàn);對算法進行了測試。
關(guān)鍵詞:遺傳算法; 正弦波; 參數(shù)提??; Matlab
中圖分類號:TN911?34 文獻標識碼:A 文章編號:1004?373X(2013)02?0119?04
0 引 言
正弦信號是在實驗和實際的工程問題中遇到得非常多的信號,因而從實際波形或者有限采樣數(shù)據(jù)中重新提取出正弦波的特征:即周期,初始相位和幅值是一項比較重要的工作。例如,轉(zhuǎn)子的轉(zhuǎn)速信號可以通過正弦波信號的頻率表現(xiàn)出來,轉(zhuǎn)子旋轉(zhuǎn)時的振動幅值的大小可以通過正弦波信號的幅值表現(xiàn)出來。利用傳統(tǒng)的最小二乘法提取正弦信號參數(shù)(通常將非線性最小二乘轉(zhuǎn)化為線性問題來處理)存在下列問題:
(1)實踐中能線性化的問題只是一小部分;
(2)隨著需要估計參數(shù)的增加,線性化方法的計算量成幾何級數(shù)增長;
(3)精度低。也可以采用非線性優(yōu)化算法如擬牛頓法、Levenberg?Marquart法等來估計正弦信號參數(shù),但該類算法具有收斂到局部極小點的缺點。而遺傳算法能很好克服上述缺點(雖然遺傳算法自身也有運算效率不高的缺點)。
遺傳算法是完全不同于傳統(tǒng)的優(yōu)化方法,它是模擬生物進化機制而發(fā)展起來的一種并行全局搜索方法,具有全局優(yōu)化能力。該算法通過選擇、重組和變異等步驟循環(huán)操作,在全局范圍內(nèi)搜索最優(yōu)個體,即優(yōu)化找到最佳參數(shù)估計。
1 遺傳算法綜述
遺傳算法(GA)是借鑒生物界自然選擇和群體進化機制而形成的一種全局尋優(yōu)算法,其本質(zhì)上是一種基于概率的隨機搜索算法[1]。一般認為遺傳算法由五個基本部分組成(由Michalewicz歸納)[2]:
(1)問題的解得遺傳表示;
(2)創(chuàng)建解的初始種群的方法;
(3)根據(jù)個體適應(yīng)值對其進行優(yōu)劣判定的評價函數(shù);
(4)用來改變復(fù)制過程中產(chǎn)生的子個體遺傳組成的遺傳算子;
(5)遺傳算法的參數(shù)值。
在遺傳算法中,首先將需要解決問題中的決策變量通過一定的編碼表示成遺傳空間的一個個體,它是一個基因型串結(jié)構(gòu)數(shù)據(jù),然后將目標函數(shù)轉(zhuǎn)換成適應(yīng)度值,用來評價每個個體的優(yōu)劣,并將其作為遺傳操作的依據(jù)。初始產(chǎn)生的一系列個體構(gòu)成初始的種群。
遺傳操作包括三個算子:選擇、雜交和變異。選擇是從當(dāng)前群體中選擇適應(yīng)值高的個體以生成交配池的過程,交配池是當(dāng)前代與下一代之間的中間群體。選擇算子的作用是用來提高群體的平均適應(yīng)度值。雜交算子先從交配池中的個體隨機配對,然后將兩兩配對的個體按一定方式相互交換部分基因,其作用是將原有的優(yōu)良基因遺傳給下一代個體,并生成包含更復(fù)雜基因的新個體。變異算子是通過模擬自然界的基因突變現(xiàn)象對個體的某一個或幾位按某一較小的概率進行反轉(zhuǎn)其二進制字符而形成新的個體。新產(chǎn)生的個體(稱為后代)也通過適應(yīng)度值被評價優(yōu)劣。新產(chǎn)生的個體中比較優(yōu)秀的個體構(gòu)成下一代的種群(即子代種群)。在若干代以后算法收斂到一個最優(yōu)個體,該個體很有可能就是問題的最優(yōu)或者次優(yōu)解。
將問題的解進行遺傳表示,也即染色體的編碼有多種方法,包括:二進制編碼,實數(shù)編碼,證書或字母排列編碼,一般數(shù)據(jù)編碼等。各種方法各有利弊,但都必須滿足以下原則:不冗余、合法性、完備性、Lamarckian性質(zhì)和因果性。
選擇算子的選擇也有多種:輪盤賭選擇、[μ+λ]選擇、競爭選擇、穩(wěn)態(tài)復(fù)制、排序與比例變換、共享等方法都有各自的優(yōu)點和適應(yīng)的問題。
同理,雜交算子和變異算子也有多種。經(jīng)常使用的雜交算子有:算術(shù)雜交、混合雜交、單峰正態(tài)分布雜交、邊界算子和基于方向的雜交。使用的較多的變異算子是:非均勻變異、有向變異何高斯變異。
在使用遺傳算法時,除需要選定各個算子外,還必須確定一些運行參數(shù),比如:編碼串長度、選擇壓力、雜交和變異概率、種群規(guī)模等等。編碼串長度由問題的所要求的精度來決定,長的編碼能得到較精確的解,但可能導(dǎo)致過長的求解時間。選擇壓力用來限制搜索空間的大小,較小的選擇壓力可以在更大的空間上進行廣度搜索,但可能保留較多的不可行解(實際上,保持適量的不可行解是必要的,因為這其中的某一些個體可能提供關(guān)于最優(yōu)解的有用信息,即某些優(yōu)良基因)。雜交概率控制著雜交操作的頻率,雜交操作是遺傳算法中產(chǎn)生新個體的主要方法,所以雜交概率通常應(yīng)取較大值,但如果雜交概率太大的話又可能反過來會破壞群體的優(yōu)良模式,反而增加迭代代數(shù)。變異概率也是影響新個體產(chǎn)生的一個因素,如果變異概率太小,則產(chǎn)生新個體較少;如果變異概率太大,則又會使遺傳算法變成隨機搜索,通常取變異概率取較小,以保證種群發(fā)展的穩(wěn)定性。至于種群規(guī)模的選擇,種群規(guī)模太大時,計算量會很大,使遺傳算法的運行效率降低,運行時間增加,但種群規(guī)模太小時,卻降低了種群的多樣性,有可能找不出最優(yōu)解。
從理論上講,不存在一組適用于所有問題的最佳參數(shù)值和最佳算子,隨著具體問題的不同,有效參數(shù)和高效遺傳算子選擇的差異往往是十分顯著的。在此處所用到Matlab下的遺傳算法工具箱具有強大的功能,可以讓用戶自己選擇具體使用何種遺傳算子,也允許用戶在規(guī)定范圍內(nèi)自己選擇各組參數(shù)值,甚至還包括結(jié)束搜索的方式和結(jié)果的輸出方式等都可以自由選擇。
5 結(jié) 語
從實驗結(jié)果來看,遺傳算法在正弦波信號參數(shù)提取中的應(yīng)用比較很成功,能夠比較好的得到優(yōu)化參數(shù),尤其是在算法參數(shù)的選擇比較恰當(dāng)和待尋優(yōu)參數(shù)的范圍能限定到比較小的范圍,同時,噪聲干擾較小時能更好的工作。
當(dāng)然,即使存在一定的白噪聲對結(jié)果的影響也是非常小的。另外,遺傳算法過于耗時的毛病在本問題中也幾乎沒有體現(xiàn)出來,算法運行用時很短。當(dāng)然“耗時長短”這一點還與給定的采樣數(shù)據(jù)量,也就是計算量由一定的關(guān)系。
總之,在Matlab環(huán)境下基于遺傳算法的正弦波信號參數(shù)提取能很好的實現(xiàn)。實際應(yīng)用上也有較好的前景,在實驗室或者工程項目中都可以由本算法和一些前期的采樣裝置較好較快的得到結(jié)果。
參考文獻
[1] 玄光男,程潤偉.遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社,2004.
[2] 梁科.Matlab環(huán)境下的遺傳算法程序設(shè)計及優(yōu)化問題求解[J]. 開發(fā)研究與設(shè)計技術(shù),2006(4):1049?1051.
[3] 席裕庚,柴天佑,惲為民.遺傳算法綜述[J]. 控制理論與應(yīng)用,1996(6):69?70.
[4] 李少遠,蔡文劍.工業(yè)過程辨識與控制[M].北京:化學(xué)工業(yè)出版社,2005.
[5] 殷銘,張興華,戴先中.基于Matlab的遺傳算法實現(xiàn)[J]. 電子技術(shù)應(yīng)用,2000(1):8?10.
[6] 曹志松.基于混合遺傳算法的航空發(fā)動機PID控制參數(shù)尋優(yōu)[J].航空動力學(xué)報,2003(9):1588?1592.
[7] 陳秋靈,徐江峰.用遺傳算法搜索一維光子晶體帶隙[J].中國計量學(xué)院學(xué)報,2007(1):97?101.
[8] 周雄偉,熊慶國,況海龍,等.基于遺傳算法的組合邏輯電路設(shè)計的FPGA實現(xiàn)[J].電子設(shè)計工程,2012(1):148?150.