李云強(qiáng)

摘 要：本文對(duì)遺傳算法進(jìn)行了研究，給出了遺傳算法的基本原理，以及其優(yōu)勢(shì)和劣勢(shì)，對(duì)此的改進(jìn)方法。然后應(yīng)該算法進(jìn)行了極值研究與仿真。

關(guān)鍵詞：遺傳；仿真；算法；計(jì)算；模式識(shí)別

1 遺傳算法原理

交叉：根據(jù)上面給出的Pr（hi），從P中按概率選擇r·p/2對(duì)假設(shè)。對(duì)于每一對(duì)假設(shè)應(yīng)用交叉算子產(chǎn)生兩個(gè)后代。把所有的后代加入PS。變異：使用均勻的概率從PS中選擇m百分比的成員。對(duì)于選出的每個(gè)成員，在它的表示中隨機(jī)選擇一個(gè)位取反。更新：P←PS。評(píng)估：對(duì)于P中的每一個(gè)h計(jì)算Fitness（h）

（4）從P中返回適應(yīng)度最高的假設(shè)。算法每次迭代里，基于當(dāng)前群體產(chǎn)生新一代假設(shè)。從當(dāng)前的群體中選擇一定數(shù)量的假設(shè)包含在下一代中。

2 遺傳算法的特點(diǎn)

2.1 優(yōu)勢(shì)

⑴對(duì)可行解表示的廣泛。遺傳算法的處理對(duì)象不是參數(shù)本身，而是針對(duì)那些通過(guò)參數(shù)集進(jìn)行編碼得到的基因個(gè)體。這一特點(diǎn)使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。⑵許多傳統(tǒng)的搜索方法都是單點(diǎn)搜索，遺傳算法采用的是同時(shí)處理群體中多個(gè)個(gè)體的方法，使遺傳算法具有較好的全局搜索效率，也使得遺傳算法本身易于并行化。⑶不需要輔助信息。僅用適應(yīng)度函數(shù)的數(shù)值來(lái)評(píng)估基因個(gè)體。⑷內(nèi)在啟發(fā)式隨機(jī)搜索特性。

2.2 不足

⑴編碼不規(guī)范及編碼存在表示的不準(zhǔn)確性。⑵單一的遺產(chǎn)算法編碼不能全面地將優(yōu)化問(wèn)題的約束表示出來(lái)，計(jì)算時(shí)間增加。⑶遺傳算法通常的效率比其他傳統(tǒng)方法低。⑷遺傳算法容易出現(xiàn)過(guò)早收斂。⑸遺傳算法對(duì)算法精度、可行度、計(jì)算復(fù)雜度，還沒(méi)有有效定量分析方法。

所以綜上，對(duì)于遺傳算法，應(yīng)該充分認(rèn)識(shí)到其優(yōu)缺點(diǎn)，確定應(yīng)用場(chǎng)合和環(huán)境，結(jié)合硬件條件、時(shí)間特性、計(jì)算規(guī)模，充分發(fā)揮其優(yōu)勢(shì)，盡可能壓縮其缺點(diǎn)。

3 遺傳算法改進(jìn)

為提高遺傳算法的運(yùn)算速度、改善其性能，在并行機(jī)或局域網(wǎng)環(huán)境下開(kāi)發(fā)出了一些并行遺傳算法，大體可分為標(biāo)準(zhǔn)并行方法（standard parallel approach）和分解型并行方法（decomposition parallel approach）。前者利用共享存貯器結(jié)構(gòu)的并行機(jī)，可對(duì)群體的進(jìn)化過(guò)程進(jìn)行并行計(jì)算以達(dá)到提高遺傳算法運(yùn)行速度的目的。后者從全局的角度開(kāi)發(fā)群體進(jìn)化的并行性，改變了簡(jiǎn)單遺傳算法的基本特點(diǎn)，各子群體獨(dú)立地進(jìn)行進(jìn)化。

4 極值應(yīng)用與仿真

遺傳算法可以較好的達(dá)到局部最優(yōu)，用來(lái)求解局部的極大或者極小值。所以這里極值問(wèn)題為f（x）=x+9*sin（4x）+8*cos（3x）的最大值，其中4<=x<=15，二進(jìn)制編碼，選取種群個(gè)體數(shù)目為30，二進(jìn)制編碼長(zhǎng)度為15，交叉概率為0.7，變異概率是0.15。在仿真里采用遺傳算法求解函數(shù)最大值問(wèn)題，應(yīng)用常規(guī)的二進(jìn)度編碼，利用賭輪算法選擇最優(yōu)化群體，進(jìn)行交叉變異等遺傳操作，最終求出所求函數(shù)最大值即最憂解。遺傳算子選擇運(yùn)算，使用賭輪選擇算法，求解最佳適應(yīng)度種群：分別求出30個(gè)初始種群中每個(gè)種群個(gè)體的適應(yīng)度函數(shù)，并計(jì)算所有種群的和S。在區(qū)間（0，S）上隨機(jī)的產(chǎn)生一個(gè)數(shù)r從某個(gè)基因開(kāi)始，逐一取出基因來(lái)，把它的適應(yīng)度加到s上去（s開(kāi)始為0），如果s大于r，則停止循環(huán)并返回當(dāng)前基因。

群體M小時(shí)可以提高遺傳算法的運(yùn)行速度，但是降低了群體的多樣性有可能引起算法的早熟現(xiàn)象，當(dāng)M大時(shí)使得運(yùn)行效率降低。交叉操作是產(chǎn)生新個(gè)體的主要方法一般應(yīng)取值較大，但太大會(huì)破壞群體的優(yōu)良模型，對(duì)進(jìn)化產(chǎn)生不利影響。取值太小產(chǎn)生新個(gè)體速度又較慢。變異概率較大時(shí)雖能產(chǎn)生比較多的新個(gè)體，但有可能破壞掉較好的模型使得遺傳算法的性能近似于隨機(jī)搜索算法性能，Pm太小變異操作產(chǎn)生新個(gè)體和抑制早熟的能力較差，最佳范圍

遺傳代數(shù)增加，變異概率增加，全局最憂解收斂性最優(yōu)，計(jì)算出來(lái)最優(yōu)解17.34。

[參考文獻(xiàn)]

[1]肖燕彩.《MATLAB 語(yǔ)言及實(shí)踐教程》.清華大學(xué)出版社，2004年5月.

[2]李敏強(qiáng)，寇紀(jì)淞.《遺傳算法的基本理論與應(yīng)用》.科學(xué)出版社， 2003.3.