基于改進(jìn)遺傳算法的應(yīng)用研究

郭來軍

摘要：在計算機技術(shù)的研究中，關(guān)于遺傳算法的應(yīng)用研究是熱門的課題。目前，隨著社會經(jīng)濟的不斷發(fā)展，遺傳算法被應(yīng)用到人們生活的很多領(lǐng)域。文章對遺傳算法基本概念及工作原理進(jìn)行了分析，對遺傳算法在實際應(yīng)用中存在的收斂速度和局部最優(yōu)之間的矛盾問題，提出了遺傳算法的改進(jìn)方法。

關(guān)鍵詞：遺傳算法；計算機技術(shù)；選擇算子；編譯算子

遺傳算法是一種全局優(yōu)化隨機搜索算法，遺傳算法是對自然界中生物遺傳進(jìn)化的過程進(jìn)行模仿的一種原理。傳統(tǒng)的遺傳算法在工業(yè)設(shè)計和交通運輸?shù)确矫娑嫉玫搅藦V泛的應(yīng)用，但是遺傳算法存在局部最小和過早收斂的矛盾問題為了讓遺傳算法更好地被應(yīng)用，本文對遺傳算法中的3種基本遺傳算子進(jìn)行了研究。在遺傳算法的遺傳算子的研究中對遺傳算子參數(shù)的選擇決定了遺傳算法的全局性能，遺傳算子參數(shù)選擇的合理性是遺傳算法全局優(yōu)解的關(guān)鍵。

1遺傳算法的概念及原理

1.1遺傳算法概念

遺傳算法中的遺傳因子也叫作基因，其承載著很多遺傳信息，基因是用來控制生物特征的最基本的遺傳單元，生物體通過基因把遺傳信息傳遞給下一代，在遺傳算法中利用的就是基因的這個特點。在遺傳算法中的基因是一個二進(jìn)制數(shù)或者字符等，通過計算機對基因的整個操作過程進(jìn)行模擬，在遺傳算法中基因是最基本的構(gòu)成單元。染色體是基因的載體，也是遺傳信息的重要載體，染色體是生物中最有價值的部分。在遺傳算法中染色體也是重要的部分，遺傳算法對染色體進(jìn)行編碼，編碼采用二進(jìn)制碼的方式，二進(jìn)制碼使用簡單，二進(jìn)制碼和生物體的染色體非常相似，在遺傳算法中進(jìn)行遺傳的操作非常方便。種群是生物個體組成的群體，在遺傳算法中種群是所有染色體的總和，在遺傳算法中染色體是個體，在遺傳過程中的某一代中的染色體的總和構(gòu)成種群。在遺傳算法中種群為遺傳進(jìn)化的搜索提供空間。在遺傳算法中，先對種群中的染色體進(jìn)行編碼，這樣就可以得到每一個染色體對應(yīng)的編碼，每個個體就是實際中的一個解，每個解都和函數(shù)值相對應(yīng)，其中適度函數(shù)影響著遺傳算法中的收斂速度等性能[2]。

1.2遺傳算法的基本算子

選擇算子是遺傳算法中的基本算子之一，通過選擇算子遺傳算法可以模擬大自然物種的自然選擇方式，選擇算子是通過適度函數(shù)來對種群的個體進(jìn)行選擇，根據(jù)個體的適應(yīng)度值的高低把種群中優(yōu)良的個體選擇到下一代種群中，個體的適應(yīng)度越高被選擇的可能性就越大。選擇算子保證了種群向適應(yīng)度高的方向發(fā)展，其決定遺傳算法的收斂性，還可以保證遺傳算法中種群的多樣性。選擇算子的有效設(shè)計可以保證遺傳算法具有更局的收斂速度。

交叉算子在遺傳算法中起到?jīng)Q定性的作用，在遺傳算法中通過交叉算子可以得出比父代更加優(yōu)秀的個體，這樣可以更快地得出最優(yōu)解。交叉算子中交叉概率對遺傳算法的影響很大，交叉概率大不利于對最優(yōu)解的計算，交叉概率小對算法的搜索能力就降低了，得到最優(yōu)解的概率也變小了，所以對交叉算子概率的選擇要仔細(xì)考慮。

變異算子是遺傳發(fā)生變化的主要根源之一，在遺傳算法中變異算子是解決局部收斂的最有效辦法。遺傳算法中交叉算子決定全局搜索能力，變異算子作為主要的輔助，完成對空間的局部搜索，交叉算子和變異算子的有效結(jié)合可以提高遺傳算法的最優(yōu)解的求解性能[3]。

2基于改進(jìn)遺傳算法的應(yīng)用研究

對遺傳算法的改進(jìn)研究是基于3個基本的遺傳算子，分別是選擇算子、交叉算子和變異算子[4-5]。

2.1選擇算子的改進(jìn)

