遺傳算法研究和探討

范文廣

（安徽國防科技職業(yè)學院,安徽六安 237011）

遺傳算法（Genetic Algorithm又稱GA）是借鑒生物遺傳學和自然選擇機理的一類優(yōu)化搜索算法。它不同于傳統(tǒng)的數(shù)學模型,主要適用于非線性等復雜問題的解決,同時通過進化計算和遺傳算法操作,使種群達到優(yōu)化狀態(tài)。

1 遺傳算法的特點

遺傳算法[1]是通過選擇、遺傳、變異等操作及適者生存的理論,利用簡單的編碼技術和繁殖機制來描述較復雜的現(xiàn)象,以達到解決非常困難問題的目的,能從多極值、離散的、含噪音的多維問題中搜索到最優(yōu)解,非常適用于規(guī)模較大的并行計算。目前廣泛應用在機器學習、并行處理等領域。但它并不能確保問題的答案是最佳的,只是將誤差控制在一定的范圍內(nèi)。

遺傳算法不是針對參數(shù)本身進行進化,而是對參數(shù)形成數(shù)據(jù)集合的編碼,將問題結構變換為有限字符串形成編碼,然后模仿生物遺傳對其進化處理,減少約束條件的限制,優(yōu)化了計算。

遺傳算法具有并行性,它組織搜索是從問題解的種群開始并可以同時向不同的方向,不是從單個解開始。因而可以對多個區(qū)域進行搜索,避免了陷入局部最優(yōu)解而無法跳出的局面。

遺傳算法的搜索由問題的適應度函數(shù)來指導,不需要外部的輔助信息,不象其它方法需要類似導數(shù)值等輔助信息,從而有效地提高了搜索效率。

遺傳算法采用了選擇、交叉和變異等操作而不是用確定性規(guī)則進行隨機操作,使搜索過程更具有靈活性和魯棒性。

2 基本遺傳算法

遺傳算法類似于生物進化,是通過搜索基因上的染色體來求解,它和需要解的問題本身沒有任何關聯(lián),只是評價算法所產(chǎn)生的每個染色體,并通過適應值來對染色體進行篩選,選擇適應性好的染色體,以便繼續(xù)繁殖。在遺傳算法中,染色體的形成是通過所求解問題的編碼隨機獲取,得到初始種群。對每個個體用適應度函數(shù)進行評價,對適應值低的個體淘汰,適應值高的個體參加遺傳操作,從而形成下一代新種群,再對新種群進行進化,這樣反復操作,最后可得到最優(yōu)解。

3 遺傳算法的基本操作

3.1 編碼方案

對于具有復雜結構的應用性問題,為了能夠對其進行描述,往往用簡單的位串編碼來表示。這種用位串形式編碼表示問題結構的變換方式稱之為編碼或編碼方案[2],該編碼表示稱為染色體或稱為個體。編碼是建立遺傳算法的基礎,它影響著算法的性能,是把復雜結構問題轉化為遺傳算法所能處理的關鍵。編碼方法主要有:二進制編碼、格雷碼、符號編碼和浮點數(shù)編碼。

二進制編碼是用一個二進制數(shù)表示一個染色體,二進制數(shù)中的每一位稱為染色體的遺傳因子,其位數(shù)由所要求的精度確定。二進制編碼的優(yōu)點是編碼操作簡單,后面的遺傳操作容易實現(xiàn),而且便于進行理論分析等。缺點是長度較大,對于一些個體編碼位串比較短時,無法達到所要求的精度,如果長度較大時,精度雖然提高了但遍歷空間急劇擴大,大大降低了算法的性能。

格雷碼是連續(xù)的兩個整數(shù)編碼值只有一個碼位不相同,其余一樣。如十進制數(shù)5和6的格雷碼分別為0111和0101,其二進制編碼分別為0101和0110。

符號編碼是指編碼串中的表示是取自只有代碼含義的符號集而無數(shù)值含義。符號集的組成可以是一個字母表,如{a,b,c,d,e,...},也可以是一個代碼表,如{Y1,Y2,Y3,Y4,...}等。

3.2 生成初始群體

群體的初始設置并不復雜,它是通過隨機產(chǎn)生若干個染色體的初始群體[3],每個染色體的組成應符合上述所選定的編碼方案。這個我們可以稱為遺傳的第一代,以此為起點執(zhí)行進化操作,直至優(yōu)化準則終止條件,得到最優(yōu)解。

