遺傳算法及計算機仿真應用研究

李云強

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

關鍵詞：遺傳；仿真；算法；計算；模式識別

1 遺傳算法原理

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

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

2 遺傳算法的特點

2.1 優(yōu)勢

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

2.2 不足

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

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

3 遺傳算法改進

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

4 極值應用與仿真

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

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

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

[參考文獻]

[1]肖燕彩.《MATLAB 語言及實踐教程》.清華大學出版社，2004年5月.

[2]李敏強，寇紀淞.《遺傳算法的基本理論與應用》.科學出版社， 2003.3.