范文廣

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

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

1 遺傳算法的特點

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

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

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

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

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

2 基本遺傳算法

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

3 遺傳算法的基本操作

3.1 編碼方案

對于具有復(fù)雜結(jié)構(gòu)的應(yīng)用性問題,為了能夠?qū)ζ溥M行描述,往往用簡單的位串編碼來表示。這種用位串形式編碼表示問題結(jié)構(gòu)的變換方式稱之為編碼或編碼方案[2],該編碼表示稱為染色體或稱為個體。編碼是建立遺傳算法的基礎(chǔ),它影響著算法的性能,是把復(fù)雜結(jié)構(gòu)問題轉(zhuǎn)化為遺傳算法所能處理的關(guān)鍵。編碼方法主要有:二進制編碼、格雷碼、符號編碼和浮點數(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 生成初始群體

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

3.3 適應(yīng)度函數(shù)

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

式中Xi—第 i個約束條件的權(quán)值;Yi=0表示無第i個約束條件的取值;f—適應(yīng)度。

3.4 遺傳操作

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

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

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

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

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

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

3.5 算法參數(shù)

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

4 結(jié)束語

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

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

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

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

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

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

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