郭來(lái)軍

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

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

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

1遺傳算法的概念及原理

1.1遺傳算法概念

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

1.2遺傳算法的基本算子

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

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

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

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

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

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

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

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

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

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

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

3結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

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

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