傳統(tǒng)的遺傳算法中比較常用的選擇方法是輪盤賭選擇，這種選擇方式比較直觀而且簡單，輪盤賭選擇是把種群中所有的個體都進(jìn)行累加，這樣就形成了種群的總適應(yīng)度，之后對種群中的個體進(jìn)行相對適應(yīng)度的計算，通過計算可以在選擇之前就得出一個隨機數(shù)，然后就可以根據(jù)個體的相對適應(yīng)度作為選擇依據(jù)來對個體進(jìn)行選擇。在選擇方式中，適應(yīng)度的個體越大，個體被選擇的機會就更大。輪盤賭選擇方式使用比較普遍，但是在選擇的時候還是存在一些問題。針對問題提出了對選擇算子的改進(jìn)，要對種群中所有的個體進(jìn)行排序，按照個體適應(yīng)度的高低進(jìn)行排列。對排列完的個體分成4個等份，把適應(yīng)度低的排在后面，按一定的比例進(jìn)行淘汰，不進(jìn)入到下一代；把適應(yīng)度中等的排在中間按2/4的比例把個體拷貝出來，作為下一代；適應(yīng)度高的排最前面拷貝成兩份，都選擇到下一代中。這樣經(jīng)過選擇后，下一代的種群數(shù)量相等。這樣的選擇算子的改進(jìn)辦法可以把適應(yīng)度低的個體直接淘汰，提高了遺傳算法的收斂速度。種群中適應(yīng)度高的個體數(shù)量增加，遺傳算法更加高效，這樣可以有效地解決前面提到的選擇的問題。

2.2交叉算子的改進(jìn)

交叉算子作為遺傳算法中重要的操作性算子，交叉算子對遺傳算法的收斂性起著重要的作用，而且可以提高遺傳算法的收斂速度。所以需要設(shè)計一個有效的交叉算子來提高遺傳算法的性能。交叉算子的改進(jìn)方法，更好地保護親代個體的優(yōu)良基因，提高遺傳算法的性能，在交叉算子中引入相似度的概念，利用兩個父體之間相識度值的大小來決定是否進(jìn)行交叉操作。假設(shè)兩個編碼是二進(jìn)制的父體，分別是X，Y，相識度是S，交叉臨界值為R，如果父體的相識度值大于交叉臨界值，那么兩個父體不可以進(jìn)行交換，這樣它們的優(yōu)良基因模式就不會被破壞了，如果父體的相識度值小于交叉臨界值，那么兩個父體可以進(jìn)行交換。本文對兩個父代個體的共同子串長度程序代碼設(shè)計如下：

2.3變異算子的改進(jìn)

在最基本的遺傳算法中，變異的概率值作為一個常數(shù)是不變的。如果變異概率在遺傳進(jìn)化中不發(fā)生變化，那么種群適應(yīng)度和最優(yōu)的個體適應(yīng)度相似，遺傳進(jìn)化就沒有競爭性了，進(jìn)化速度就會降低，種群多樣性也會減少，局部收斂情況很容易發(fā)生，嚴(yán)重影響算法的運行效率。變異概率值應(yīng)該根據(jù)遺傳算法進(jìn)行適當(dāng)調(diào)整，這樣遺傳算法就可以具有躲避局部收斂的能力，使算法的效率得到提高。我們采取的改進(jìn)措施是盡量減少對種群優(yōu)秀模式破壞的可能性，并生成有效的和優(yōu)秀的模式。變異個體的適應(yīng)度的值比種群評價適應(yīng)度的值大，那么個體變異的概率就小，這是符合生物進(jìn)化規(guī)律的，個體的適應(yīng)度越大，發(fā)生變異的情況就小，這樣可以避免優(yōu)良個體被破壞。如果變異個體適應(yīng)度值比種群平均適應(yīng)度的值小，那么個體不是優(yōu)良的，不適合生存。所以個體的變異率越大，個體的優(yōu)良品種越多，這樣可以提高算法的局部搜索能力，更可以加快全局收斂，從而改進(jìn)遺傳算法的性能。

3結(jié)語

傳統(tǒng)的遺傳算法交叉率是固定的，收斂速度慢。本文通過對遺傳算法中選擇算子、交叉算子和變異算子的改進(jìn)，提高了遺傳算法跳出局部的收斂能力和遺傳算法的收斂速度，并且緩解了收斂速度和局部最優(yōu)解之間的矛盾?；诟倪M(jìn)遺傳算法的應(yīng)用研究在遺傳算法中具有一定的應(yīng)用價值。

[參考文獻(xiàn)]

[1]單錦輝，高友峰，劉明浩，等一種新的變異測試數(shù)據(jù)自動生成方法[J].計算機學(xué)報，2008（6）：1025-1034.

[2]劉鐵男，劉斌，梁福責(zé)一種帶局部搜索策略的遺傳算法及其應(yīng)用[J].大慶石油學(xué)院學(xué)報，2005（2）：76-78.

[3]楊曉華，陸桂華，楊志峰，等格雷碼加速遺傳算法及其理論研究[J].系統(tǒng)工程理論與實踐，2003（3）：100-106.

[4]潘俊輝，王輝.一種基于改進(jìn)的遺傳算法的關(guān)聯(lián)規(guī)則挖掘及應(yīng)用[J].齊齊哈爾大學(xué)學(xué)報（自然科學(xué)版），2011（2）：11-14.

[5]劉偉，朱珍民，蔣發(fā)群，等普適計算中一種最優(yōu)服務(wù)選擇算法的設(shè)計與仿真[J].計算機應(yīng)用研究，2010（3）：899-903.endprint