3.3 適應度函數(shù)

在遺傳和進化的研究領域,為了能夠確定某個物種適應環(huán)境的能力,我們可以使用適應度來對其進行衡量和判斷,具有存活和繁殖機會的當然是適應度較高的物種,適應度低的將被淘汰。因此在遺傳算法中也同樣用適應度來確定解的優(yōu)劣,為此要根據(jù)所求問題構造適應度函數(shù),它可以對問題中的每一個染色體進行度量,從而確定染色體的優(yōu)良程度。它在算法中的作用是很重要的,將問題的標準評價以適應值來直觀描述,對于最終獲得最優(yōu)解起到了決定性作用。一般情況下,適應度函數(shù)確定的依據(jù)為對約束條件違反情況加權求和,若用Yi表示約束條件i的值,若違反了其值為1,否則為0。其對應的權值為Xi,把所有違反約束的權值加起來,求其倒數(shù),值越大說明違反約束條件的就越少,適應能力就越強,繁殖的機會就越大。適應函數(shù)可表示為

式中Xi—第 i個約束條件的權值;Yi=0表示無第i個約束條件的取值;f—適應度。

3.4 遺傳操作

遺傳操作[4]的方式主要三種:復制操作、交叉操作和變異操作。

復制操作其實是一種選擇,就是根據(jù)每個個體的適應度值來選擇,哪些個體是優(yōu)良的能夠有機會繁殖后代,哪些個體將被淘汰。這也符合生物進化的優(yōu)勝劣汰、適者生存的原則,從而得到較為優(yōu)質的后代。選擇的原則一般可以根據(jù)適應度函數(shù)求得每個個體的適應度值,其值較大的個體能夠存活,值較小的個體將被淘汰。賭輪選擇是簡單遺傳算法常采用的機制,具體的說,首先求出群體中所有個體適應度的總和,計算方法如下:

式中fi—第i個個體的適應度值;Pi—第i個個體的選擇概率。

交叉操作是利用兩個個體作為父母個體,對其兩個個體中的部分代碼進行交換,以便產(chǎn)生新的個體,這是優(yōu)良個體獲取的重要手段。現(xiàn)以單點交叉說明交叉的方法,設個體的編碼為一個十位的二進制數(shù),隨機取其兩個個體A和B,交叉點為第4位遺傳因子,交叉操作后的A和B個體分別為A'和B',表示為變異操作就是改變個體上某個位置的數(shù)碼,

對于編碼為二進制的個體,就是把相應位的0變?yōu)?,1變?yōu)?,如把上面的個體 A,從第五位開如進行變異操作,得到 A″。

變異操作主是防止有用解的丟失,確保對空間中重要點的遍歷,使算法的全局收斂性增強。

3.5 算法參數(shù)

遺傳算法在實際應用研究中,為了能更好地獲得最優(yōu)解,需要提前設定遺傳算法的控制參數(shù)[5-6],包括主要參數(shù)和次要參數(shù)的設定。主要參數(shù)有算法的群體大小和執(zhí)行算法的代數(shù),次要參數(shù)是遺傳操作的三種算法所對應的概率,分別是:復制概率、交叉概率和變異概率。

4 結束語

在遺傳算法中其基本操作的要素是至關重要的,對于問題的描述要設置一定的編碼形式給出,形成染色體,以便后面的遺傳操作。對于問題的適應力處理要確定相應的適應函數(shù),為個體的選擇和優(yōu)化提供依據(jù)。

[1]蔡自興.人工智能及其應用[M].北京:清華大學出版社,2004.

[2]顏富強.遺傳算法在數(shù)據(jù)挖掘中的應用研究[D].長沙:湖南大學,2008.

[3]吳曉虹.遺傳算法在數(shù)據(jù)挖掘中的應用[D].桂林:桂林工學院,2008.

[4]李文科.基于遺傳算法的數(shù)據(jù)挖掘技術的研究[D].南京:中南大學,2009.

[5]盛文峰.數(shù)據(jù)挖掘的遺傳算法的研究與應用[D].上海:上海交通大學,2007.

[6]趙建峰.數(shù)據(jù)挖掘中一種基于遺傳算法改進的ID3算法[D].武漢:武漢科技大學,2008.