基于改進遺傳算法的應用研究

郭來軍

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

關鍵詞：遺傳算法；計算機技術；選擇算子；編譯算子

遺傳算法是一種全局優化隨機搜索算法，遺傳算法是對自然界中生物遺傳進化的過程進行模仿的一種原理。傳統的遺傳算法在工業設計和交通運輸等方面都得到了廣泛的應用，但是遺傳算法存在局部最小和過早收斂的矛盾問題為了讓遺傳算法更好地被應用，本文對遺傳算法中的3種基本遺傳算子進行了研究。在遺傳算法的遺傳算子的研究中對遺傳算子參數的選擇決定了遺傳算法的全局性能，遺傳算子參數選擇的合理性是遺傳算法全局優解的關鍵。

1遺傳算法的概念及原理

1.1遺傳算法概念

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

1.2遺傳算法的基本算子

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

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

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

2基于改進遺傳算法的應用研究

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

2.1選擇算子的改進

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

2.2交叉算子的改進

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

2.3變異算子的改進

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

3結語

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

[參考文獻]

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

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

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

[4]潘俊輝，王輝.一種基于改進的遺傳算法的關聯規則挖掘及應用[J].齊齊哈爾大學學報（自然科學版），2011（2）：11-14.

[5]劉偉，朱珍民，蔣發群，等普適計算中一種最優服務選擇算法的設計與仿真[J].計算機應用研究，2010（3）：899-903.endprint